Mind your bits, will you?

C# doesn’t provide Bit Fields like C++, and as far as I know the smallest data you can work with is a byte (8 bits). For most cases that’s fine, but sometimes you may want to micromanage every single bit of your memory, and although C# isn’t the most recommended language if you need to do that regularly, you can use bitwise operations to achieve more efficient memory usage, what can be especially useful if you plan to optimize for CPU caching which is limited to only a few KBs on L1.

In a game I’m working on I’ve recently replaced general purpose “structs” for extra object composed data with “packed bits”. In that case the usage was in a map composed of Tile structs which have a few fields like: TileType (byte), DynamicFlags (byte), and LightLevel (byte). Each Tile also contained an array of structs that I removed and used multi-purpose uints instead.

I’m using a pattern inspired by flyweight. The TileType field of each Tile struct represents an index of an array that holds classes containing block logic, and the methods in these classes use data stored in the uints of each struct. To make good use of the data stored there while still maintaining a ‘sane’ approach, I’m not storing more than a single system datum on each uint.

Let’s say you have a Tile representing water, so its TileType field contains the index of the single instance of the ‘Water : UpdatableTile’ class. When the map updating loop reach that tile, it checks if it’s updatable (bitwise flag mask) and passes the data stored in the uints to the ‘UpdateTile()’ function in the ‘Water’ class instance, and that function decides what to do with it. In the case of the water, I’m storing all the data I need in a single uint: 13 bits for the X position, 11 bits for the Y position, and 8 bits for the water level on that individual block. I’m considering using 16x+16y for the position and use another uint for the water level to keep things simpler. You can scale this pattern to unimaginable levels… for the ‘conveyor belt’ tiles for example, I’m using one uint for its position, and the other uints represent the objects on the belt (ID and position).

Especially for that approach, direct control over your bits is very useful, however, I couldn’t find a good library to pack data into bits, so I decided to code my own functions to do that:

Gist Link

As you can see usage is very simple, and I guess you can’t go much more efficient than that. One element of the packing format isn’t used, so it’s useless data flowing around what’s not good for micro optimization, but it keeps things easier to understand and it’s pretty much negligible. Please note that there’s no checking whatsoever, so if the data you’re storing overflows the max number your bit count would allow, it will affect the adjacent numbers. A quick fix to that is using a mask, but that’s less efficient and not necessary if you know your sizes.

On a future article I’m going to show how I’m using bitwise to efficiently perform flag operations, like determining if an object contains multiple flags in a single bitwise operation, basically like this:

 

3 thoughts on “Mind your bits, will you?

Leave a Reply