3 ms·

Skip lists in practice are faster than balanced binary trees in insertion, since rebalancing is slow, while insert and delete in a sl are very fast (if you have

Skip lists in practice are faster than balanced binary trees in insertion, since rebalancing is slow, while insert and delete in a sl are very fast (if you have a fast source of random or pseudorandom numbers). Skip list insertion is also very easily to parallelize. Insert on a bbt requires locking basically the whole tree.

thesz 4y ago
If you can turn your keys into byte/bit sequences, and most of the time you can, you can use crit bit trees or binary Patricia trees. These are fast structures and support ordered traversal. They also do not rebalance and do not require locking the whole tree. Skip lists are built upon double linked lists, many of them. Parallelizing operations on double linked lists is not easy, it is quite easy to introduce potential deadlock.
- Tyr42 4y ago
  Looks like singlely linked lists in the linked article.
  - thesz 4y ago
    Double linked lists would help navigate quicker. But let's discuss why even skip list on even single linked lists is not that easy. The problem with double-linked lists modified in parallel is that one should lock at least two places where changes are performed. When you lock two things, you need an order between them on which to lock first. Otherwise, it is possible to introduce deadlocks - first actor needs A and B and locks A, second actor needs A and B and locks B. Crucial part here is the need to lock more than one object. If I understand skip lists correctly, it is possible to insert element into several lists at once. Thus, the need to work on more than one element. Thus, the possibility of deadlock that needs to be accounted for.
- dragonwriter 4y ago
  > Skip lists are built upon double linked lists, I've always seen them with singly-linked lists; double doesn't give an average or worst-case order improvement to anything, but it does make some ops faster within the same complexity class.
  - thesz 4y ago
    Okay, skip lists are built upon singly-linked lists, but there are still need to lock more than one object to modify. The need to lock multiply objects at once is the potential source of deadlocks.

thesz 4y ago

If you can turn your keys into byte/bit sequences, and most of the time you can, you can use crit bit trees or binary Patricia trees. These are fast structures and support ordered traversal. They also do not rebalance and do not require locking the whole tree. Skip lists are built upon double linked lists, many of them. Parallelizing operations on double linked lists is not easy, it is quite easy to introduce potential deadlock.

Tyr42 4y ago
Looks like singlely linked lists in the linked article.
- thesz 4y ago
  Double linked lists would help navigate quicker. But let's discuss why even skip list on even single linked lists is not that easy. The problem with double-linked lists modified in parallel is that one should lock at least two places where changes are performed. When you lock two things, you need an order between them on which to lock first. Otherwise, it is possible to introduce deadlocks - first actor needs A and B and locks A, second actor needs A and B and locks B. Crucial part here is the need to lock more than one object. If I understand skip lists correctly, it is possible to insert element into several lists at once. Thus, the need to work on more than one element. Thus, the possibility of deadlock that needs to be accounted for.
dragonwriter 4y ago
> Skip lists are built upon double linked lists, I've always seen them with singly-linked lists; double doesn't give an average or worst-case order improvement to anything, but it does make some ops faster within the same complexity class.
- thesz 4y ago
  Okay, skip lists are built upon singly-linked lists, but there are still need to lock more than one object to modify. The need to lock multiply objects at once is the potential source of deadlocks.