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:
node_t* alloc_node(thread_t* thr, size_t level, item_t item)
{
void* mem = thr->cache[level];
if (mem)
{
thr->cache[level] = *(void**)mem;
node_t* node = new (mem) node_t (item);
return node;
}
return alloc_node_slow(thr, level, item);
}
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