9
\$\begingroup\$

I made this because I need to make a program that creates and destroys huge trees in gigabytes for hours or time. The default malloc/free in MinGW/GCC is too slow.

I wrote two equivalent test programs, in C and in Java, which does a large amount of small frequent dynamic memory allocation. The C program using the basic malloc/free runs 10 times slower than the Java version... well, when compiled with MinGW/GCC in my Windows 7 machine with -O3 -march=native. When using my version of malloc/free now the test code is a lot more faster but still twice as slower than the Java version.

I believe there must be more optimization possible in my custom allocator's code. Please let me know if there are any.

After running some more tests, the running time of the test programs is (approximately)

120s [MinGW/GCC default]
61s [VC++ default] (compiles in C++ too)
23s [MinGW/GCC custom]
13s [VC++ custom]
11s [Java]

mj_allocator.c

#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef unsigned char byte;

byte *pool, *pool_ptr, *helper, *helper_ptr;
size_t pool_size, left_space;
const byte SIZE_MARK_MAX = UCHAR_MAX >> 1;

void use_mj_allocator(size_t size)
{
    pool = pool_ptr = (byte *)malloc(size);
    helper = helper_ptr = (byte *)calloc(size, 1);
    pool_size = left_space = size;
}

void free_mj_allocator()
{
    free(pool);
    free(helper);
}

void set_size_mark(size_t size, byte *ptr)
{
    if (size <= SIZE_MARK_MAX)
    {
        *ptr = (size << 1) + 1;
    }
    else
    {
        *ptr = 2;
        *(size_t *)(ptr + 1) = size;
    }
}

size_t get_size_mark(const byte *ptr)
{
    if (*ptr & 1)
    {
        return *ptr >> 1;
    }
    return *(size_t *)(ptr + 1);
}

int search(size_t size)
{
    if (size > pool_size)
    {
        return 0;
    }
    byte *start_ptr = helper_ptr;
    if (left_space == 0)
    {
        goto no_left_space;
    }
    helper_ptr += left_space;
    left_space = 0;
    while (1)
    {
        if (helper_ptr == start_ptr)
        {
            return 0;
        }
    no_left_space:
        if (helper_ptr == helper + pool_size)
        {
            helper_ptr = helper;
            left_space = 0;
        }
        if (*helper_ptr)
        {
            left_space = 0;
            helper_ptr += get_size_mark(helper_ptr);
        }
        else
        {
            ++left_space;
            ++helper_ptr;
        }
        if (left_space == size)
        {
            while (1)
            {
                if (helper_ptr == helper + pool_size || *helper_ptr)
                {
                    break;
                }
                ++left_space;
                ++helper_ptr;
            }
            break;
        }
    }
    helper_ptr -= left_space;
    pool_ptr = helper_ptr - helper + pool;
    return 1;
}

void *mj_malloc(size_t size)
{
    if (size > left_space)
    {
        if (!search(size))
        {
            return NULL;
        }
    }
    set_size_mark(size, helper_ptr);
    byte *ptr = pool_ptr;
    pool_ptr += size;
    helper_ptr += size;
    left_space -= size;
    return ptr;
}

void *mj_calloc(size_t len, size_t unit)
{
    size_t size = len * unit;
    void *ptr = mj_malloc(size);
    memset(ptr, 0, size);
    return ptr;
}

void mj_free(void *ptr)
{
    byte *temp_helper_ptr = (byte *)ptr - pool + helper;
    if (*temp_helper_ptr & 1)
    {
        *temp_helper_ptr = 0;
    }
    else
    {
        // OLD
        // memset(temp_helper_ptr, 0, sizeof(size_t) + 1);

        // NEW
        *temp_helper_ptr = 0;
        *(size_t *)(temp_helper_ptr + 1) = 0;
    }
}

size_t kb_to_b(size_t kb)
{
    return 1000 * kb;
}

size_t mb_to_b(size_t mb)
{
    return kb_to_b(1000 * mb);
}

size_t gb_to_b(size_t gb)
{
    return mb_to_b(1000 * gb);
}

mj_allocator.h

#ifndef MJ_ALLOCATOR_H
#define MJ_ALLOCATOR_H

#include <stddef.h>

#define malloc mj_malloc
#define calloc mj_calloc
#define free mj_free

void use_mj_allocator(size_t size);
void free_mj_allocator();
void *mj_malloc(size_t size);
void *mj_calloc(size_t len, size_t unit);
void mj_free(void *ptr);
size_t kb_to_b(size_t kb);
size_t mb_to_b(size_t mb);
size_t gb_to_b(size_t gb);

#endif

test.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#ifdef MJ_ALLOCATOR
#include "mj_allocator.h"
#endif

enum {ARRAY_LEN = 50000};
int *array[ARRAY_LEN];
long long sum = 0;

int confuse_the_compiler(int n)
{
    return n % 10 > 5 ? -n / 2 : n * 2;
}

void start()
{
    for (int i = 1; i <= ARRAY_LEN; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            array[j] = (int *)malloc(sizeof(int));
            array[j][0] = j + 1;
        }
        for (int j = i - 1; j >= 0; --j)
        {
            sum -= j;
            int n = confuse_the_compiler(array[j][0]);
            if (n != 0)
            {
                sum += n;
                free(array[j]);
            }
        }
    }
}

int main()
{

#ifdef MJ_ALLOCATOR
    use_mj_allocator(ARRAY_LEN * sizeof(int));
#endif

    time_t start_time = clock();
    start();
    time_t end_time = clock();
    printf("\nelapsed time: %.3f\n", (double)(end_time - start_time) / CLOCKS_PER_SEC);
    printf("%lld", sum);

#ifdef MJ_ALLOCATOR
    free_mj_allocator();
#endif

    return 0;
}

test.java

class test
{
    final static int ARRAY_LEN = 50000;
    static int[][] array = new int[ARRAY_LEN][];;
    static long sum = 0;

    static int confuse_the_compiler(int n)
    {
        return n % 10 > 5 ? -n / 2 : n * 2;
    }

    static void start()
    {
        for (int i = 1; i <= ARRAY_LEN; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                array[j] = new int[1];
                array[j][0] = j + 1;
            }
            for (int j = i - 1; j >= 0; --j)
            {
                sum -= j;
                int n = confuse_the_compiler(array[j][0]);
                if (n != 0)
                {
                    sum += n;
                    // free(array[j]);
                }
            }
        }
    }

    public static void main(String[] args)
    {
        long start_time = System.currentTimeMillis();
        start();
        System.gc();
        long end_time = System.currentTimeMillis();
        System.out.printf("\nelapsed time: %.3f\n", (end_time - start_time) / 1000.0);
        System.out.println(sum);
    }
}
\$\endgroup\$
  • \$\begingroup\$ the java version won't ever free the array until memory gets full, so I would call the comparison invalid \$\endgroup\$ – ratchet freak Nov 24 '14 at 12:44
  • \$\begingroup\$ @ratchetfreak And why is that? \$\endgroup\$ – YoYoYonnY Oct 14 '16 at 22:33
  • \$\begingroup\$ @YoYoYonnY cause it's faster to not do any collections until it's actually needed. For short running programs it's an entirely valid GC strategy as the OS will reclaim all RAM you take. \$\endgroup\$ – ratchet freak Oct 14 '16 at 22:58
6
\$\begingroup\$
  1. The code totaly explodes on a big endian system so that certainly doesn't make it faster
  2. in search you have

     if (*helper_ptr)
    {
        left_space = 0;
        helper_ptr += get_size_mark(helper_ptr);
    }
    else
    {
        ++left_space;
        ++helper_ptr;
    }
    

    You are searching the pool byte for byte for a large enough chunk of free space skipping any allocated blocks. This takes a long time. Longer if the size is large, longer when memory is fragmented. You should set a size mark for free chunks too and include one bit to say wether the chunk is free or in use. That way you know with one look wether the chunk is large enough or not. If you store the size of each chunk before and after each block the free function can check if the previous and next chunks are free and merge them with the current chunk into a single larger chunk.

  3. Allocations have a minimal alignment requirement (16 byte on x86 and amd64), at least 4 byte on any 32bit system I know and usualy at least 8 byte on 64bit systems. That means your effort to encode small sizes into a single byte size mark is wasted and breaks the alignment requirement for structures. On x86/amd64 this makes things slow. On other archs this causes segfaults or bus errors. Align things properly and it will be faster.
  4. You say you have "huge trees in gigabytes". That usualy means you have many many allocations and free of identical size. Overall you might have different sizes but they will be clustered a lot. You can take advantage of that. Create seperate pools for each cluster (8 byte, 16 byte, 24 byte, ... do some statistics to see what sizes are common). Then when an allocation is made check if the size if one of the clusters. If so allocate from the special pool, otherwise the generic pool. Now how does that help? Since all 8 byte objects will be in one pool and only 8 byte objects will be in there you dont have to store the size of each object. Make the pool an array of 8 byte objects. You can link all free 8 byte objects into a list (use the 8 free bytes for that, no overhead). Then on alloc pop the first object from the list and return it. On free add the object to the free list. Since everything is 8 byte big you don't have to worry about fragmentation or anything. Same thing for other sizes.
\$\endgroup\$
  • 1
    \$\begingroup\$ I second the idea of just using pools instead of rewriting malloc. Just allocate a huge chunk of memory and split it into N nodes. Treat the nodes as a linked list and put them all on a "free list". When you want to allocate a new node, take the head of the free list in constant time. When you want to free a node, add it to the head of the free list, also in constant time. The only slow part is when you run out and need to allocate another huge chunk to split into free nodes. \$\endgroup\$ – JS1 Nov 24 '14 at 4:08

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.