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);
}
}
