Memory Allocation

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