Fast 2D matrix of bits

[Timon Gehr]

On 09/20/2011 12:19 AM, bearophile wrote:
> In Phobos (beside fast 2D/3D/4D vectors) I'd like a fast 2D matrix of bits. I have added an implementation in attach in this enhancement request:
>
> http://d.puremagic.com/issues/show_bug.cgi?id=6697
>
> It's a common enough data structure, and despite being simple it's not obvious, especially if you want it to be fast. A naive implementation that uses a BitArray is not fast enough.
>
> Bye,
> bearophile

The implementation uses int and uint everywhere. I think it is not 64 
bit aware?

 > // sizex_, sizey_ are signed to catch negative arguments bugs.

There would be no negative arguments if they were unsigned.


 > // opIndex not used because it's slower on LDC

Why is it slower? The structure should imho certainly use opIndex(Assign).


Since you want it to be really fast, this occurs multiple times:

 > immutable int index = x + (y << this.pow2); // 1D bit index
 > this._bits[index / nbits_item] |= 1 << (index % nbits_item);

nbits_item is a power of two. So the divisions/modulo have the potential 
to be really fast. But the signedness of index makes some 
straightforward optimizations very hard to carry out for the compiler. 
(it will probably use bit shifts and logical and, but it has to emit 
something more to cope with (im)possible negative values) Try making 
index unsigned in those cases, it'll probably save some machine 
instructions. (size_t is always your best bet for indexes)