Benchmarks used to test a C and C++ allocator?

Question

Please kindly advise on benchmarks used to test a C and C++ allocator? Benchmarks satisfying any of the following aspects are considered:

1. Speed
2. Fragmentation
3. Concurrency

Thanks!

Answer 1

You can download nedmalloc and try to compare your allocator with it. It has a test called test.c with the source code, which you can rewrite according to your allocator.

Answer 2

If you ask about a general allocator for a C/C++ program then I have found this paper Hoard: A Scalable Memory Allocator for Multithreaded Applications which considers this question. This is a quote from this document

There is as yet no standard suite of benchmarks for evaluating multithreaded allocators. We know of no benchmarks that specifically stress multithreaded performance of server applications like web servers 1 and database managers. We chose benchmarks described in other papers and otherwise published (the Larson benchmark from Larson and Krishnan [22] and the shbench benchmark from MicroQuill, Inc. [26]), two multithreaded applications which include benchmarks (BEMengine [7] and barnes-hut [1, 2]), and wrote some microbenchmarks of our own to stress different aspects of memory allocation performance (threadtest, active-false, passive-false).

This paper is sort of old. However I have seen recently an allocator for HP-UX (MallocNextGen) and HP also can't ensure that it is good for all possible applications. It says:

The new allocator is generally expected to improve the performance of applications. However, there may be some applications for which performance may degrade. Hence users are advised to benchmark their applications with the default memory allocator in libc and with the allocator in libmallocng before using the new allocator in a production environment.

As for speed and concurrency my own experience is that you have to measure performance of your own program in order to compare two different allocators. If we talk about Linux you can use LD_PRELOAD in order to load different allocators.

Answer 3

I tested several allocators myself a few years ago and my experience is that the results all depend on the kind of test. If you want to write some benchmarks yourself, consider the following situations:

• allocate lots of memory of a single size, then free it all
• allocate lots of memory of different sizes, then free it all
• allocate only a few blocks of memory, free them, and repeat this loop several times (repeat for same-sized blocks and different-sized blocks)
• allocate lots of memory of different sizes, free half of it (e.g. the even allocations), then allocate and free memory in a loop
• use two threads to allocate memory in parallel
• use three, four, five, ... threads to allocate memory in parallel

You will notice that the results will be different for every test. Allocators that are very good in one situation, may be bad in other situations.

In practice this means that it's best to test it in your application, in a live/realistic situation.