So, it's been over a month since my last (tiny) post, so I thought I'd do a good update on my current workings.
Coding-wise, I'm working on a game with my g/f for the Android. Progress is going slow, since I have this one stubborn bug that I can't seem to find the cause to. It's a really annoying bug, where a call to free() is failing. I know for a fact that the memory address is valid, since I can access it correctly right before the call, and I've looked at every free() that preceded this one, so I know this isn't some random double-free error. I'm just completely baffled. For now, I've simply commented out the free() call, so I can test other portions of the app. But that one naggy line of code is driving me nuts. (I'm starting to see the appeal of Java's garbage collector, now...) :X
Non-coding-wise, however, things have been going much, much worse. You see, I am, sadly, a terminally boring person. :) As such, I like to study things that don't interest many other people, and this week has been a prime example. Taking a slight cue from my programming problems mentioned above, I've been studying memory allocators.
Memory allocators are the things that actually power C/C++'s dynamic memory capabilities through function calls like malloc(), realloc(), and free(). I, for some god-awful reason, find these libraries fascinating! I've always wondered how they actually work, and now seemed like as good a time as any to start, so I dived right in.
First of all, I looked into dlmalloc. When it comes to malloc implementations, dlmalloc (which stands for Doug Lea's Malloc) is pretty much the de-facto standard of single-threaded allocators. It's fast, simple, uses little memory, can usually avoid severe fragmentation, and is released into the public domain. Android uses a stock version of dlmalloc in their 'Bionic' libc, and glibc uses a heavily modified version of dlmalloc called ptmalloc. (A version that has been modified to handle multi-threading better.)
The way dlmalloc works is moderately simple. The memory from the OS is obtained with a call to sbrk(), and is organized into 'Segments' of contiguous memory, which are stored in a linked-list. This memory is then partitioned up into 'Chunks' which can be marked as either 'free' or 'in-use', where the in-use Chunks have been provided to the user based on a malloc() call (or similar), and the free Chunks are... well... free. :)
Those 'free' Chunks are treated differently based on their size. Small Chunks are stored in a double-linked list for quick access. Malloc() will then try to pick chunks that are next to other small chunks that were recently allocated. (Hopefully improving cache performance.) Larger Chunks are stored in a trie, which is bit-wise keyed based on the size of the chunk. Chunks with the same size in this trie are linked together in a linked list, and sorted in FIFO order. That way, malloc() can find the best fitting chunk quickly. (A lookup should take O(B) time, where B=the number of bits in a pointer.)
... And that's pretty much it.
Of course dlmalloc uses all kinds of clever tricks, like using mmap() for the REALLY big allocations, using /dev/urandom to secure the data from heap-based overflows with random keys, or storing most metadata inside of the freed space, resulting in a fairly small overhead, but those are mostly implementation details. What is really surprising is just how effective these (relatively) simple algorithms are. Sure, over the years, the code has definitely been polished to a mirror-shine. (Some portions have different implementations based on what compiler is being used, for example.) But ultimately, at a high-level, this is a fairly straight-forward malloc(), and it's no wonder why dlmalloc is put to so much use.
There is another interesting malloc implementation out there, and this one is from FreeBSD-land. jemalloc (for Jason Evans' malloc) is the latest allocator used in FreeBSD, and was actually brought into Firefox several years ago, to fix some memory fragmentation problems that were giving the illusion of huge memory leaks.
jemalloc was designed with scalable multithreading in mind, and uses the concept of an 'arena' to do this. An arena is basically a section of the available space that will be used for allocations. Different threads will stick to different arenas, so memory allocated by one thread will tend to be stored in the same memory range as other allocations from that thread, which should improve cache performance. Now, if jemalloc is running on a single-cpu system, then it'll only make one arena and will try to operate similarly to other allocators. However, on systems with multiple cpu's, it will create 4 arenas per processor.
Now, what does jemalloc do to keep track of the actual allocations? Well, that depends on the size of the allocation. Allocations get classified as either Small (with subcategories of Tiny, Quantum-spaced, and Sub-page), Large, and Huge. Based on what category each allocation falls under, the amount of memory being asked for is rounded up to certain strategic values, to make sure that they fit together well. Then, different strategies are employed for all of the different chunk-size categories. (I won't get into the mucky details of this, because it's fairly tedious, but I will note that they do employ red-black trees. :) )
jemalloc has been shown to be an incredibly efficient malloc when it comes to multi-core systems. jemalloc's white paper has figures that show it beating dlmalloc in pretty much anything with more than one thread, which makes sense, given that dlmalloc's idea of multithreading support is one single lock that makes sure that dlmalloc is only being called from one thread at a time. (Can you say: "bottleneck"? :) ) However, dlmalloc still beats jemalloc in single-threaded applications. (But they're pretty darn close.)
Both of these allocators do fairly well, but fragmentation will always be an issue. Thus far, there is no allocator that can perfectly prevent fragmentation, and thanks to how C/C++ handles things, you can't write a memory defragmentor. Since the programmer has access to the raw pointers in both C and C++, he/she can hide those pointers in any number of ways. The best a C/C++ memory defragmenter could do is perform an exhaustive search of the program's memory. Not only would this be incredibly slow, but it would also be very wrong. What if the program stored a pointer to some position in the middle of the allocated memory? Those have to be updated as well, so that means we have to be searching for a potentially huge range of values. Or what if the program has an integer that JUST HAPPENS to have the same value as that pointer? Then, since memory is un-typed, there is no way to tell that integer apart from a pointer, and it will be altered, potentially causing seemingly random crashes, or even worse, errant behaviour.
I guess this would be a big plus for some of those other languages, like C# or Java, which just hide pointers from the programmer. Allocators for those languages could arbitrarily move data for defragmentation purposes, and need only make sure they document their changes. Plus, these languages come with garbage collectors, and so that's nice too. :)
Of course, defragmentation isn't the cure-all for everything. Defrag-ing is going to be slow, and the allocators used in Java and C# still take some cues from the standard allocators, like dlmalloc, ptmalloc, or jemalloc, and it only makes sense. All of those normal allocators try to set things up so that a defragmenter would rarely be neccessary, so, given that we only defag when things really go south, we could be fairly certain that the defragmenter would rarely be used. Then, the program would only really see the practical benefits of a nice, orderly heap. :)
(Alternatively, we could just have an incremental defragmenter, and just move one or two chunks every time we malloc(), or free() something...)
Well, that's pretty much what I've been up to recently. I hope I didn't bore anyone who was brave enough to read through all of that... I don't want to bore any of my 2 loyal readers. ;)
Anyway, now for some sleep, cause I really want to get a good start on that level editor tomorrow... :)
All kind of resources:
PS: On an unrelated note: Defensio is absolutely amazing. It has caught 100% of all spam thus far, with no false positives! Cool! :D