malloc() not the one-size-fits-all allocator

malloc() is extremely convenient because it is generic. It does not make any assumptions about the context of the allocation and the deallocation. Such allocators may just follow each other, or be separated by a whole job execution. They may take place in the same thread, or not… Since it is generic, each allocation is different from each other, meaning that long term allocations share the same pool as short term ones.

Consequently, the implementation of malloc() is complex Since memory can be shared by several threads, the pool must be shared and locking is required. Since modern hardware has more and more physical threads, locking the pool at every single allocation would have disastrous impacts on performance. Therefore, modern malloc() implementations have thread-local caches and will lock the main pool only if the caches get too small or too large. A side effect is that some memory gets stuck in thread-local caches and is not easily accessible from other threads.

Since chunks of memory can get stuck at different locations (within thread-local caches, in the global pool, or just simply allocated by the process), the heap gets fragmented. It becomes hard to release unused memory to the kernel, and it becomes highly probable that two successive allocations will return chunk of memories that are far from each other, generating random accesses to the heap. As we have seen in the previous article, random access is far from being the optimal solution for accessing memory.

As a consequence, it is sometimes necessary to have specialized allocators with predictable behavior. At Intersec, we have several of them to use in various situations. In some specific use cases we increase performance by several orders of magnitude.

Benchmarks

In order to provide some comparison points, we ran a small synthetic benchmark. This benchmark tests the performance of malloc() and free() in two scenarios. The first scenario is simple: we allocate a 100 million pointers and then we free them all. The allocator’s raw performance is tested in a single-threaded environment for small allocations.

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <sys/time.h>

struct list {
    struct list *next;
};

static int64_t timeval_diffmsec(const struct timeval *tv2,
                                const struct timeval *tv1)
{
    int64_t delta = tv2->tv_sec - tv1->tv_sec;

    return delta * 1000 + (tv2->tv_usec - tv1->tv_usec) / 1000;
}

int main(int argc, char *argv[])
{
    for (int k = 0; k < 3; k++) {
        struct timeval start;
        struct timeval end;
        struct list *head = NULL;
        struct list *tail = NULL;

        /* Allocation */
        gettimeofday(&start, NULL);
        head = tail = malloc(sizeof(struct list));
        for (int i = 0; i < 100000000; i++) {
            tail->next = malloc(sizeof(struct list));
            tail = tail->next;
        }
        tail->next = NULL;
        gettimeofday(&end, NULL);

        printf("100,000,000 allocations in %ldms (%ld/s)\n",
               timeval_diffmsec(&end, &start),
               100000000UL * 1000 / timeval_diffmsec(&end, &start));

        /* Deallocation */
        gettimeofday(&start, NULL);
        while (head) {
            struct list *cur = head;

            head = head->next;
            free(cur);
        }
        gettimeofday(&end, NULL);
        printf("100,000,000 deallocations in %ldms (%ld/s)\n",
               timeval_diffmsec(&end, &start),
               100000000UL * 1000 / timeval_diffmsec(&end, &start));
    }

    return 0;
}

The second scenario adds multithreading: after allocating all our pointers, we start freeing them in another thread while allocating new batches of pointers in the main thread. As a consequence, allocation and deallocation are run concurrently in two different threads, creating contention on the allocation pool.

The benchmark was run three times: once with the ptmalloc (glibc‘s implementation), another with tcmalloc (Google’s implementation), and finally with jemalloc (Linux port of FreeBSD implementation).

Indeed, the results depend vastly on the implementation of malloc(). While, on a non-contended environment, the ptmalloc shows slightly better performances than tcmalloc (at the cost of a much larger memory footprint), tcmalloc behaves much better in a multithreaded environment.

One allocation batch contains 100M 8-byte pointers, this means it allocates 800MB (762MiB). As a consequence, in the single threaded case, the payload is 762MiB. As we can see tcmalloc is near-optimal in terms of memory consumption. However, one odd thing about tcmalloc is that deallocation is slower than allocation: the deallocation thread is not able to free memory as fast as it is allocated, causing an ever growing memory footprint if we increase the number of threads run in the benchmark.

The benchmark is synthetic and stresses only the small-chunk allocator in an extremely specific use-case. Thus, it should not be considered as an absolute proof that tcmalloc is faster in multithreaded environment while ptmalloc is faster in single threaded ones. However, the benchmark shows that there is no perfect malloc() implementation and that choosing the right implementation for your use case may have huge impacts on overall performance.

Last, but not least, this benchmark shows that you can perform only a few millions of allocations/deallocations per second. This may seem quite large, but as soon as you want to process several hundreds of thousands of events per second, and if each event triggers one or more allocations, then malloc() will start being a bottleneck.

Stack allocator

The first (and certainly the most used) custom allocator at Intersec is the stack allocator. This is a LIFO allocator, meaning that allocations are deallocated in the reverse order of their allocation. It mimics the behavior of the program’s stack since allocations are grouped in frames, and frames are deallocated at once.

Internals

The stack allocator is an arena-based allocator. It allocates huge blocks and then splits them into smaller chunks.

It keeps track of two key pieces of information about each block:

• the bottom of the stack
• the delimitation of the frames

When an allocation is performed, the bottom of the stack is incremented by the size of the requested memory (plus the alignment requirements and the size of the canaries). If the requested size cannot fit in the current block, a new one is allocated: the allocator will not try to fill the gap left in the previous block.

When a frame is created, a mark is pushed at the bottom of the stack with the position of the beginning of the previous frame. The allocator always knows the position of the beginning of the current frame. That way, removing a frame is extremely fast: the allocator sets the bottom of the stack back to the current frame’s position, then it reloads the previous frame’s position and makes it its current. Additionally, the allocator will list the blocks that were totally freed by the operation and deallocate them.

">↩]