How do I reinterpret bool as byte/int without branching in C#?

Question

Is it possible in C# to turn a bool into a byte or int (or any integral type, really) without branching?

In other words, a ternary is not good enough:

var myInt = myBool ? 1 : 0;   // could compile to a branch

We might say we want to reinterpret a bool as the underlying byte, preferably in as few instructions as possible. The purpose is to avoid branch prediction fails as seen here.

---

For the sake of argument, let's assume that a bool already exists as a 0/1 in an integer register or memory, not just as a compare result in FLAGS. Most modern ISAs do have a branchless way get a 0 or 1 from an int or FP compare, so we can hope C# used that. Or if the bool just came from an x<y, we'd like to force the compiler to materialize it as an integer instead of turning count += myInt into a branch around count++.

Contrapuntal

I will add that a 2-entry Dictionary<bool, byte> feels like overkill. Hash-based lookup seems on the heavy side for what we are trying to do. – Contrapuntal

"The purpose is to avoid branch prediction fails as seen here" -- do you have any evidence whatsoever that you actually need to do that? I.e. you have a measured performance problem, which you have specifically confirmed is 100% caused by the branch-prediction issue described? Bottom line: you can cast using unsafe code, but you'd have to do it inline, otherwise the method call may cause as much overhead than a missed branch, and even then you still have to deal with the problem that there's no guarantee about what value is stored in a bool. You can't rely on 1 for a true value. – Granitite

@PeterDuniho Indeed, I'm making no assumptions about true values other than that they are non-zero. As for measurements: The linked question and its accepted answer cover that well, in my opinion. Otherwise, you may consider this a theoretical exercise, to be measured whenever it is applied in a particular scenario. Let's say that I want to have a solution available when the branch prediction failure is determined to be an issue. And yes, that requires something inline that is very efficient! – Contrapuntal

"that requires something inline that is very efficient" -- not really. Most branch-prediction issues can be addressed by restructuring the data. It seems to me that you're at least two steps ahead of the horse with your cart (there's no actual problem, and you've already decided what solution you think is required, even though you don't have a problem to measure). :) That said, I've addressed what is the simplest efficient way to avoid the bool test, in my answer below. – Granitite

@PeterDuniho Although the suggestion to take a different route altogether is good and welcome, I think it's nice to have room to solve interesting problems, even if they can be circumvented in some or all circumstances. – Contrapuntal

@Contrapuntal Does the standard System.Convert.ToByte(bool) branch? – Monochrome

Nevermind, yes, it does ( public static byte ToByte(bool value) { return value? (byte)Boolean.True: (byte)Boolean.False; }) – Monochrome

Answer 1

unsafe
{
     byte myByte = *(byte*)&myBool;   
}

Another option is System.Runtime.CompilerServices.Unsafe, which requires a NuGet package on non-Core platforms:

byte myByte = Unsafe.As<bool, byte>(ref myBool);

The CLI specification only defines false as 0 and true as anything except 0 , so technically speaking this might not work as expected on all platforms. However, as far as I know the C# compiler also makes the assumption that there are only two values for bool, so in practice I would expect it to work outside of mostly academic cases.

Catchup

Out of curiosity, can Unsafe.As be used without declaring our method and project as unsafe? – Contrapuntal

@Contrapuntal Yes, since it doesn't involve any pointer types (some other methods on S.R.CS.Unsafe do). However, just because it doesn't require the "unsafe" compiler flag doesn't make it safe, it's still unverifiable code that could be misused to violate memory safety. The same goes for all the other answers that have been posted to this question so far. – Catchup

Perfect. That's good to know. Actually, I believe using MemoryMarshal.AsBytes on a ReadOnlySpan<bool> cannot be misused to violate memory safety, as the elements are of the exact same size and cannot be mutated! – Contrapuntal

@Contrapuntal MemoryMarshal.CreateReadOnlySpan doesn't verify the length parameter and could create good old buffer overflows, however. – Catchup

Ok, ok, if one is foolish enough to pass it >1 length, you're right. :p – Contrapuntal

@Contrapuntal I didn't mean to sound pedantic, it's just that I think one should carefully consider the motivations for avoiding the unsafe keyword. The issue isn't having to check the checkbox, the issue is gaining the ability to screw things up without the language and runtime catching it. – Catchup

Understood. I think enabling the unsafe checkbox potentially opens up a whole range of dangers, so it's pleasant to avoid it and at least minimize the risk of violating memory safety. – Contrapuntal

Judging from the generated assembly, the solutions in this answer are the fastest. Next comes MemoryMarshal, then StructLayout, and finally the naive branch. – Contrapuntal

Answer 2

The usual C# equivalent to "reinterpret cast" is to define a struct with fields of the types you want to reinterpret. That approach works fine in most cases. In your case, that would look like this:

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

Then you can do something like this:

BoolByte bb = new BoolByte();
bb.Bool = true;
int myInt = bb.Byte;

Note that you only have to initialize the variable once, then you can set Bool and retrieve Byte as often as you like. This should perform as well or better than any approach involving unsafe code, calling methods, etc., especially with respect to addressing any branch-prediction issues.

It's important to point out that if you can read a bool as a byte, then of course anyone can write a bool as a byte, and the actual int value of the bool when it's true may or may not be 1. It technically could be any non-zero value.

All that said, this will make the code a lot harder to maintain. Both because of the lack of guarantees of what a true value actually looks like, and just because of the added complexity. It would be extremely rare to run into a real-world scenario that suffers from the missed branch-prediction issue you're asking about. Even if you had a legitimate real-world example, it's arguable that it would be better solved some other way. The exact alternative would depend on the specific real-world example, but one example might be to keep the data organized in a way that allows for batch processing on a given condition instead of testing for each element.

I strongly advise against doing something like this, until you have a demonstrated, reproducible real-world problem, and have exhausted other more idiomatic and maintainable options.

Granitite

Agreed on the caveat, but a very interesting solution nonetheless. I'm familiar with StructLayout(LayoutKind.Explicit), but I hadn't thought of it as a solution to this particular problem. :) It's a nice one if we have control of the initial booleans. If not, then we still have to copy them to this struct, which is a pity, but it does eliminate branching! – Contrapuntal

Agreed (and aware) that false is 0 and true is non-zero (not 1 per se). – Contrapuntal

Maybe this is more usable with Unsafe.As<bool, BoolByte>(ref myBool);? – Iatric

@BrunoZell I really like that! That suddenly makes this an actual contender against my own solution. Particularly not having to reinterpret twice or performing an indexing operation feels better... although it might just be all the same, performance-wise. Would be interesting to benchmark. As a downside, we need to have the struct definition somewhere, rather than relying purely on System types. – Contrapuntal

Answer 3

Here is a solution that takes more lines (and presumably more instructions) than I would like, but that actually solves the problem directly, i.e. by reinterpreting.

Since .NET Core 2.1, we have some reinterpret methods available in MemoryMarshal. We can treat our bool as a ReadOnlySpan<bool>, which in turn we can treat as a ReadOnlySpan<byte>. From there, it is trivial to read the single byte value.

var myBool = true;
var myBoolSpan = MemoryMarshal.CreateReadOnlySpan(ref myBool, length: 1);
var myByteSpan = MemoryMarshal.AsBytes(myBoolSpan);
var myByte = myByteSpan[0]; // =1

Contrapuntal

Answer 4

maybe this would work? (source of the idea)

using System;
using System.Reflection.Emit;

namespace ConsoleApp10
{
    class Program
    {
        static Func<bool, int> BoolToInt;
        static Func<bool, byte> BoolToByte;

        static void Main(string[] args)
        {
            InitIL();

            Console.WriteLine(BoolToInt(true));
            Console.WriteLine(BoolToInt(false));
            Console.WriteLine(BoolToByte(true));
            Console.WriteLine(BoolToByte(false));

            Console.ReadLine();
        }

        static void InitIL()
        {
            var methodBoolToInt = new DynamicMethod("BoolToInt", typeof(int), new Type[] { typeof(bool) });
            var ilBoolToInt = methodBoolToInt.GetILGenerator();
            ilBoolToInt.Emit(OpCodes.Ldarg_0);
            ilBoolToInt.Emit(OpCodes.Ldc_I4_0); //these 2 lines
            ilBoolToInt.Emit(OpCodes.Cgt_Un); //might not be needed
            ilBoolToInt.Emit(OpCodes.Ret);

            BoolToInt = (Func<bool, int>)methodBoolToInt.CreateDelegate(typeof(Func<bool, int>));

            var methodBoolToByte = new DynamicMethod("BoolToByte", typeof(byte), new Type[] { typeof(bool) });
            var ilBoolToByte = methodBoolToByte.GetILGenerator();
            ilBoolToByte.Emit(OpCodes.Ldarg_0);
            ilBoolToByte.Emit(OpCodes.Ldc_I4_0); //these 2 lines
            ilBoolToByte.Emit(OpCodes.Cgt_Un);  //might not be needed
            ilBoolToByte.Emit(OpCodes.Ret);

            BoolToByte = (Func<bool, byte>)methodBoolToByte.CreateDelegate(typeof(Func<bool, byte>));

        }
    }
}

based on microsoft documentation of each emit.

1. load the parameter in memory (the boolean)
2. load in memory a value of int = 0
3. compare if any the parameter is greater than the value (branching here maybe?)
4. return 1 if true else 0

line 2 and 3 can be removed but the return value could be something else than 0 / 1

like i said in the beginning this code is taken from another response, this seem to be working yes but it seem slow while being benchmarking, lookup .net DynamicMethod slow to find way to make it "faster"

you could maybe use the .GetHashCode of the boolean?

true will return int of 1 and false 0

you can then var myByte = (byte)bool.GetHashCode();

Braddy

I like this idea! But alas, I've check the reference source: the implementation is return (m_value)?True:False;. – Contrapuntal

@Timo, i have updated my answer with an alternative solution :-) – Braddy

Your new solution made me chuckle. That is extravagant! And indeed it solves the problem! Could you add a little more explanation on what the opcodes in question do and why you are using these ones? – Contrapuntal

I can't seem to find a definitive answer, but it seems likely that OpCodes.Cgt_Un branches. :( – Contrapuntal

Answer 5

(Modified) from the source code for System.Convert.ToByte(object):

bool b = true;
byte by = ((IConvertible)b).ToByte(null)

Looking at the assembly confirms that we don't get any additional branches.

    public int M(bool b) {
        byte by = ((IConvertible)b).ToByte(null);
        return by;
    }

C.M(Boolean)
    C.M(Boolean)
    L0000: movzx eax, dl
    L0003: test eax, eax
    L0005: setne al
    L0008: movzx eax, al
    L000b: ret

However, as noted in the comments, depending on the compiler settings and whether your are building for .NET Framework or not, you may get additional code added as well. Compiling the below code for .NET Framework on sharplab.io results in code with call commands which could end up being slower depending on your hit-miss rate.

By comparison, if you are fine with using "unsafe" code,

public byte M(bool myBool) {
        unsafe
        {
            byte myByte = *(byte*)&myBool;   
            return myByte;
        }
    }

returns a much cleaner, non-calling, non-branching asm code. (even on .NET Framework)

C.M(Boolean)
    L0000: mov [rsp+0x10], edx
    L0004: movzx eax, byte [rsp+0x10]
    L0009: ret
    

Monochrome

Have you tried looking at the x86 asm from a function using this, e.g. on sharplab.io? That would be one way to see how it actually compiles. – Galven

Response is way late, but sharplab doesn't seem to provide the inner assembly for ToByte. – Monochrome

Works for me: sharplab.io/… - in a function taking a bool b arg (not a constant, that would optimize away!) we get movzx eax, dl / test eax,eax (silly instead of test dl,dl but ok) then setne al to "booleanize" the incoming bool in case it was 0 / non-zero instead of 0 / 1. Then a redundant movzx eax, al to zero-extend it. But the high bytes of RAX were already zero from the first MOVZX. – Galven

(On ancient CPUs like Nehalem, the final movzx can avoid partial-register stalls when the caller reads the whole EAX. On all other CPUs it's unnecessary. And could at least have avoided defeating mov-elimination by doing setcc dl. – Galven

@PeterCordes Ah, I was running on .NET, which results in some CALLs. But either way, it still appears to not have any additional branches. (Debug has some jz s though) – Monochrome

Oh wow, yeah the ".NET Framework (x64)" version is a disaster, with two call instructions! That's what you're showing in the current version of your answer. It might not have any data-dependent branching (at least not in this code, and probably not the callees), but it's so slow that simple branchy code might be faster if the mispredict rate is like 5 or 10%, not 50%. – Galven

@PeterCordes Oops, good catch. Copied the wrong page. Fixed! – Monochrome

Is ".NET Framework" still something that matters for some codebases? (I mostly only know about .NET from Q&As like this popping up on SO, I don't actually use it.) If the Framework version matters at all, it's probably important to warn people that this answer will compile terribly in that case, unlike with normal .NET where it's usable, although not as efficient as what the OP asked for (wasting instructions on test/setcc instead of using the bool's bit-pattern directly. I assume the ABI already requires a bool to be 0 or 1, like the C++ ABI?). – Galven

Not sure which versions sharplab's compilers use and how compilers differ between different versions of .NET (+.NET Core,which I believe is also just .NET now). I think your comment is enough of a warning--none of the other answers prove their correctness with assembly code :p – Monochrome

Not everyone reads comments; I'd suggest mentioning that much worse asm seems to be possible on some implementations of C#. Re: other answers not showing asm: I'd suggest putting their code into sharplab and having a look. You could edit the answers with code blocks and links. The unsafe type-pun for example is extremely likely to compile as written, extremely unlikely for a compiler to invent a branch from that for a bool object that already exists in memory. – Galven

@PeterCordes Updated! If there is anything else you think should be included, feel free to propose an edit~ – Monochrome

Oh, so the type-pun actually stores to memory and then reloads, like 5 cycle latency. :/ This is what you get when being overly paranoid about the compiler possibly branching, and you try this hard to stop it from seeing the simple logic of your program, I guess. Maybe that compiles ok when the ultimate destination is memory, not reloading, we can hope. – Galven