-
Notifications
You must be signed in to change notification settings - Fork 46
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Implement the tree-bin optimization #13
Comments
I've been looking through the Java code to get a feel for this. Some things I noticed:
|
I think adding a requirement that As for storing thread referenced and parking/unparking threads, that should work just fine with |
Thanks for the suggestions concerning the thread lock! Having an ordered key type would certainly be helpful. If we require |
I don't know that we actually have a tie-breaker in Rust if we don't require For |
I agree, as indicated, but I think it was worth discussing. I'll probably not get to work on any implementation in this or the coming week, so if anyone comes across this and wants to start implementing |
Alright, I'm back! It seems no one worked on this so far, so I started with the implementation. I'll report back when I have something working. So far I implemented the tree nodes themselves and the red-black tree methods. After insertion/deletion of tree nodes I should at least be able to construct some Also, I'm currently on 111 |
As I'm working through this, I think there might be a problem with implementing the additional locking mechanism. The Java code for finding a node (reading a value) uses the approach of following the tree pointers ( What is tricky with this is that all of these pointers are accessed via the same node. So a writing thread might |
Yeah, you certainly can't give out a |
It may be best to stick to that. The I know |
@domenicquirl I would use |
Any operation that takes the additional Edit: an example of this behaviour in the Java code can be seen here: flurry/jsr166/src/ConcurrentHashMap.java Lines 2937 to 2942 in 3bf0c4f
|
I think that's just in case of exceptions, which would be equivalent to panics in Rust. They already drop on unwind, so I don't think you need the equivalent of that in the Rust code? |
I'm not sure. The Java code has no explicit Exceptions, or ones that would be obviously caused by anything. It's just pointer swaps. Maybe they're just extra careful, I wouldn't know where their exceptions would come from. I've left it out for now, but wanted to double check. |
A small update on this: I'm back from my holiday and finished porting the code. I crashed some tests, but when working through the resulting errors I could verify that TreeBin cases are being hit. I still need to add some info about TreeBins to the global documentation, then this should be ready for review. With the TreeBin code added, clippy now complains about cognitive complexity in some functions. For the time being, I just I also ran our benchmarks against the new code, more so as a more heavy-weight test than for the actual numbers. Nevertheless, the rough direction for performance seems very nice for insert, where the improvement scales visibly with the number of threads. Iterator related benches also went up significantly, |
Bumps [actions/checkout](https://github.com/actions/checkout) from 3 to 4. - [Release notes](https://github.com/actions/checkout/releases) - [Changelog](https://github.com/actions/checkout/blob/main/CHANGELOG.md) - [Commits](actions/checkout@v3...v4) --- updated-dependencies: - dependency-name: actions/checkout dependency-type: direct:production update-type: version-update:semver-major ... Signed-off-by: dependabot[bot] <support@github.com> Co-authored-by: dependabot[bot] <49699333+dependabot[bot]@users.noreply.github.com>
The Java code modified large bins to be trees instead of lists. We should do the same. See the
TreeNode
optimization and the implementation notes on that optimization for much more detail.The text was updated successfully, but these errors were encountered: