Even faster Alloc and Free

By melfar

In Hugi 28, TAD offered his favorite memory alloc and free functions. I want to introduce to you an even faster and memory saving way to allocate memory, which I found in Scott Meyers' "Effective C++" book. We aren't going to use stack here, we'll use a linked list instead. The advantage of this method is that we can store linked list items as the first words of free entries. After the list is created, all that's left to do is to make a *ptrfee pointer to point out to the first free entry. When the user invokes alloc (), we do ptrfree = reinterpret_cast<int*> (*ptrfree) and return the old ptrfree value. When the user invokes free (user_ptr), we do *ptrfree = reinterpret_cast<int> (ptrfree) and ptrfree = user_ptr. Easy, huh?

Once more:

1) Create a large memory block:
int* mem = std::malloc (4*4096);

2) Create the linked list of items, provided that your object size is sizeof(object):
for (int i = 0; i < (4*4096)/sizeof (int);

i +=sizeof(object)/sizeof(int)) {
mem[i] = reinterpret_cast<int> (&mem[i+sizeof(object)/4]);
mem[(4*4096)/sizeof(int)-1] = 0; // end it up with NULL

3) Make a ptrfree pointer:
int *ptrfree = &mem[0];

4) In your alloc () function, act as follows:
int* oldptrfree = ptrfree;
ptrfree = reinterpret_cast<int*> (*ptrfree);
return oldptrfree;

5) In your free () function, act as follows:
*ptrfree = reinterpret_cast<int> (ptrfree);
ptrfree = user_ptr;

6) What to do if you have reached the end of the list? Do (1), (2) and (3) again, and don't forget to organize a linked list of allocated memory blocks in order to free them up when the job is done - just reserve the first word of each memory block for the "next" pointer. Unfortunately, there's no obvious way to free excessive memory blocks when they are no longer used.

That's all. Happy (and effective) coding!