Friday, August 14, 2015


[UPDATE 3] Removed the unnecessary function ClearBits() and its calls to result in >3x performance increase on adding bits (benchmark times updated).

[UPDATE 2] Changed out arithmetic operators for bit-wise operators as well as omitting the use of Math.Floor for a result of ~20 percent speed increase in setting bits (benchmark times updated).

[UPDATE 1] Fixed a bug where the 8th bit added is always set to True(1).

I previously made a class called TBitArray with the purpose of storing individual bits. At the time I didn't know that .Net already had a BitArray class which I could use so I made mine. I then thought well if I have an array I might as well make a list version as well. At the time I never got around to it. Then time passed and I started work on my encoding schemes. I needed to store bits that would resize as needed but I was lazy and instead stored each bit as a byte (yeah waste of space I know). This time I am working on a potential image format for my game. For this format everything is encoded and decode by bits and so again I needed something that would resize as needed. This time though I actually got to working on it. I know that one can resize the BitArray that is built into .Net but I did some benchmarks and well its VERY slow. So with speed and dynamic size in mind I set out to create a BitList class to make my life easier for this and potentially future projects. And I am sharing it here for those who may want to use it. I will provide the benchmarks first to show the difference. If anyone has any suggestions please leave a comment :)

As you can see BitList is much faster at adding bits when size is unknown and where size needs to be changed dynamically.
If you know exactly the number of bits needed please use the built in BitArray instead as you can see it is much faster at setting bits.

This class was made for my purpose of adding bits and not the constant manipulation of bits in memory. So if you need to constantly add bits this might be for you. The bit manipulation implemented is only for light use as it is slower than bit manipulation with BitArray, though slow it is still reasonably fast. Just use it where appropriate is all I'm saying.

Note: This class only implements the functionality that I myself needed, it does not provide other functionality that a typical List(Of T) has. If you need them you may implement them yourself or I might add this when my needs apply. I guess this is much closer the a queue then a list but too lazy to rename it lol. I could have also used a BitArray to store the lookup table but anyone who wants to do that is free to.

Code (VB.Net):

No comments: