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 conditional 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?
new string() down there, which copies the result char array! I won't even bother explaining the Array.Length property, which is 32-bit. –
Louannlouanna true always, always ends up as 1 when converted this way? It still seems unlikely that this is really the bottleneck... it processes data insanely quickly; where are you getting the data from that doesn't make IO the bottleneck? –
Genarogendarme 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);
}
& and >> into a small lookup vs. dual full lookup tables. In particular if the latter plays havoc with the cache/locality or not. –
Meandrous terabyte"? –
Astragalus 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.)
© 2022 - 2024 — McMap. All rights reserved.
optimization. If you haven't got a good enough reason, well the people here have saved you from a tonne of effort trying to improve something meanlingless. – Scanlanx ? 1 : 0is actually too slow for you, then you REALLY need to reexamine what you're trying to do. If a conversion at that level is happening tens of millions of times per second (the only way it'll ever noticeably affect performance), then why aren't you writing it in ASM or something anyway? That's the only way you're ever going to significantly beatx ? 1 : 0for speed. – Trimmer