search

amethyst / hibitset

Hierarchical bit set container
Other
118 stars 33 forks source link

Added parallel iterator. From slide-rs/specs#120 #4

Closed WaDelma closed 7 years ago

WaDelma commented 7 years ago

Should propably add benchmarks for it.

slide-rs/specs#120

torkleyy commented 7 years ago

I guess you did not git add the new file. Also, we might also just have a par_iter file to keep the file tree flat.

WaDelma commented 7 years ago

Which file is missing? I don't see it. Tests seem to fail to stack overflow...

The BitParIter needs access to BitIter private fields, so it cannot be flattened (without pub(restrict)).

torkleyy commented 7 years ago

Now it's there! Hm, seems the recursion is too deep / does not end?

WaDelma commented 7 years ago

I cannot reproduce it locally and can't tell from the output which test overflowed.

WaDelma commented 7 years ago

I do no recursion on my end, so the recursion is happening in rayon I think. I have debug it more deeply, but my first guess is that I am splitting too many times (or infinitely).

I also realized yesterday that I am using 32bit rust on my computer (I tried to install 64bit version, but trying to rustup run cargo test with that toolchain results into infinite recursion‽), so that's probably the difference between travis and local test.

WaDelma commented 7 years ago

I was able to test it with 64bit rust and couldn't reproduce stack overflow with it either... I even tried test where I fill whole bitset with ones and it still didn't overflow.

So I have no clue what is wrong and now it goes through travis too.

kvark commented 7 years ago

Well, this is unsettling. I'll try to make a close look at the logic then to spot a potential error. Edit: Also, thank you for addressing my comments! I know it's not the easiest PR ever. Given that the crate is rather fundamental and low level, we can't take much risks.

WaDelma commented 7 years ago

Well I don't expect this getting merged anytime soon: When I started it I had no clue how it would work and I am not 100% confident it's correct now.

WaDelma commented 7 years ago

Welp... I started to add those asserts you wanted and I actually realised that there is huge oversight: When there is only one bit left descending to the next layer doesn't actually work as the lower levels mask is never set to anything but 0. This means that it couldn't actually split more finely than for the highest level.

When I fixed that I ran into more problems. One of them is that the avarage is rounded down which meant that sometimes it thought that it could split, but splitting actually didn't change anything and there was infinite recursion. After that it still runs to problem that I haven't yet debugged.

I should really look into making the tests better. Biggest problem with them is that it uses the machinary of the normal iterator which masks these kinds of problems as the iteration is still correct, but not split enough.

This PR and the one in specs has turned into quite an adventure :D

torkleyy commented 7 years ago

@WaDelma IIRC the logic should work now? Would you please rebase onto the latest master?

WaDelma commented 7 years ago

AFAIK it should work correctly now. I rebased it.

torkleyy commented 7 years ago

@WaDelma Great, thanks! I couldn't spot any stylistic or doc issues, and I'd rather delegate reviewing the logic to @kvark

Really amazing work here!

kvark commented 7 years ago

@torkleyy I somewhat reviewed it once more. It would be best to have @csherratt glancing at the code. If they don't make it, we can merge and then fix post-release, given that the API will not change. After all, this is an extra feature, not a change in existing logic.

csherratt commented 7 years ago

This is seriously cool. I don't see anything I object to in the implementation.

But I would ask that we add a few more targeted tests. All of the tests will tend to fill the tree and maybe leave some empty spaces, even the random number one has no guarantee of this. It would be good to see entire leafs that were empty to make sure there isn't some ugly edge case we overlooked.

Something like this: https://play.rust-lang.org/?gist=387d26b94a6b3cddcd2eb4ff085a4d7e&version=stable&backtrace=0

That should generate clusters of keys that don't completely fill the l3/l2 nodes.

kvark commented 7 years ago

@csherratt thanks for expertise! I hope you'll join us on Gitter, like the olde good times ;)

WaDelma commented 7 years ago

Added the clustered test. Any other ideas for tests?

kvark commented 7 years ago

Thanks @WaDelma !