Game Development

Memory heap allocator faster than new/delete

Here’s a class that given a predefined area of memory, allows you to allocate and deallocate areas of that memory. In other words, a custom memory manager.

Only partially done yet, but it’s already 25% or so faster than malloc and free

Full alloc, then dealloc
Heap = 1304 us
malloc = 878256 us

Heap = 3525 us
malloc = 4462 us

Most of the speedup comes from linked lists of buckets. There are 7 buckets, from 32 bytes to 2048 bytes, incrementing in powers of two. 20% of the given memory is dedicated to buckets. If an allocation is requested and a bucket is available, the allocation goes to that bucket instead. Because buckets are contiguous and reserved, those allocations cannot cause fragmentation.

The alignment boundary is 32 bytes, so all allocations returned to the user are aligned, and the average memory wasted per allocation is 32 bytes, excluding buckets.

The speeds shown are with a critical section lock. This is not necessary, and for single threads it would be even faster.

4 replies on “Memory heap allocator faster than new/delete”

I’ve recently also made a malloc replacement, from what i’ve read of yours, very similar. However im having trouble downloading your source, the link is broken, or you’ve renamed a svn file??.. I noticed you mentioning Critical sections, have you considered using Interlocked instructions instead, they can be twice as fast as critical sections, with a lot less contention issues. A critical section causing a context switch can be very expensive. The other concern for my contextual usage is realloc effeciency for buffers that grow, does your allocation strategy help with that?

Link is fixed.

I’ll look into interlocked instructions. I thought they were only for adding such as interlocked increment and decrement.

I don’t do much with realloc at the moment. The code wasn’t finished, because I found an alternative solution with placement new where I didn’t need a memory manager anymore.

Leave a Reply

Your email address will not be published. Required fields are marked *