Survey of Skip List Implementations

Here is a brief summary of skip list packages available in Go that you may consider using after a quick Google/Github search. If you know of any others, please contact me so I can add them here.

Some things most of the packages have in common:

• Keys are int type, which are 32 or 64 bit depending on GOARCH
• Values are generally of type interface {}, so they accept any datatype (Go does not have generics).
• The probability of adding new nodes to each linked level is P. The values vary from 0.25 to 0.5. This is an important parameter for performance tuning and memory usage.

Here are some brief notes on each implementation:

• github.com/mtchavez/skiplist
  • Values are type []byte, which almost always means conversion.
  • Global constant for P value = 0.25, cannot be changed at runtime.
• github.com/huandu/skiplist
  • Globally sets P to almost 0.25 (using bitmasks and shifting) and can be changed at runtime.
  • You must specify a comparator and type for keys when creating the list.
  • Keys are of type interface{}
  • Not threadsafe
• github.com/zhenjl/skiplist
  • Adjustable P value and max level per list.
  • Adjustable insert level probability per list.
  • Allows duplicates stored at a single key and therefore does not have an update operation.
  • When creating a list, you specify a comparator. It has many built-in that are generated by running an external script that writes out a Go source file with the interfaces.
  • Uses separate search and insert fingers to speed up finding highly local keys consecutively.
  • Threadsafe but fingers are shared as well across all lists
• github.com/golang-collections/go-datastructures/slice/skip
  • Intelligently sets maximum level based on key's datatype (uint8 up to uint64)
  • More complex interface; you must define an Entry type that implements the interface it specifies with a comparator
  • P value is a global constant, 0.5
• github.com/ryszard/goskiplist
  • P value is a global constant, 0.25
  • Very straightforward implementation and interface
  • Not threadsafe
• github.com/sean-public/fast-skiplist
  • Fastest concurrent implementation in all benchmarks; huandu is very close in every benchmark but it is not threadsafe.
  • See fast-skiplist's README for details on how this is achieved.

Benchmarks

Running the benchmarks found in this repo locally is easy:

Inserts

https://raw.githack.com/benz9527/skiplist-survey/master/bench/inserts.html

Worst Insert

https://raw.githack.com/benz9527/skiplist-survey/master/bench/worst-inserts.html

Delete

https://raw.githack.com/benz9527/skiplist-survey/master/bench/deletes.html

Worst Delete

https://raw.githack.com/benz9527/skiplist-survey/master/bench/worst-deletes.html

Average Search

https://raw.githack.com/benz9527/skiplist-survey/master/bench/avg-search.html

Search End

https://raw.githack.com/benz9527/skiplist-survey/master/bench/search-end.html