Map B=6 support. #65
Map B=6 support. #65
Conversation
| using bitmap_t = std::uint32_t; | ||
| using count_t = std::uint32_t; | ||
| using shift_t = std::uint32_t; | ||
| }; |
There was a problem hiding this comment.
Hi @fedormatantsev!
One thing that is important: only bitmap_t depends on B! The other types should remain outside of this types template. In this way, you can also keep the bits_t type, which you have removed. Also in that way you need to change way less things overall in the code. There are very few mentions to bitmap_t in the code, which is the only type dependent on B.
There was a problem hiding this comment.
Yeah, sounds reasonable.
immer/detail/hamts/bits.hpp
Outdated
| #endif | ||
| } | ||
|
|
||
| inline count_t<6> popcount(bitmap_t<6> x) |
There was a problem hiding this comment.
Instead of overloading popcount for different bitmap_t<X>, I would suggest defining the overloads in terms of the underlying representation types. This is, to provide functions:
std::uint32_t popcount(std::uint32_t x);
std::uint64_t popcount(std::uint64_t x);
...
There was a problem hiding this comment.
Otherwise you are unnecesarily coupling a general function (popcount) to implementation details of hamts (the notion of bitmap). Does this make sense?
There was a problem hiding this comment.
Good suggestion, thanks!
immer/detail/hamts/bits.hpp
Outdated
| # else | ||
| return __builtin_popcount(x); | ||
| # endif | ||
| #else | ||
| // More alternatives: | ||
| // https://en.wikipedia.org/wiki/Hamming_weight | ||
| // http://wm.ite.pl/articles/sse-popcount.html | ||
| // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel | ||
| x = x - ((x >> 1) & 0x55555555); | ||
| x = (x & 0x33333333) + ((x >> 2) & 0x33333333); | ||
| return ((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; |
There was a problem hiding this comment.
Be careful, this fallback only works for 32 bits, not for any size of bitmap!
There was a problem hiding this comment.
Ah, I will adjust constants based on wiki page
https://en.wikipedia.org/wiki/Hamming_weight
int popcount64c(uint64_t x)
{
x -= (x >> 1) & m1; //put count of each 2 bits into those 2 bits
x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
x = (x + (x >> 4)) & m4; //put count of each 8 bits into those 8 bits
return (x * h01) >> 56; //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...
}
Codecov Report
@@ Coverage Diff @@
## master #65 +/- ##
==========================================
+ Coverage 94.45% 94.49% +0.04%
==========================================
Files 84 84
Lines 6901 6902 +1
==========================================
+ Hits 6518 6522 +4
+ Misses 383 380 -3
Continue to review full report at Codecov.
|
|
At this point I'd like to discuss a special test to check if two values are not colliding when their hash differs only in the last 32 bits. I basically have no idea how to make it, but it actually makes sense to me since tests shouldn't fail even without my changes... I think it requires some kind of introspection for internal data structure |
|
Hmmm, I don't think that a test needs to instrospect the internal data-structure. I prefer tests that only use the observable interface. There are already tests that generate collisions by overriding the hash function passed. I think it is ok to just reuse the same test-suite and use it for different B's. The tests are already generic, you can look at Once again, thanks for doing this work! |
|
I already did B6 tests for map/set =) But the point is not to check if values with hash collision work, but, on the contrary, values with different hashes don't collide I agree test shouldn't know too much about internals |
|
Nice! This is starting to look very good. It looks to me like it is almost ready, right? There are a couple of suggestions that I still have. The first one is more stylistic: can you define an alias to the right The other thing that I don't like a lot is the |
|
Yeah, I think it's ready to be merged. Feel free to squash&merge the PR whenever you think it's OK. |
|
This is looking great! I am happy to merge if you want, but I can also wait if you have some other changes in mind. One potential line improvement would be to use 16bit bitmaps for B=4 and 8bit bitmaps for B=3, but it is not a condition for merge. Great work! |
|
I think I'd like to implement your suggestion in scope of another weekend-PR. We can file an issue and assign it to me so I'll not forget to do it. Let's wait for tests to complete and merge it! |
|
Done, thanks a lot! |
|
Cool, thanks! |
I still have to refine the implementation, but the idea is clear.
I have some issues with building tests, will continue tomorrow.
Looking forward for the review :)