I'm currently attempting to write a 2D scene graph in C, and I need to decide on a way of storing the child nodes. I'm expecting very many reads and few writes, so a linked list is out of the question due to poor spatial locality of reference, and using realloc every time to add a child node would probably fragment the free list into oblivion. A pool allocator seems to be the best solution, but I can't seem to find any implementations to use. Does anyone know of an allocator that would efficiently handle random-ish allocations and deallocations of a few hundred small structs, or perhaps a better allocation scheme?
Add a comment
|
2 Answers
I'm preparing to deploy TLSF as a real-time allocator. I haven't had a chance to profile its performance yet, but it seems to work, and the license is right.
According to their docs, its operations execute "a maximum of 168 processor instructions in a x86 architecture". It comes as a single .c file, which compiled without modifications on my system.
5 Comments
T.E.D.
@CAFxX - Shame. Google finds me some alternate sites, but none seem to be official. Hopefully that will change.
T.E.D.
Yay! Thanks for the fix, @Electro . Giving you a semi-random upvote. Chalk another win for crowd-sourced knowledge.
Electro
@T.E.D. Well, I do like to go over my own questions once in a while - can't have links rotting away :P
Gaslight Deceive Subvert
Thanks for the tip. In my informal benchmark, it beats glibc's
malloc by 25% or more. But it is slightly slower for free. Unfortunately, it segfaults when you try to make a memory pool 2gb or larger in size.T.E.D.
@BjörnLindqvist - ...which immediately tells me - signed 32-bit integer being used somewhere. Hopefully its fixable. 32-bit systems are essentially obsolete now, except for specialized uses.
Take a look at halloc, it might be of some help.
1 Comment
Electro
halloc looks interesting, but it still works on top of malloc, so the fragmentation issue remains, though I guess it might prove useful as a starting point for a pool allocator.