• 9
• 9
• 10
• 9
• 10

# Custom heap allocator that allocated only within a chunk (for game)

## Recommended Posts

I am trying to develop a heap allocator that has following properties :-

• I will assign a contiguous memory chunk (begin-end address) to it.
• It will allocate using memory only in the assigned chunk. (not a property of std::allocator)
• I can ask it to allocate any size.
• If the chunk is not large enough / it is full, it will return null.
• reasonable performance (It is totally ok to be slower than poll, scope, linear allocators.)

Something like this :-

HeapAllocator heap;
void* beginByte=...;
int numByte=...;
heap.assignMemory(beginByte,numByte);
....

int iWantNumByte=sizeof(SomeClass);
void* iGetYou=heap.allocate(iWantNumByte);
heap.deallocate(iGetYou);


To avoid reinventing the wheel, here are such libraries I found :-

As I skimmed the code :-

• 1 and 2 and 4 : cost max cost of allocate/deallocate = O(amountOfFreeBlock).  They are very easy to understand.
• 3 : cost =  O( log(amountOfFreeBlock))  The document is quite good, but it doesn't cover every aspect.
• 3 : also has a bug ( comment in that page)

Are there more libraries that I can copy study?

Are there any good books/articles I should read?

Edited by hyyou

##### Share on other sites

hm, i think the problem/solution with O( f( amountOfFreeBlocks)) really depends on the size of the storage. at a certain point it might be beneficial to sort freeBlocks in a binTree or something, but this really is something i feel needs to be profiled under a real workload to see if there is any point in optimizing.

at least for me the last time it was more important how i grouped stuff to store in my custom allocator(s) (caching i guess) than O(-1) operation.

naive O(amountOfFreeBlocks) with some even more naive tweaks worked fine. like sort freeBlocks by size after release - might sound insane, but actually works well in my specific case. that way either the first freeBlock is large enough, or i would have to resize or defragment.

##### Share on other sites
ninnghazad ... like sort freeBlocks by size after release ...

Yes!! The project in codeproject (3) sorts like that (by size and by address), so it is very fast.

How do you sort it?   Do you need some more allocated memory?

I found that it is really hard to sort thing without standard allocation in places.

More specifically, I am trying to make my game allocated only once .... so my heap have to allocate some memory inside the chunk for that sort operation.

The size of memory that used to sort is not fixed, and can't be known in advance (as far as I know).

Thus, this problem is like finding a memory to manage memory .... so recursive.  :wacko:

Edited by hyyou

##### Share on other sites

i actually use std::sort on std::vector<MyChunkStructWhichIsJustTwoSize_T>. std::sort does inplace sorting using move-swap where possible. so low mem-needs. and i think you need at most sizeof(item) mem to sort a vector even without move-swap-magic. but you might use sorted linked list, and plop in released blocks in the right spot so you don't have to sort - or well it just *is* sorted all the time. start simple and solid - optimize later.
but that aside, i think you may have entered the vast regions of YAGNI. as long as you aren't working on some strictly restricted platform with tiny mems, you might create more problems for yourself as you solve. is it for some old console? otherwise the 13-and-a-half bits you need to store the meta-info a few vectors need really won't make a difference.

also sizeof(std::vector<WhatEvs>) is implementation-defined i think.

##### Share on other sites

Thank a lot, ninnghazad.

Seeing an expert recommends that it usually does not cost too much (i.e. it is a premature optimization) make me clam down and start to seek for a solution which is a little more expensive but much easier-to-code.

Now, I can use std::multimap, then might optimize later.  :D

##### Share on other sites

Thus, this problem is like finding a memory to manage memory .... so recursive.
An early Unix file system used the free blocks at the disk for its free blocks administration. When you have many free blocks, you need more space, but you have lots of free blocks for it then :)

##### Share on other sites

Thank a lot, everyone, for good advises!

I found out later that even using std::map AND a lot of function pointer (my poor skill) to implement custom heap ->

an experimental custom heap allocator still faster than the standard new/delete!

(It is an evidence that it is somehow a premature optimizaton, as ninnghazad mentioned.)

I still want to know where should I read more / find more library though ....

Windows API Heap* calls meet these requirements: https://msdn.microsoft.com/en-us/library/windows/desktop/aa366599(v=vs.85).aspx

Thanks.  Does anyone know any others open source library?

An early Unix file system used the free blocks at the disk for its free blocks administration. When you have many free blocks, you need more space, but you have lots of free blocks for it then :)

It is interesting!   :D  I believe there is no guarantee how std::map allocated, so I think I can't adapt that concept, though.

Edited by hyyou

##### Share on other sites

an experimental custom heap allocator still faster than the standard new/delete!

It's interesting to note that most standard libraries implement new/delete in terms of malloc() (as dictated by the standard), and malloc() is generally a really good caching allocator with best-fit and compaction.
The trick is that malloc() is required to be threadsafe, which means locking and unlocking on every call.  In other words, even the worst poorly-coded and poorly-designed replacement for new/delete is likely to outperform the library by an order of magnitude.  Until the moment you have a threaded app, in which case you lose big.
A good reference for a fast, efficient, and portable chunk allocator can be found in one of the most widely-used implementations in the world.

##### Share on other sites

Bregma, thank for a good link to the so-satisfying big code.

In my code, here is how I allocate/deallocate a new byte array (I do it without mutex).

::operator new(numByte);
::operator delete(void_star_pointer);


Is it the same as malloc()/alloc() you mentioned?

(clarify) My prototype performance linear allocator is generally better than standard new/delete :-

allocator->makeStrong<SomeClass>()   .... faster than ....... new SomeClass().

Is it partially because my class is not thread-safe comparing to new SomeClass()?

Edited by hyyou

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account