4 ms·
Skip list is essentially a hierarchy of linked lists. It is very hard to make a doubly linked list work concurrently without using locks. One would have to upda
by tintor 14y ago
Skip list is essentially a hierarchy of linked lists. It is very hard to make a doubly linked list work concurrently without using locks. One would have to update two pointers atomically in order to insert a new element in a doubly linked list.
- Nitramp 14y agoYou could probably pull that off if you implement it like full text search indices in e.g. Lucene. Have every modification create a "diff" skip list that takes precedence over older skip lists, and then have a merge operation that runs asynchronously (and will either have to lock, or copy the entire data structure and switch it in atomically). That's also essentially how Bigtable's disk format works.
- dhruvbird 14y agoActually, there are papers about it http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.4693 http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.140.4... but I don't know much about the implementation complexity since I've never implemented one.
- bcoates 14y agoThat shouldn't be any harder than updating one pointer atomically, modern x64s have two-pointer sized atomic exchange operations.
- tintor 14y agoModern x64s have 128-bit CAS instruction, but the problem is that those two pointers can be far apart in memory, in two different elements of the list.