I wrote something fun during my week off: a concurrent map & set. https://gitlab.com/boats/skiplist/tree/master …
-
Show this thread
-
Rust doesn't have any lock-free maps because of the difficulty of implementing them without garbage collection. Turns out, that difficulty comes from the remove operation
3 replies 1 retweet 7 likesShow this thread -
Replying to @withoutboats
I and
@ecbos_ spent like a day trying to design the perfect lock free hashtable (tailored to some extra needs we had). Too bad we never implemented it (didn't end up needing it)1 reply 0 retweets 0 likes -
Replying to @ManishEarth @withoutboats
Yeah, we had nice requirements, like being able to GC it on a single thread and such, which helps :)
1 reply 0 retweets 1 like -
Can I read somewhere more about this? I'd be curious what were the requirements exactly.
1 reply 0 retweets 0 likes -
It was while implementing this: https://github.com/servo/servo/blob/master/components/style/rule_tree/mod.rs … Basically you have a simple tree of nodes representing rules you populate and read from multiple threads. ensure_child and reads happen in parallel, gc can happen on the main thread, once the thread pool is done styling.
1 reply 0 retweets 2 likes
So if I got this right, this is a lock-free singly-linked list used as a map keyed by (level, source), and you wanted to turn it into a hash table to speed up lookup/insert? And presumably you didn't need it because the lists are reasonably short anyways (now I'm just guessing)?
-
-
Yep. Gecko switches to a hashmap when it gets over 30 elements or something but that's reasonably rare anyway. Common case is one or two children
0 replies 0 retweets 1 likeThanks. Twitter will use this to make your timeline better. UndoUndo
-
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.