There are two problems with memory allocation in the skip list. First is concurrency – a lot of allocation requests from a plurality of threads must proceed in parallel. Second problem is memory consumption – the skip list in intended to consume gigabytes of memory, so it must consume memory optimally. In order to satisfy both requirements I used a per-thread slab allocators. Each thread has it's own private cache of nodes for each level (i.e. with a given number of 'next' pointers), so allocation is very fast, scalable and uses memory optimally (no 'technological' gaps between nodes). Here is a fast-path of the node allocation algorithm: The alloc_node_slow() function refills the cache for a given level, and recursively calls alloc_node() (which must succeed this time). Move on to Parallelization - Problem Analysis |