What is fastest way to convert bool to byte?

What is fastest way to convert bool to byte?

I want this mapping: False=0, True=1

Note: I don't want to use any if statements or other co开发者_StackOverflow中文版nditional statements. I don't want the CPU to halt or guess next statement.

Update: For those who want to see the point of this question. This example shows how two if statement are reduced from the code.

byte A = k > 9 ; //If it was possible (k>9) == 0 || 1
c[i * 2] = A * (k + 0x37) - (A - 1) * (k + 0x30);

---

Using unsafe code this method is pretty fast. With optimizations enabled its about 30% faster than the conditional operator.

bool input = true;
byte value = *((byte*)(&input)); // 1

---

How about:

byte x = value ? (byte) 1 : (byte) 0;

If you're talking about the most efficient way of doing it, there may be some tricks you could do with unsafe code... but is this really a bottleneck for you?

EDIT: I just realized that the conditional operator needs those casts for the operands in order to make the overall expression a byte.

EDIT: Having seen your question, there's a much better way of optimizing it IMO. Currently you'll be performing operations you don't need to either way. Try this instead:

c[i << 1] = k > 9 ? k + 0x37 : k + 0x30;

or

c[i << 1] = k + (k > 9 ? 0x37 : 0x30);

(I suspect it doesn't matter which.)

You only need to perform the comparison and then one addition - instead of two additions and two multiplications after the conversion from bool to byte.

EDIT: Having just tried this, due to potentially branch misses, this can still definitely be slower than the unsafe version... or it can be faster. Picking a random value for k in the range [0, 18), this approach takes twice as long as the unsafe code. Picking a random value for k in the range [0, 1000) (i.e. one branch is picked much more often than the other), this approach is faster than the unconditional one. So what's the pattern for your k value?

Here's some benchmark code:

using System;
using System.Diagnostics;

class Test
{
    static void Main()
    {
        Random rng = new Random();
        int[] ks = new int[100000000];
        for (int i = 0; i < ks.Length; i++)
        {
            ks[i] = rng.Next(1000);
        }

        for (int i = 0; i < 3; i++)
        {
            Console.WriteLine("Iteration {0}", i);
            long sum = 0;
            Stopwatch sw = Stopwatch.StartNew();
            for (int j = 0; j < ks.Length; j++)
            {
                int k = ks[j];
                unsafe
                {
                    bool input = k > 9;
                    byte A = *((byte*)(&input)); // 1
                    sum += A * (k + 0x37) - (A - 1) * (k + 0x30);
                }
            }
            sw.Stop();
            Console.WriteLine("Unsafe code: {0}; {1}ms",
                              sum, sw.ElapsedMilliseconds);

            sum = 0;
            sw = Stopwatch.StartNew();
            for (int j = 0; j < ks.Length; j++)
            {
                int k = ks[j];
                sum += k > 9 ? k + 0x37 : k + 0x30;
            }
            sw.Stop();
            Console.WriteLine("Conditional: {0}; {1}ms",
                              sum, sw.ElapsedMilliseconds);
        }
    }
}

Note that on my computer this does give the same values for sum, but I'm not at all sure whether it's guaranteed to. I don't know that there's any guarantee of what the in-memory representation of true is... so on some CLRs you could potentially get the wrong answer.

However, I would point out that on my laptop, this loop of 100 million operations only takes around 300ms (and that's including adding to the sum and the initial array access, which may well be taking significant time, particularly due to cache misses)... are you really sure this is the bottleneck? How are you hoping to obtain data to hash so fast that this becomes the problem?

EDIT: I've just added another loop to see a "base case":

for (int j = 0; j < ks.Length; j++)
{
    int k = ks[j];
    sum += k + 0x30;
}

That takes about half the time... so only half the time is actually spent in the hash-specific code. Are you really, really sure this is a crucial bit of code to optimize at the cost of readability and potentially correctness?

---

How about

byte x = Convert.ToByte(true);

---

// Warning! Brain-compiled code ahead!
static readonly char[] HexChars = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };
public static string ToHex(this byte[] me)
{
    if ( me == null ) return null;
    int ml = me.Length;
    char[] c = new char[2*ml];

    int cp = 0;
    for (int i = 0; i < ml; i++ )
    {
        c[cp++] = HexChars[me[i]&15];
        c[cp++] = HexChars[me[i]>>4];
    }
    return new string(c);
}

---

The following is a simple benchmark to compare the three options:

    Int32 j = 0;
    bool b = true;

    for (int n = 0; n < 5; n++) {
        Stopwatch sw1 = new Stopwatch();
        Stopwatch sw2 = new Stopwatch();
        Stopwatch sw3 = new Stopwatch();
        sw1.Start();
        for (int i = 100 * 1000 * 1000; i > 0; i--)
            unsafe { j = *(int*)(&b); }
        sw1.Stop();

        sw2.Start();
        for (int i = 100 * 1000 * 1000; i > 0; i--)
            j = b ? 1 : 0;
        sw2.Stop();

        sw3.Start();
        for (int i = 100 * 1000 * 1000; i > 0; i--)
            j = Convert.ToInt32(b);
        sw3.Stop();
        Trace.WriteLine("sw1: " + sw1.ElapsedMilliseconds +
            "  sw2:" + sw2.ElapsedMilliseconds + ", +" + 100 * (sw2.ElapsedMilliseconds - sw1.ElapsedMilliseconds) / sw1.ElapsedMilliseconds + "% relative to sw1" +
            "  sw3:" + sw3.ElapsedMilliseconds + ", +" + 100 * (sw3.ElapsedMilliseconds - sw1.ElapsedMilliseconds) / sw1.ElapsedMilliseconds + "% relative to sw1"
            );
    }

The results:

sw1: 172  sw2:218, +26% relative to sw1  sw3:213, +23% relative to sw1
sw1: 168  sw2:211, +25% relative to sw1  sw3:211, +25% relative to sw1
sw1: 167  sw2:212, +26% relative to sw1  sw3:208, +24% relative to sw1
sw1: 167  sw2:211, +26% relative to sw1  sw3:209, +25% relative to sw1
sw1: 167  sw2:212, +26% relative to sw1  sw3:210, +25% relative to sw1

Conclusion:

The unsafe method is about 25% faster than the other two!

The relative slowness of the "if" version is due to the high cost of branching. The cost of the Convert could have been avoided if Microsoft would do the conversion at compile time..

---

Convert.ToByte(myBool) 

will give you 0 if myBool is False or 1 if it is True.

---

Hand-written IL:

.method private hidebysig static 
    int32 BoolToInt (
        bool b
    ) cil managed noinlining 
{
    .maxstack 8

    IL_0000: ldarg.0
    IL_0001: ldc.i4.0
    IL_0002: cgt.un
    IL_0004: ret
}

And they are jitted to few x86 codes:
(clrjit.dll version 4.7.3131.0)

test        cl,cl
setne       al
movzx       eax,al
ret

The only problem is that I have found no simple way to inline IL in C#. This answer is done using dnSpy.

---

You can use this struct to do similar to ChaosPandion's solution, but with safe code.

[StructLayout(LayoutKind.Explicit)]
struct BoolByte
{
    [FieldOffset(0)]
    public bool flag;
    [FieldOffset(0)]
    public byte num;
}

...

bool someBool = true;
byte num = new BoolByte() { flag = someBool }.num;

I haven't benchmarked it, so I'm not sure how the speed compares.

[EDIT] Well I ran the benchmark with .NET 3.5 equivalent mono and it looks like this is ~10% slower than a plain if check (on my macbook pro). So forget about this one. I doubt .NET 4+ would make a difference there.

---

Since .NET Core 2.1 you can reinterpret the bool as a byte this way. This is branch-free and should be very fast, as it hardly needs to "do" anything.

Technically, the true value could be any non-zero byte, but in practice, it is 1. That deserves some consideration. If you want absolute certainty, you could look for an efficient, branch-free way to turn a byte into 1 if it is non-zero, or leave it 0 otherwise. (Two approaches come to mind: A) Smear the bits so that either all bits are 0 or all bits are 1, then do & 1 to get either 0 or 1. B) Take 0 - n as an int, which will be either zero or negative. Shift the sign bit so that it becomes the least significant bit, resulting in either 0 or 1.)