Fast lock-free stack and flex-array. #5
Merged
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
… on the contents being pointers, you only need 64 bits per bucket, but we don't make that assumption here. Also note that this does not have append/pop operations; We will put those into a separate Vector class.
… a classic lock-free linked-list based stack, using MMM instead of an ABA field. The second I believe is lock-free, and ALMOST wait free; the pop operation could theoretically get stuck if it's slow and subject to specific patterns of pushes/pops. It'd be easy to make this fully wait free, but I think the situation is pretty unlikely; I'd like to measure and make sure it's necessary.
…o avoid unneeded compressions.
…plexity for no real performance gain over the simpler alternative. Also, added an example for stacks, which doubles as a performance test bench. Shows excellent results, especially over the traditional linked-list approach, which essentially dies in a fire when there is significant contention for pushers.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
I added a fast stack, that eliminates the head contention one sees with the traditional approach (favoring FAA over CAS). I originally had a complicated in-place compression algorithm to incrementally compress the stack, but it turned out the simpler migration strategy used on the hash tables is better in practice, and simpler.
I will probably still do the little bit of work necessary to make the stack wait-free (at least optionally).
Additionally, I added an initial fast, wait-free flexible array. It does bounds checking and can be resized up or down.
The flexarray does NOT support push and pop the way C++ vectors do. I have an algorithm I need to implement that will allow for that, with the random access being almost as fast as flex array, and the push/pop being possible. When I get to that, it will be called a "vector", not a flexarray.
The two separate constructions will be much faster on their own (especially the stack; there are reasons why the approach for this stack won't work in a vector), but if you need both in one data structure, I'll soon have you covered.