saturn icon indicating copy to clipboard operation
saturn copied to clipboard

Optimized `Skiplist` with unboxed `Atomic_array`

Open polytypic opened this issue 1 year ago • 0 comments

For background, see PR in multicore-magic.

This seems to give up to 40%-70% performance improvement in some cases and seems to generally improve performance. The reason for the speed up is obvious: 3x less words per a link in a node and 1 less indirection. This means things will better fit into caches and there will be less stalls waiting for memory.

It is interesting to note that despite having only a fenceless_get and not having an "atomic" get, this seems to pass the QCheck STM test. I assume this is due to the use of the linearizable size. All add and remove operations update the linearizable size, which means they will be linearizable. Read-only operations also potentially update the linearizable size. It seems that is enough to keep the data structure linearizable even when reads from the atomic arrays are relaxed reads rather than sequentially consistent reads.

TODO:

  • [x] Update dscheck test to work with Atomic_array — this happened automatically after the switch to use multicore-magic-dscheck
  • [ ] Consider implementing resizing

polytypic avatar May 26 '24 00:05 polytypic