News for hackers. Stuff that matters.
Re:What Cannot Be Skipped About the Skiplist: A Survey of Sk... by _benedict on Sunday March 10, 2024 @06:14AM (#39658040)
Garbage collectors are really nice for concurrent data structures, making lock-free algorithms very practical. Java's skip list does not require any locks for write, and requires essentially no synchronisation at all for reads (just suitable platform-dependent memory barriers). I believe reads are also wait free.

There is a locality penalty for lookups, although I don't think this is core to skip-lists, just an impracticality of the Java language and how you can use its standard libraries. The variable size of the nodes is not a problem for the Java heap, due to how compacting garbage collectors work.

There are no comments on this comment yet.