search

vorner / contrie

Concurrent hash trie
Apache License 2.0
51 stars 3 forks source link

Using lock-free linked lists instead of arrays for collisions #11

Open vorner opened 5 years ago

vorner commented 5 years ago

Currently, the end data node is an array (well, SmallVec). It usually contains only a single element. In case we have a collision on the whole length of 64bit hash, we have more elements.

In case we add or remove items from the colliding data node, we make a brand new copy of the array and clone the relevant elements there. This is not elegant. Furthermore, it requires the Config::Payload: Clone bound. If we got rid of that bound, a user with very special needs could use the Raw directly with types that are not Clone, but are not inside an Arc either and get just references into the data structure (by providing their own crossbeam_epoch::Guard).

To accomplish that we can replace the data nodes with (singly) linked lock-free lists. They should be relatively easy to implement (note that we need to be able to delete from the middle as well, not only pop ‒ watch out for race conditions on deleting two consecutive elements).

:question: Is there a linked list we could just reuse lying around somewhere? :question: If we decide to implement our own list, should it go into a separate crate or should it live in this one, in a separate module? :question: Is the feature (of supporting non-Clone types as Raw's payload) worth the added work and complexity?

terrarier2111 commented 1 year ago

What you need is not really a singly linked list but a lock-free doubly linked list because of the remove-from-the-middle requirement, i started implementing such a doubly linked list based on a paper, but it is in no way fully functional, there are still a lot of bugs. https://github.com/terrarier2111/Miri-weirdness/blob/master/src/doubly_linked_list.rs

vorner commented 1 year ago

I'd say this repo is mostly dormant, because it turned out this implementation is not really performant (it consumes a lot of RAM and is slow because of jumping a lot of pointers). I don't think introducing linked lists in there would improve things 😇

But if you want to play around with it for something like study / hobby, I think it might be a nice opportunity (actually, that was my motivation about the repo anyway).