Thread: Custom Allocation

Originally Posted by iMalc

You'd probably be interested in this memory pool allocator I wrote a while ago:
http://www.flipcode.com/cgi-bin/fcar...cgi?show=64152

Thanks, that's pretty darn clever. I like how you reuse the fixed object space (which has been padded a bit) to provide the infrastructure for your free pointer linked list. Thats pretty nifty. I think the C++ code actually hides the elegance of what you're doing however.

I guess also there is no mechanism right now to grow your initial block of memory if it proves inadequate, though this can be easily fixed. Also there is one potential gotcha the way this is written. An important, though not often used compiler optimization is to rip apart structures and classes and treat their individual elements as atomic variables for register allocation and other standard optimizations. It has a name but it escapes me right now.


Such an optimization could potentially nerf your initial allocation of the free list, since you may not be guaranteed that there is head room after the end of your class/structure. I am not sure, but ANSI C, for example, may not necessarily require structs to be held in contiguous memory. Though in this case you are probably safe since it seems to essentially be a recast of a pointer to the larger size pool. C++ is kind of weird though. I'm always surprised at what is really going on under the hood.

For the technique I use, I basically want an allocation to pop the address off of a stack (an array) and return, whilst free pushes the address on to a stack. So which is faster, reading an entry from the top of an array and increment the array pointer, or simply returning the next entry in the linked list. The linked list approach has a slightly smaller instruction count I suppose. However if the stacked is used often it should be in cache memory, possibly reducing memory look up time, although perhaps that's true in your case as well since the data item itself should be contiguous to the next pointer.

Freeing however requires looking up the data structure in the next pointer which may not be in the cache. One can never tell these things until one tries it however. It would be interesting to benchmark it.

Originally Posted by Salem

So you could have

Create a pool of small objects
smallObj *small = malloc( max * sizeof *small );

Then to allocate
return &small[count++];

To free a block, one could simply abandon it, and carry on allocating quickly from the end of the array. But that would depend on whether the speed improvement was worth the acceptable losses.
Or if you have a few more 'free', then perhaps create a free list which you allocate from when you get to count == max.

When everything is done, just
free( small );

Yup simple and sweet for a lot of problems and I always prefers simplicity. This one however requires just a touch more flexibility. My ternary tree could hold anything from a few strings to run test cases or an enormous tree that fills up available memory. So in my code, when I exhaust the free list I load up another block of memory. When my free list gets too big, I grow the list using realloc, using the 50% growth trick, which grows the array in order n (n is the number of bytes needed.)

However malloc on my linux distro is competitive with a simple decrement stack pointer and read off the free pointer trick. I'll venture a guess and suggests that MS's malloc is not this efficient.

> I am not sure, but ANSI C, for example, may not necessarily require structs to be held in contiguous memory.
Yes it does.

I'm glad to hear it. My compiler optimization book was not so certain about this.