I suspect that some of the functions for iterating the linked lists are a big drag on performance. Such as: https://github.com/CCareaga/heap_allocator/blob/master/llist... An optimization that most memory allocators use are to instead store the nodes in a balanced tree, such as a red-black one. Or even better, a B-tree. That turns those functions from O(n) to O(log n).
> An optimization that most memory allocators use...
Got any evidence to support this claim? I call b/s, especially on the "most" part.
Balanced trees introduce an extra per-node overhead, they tend to thrash the cache and are generally inferior to a simple array of double-linked lists indexed by the block size range.
* An AVL tree doesn't have the per-node overhead, but it is very cache-unfriendly.
How about the memory allocators used by Linux, Windows, BSD and Solaris? :)
It doesn't matter if the allocator uses buckets (indexed by the block size range) or not, it still has to find blocks of suitable size, for some definition of "suitable." So look at his get_best_fit and add_node functions. These ensure that his alloc and free functions are O(n) at best. Clearly, we can do better.
Are you making an educated guess that there should be a blanced tree somewhere in there? If yes, then it's a wrong guess, because there are better options that aren't based on a boatload of conditional branching and that _are_ routinely used in a lot of allocators. If no, there shouldn't be hard to produce relevant code segments. Especially since these trees are virtually everywhere as per your opening remark.
Address spaces in modern operating systems. Address spaces can consist of a large number of virtual address regions. As one example, on a typical Linux desktop, GNOME applications and web browsers such as Firefox and Chrome use nearly 1,000 distinct memory regions in each process. To manage this large number of regions, most modern operating systems use structures like the ones in Figure 1 to represent an address space. Linux uses a red-black tree for the regions, FreeBSD uses a splay tree, and Solaris and Windows (prior to Windows 7) use AVL trees [18, 24].
If you know of any better search structures, then I'd love to hear about them. I wrote my own memory allocator for a vm project and found that storing the free list in a red-black tree was absolutely required for decent performance.
This is unrelated, you are switching the subject. The context is an application-level memory allocators, not the underpinnings of the virtual memory systems.
You said -
> An optimization that most memory allocators use are to instead store the nodes in a balanced tree, such as a red-black one
Yet, you still haven't shown a single memory allocator that actually does that. Except for your own.
Now I'm beginning to think that you are trolling me. Memory allocators within the kernel works exactly the same as those outside of it. But for one stand-alone library using balanced trees, look at jemalloc.
jemalloc uses trees (off the fastpath nonetheless), but hoard doesn't, dlmalloc doesn't, etc.
Common sense derived from CS101 on data structures doesn't directly translate to what's happening in the real world. Your opening comment was pure armchair athelitics.
