Home‎ > ‎Parallel Computing‎ > ‎Concurrent Skip List‎ > ‎

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

Comments