# Can the compiler stuff booleans into a bitmask since it has the borrow checker?

**URL:** <https://internals.rust-lang.org/t/can-the-compiler-stuff-booleans-into-a-bitmask-since-it-has-the-borrow-checker/16472>\
**Category:** compiler\
**Created:** [April 14, 2022, 11:25pm UTC](https://internals.rust-lang.org/t/can-the-compiler-stuff-booleans-into-a-bitmask-since-it-has-the-borrow-checker/16472 "2022-04-14T23:25:13Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![Corallus-Caninus](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/corallus-caninus/32/7791_2.png) [@Corallus-Caninus](https://internals.rust-lang.org/u/Corallus-Caninus)\
**Post date:** [April 14, 2022, 11:25pm UTC](https://internals.rust-lang.org/t/can-the-compiler-stuff-booleans-into-a-bitmask-since-it-has-the-borrow-checker/16472/1 "2022-04-14T23:25:13Z")

</div>

I was thinking about how I was told booleans each take up entire word size to be represented in a program. if we have the borrow checker and know they will only be mutated one at a time or copied, can we push all booleans in a program into one bitmask? In the best case the value would never be copied and would be loaded at each comparison or mutation from a single register for the entirety of a program.

It seems like it would be a vectorizer pass similar to AVX but for bitmasking operations. Does this already exist? It seems possible even without the borrow checker.

---

<div class="post-metadata">

**Author:** ![mathstuf](https://avatars.discourse-cdn.com/v4/letter/m/958977/32.png) [@mathstuf](https://internals.rust-lang.org/u/mathstuf)\
**Post date:** [April 14, 2022, 11:52pm UTC](https://internals.rust-lang.org/t/can-the-compiler-stuff-booleans-into-a-bitmask-since-it-has-the-borrow-checker/16472/2 "2022-04-14T23:52:11Z")

</div>

This sounds like it'd require atomics around any `bool` access (because who knows if another thread will be doing something with a neighboring bit. CPUs with bit addressing modes are few and far between and I suspect those tend to lack threads so maybe _they_ don't care, but such things are beyond the Rust language spec IMO.

I think if you know you can bitpack, there are crates for you already to manage them (with appropriate lack of access via any `&bool` or `&mut bool` handles).

---

<div class="post-metadata">

**Author:** ![Corallus-Caninus](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/corallus-caninus/32/7791_2.png) [@Corallus-Caninus](https://internals.rust-lang.org/u/Corallus-Caninus)\
**Post date:** [April 15, 2022, 12:38am UTC](https://internals.rust-lang.org/t/can-the-compiler-stuff-booleans-into-a-bitmask-since-it-has-the-borrow-checker/16472/3 "2022-04-15T00:38:18Z")

</div>

The threading model would be on top of the primitive type anyways because of the borrow checker. You need AtomicBool or Arc already for bool so it should be the same as bool thanks to the borrow checker. Essentially for some set of Bool types if they are all bool and not wrapped in another type such as Arc, therefore following the borrow checker, they should be able to be vectorized into a "boolmask" type of size word. its not really bitpacking so much as auto-vectorization of "bit words" to architecture word size.

this seems to be the closest crate in relation to this I could find [https://crates.io/crates/bitvec](https://crates.io/crates/bitvec)

---

<div class="post-metadata">

**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\
**Post date:** [April 15, 2022, 5:59am UTC](https://internals.rust-lang.org/t/can-the-compiler-stuff-booleans-into-a-bitmask-since-it-has-the-borrow-checker/16472/4 "2022-04-15T05:59:04Z")

</div>

Because `size_of::<bool>()` is `1`, reference need to be able to replace the whole byte.

One way that packing like you describe could be legal would be something like "copy-only fields" ([A #[repr] to allow an enum containing enums to use a single discriminant - #5 by scottmcm](https://internals.rust-lang.org/t/a-repr-to-allow-an-enum-containing-enums-to-use-a-single-discriminant/11670/5)) so there's always the opportunity to run code, and thus it's work fairly easily.

---

<div class="post-metadata">

**Author:** ![SkiFire13](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/skifire13/32/7579_2.png) [@SkiFire13](https://internals.rust-lang.org/u/SkiFire13)\
**Post date:** [April 15, 2022, 7:56am UTC](https://internals.rust-lang.org/t/can-the-compiler-stuff-booleans-into-a-bitmask-since-it-has-the-borrow-checker/16472/5 "2022-04-15T07:56:38Z")

</div>

> [@Corallus-Caninus](#):
>
> I was thinking about how I was told booleans each take up entire word size to be represented in a program.

It takes one byte, not a word (which would be 2 bytes AFAIK).

> [@Corallus-Caninus](#):
>
> if we have the borrow checker and know they will only be mutated one at a time or copied, can we push all booleans in a program into one bitmask?

No. The reason that the borrow checker can avoid data races is because values in rust are always multiple of bytes, so even if two values are mutated from two different threads they won't touch the same byte. This would no longer be true with your proposal since a bool would be smaller than a byte, so mutating two adjacent bools from two different thread may result in mutating the same byte, thus in a data race.

Maybe an example would make this cleaner:

```rust
let mut bools = [true, true];
let (first, second) = bools.split_at_mut(1);
let first = &mut first[0];
let second = &mut second[0];
// Now `first` and `second` are two references that point to adjacent bools

// Using `rayon::scope` to send non-`'static` data
rayon::scope(|scope| {
    // One thread mutates `first`
    scope.spawn(|_| {
        *first = false;
    });
    // The other mutates `second`
    scope.spawn(|_| {
        *second = false;
    });
});

dbg!(first, second);

```

If `bools` was a bitmask, the `first` and `second` would point to the same byte, and thus modifying them at the same time would result in a data race. Note that this code doesn't use atomics right now, because bool being 1 byte makes this safe even without them. Your proposal however would require every `bool` to become an `AtomicBool`.

Not to mention all the code that currently expects `bool` to have size `1`, and thus would break if this was changed.

---

<div class="post-metadata">

**Author:** ![chrefr](https://avatars.discourse-cdn.com/v4/letter/c/e480ec/32.png) [@chrefr](https://internals.rust-lang.org/u/chrefr)\
**Post date:** [April 15, 2022, 9:46am UTC](https://internals.rust-lang.org/t/can-the-compiler-stuff-booleans-into-a-bitmask-since-it-has-the-borrow-checker/16472/6 "2022-04-15T09:46:16Z")

</div>

How will a code like `*b = true;` compiled? We cannot know the bit pattern for `true` for \*`b` ahead of time!

---

<div class="post-metadata">

**Author:** ![Corallus-Caninus](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/corallus-caninus/32/7791_2.png) [@Corallus-Caninus](https://internals.rust-lang.org/u/Corallus-Caninus)\
**Post date:** [April 15, 2022, 8:40pm UTC](https://internals.rust-lang.org/t/can-the-compiler-stuff-booleans-into-a-bitmask-since-it-has-the-borrow-checker/16472/7 "2022-04-15T20:40:22Z")

</div>

hmmm maybe for all Booleans within a scope? seems like this could happen alot with object oriented programming. If a struct contains several booleans its object will be whats borrow checked. But yes this is admittedly not as generalizable as I first thought. If its a tricky enough edge case it should probably just be in a crate.

---

<div class="post-metadata">

**Author:** ![toc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/toc/32/6692_2.png) [@toc](https://internals.rust-lang.org/u/toc)\
**Post date:** [April 15, 2022, 10:48pm UTC](https://internals.rust-lang.org/t/can-the-compiler-stuff-booleans-into-a-bitmask-since-it-has-the-borrow-checker/16472/8 "2022-04-15T22:48:30Z")

</div>

> [@chrefr](#):
>
> How will a code like `*b = true;` compiled? We cannot know the bit pattern for `true` for \* `b` ahead of time!

Obviously boolean pointers would have to become fatter to hold the byte address and 3 bits of index. This could even be done in a library type today. Most of the problems being presented here are not intractable, and even the far-reaching problems can be solved with just sometimes making bools 8 bits anyway (e.g. for atomics).

@Corallus-Caninus `bool` is currently the smallest addressable size. This keeps it simple (it's like C), makes references to it simple, and it usually doesn't use up that much extra space. Compare it to how often you use a u64/usize when a smaller integer type would have worked. Or how often your structs have literally unused padding bytes. There are performance issues, doing a mask operation every time you dereference may not be what you want. And there are aliasing issues of having multiple mutable references to the same byte (tractable but probably not fun).

Even applying this space optimization only within a function body, only for bools which do not get referenced, would probably just lose a small amount of performance. It would be worth it only if you had exhausted almost all other avenues of compressing stack space.

When you do want to make these tradeoffs though, they can be done explicitly. Bitflags don't (really) exist in Rust yet, but they probably should, and this would allow you to pack a single struct's fields and opt into masking with either fat references or inability to reference. `bitvec` is there for when you want just a ton of booleans in one place, probably one of the big spots that 8×ing memory isn't helpful.

---

<div class="post-metadata">

**Author:** ![CAD97](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cad97/32/3460_2.png) [@CAD97](https://internals.rust-lang.org/u/CAD97)\
**Post date:** [April 15, 2022, 11:37pm UTC](https://internals.rust-lang.org/t/can-the-compiler-stuff-booleans-into-a-bitmask-since-it-has-the-borrow-checker/16472/9 "2022-04-15T23:37:20Z")

</div>

> [@toc](#):
>
> This could even be done in a library type today.

This is exactly what [bitvec](https://docs.rs/bitvec/latest/bitvec) does, and more. @myrrlyn has written the best bit addressing library out there, in any language.

---

<div class="post-metadata">

**Author:** ![zackw](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/zackw/32/2071_2.png) [@zackw](https://internals.rust-lang.org/u/zackw)\
**Post date:** [April 17, 2022, 12:31am UTC](https://internals.rust-lang.org/t/can-the-compiler-stuff-booleans-into-a-bitmask-since-it-has-the-borrow-checker/16472/10 "2022-04-17T00:31:54Z")

</div>

I've actually personally written code that could benefit from compiler compaction of booleans into a single register. They weren't `bool`s, though, they were enum discriminators...

```rust
struct LandmarkFileColumns {
    addr: usize,
    lon: usize,
    lat: usize,
    dist: usize,
}

fn select_columns(header: &csv::StringRecord, location: &str)
    -> Result<LandmarkFileColumns, LandmarkFileMissingColumnsError> {

    let mut addr: Option<usize> = None;
    let mut lon: Option<usize> = None;
    let mut lat: Option<usize> = None;
    let mut dist: Option<usize> = None;

    for (index, field) in header.iter().enumerate() {
        match field {
            "addr" => { addr = Some(index); },
            "longitude" => { lon = Some(index); },
            "latitude" => { lat = Some(index); },
            f if f == location => { dist = Some(index); },
            _ => {},
        }
        if let (Some(addr), Some(lon), Some(lat), Some(dist)) =
            (addr, lon, lat, dist) {
                return Ok(LandmarkFileColumns { addr, lon, lat, dist });
            }
    }
    return Err(LandmarkFileMissingColumnsError(/* ... */));
}

```

Because `usize` has no niches, at the assembly level each of the mutable `Option<usize>` variables requires two words, and (on x86-64) [we run out of registers](https://play.rust-lang.org/?version=nightly&mode=release&edition=2021&gist=221b27a910acdd9d94770b0db6caeb32).

---

<div class="post-metadata">

**Author:** ![chrefr](https://avatars.discourse-cdn.com/v4/letter/c/e480ec/32.png) [@chrefr](https://internals.rust-lang.org/u/chrefr)\
**Post date:** [April 23, 2022, 9:54pm UTC](https://internals.rust-lang.org/t/can-the-compiler-stuff-booleans-into-a-bitmask-since-it-has-the-borrow-checker/16472/11 "2022-04-23T21:54:20Z")

</div>

> [@toc](#):
>
> Obviously boolean pointers would have to become fatter to hold the byte address and 3 bits of index.

But then you break pointer casts (`&*(&b as *const bool as *const u8 as *const bool)`).

You can pack it inside one word by using the unused high bits, but this is only possible on 64 bit platforms.

---

<div class="post-metadata">

**Author:** ![toc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/toc/32/6692_2.png) [@toc](https://internals.rust-lang.org/u/toc)\
**Post date:** [April 24, 2022, 1:28am UTC](https://internals.rust-lang.org/t/can-the-compiler-stuff-booleans-into-a-bitmask-since-it-has-the-borrow-checker/16472/12 "2022-04-24T01:28:27Z")

</div>

> [@chrefr](#):
>
> But then you break pointer casts ( `&*(&b as *const bool as *const u8 as *const bool)` ).
> 
> You can pack it inside one word by using the unused high bits, but this is only possible on 64 bit platforms.

I mean, it breaks a lot of things for sure if this is applied globally, yes. I guess I am interpreting @Corallus-Caninus's question as "can we have a space optimization pass that packs booleans into bitmasks". My answer would be "yes definitely", with some caveats mentioned in this thread. Reifying bitreferences seems pretty easy, this is already done explicitly in bitvec. Framed as an optimization pass we would not, as you say, want to make this observable.

LLVM doesn't do this optimization even with `-Os`, [as far as I can tell](https://godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAMzwBtMA7AQwFtMQByARg9KtQYEAysib0QXACx8BBAKoBnTAAUAHpwAMvAFYTStJg1DEArgoKkl9ZATwDKjdAGFUtEywYgATKUcAZPAZMADl3ACNMYm8ADlIAB1QFQjsGFzcPb3jE5IEAoNCWCKivWKtMGxShAiZiAjT3Tx8yioEqmoI8kPDImMtq2vqMpv6OwK7CnpKASktUE2Jkdg44kzCAaioGNeaCAH00dIYFCARMJiwotYBSLwA2K4BWACEb2/NiR4ARUjXaVFFbPZrnd3lM1gBaK4AZmwawASpgFCZaARoU4IGY8AAvTA/TE4vFJAlrfGYGZrCBTaGwq4AdheGgAgmsWb9MAQ1iwTBzzuhLgB5OKAhho0nU65Qz5rYICTDQhnM1n0Dlcjl/TxrQXC0VEuUwiVSmVBeVXJmstkq7m/JgEECaoUpHXYvU0yXS2Ums1K9mcq34cx2rWOqFOMX66GGj1QhWmxUs/jECmBLCqH6vGiYWjoMGBNanc6RAB0hEilMLjHckRtmEp13psfN5pYNuQCA2eEz6DrCsbveBXl5Hy8XgN4rpPb7k8HBrWQlQbAgycwqip0Ybk9ZdM%2B643/fVwEIJiwNxHEbH9a9u/N6pnc4XS5XnrjG63O5fw4MtgIR7lw9H4YvZ8r2tDkI1necawfVcJ13V9Lw3Kg1jwRDELPN0/gBFJ/xpQDgPNf1QLdO9IIYFNoLfSc4KAvtdmw7sqMo2lt3g81kItCliIgQdyU49UeIgiBP34hcCKmMEwK49A%2BR%2BdUZJtH5RPoli%2B2Idl5i2fkAGsoEHGSBDkiw1lE8jlJZBjNyYt9VO/YgtmwYhiCgMSny3DgZloTgHl4TwOC0UhUE4OEzA5BQ5gWTBgShHhSFtXy3JmTSQAeDR9E4SReBYCQNBSny/ICjheAUEAUtirQZjgWAkDQFg4joSJyEoaravoKIGDwYAEAIWgAE8%2BDoAhIiKiAwk0XgwkCGpus4aLqrYQR%2BQYHrRtILBmyMcQ4pWvBVIqAA3RFluXcpuSWaLAgGjzNtoPAwmISaXCwZaCGIPBMu4Ny%2BAMYAFAANQ7AB3QVGGm3h%2BEEEQxHYKQZEERQVHUTbdC4fRDGMYL9BuorIBmVAHQEIqOHBJw1lxghwXofbaAjBRCszcphQcUjBk8ABOXxSM6AoihAWkoSyJJhWZkA2YSAWUk57ool5yw6ZaBg2gGVwGmFmXrGFBXRnySWeb58x2iFtm9dqCWJilqEZlC%2BZFj0Z7MFOj7Lq80hct4fLTHMZA1jajquu6ikgvMH5cEIEhIuRtYXBqurExuKKpl4Ur4tIRLktSjh0tITKuGy53lvywripi0axLTrxvLzzgE%2BLmZ9uIJJ7EkIA%3D), I assume for some good reason(s). But maybe it would make sense as part of a suite of `-Oregister_starved` passes? Probably this isn't something you would build into rustc specifically.

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [July 23, 2022, 1:28am UTC](https://internals.rust-lang.org/t/can-the-compiler-stuff-booleans-into-a-bitmask-since-it-has-the-borrow-checker/16472/13 "2022-07-23T01:28:42Z")

</div>

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.