Hi,
Yuya Watari presented a series of patches, with the objective of improving the Bitmapset [1].
After reading through the patches, I saw a lot of good ideas and thought I'd help.
Unfortunately, my suggestions were not well received.
Even so, I decided to work on these patches and see what could be improved.
Eventually it arrived at the attached patch, which I'm naming v7, because of the sequence it had established.
Those who follow the other thread will see that the original patch actually improves the overall performance of Bitmapset,
but I believe there is room for further improvement.
I ran the same tests provided by Yuya Watari and the results are attached.
Both on Windows and Linux Ubuntu, the performance of v7 outperforms head and v4.
At Ubuntu 64 bits:
v7 outperforms v4 by 29% (Query A)
v7 outperforms v4 by 19% (Query B)
At Windows 64 bits:
v7 outperforms v4 by 22% (Query A)
v7 outperforms v4 by 33% (Query B)
I believe patch v7 leaves the Bitmapset in good shape and readable, well written.
Questions arose regarding possible regression when using the backward loop, but in all the tests I ran this version with backward performed better.
Possibly because of the smaller number of variables and the efficient test (--i <= 0), which both the msvc and gcc compilers successfully optimize.
If the v7 version with loop forward performs worse on x86_64 cpus,
I don't see how it will perform better on other architectures, since the vast majority of modern ones and with great cache support.
Another question is related to an alleged "spurius test", whose objective is to avoid test and set instructions for each element of the array.
Again I ran the tests without the test and the performance was worse, showing its value.
regards,
Ranier Vilela