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)
