How efficient is malloc and how do implementations differ?

Question

If I use malloc, does malloc always use the same algorithm regardless of what it is allocating or does it look at the data and select an appriopriate algorithm?

Can we make malloc faster or smarter by choosing a more efficient algorithm? In my tests, the builtin official system malloc of Ubuntu is 10 times slower than a school project if my test results are correct. What is the catch? I'm surprised that malloc performed so bad in the tests because it should be optimized. Does it always use the same algorithm? Is there a reference implementation of malloc? If I want to look at the source for malloc , which should I look at? The tests I run are the following:

/* returns an array of arrays of char*, all of which NULL */
char ***alloc_matrix(unsigned rows, unsigned columns) {
    char ***matrix = malloc(rows * sizeof(char **));
    unsigned row = 0;
    unsigned column = 0;
    if (!matrix) abort();

    for (row = 0; row < rows; row++) {
        matrix[row] = calloc(columns, sizeof(char *));
        if (!matrix[row]) abort();
        for (column = 0; column < columns; column++) {
            matrix[row][column] = NULL;
        }
    }
    return matrix;
}

/* deallocates an array of arrays of char*, calling free() on each */
void free_matrix(char ***matrix, unsigned rows, unsigned columns) {
    unsigned row = 0;
    unsigned column = 0;
    for (row = 0; row < rows; row++) {
        for (column = 0; column < columns; column++) {
            /*    printf("column %d row %d\n", column, row);*/
            free(matrix[row][column]);
        }
        free(matrix[row]);
    }
    free(matrix);
}


int main(int agrc, char **argv) {

    int x = 10000;
    char *** matrix = alloc_matrix(x, x);
    free_matrix(matrix, x, x);
    return (0);
}

Is the test alright? I also use this test:

   for (i = 0; i < 1000000; i++) {
        void *p = malloc(1024 * 1024 * 1024);
        free(p);
   }

• update

According to the comment, I should make variably sized chunks and free in different order than allocating, so I try:

int main(int agrc, char **argv) {
     int i;
    srand(time(NULL));
    int randomnumber;
    int size = 1024;
    void *p[size];
    for (i = 0; i < size; i++) {
        randomnumber = rand() % 10;
        p[i] = malloc(1024 * 1024 * randomnumber);
    }

    for (i = size-1; i >= 0; i--) {
        free(p[i]);
    }

    int x = 1024;
    char *** matrix = alloc_matrix(x, x);
    free_matrix(matrix, x, x);
    return (0);
}

Then my custom malloc is no longer faster:

$ time ./gb_quickfit 

real    0m0.154s
user    0m0.008s
sys 0m0.144s
dac@dac-Latitude-E7450:~/ClionProjects/omalloc/openmalloc/overhead$ time ./a.out 

real    0m0.014s
user    0m0.008s
sys 0m0.004s

The algorithm I used was:

void *malloc_quick(size_t nbytes) {

    Header *moreroce(unsigned);
    int index, i;
    index = qindex(nbytes);

    /* 
     * Use another strategy for too large allocations. We want the allocation
     * to be quick, so use malloc_first().
     */

    if (index >= NRQUICKLISTS) {
        return malloc_first(nbytes);
    }

    /* Initialize the quick fit lists if this is the first run. */
    if (first_run) {
        for (i = 0; i < NRQUICKLISTS; ++i) {
            quick_fit_lists[i] = NULL;
        }
        first_run = false;
    }


    /*
     * If the quick fit list pointer is NULL, then there are no free memory
     * blocks present, so we will have to create some before continuing.
     */

    if (quick_fit_lists[index] == NULL) {
        Header* new_quick_fit_list = init_quick_fit_list(index);
        if (new_quick_fit_list == NULL) {
            return NULL;
        } else {
            quick_fit_lists[index] = new_quick_fit_list;
        }
    }

    /*
     * Now that we know there is at least one free quick fit memory block,
     * let's use return that and also update the quick fit list pointer so that
     * it points to the next in the list.
     */

    void* pointer_to_return = (void *)(quick_fit_lists[index] + 1);
    quick_fit_lists[index] = quick_fit_lists[index]->s.ptr;
   /* printf("Time taken %d seconds %d milliseconds", msec/1000, msec%1000);*/
    return pointer_to_return;
}

Answer 1

There are multiple implementations of malloc and they can use very different algorithms. Two very widely used implementations are jemalloc and dlmalloc. In both cases the links have a lot of information about the thought process and trade-offs made in a general purpose allocator.

Bear in mind a malloc implementation has very little information to go on, just the size of the allocation requested. A free implementation only has the pointer and whatever data 'malloc' may have secretly attached to it. As such there ends up being a fair amount of heuristics i.e. inspired guesswork in deciding how to allocate and deallocate.

Some issues that an allocator needs to address are:

1. alignment - some memory alignment are faster than others
2. fragmentation - naive allocation and freeing can leave holes that cause bloat
3. performance - going back to the OS for more memory can be expensive
4. Common requests - in practice applications (especially C++) often do a lot of small allocations so making these efficient can help a lot

Taking all this into account, what you'll find is that the allocators tend to be complex pieces of software so that, in general usage, they perform well. However, in specific cases, it may well be better to manage memory outside the allocator if you happen to know a lot more about the structure of the data. Obviously the downside is that you need to do the work yourself.

Answer 2

If you care only about efficiency, here is a standard conforming and very efficient implementation:

void* malloc(size_t sz) {
  errno = ENOMEM;
  return NULL;
}

void free(void*p) {
  if (p != NULL) abort();
}

I'm pretty sure you won't find any faster malloc.

But while still conforming to the standard, that implementation is useless (it never successfully allocates any heap memory). It is a joke-implementation.

This illustrates that in the real world, malloc & free implementations need to make trade-offs. And various implementations are making various tradeoffs. You'll find many tutorials on malloc implementations. To debug memory leaks in your C programs, you'll want to use valgrind.

Notice that on Linux systems at least, (almost) all C standard libraries are free software, so you can study their source code (in particular the one for malloc & free). musl-libc has some very readable source code.

BTW, the code in your question is wrong (and will crash with my malloc above). Every call to malloc can fail, and you should test that.

You may want to read Advanced Linux Programming and some more general material about operating systems, e.g. Operating Systems: three easy pieces.

You probably should read something about garbage collection, at least to get the main concepts & terminology; perhaps by reading the GC handbook. Notice that reference counting can be viewed as a form of GC (a poor one, which does not handle well reference cycles or cyclic graphs...).

You could want to use in your C program Boehm's conservative garbage collector: you would then use GC_MALLOC (or, for data without pointers like strings or numerical arrays, GC_MALLOC_ATOMIC) instead of malloc and you won't bother about calling free anymore. There are some caveats when using Boehm's GC. You might consider other GC schemes or libraries...

NB: To test failure of malloc on a Linux system (malloc would sometimes call the mmap(2) and/or sbrk(2) system calls on Linux to grow the virtual address space, but most often it tries hard to reuse previously freed memory), you might call setrlimit(2) appropriately with RLIMIT_AS and/or RLIMIT_DATA, often thru the ulimit bash builtin of your terminal shell. Use strace(1) to find out the system calls done by your (or some other) program.

Answer 3

First, malloc and free work together, so testing malloc by itself is misleading. Second, no matter how good they are, they can easily be the dominant cost in any application, and the best solution to that is to call them less. Calling them less is almost always the winning way to fix programs that are malloc-limited. One common way to do this is to recycle used objects. When you're done with a block, rather than free-ing it, you chain it on a used-block stack and re-use it the next time you need one.

Answer 4

The main problem with your malloc_quick() implemenation is, that it is not thread-safe. And yes, if you omit thread-support from your allocator, you can achieve a significant performance gain. I have seen a similar speedup with my own non-thread-safe allocator.

However, a standard implementation needs to be thread-safe. It needs to account for all of the following:

• Different threads use malloc() and free() concurrently. That means, that the implementation cannot access global state without internal synchronization.

  Since locks are really expensive, typical malloc() implementations try to avoid using global state as much as possible by using thread-local storage for almost all requests.

• A thread that allocates a pointer is not necessarily the thread that frees it. This has to be taken care of.

• A thread may constantly allocate memory and pass it to another thread to free it. This makes handling of the last point much more difficult, because it means that free blocks may accumulate within any thread-local storage. This forces the malloc() implementation to provide means for the threads to exchange free blocks, and likely requires grabbing of locks from time to time.

If you don't care about threads, all these points are no issues at all, so a non-thread-safe allocator does not have to pay for their handling with performance. But, as I said, a standard implementation cannot ignore these issues, and consequently has to pay for their handling.

Answer 5

If you compare a real malloc implementation with a school project, consider that a real malloc has to manage allocations, reallocations and freeing memory of hugely different sizes, working correctly if allocations happen on different threads simultaneously, and reallocation and freeing memory happen on different threads. You also want to be sure that any attempt to free memory that wasn't allocated with malloc gets caught. And finally, make sure that you don't compare with a debugging malloc implementation.

Answer 6

I think that the two SUT are not direct comparisons. I would not be surprised at any comparable difference when you consider all the variables: memory manufacture, motherboard architecture, compiler version (that compiled malloc), what the memory space application is like on the SUT at the time, etc etc etc ....... Try using your test harness to be more representative of how you would use memory in a real project - with some large/small allocations, and some applications held for a long time and some freed soon after being taken.