So i have recently become fascinated with allocators, and have tried my hand at writing a general purpose allocator, with tentative success i might add, but the main question I’m left asking myself if i can make a faster allocator than the general glibc allocator, then what is it doing that I’m possibly not doing, that is necessary for safety or correctness, that is making it slower. Any how to anyone out there who loves low level programming and has some thoughts on the subject i would welcome them.
1 Like
Generally speaking its usually because they have to be more general purpose and safety.
Now I am a bit rusty since I haven’t worked with allocators in a serious manner in since college but there is a lot of bookkeeping that has to happen behind the scenes for them. Also, memory is a really security sensitive area so allocators may do a ton of checks to ensure memory integrity, applications are not writing where they shouldn’t be, ect.
The heap though is one of the largest sources of slowdown if I remember. To ensure the the computers memory is being used and not wasted allocators and OSs do a lot of work to try to prevent memory fragmentation which is not an easy job and can be slow.
Like with the C++ standard library, custom implementations are usually faster, but that is usually because they don’t have to worry about edges cases, checks, or can make reasonable assumptions that a general implementation can not do.
Allocators are a big, fun, complex topic! I’m no expert here, but what I’ve heard or reasoned through:
Code that makes a bunch of tiny allocs and frees is likely to be slow regardless of allocator engineering. Don’t make a pile of little objects with their own addresses; consolidate them into nice, linear, arrays and vecs! This makes for better memory access (less pointer-chasing, more predictable to prefecter, less stalling, less per-object overhead), and has the benefits of being simpler if not in fact already done for you.
Where there must be many small allocations, see if you can use an arena. The general idea is to find a lifetime that many things will have (a simulation tic, the duration of these three functions, etc), and put them all together so when they die, free() is trivial. Any (few!) survivors can be realloc()d elsewhere.
In cases where you really do need to make many individual allocations with hetrogenous lifetimes, I’m out of my depth. Consult the ancients, writers of OSs, VMs, game engines, and the like!
Adding to BadIdea4’s good ideas, use your ability to program to make something not general purpose so it fits your problem better. General things don’t fit our problem, by definition. Read more:
Ryan Fleury, creator of RAD Debugger
Ginger Bill, creator of Odin language (Part 5, free list allocators, can be helpful in game development when arenas don’t suffice. Free lists are fast if the memory for them is near each other, not malloc’d per element, since the CPU will cache memory accessed near other memory. Measuring cache misses is not fun with modern OS apis, but you can try profiling instead.)
Edit: Also, I deflected from C++'s provided constructs quickly because they are never good. We are all better off writing our own things tailored to our games. I may use C++, but I only use it to generate the machine code I need, and never because of the standard library.
I’d be carefully not to confuse lifetime management/resource tracking with allocation strategies. They are orthogonal ideas that can work together or separately. Also the implication in the first link that RAII is some how bad when in an later example they made a C RAII pattern is not understanding that weather you choose C++ or C RAII is a good concept almost all good coders follow it weather they realize it or not. A frame arena and thread arena are both intending to provide RAII in relation to a specific frame or thread. This does not mean you have to like the C++ OO approach to RAII or even choose C++ for its OO. Also ARC is also not bad, its largely over used and misused out of fear of leaked memory and ease of use compare to other smart ptr typrs but, also its largely the only way to decople a shared resources lifetime from a specific scope or object, where you ligitamently need shared owership semantics. I feel like the first link largely misses the mark in terms of what makes a good allocator vs what makes a good resource tracker.
After having spent much time writing my process wide general purpose allocator, I definitely have some thoughts on how to better allocate memory in C++(some not all of these can port back to C), and i probly should make another post sharing some of my learnings for others out there .