Hi there!
Really enjoying Zig so far, been learning it for a few months now. I come from very high-level object-oriented languages, so it’s taking me a bit longer to fully grasp than I had hoped, but I’m getting there
Today I was in need of an array list of booleans. I figured instead of just using an std.ArrayList(bool), which would waste 7 bits per entry, I could pack them more tightly, sort of akin to a packed struct I suppose. I discovered that I can actually use an std.ArrayListAligned(u1, 1) instead, and it seems to work perfectly!
My question now is: is there any downside to this?
I’ve looked at std.DynamicBitSetUnmanaged, which seems to use an array of usizes and std.BitStack, which uses an std.ArrayList(u8) as a back-end. Seems to me that both of those could be simplified quite a bit by using an std.ArrayListAligned(u1, 1), so why aren’t they? Is it for performance reasons or is there some edge-case that I haven’t thought of? Would love to get some insight
I’m asking purely out of curiosity btw, my use-case doesn’t even really justify packing the bools so tightly – I’m just trying to learn!
Using an array list is fine if you need a growable collection of booleans. For that either std.ArrayList(bool) or std.ArrayListAligned(u1, 1) will produce the same slice and alignment. @alignOf(bool) == 1 which is the same as @alignOf(u1) == 1 (at least on my x86 machine) so you will end up taking the same amount of space for both of these. So both of these will take up 8 bits of space for every bool.
To your question:
The downsides will depend on what your usecase is. If you don’t know the upper bound on the number of booleans you need, then this is a good choice. std.DynamicBitSetUnmanaged will act very similarly because under the hood it uses a lot of the same mechanics, but using usize and it’s alignment instead of bools. This will pack them more tightly together since you will have no wasted space. If you know the bound, using something like std.StaticBitSet will not allocate and have better performance.
The main reason for using one of the bitsets is to minimize the memory space.
Especially if your bitset is sufficiently small and fits into a single integer there are some very handy builtins/instructions that the bitset can use to perform extremely fast calculations:
@popCount() to count the number of set bits
@clz()/@ctz() to count the number of leading/trailing zeroes (e.g. to find the first set bit)
I think I must’ve had the complete wrong idea then, I thought an std.ArrayListAligned(u1, 1) would pack the bits tightly! I was under the impression that alignment is measured in bits, not bytes, so I thought an alignment of 1 would place each bit after the other with no wasted space!
But from what you’re saying it seems that the 1 actually means 1 byte, meaning at the end of the day I’m still wasting the same amount of space as before
So that means that when I really do want to pack my bools as tightly as possible, I should probably use an std.DynamicBisSetUnmanaged, right? The reason I initially didn’t is because it doesn’t have the same methods as an array list – there is no simple append, I would have to manually call resize and then setValue.
I suppose I could also homecook something myself!
Yes, I believe this is correct. It will have a different api, but that is the nature of packing them tightly. There will be no way to add 1 bool at a time, you’ll have to do it by adding the backing type and keep track of how many of those bits are used. Using the std library implementation will handle a lot of that for you.
Another option you have is making an std.ArrayList(u8) (managed or not) and getting a Writer with byte_list.writer(), and then wrapping that in a std.io.BitWriter. It’s more hoops to jump through, but that will let you use .writeBits to write as little as one bit at a time to the array list.
Since I really only need an append function and direct read&write access to the bits, I wrote this simple wrapper around an std.ArrayListUnmanaged(u8). Seems to work great for me:
const BitListUnmanaged = struct {
/// both `bytes.items` and `bits` point to the same memory, just interpreted differently.
/// `bytes.capacity * 8` is the capacity of this bit list in bits.
bytes: std.ArrayListUnmanaged(u8),
/// both `bits` and `bytes.items` point to the same memory, just interpreted differently.
/// `bits.len` is the actual amount of bits stored. Bits outside of this slice should be considered undefined.
bits: []u1,
pub const empty: BitListUnmanaged = .{
.bytes = .empty,
.bits = &[0]u1{},
};
pub fn append(this: *BitListUnmanaged, allocator: std.mem.Allocator, value: bool) !void {
try this.bytes.ensureTotalCapacity(allocator, this.bits.len / 8 + 1);
this.bits = asBitArray(this.bytes.items, this.bits.len + 1);
this.bits[this.bits.len - 1] = @intFromBool(value);
}
fn asBitArray(bytes: []u8, len: usize) []u1 {
return @as([*]u1, @ptrCast(bytes))[0..len];
}
};
As you can see I didn’t even bother implementing other array list methods. This gets the job done and is simple enough to justify being in my codebase
I don’t think this does what you think it does. Each u1 in the bits slice will still take up an entire byte, so the capacity you ensure is too little.
It may appear as if it works fine at first because:
ensureTotalCapacity often acquires more memory than is needed (in order to minimize re-allocations).
The memory after the ArrayListUnmanaged’s owned allocation may still be owned by your program so you can read/write to it without a segfault.
When using @ptrCast, it’s very important that you be careful and go through the exact guarantees that the language gives you about the representation of the pointed-to data, as @ptrCast’s failures don’t always show themselves easily.
