Over the weekend I built a fairly simple allocator:
struct FreeOnes { //data structure holding the pointers to free blocks
int len;
void** array;
int capacity;
};
void append(struct FreeOnes* f, void* what){ //add a free block to FreeOnes
if (f->len < f->capacity){
f->array[f->len++] = what;
} else {
f->capacity *= 2;
f->array = realloc(f->array, sizeof(void*) * f->capacity);
f->array[f->len++] = what;
}
}
void* pop(struct FreeOnes* f){
return f->array[--f->len];
}
struct FreeOnes* newFreeOnes(int capacity){ //create a new FreeOnes datastructure
struct FreeOnes* f = malloc(sizeof(struct FreeOnes));
f->len = 0;
f->capacity = capacity;
f->array = malloc(sizeof(void*) * capacity);
return f;
}
struct Size { //the information neccessary to allocate a block
int size; //the byte size
int alignment; //the alignment to the memory-array
};
struct Size find(int size){ //find at wich alignment the size fits inside
int i = 2;
int iter = 0;
while (i <= size) {
i *= 2;
iter ++;
}
struct Size s;
s.size = i;
s.alignment = iter - 1;
return s;
}
struct FreeOnes** sizes; //holds a free ones data structure for all power of 2 sizes until 2^32
void* allocChunk(struct FreeOnes * f, size_t size, int alignment, int howMuch){ //chunk allocate memory,
//used by alloc and returns a pointer to the first element in the chunk
void* pool = malloc(size * howMuch);
void* at = pool;
for (int i = 0; i < howMuch; i++){
void* pointer = at;
at += size;
int* p = (int*) pointer;
*p = alignment; //store the alignment meta-date
append(f, pointer+ sizeof(int));
}
return pop(f);
}
void* alloc(struct Size s){ //allocate, memory for a size
if (sizes[s.alignment]->len > 0){ //if already allocated memory, just this instead
void* pointer = pop(sizes[s.alignment]);
return pointer;
} else if (s.alignment < 6){ //allocate chunk and use the first element
return allocChunk(sizes[s.alignment], s.size, s.alignment, 100);
} else if (s.alignment < 12){ //allocate chunk and use the first element
return allocChunk(sizes[s.alignment], s.size, s.alignment, 20);
} else if (s.alignment < 24){ //allocate chunk and use the first element
return allocChunk(sizes[s.alignment], s.size, s.alignment, 5);
} else { //so big not worth allocating chunk for, simply return pointer to malloc initialized memory
void* pointer = malloc(s.size);
int* p = (int*) pointer;
*p = s.alignment; //store the alignment meta-date
return pointer+ sizeof(int);
}
}
void dealloc(void* pointer){ //free the pointer, and return it to the freeOnes vector
int s = *((int*) (pointer - sizeof(int)));
append(sizes[s], pointer);
}
void init(){ //initialize the program memory needed for alloc and dealloc
sizes = (struct FreeOnes**) malloc(sizeof(struct FreeOnes*) * 32);
for (int i = 0; i < 32; i++){
sizes[i] = newFreeOnes(100);
}
}
The allocator performs very well on this slightly biased benchmark:
struct LinkedListAlloc { //small linked list benchmark int x; struct LinkedListAlloc * next; }; long benchmark1(){ //benchmark using alloc clock_t time1 = clock(); struct Size size = find(sizeof(struct LinkedListAlloc)); //the size for the linked list, in the format for alloc for (int iter = 0; iter < 1000; iter++){ //create the linked list struct LinkedListAlloc* root = alloc(size); root->x = 0; struct LinkedListAlloc* last = root; for (int i = 1; i < 1000; i++){ struct LinkedListAlloc* tmp = alloc(size); tmp->x = i; last->next = tmp; last = tmp; } struct LinkedListAlloc* current = root; while (1) { if (current->x == 999){ dealloc(current); break; } struct LinkedListAlloc* tmp = current; current = current->next; dealloc(tmp); } } clock_t time2 = clock(); return time2 - time1; } long benchmark2(){ //benchmark using malloc clock_t time1 = clock(); size_t size = sizeof(struct LinkedListAlloc); //the size for the linked list for (int iter = 0; iter < 1000; iter++){ //create the linked list struct LinkedListAlloc* root = malloc(size); root->x = 0; struct LinkedListAlloc* last = root; for (int i = 1; i < 1000; i++){ struct LinkedListAlloc* tmp = malloc(size); tmp->x = i; last->next = tmp; last = tmp; } struct LinkedListAlloc* current = root; while (1) { if (current->x == 999){ free(current); break; } struct LinkedListAlloc* tmp = current; current = current->next; free(tmp); } } clock_t time2 = clock(); return time2 - time1; } int main(){ init(); long took1 = benchmark1(); long took2 = benchmark2(); printf("alloc: %ld\n", took1); printf("malloc: %ld\n", took2); return 0; }
The test using alloc and dealloc is ten times faster than the test using malloc and free.
What could I improve on for this allocator, eg. how to make it thread-safe?
