8

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;
}
  • 7
    Try comparing performance when you are allocating and deallocating variably sized chunks and when the freeing is not called in the same order as the allocations, and see what happens with your school project then. – whatsisname May 20 '16 at 4:54
  • 1
    You'll probably find the C library source here: gnu.org/software/libc -- or you could use your package manager to download source. – kdgregory May 20 '16 at 11:59
  • 1
    If you want comments on why your allocator might be faster or slower than the standard library, you should show it rather than just the test program. I'm guessing that you pre-allocate a large block of memory and then carve out chunks, which means that you don't have to pay the price of incrementally increasing the heap size via sbrk (or whatever modern allocators use). – kdgregory May 20 '16 at 12:01
  • 1
    And unrelated, why calloc and then explicitly clear? – kdgregory May 20 '16 at 12:02
  • @whatsisname I changed the test according to your comment, and I get the reasonable result than my custom malloc is slower. That is what I would expect. – Niklas Rosencrantz May 20 '16 at 13:39
11

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 (esp 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.

  • +1 for the link to the good articles. I need to study the theory. Just stumbled on valloc that I never heard of before, need to check what it is. – Niklas Rosencrantz May 20 '16 at 18:01
  • 1
    Don't forget thread safety. – Sebastian Redl May 20 '16 at 18:11
  • valloc returns memory aligned to the page size. It's deprecated as you can use memalign for that. – Alex May 23 '16 at 9:40
18

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.

  • I care about reliability but it is easier to understand efficiency / speed. I read that malloc can crash if it gets an interrupt or similar, but I don't know enough about that yet. Thanks for pointing out that the test code is wrong, I thought the result was unreasonable. I changed the code to random allocation. I think the conclusion is that I should study more. – Niklas Rosencrantz May 20 '16 at 14:12
  • There are implementations where malloc never fails (your program might crash, however). On iOS testing whether malloc returns S null pointer is quite pointless. – gnasher729 May 20 '16 at 17:24
  • I know that (e.g. some Linux computers have memory overcommit), but I do notice that such implementations are against the C standard : their malloc is returning a (non-NULL) pointer which could not be dereferenced. – Basile Starynkevitch May 21 '16 at 5:27
5

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.

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.

2

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.

2

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.