I wrote something fun during my week off: a concurrent map & set. https://gitlab.com/boats/skiplist/tree/master …
-
Show this thread
-
Replying to @withoutboats
If your skiplist is insert-only, I'd suggest following RocksDB's implementation instead: https://is.gd/W9RdrP It should be noticeably faster since it uses no locking (meaning fewer atomic operations and fewer cache invalidations).
2 replies 0 retweets 4 likes -
Replying to @stjepang
"Writes require external synchronization, most likely a mutex." - seems strictly worse? (reads also don't require locks in this implementation)
1 reply 0 retweets 0 likes -
Replying to @withoutboats @stjepang
ah nvm they use the word 'write' differently from how I would
1 reply 0 retweets 0 likes -
Replying to @withoutboats @stjepang
I'm not great at reading C++, but I don't see how they perform unsynchronized insertions?
1 reply 0 retweets 0 likes -
Replying to @withoutboats
Actually, I think you're right about writes requiring a mutex. That's a bummer. :( But, it's fairly easy to implement truly lock-free inserts. It goes like this:
1 reply 0 retweets 0 likes -
Replying to @stjepang @withoutboats
1/4) Do a search to identify the 'hole' into which the new node will fall. The search operation returns two arrays `preds[]` and `succs[]`. These will be the predecessors and successors of the new node.
1 reply 0 retweets 1 like -
Replying to @stjepang @withoutboats
2/4) Perform a CAS operation at the lowest level to install the new node into the skiplist: new.tower[0].store(succs[0]); preds[0].tower[0].compare_and_set(succs[0], new);
1 reply 0 retweets 1 like -
Replying to @stjepang @withoutboats
3/4) If the CAS failed, go back to step 1. Otherwise, the new node is now a part of the skiplist. All that remains is to build the rest of the tower, i.e. initialize pointers `new.tower[1 .. new.height]`.
1 reply 0 retweets 1 like -
Replying to @stjepang @withoutboats
Note that once a node is installed into the lowest level (level 0), it's inserted. Building the rest of the tower is completely optional - it's just an optimization to make skiplist operations O(log n) rather than O(n).
1 reply 0 retweets 1 like
4/4) To build level `i`, do this: new.tower[i].store(succs[i]); preds[i].tower[i].compare_and_set(succs[i], new); If the CAS at level `i` fails, simply repeat the search to refresh lists `preds[]` and `succs[]` and try building this level again.
-
-
Replying to @stjepang
Interesting, seems legit but I'm going to think about it more.
0 replies 0 retweets 1 likeThanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
Replying to @stjepang @withoutboats
It looks like your code is already very close to that - so it's just a matter of getting rid of locking/unlocking and using a few CAS operations instead. :)
0 replies 0 retweets 0 likesThanks. 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.