3 ms·
This is unrelated, you are switching the subject. The context is an application-level memory allocators, not the underpinnings of the virtual memory systems. Y
by eps 9y ago
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.
- bjourne 9y agoNow 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.
- eps 9y agoOkay. "Exactly the same as outside of it." 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.
- bjourne 9y agoMost memory managers worth their salt tend to cache commonly used sizes, that's why tree accesses aren't on the fast path. I have now looked at Hoard. It does use std::map which is indeed a red-black tree.