Implementation and Optimization of Generic Skip List in Go (stl4go)

This article introduces stl4go, a generic container and algorithm library for Go 1.18, implemented similar to C++ STL. The author, a Tencent backend engineer, chose skip list instead of red-black tree for ordered Map implementation and optimized it to achieve top performance on GitHub.

Background: Over the past year, approximately 70% of the author's business systems were implemented in Go. After reviewing extensive Go code and researching existing solutions, the author found that most generic libraries similar to C++ STL were either weak or didn't support generics at all. This motivated the creation of stl4go.

What is Skip List: Skip list is a randomized data structure proposed by William Pugh in the paper "Skip lists: a probabilistic alternative to balanced trees". It stores elements in hierarchical linked lists with ordered arrangement, achieving O(log N) expected time complexity for search, deletion, and insertion operations - comparable to balanced trees. The implementation is much simpler than balanced trees, with core functionality implementable in under 200 lines.

Interface Design: The library provides creation functions for both comparable types (using < and == operators) and custom types with comparison functions. Key methods include: IsEmpty(), Len(), Clear(), Has(), Find(), Insert(), and Remove().

Node Definition: Instead of creating separate index nodes for each level, the implementation uses an array of next pointers within each element's node, reducing storage overhead and improving performance.

Algorithm Optimizations:

Random Level Generation: Replaced the coin-flipping approach with a more efficient method using math/bits.Len64() to calculate the minimum bits required, converting variable loop iterations into fixed overhead.

Adaptive Level: Instead of using a fixed maxLevel, the implementation dynamically adjusts based on the number of elements. When inserting, if a higher level appears, the level is increased; when deleting, if the top level becomes empty, the level is decreased.

Insert/Delete Optimization: Added early return optimization - when inserting a key that already exists or deleting a key that doesn't exist, the function returns immediately without searching all levels.

Type-Specific Optimization: Used interface-based implementation to provide different code paths for Ordered keys vs custom comparison functions, avoiding function pointer overhead.

Memory Allocation Optimizations:

Cache Prevs Nodes: Pre-allocated a slice at the SkipList instance level for storing previous nodes, avoiding repeated slice creation.

Node Allocation Optimization: Instead of using fixed maximum depth or dynamic allocation, defined different struct types for each depth level, embedding the nexts array directly in the struct to reduce memory allocations and improve cache locality.

Benchmark Results: The implementation was benchmarked against other Go skip list implementations and even a C++ implementation. The Go implementation achieved performance very close to C++, with some operations (like Delete) even faster due to Go's GC handling memory deallocation differently than C++'s explicit destruction.