Definitely up because realloc. Yes, the article mentions this, but it bears repeating. I wasn't aware that optimizers were so much better though!
That said, there's one useful feature that regrettably is poorly supported in most allocator discussion - where some higher alignment is wanted but not at the exact start of the object.
Microsoft has the only major allocator that I'm aware of that supports this; it uses the "align at offset" sense (which simplifies the case of prepending a header to an aligned object). GCC has some minimal support and uses the "align with offset" sense (which IMO makes literally everything else much easier). As a minimal example, if 0x4 is the low nybble of your pointer, Microsoft calls that "align 16 at offset 12", whereas GCC calls it "align 16 with offset 4".
Note that regardless of sense, you can store both the alignment and the offset in a single integer-sized variable by using your compiler's "find highest bit" or "round down to a power of 2" intrinsic. By exclusively using wrapper objects you can in fact hide the internally-chosen sense and support both publicly. This does however remove the possibility of only passing the log of the alignments, popular on BSD allocators.
Limiting `align` to positive `isize` is useful, but further restrictions can reduce the number of overflow checks you often need. I have never found a practical use (mostly: considering huge pages) for more than 3/4 of the bits to be used on alignment - that is, 6 bits (64, a typical cacheline nowadays) for 8-bit pointers, 12 bits (4K, a typical non-huge page nowadays) for 16-bit pointers, 24 bits (16M - suported on many ISAs, just not x86) for 32-bit pointers, and 48 bits (256T - theoretically available on RISC-V) for 64-bit pointers. You'll likely want a +1 when you use this, at least if you implement the logic the way I did.
Requiring alignment some distance into a contiguous allocation is interesting. The other variant is returning a pointer to the end instead of the start.
Putting those together, the generic interface would be "get a pointer with minimum alignment A, with at least N bytes available before the pointer and at least M bytes available after". Usually N=0, but N=4 would give you a word to store a size before the data etc.
That's also easy to implement on a bump allocator. I think it's a reasonable choice for the implementation with convenience wrappers for the common cases.
For the sake of branch prediction, the ABI really needs to include several functions rather than the "obvious" one allocator/deallocator function to rule them all with mere convenience wrappers.
The only thing "one function" simplifies is writing interceptor libraries, and that's not sufficiently motivating (especially given that OO is a better idea). Note that it's possible for partial interception to be detected and fall back to the generic method via `if (unlikely(interposer_detected))` in every ABI-exposed implementation function.
My initial design signature for this was:
auto utopia_alloc(Allocation, AlignAndSkew, Size, Flags) -> Allocation;
But when I actually implemented this I ended up adding an `Allocator *this` argument, then making this an inline function with fixed logic dispatching to malloc/realloc/free-like functions (but with more arguments) as needed (including a fallback if realloc isn't implemented).
Unfortunately it turns out recent versions of both GCC and Clang are gratuitously buggy regarding `malloc_usable_size` (and libcs took "advantage" of it then retroactively changed their documentation, breaking userland). Also, it turns out to be extremely useful if your libc supply a "realloc in place only" function, usually named something like "expand", but this too is not widely supported at all. Thus to make this useful I would have to implement a complete allocator, not a shim. So I kind of quit in disgust/exhaustion.
The most general allocator interface described, vmem_xalloc(), includes a "phase" parameter (their name for "align at offset"), as well as a "nocross" parameter (in case you want your oddly-aligned object to not cross a page boundary).
Hmm, paying a whole extra register for `nocross` is pretty expensive ... though representing it as a logarithm means it only needs to represent 62 values (2^1 is meaningless for both 1-byte and 2-byte allocations, 2^64 cannot be crossed regardless), which is 6 bits, so we could stuff it in the flags or even the high bits of the alignment on 32-bit-or-larger platforms. That seems like the way to do it ... unless it is instead specified as part of the allocator itself.
not sure if it was a factor in the API design, but SPARC's fixed-size register windows give you space for 8 parameters. Perhaps it's just coincidence, but vmem_xalloc() takes exactly 8 parameters!
Using microbenchmarks to measure allocation performance is a bit misleading. The optimizations that occurred in the microbenchmarks may not actually occur for real-world code. Three branches vs two branches also makes no real difference as you are better served optimizing inefficiencies/performance somewhere else.
Also realloc'ing the most recently allocated object is not a common operation, at least in my experience building memory management systems.
Every time you stream the creation of an object, you're doing a recent-object-realloc. This shows up all the time for serialization, strings, vectors, etc. If you don't think you're doing it, you're probably using a library that hides it from you - or else doing something completely inefficient (in some languages, repeated string concatenation is O(n²)).
If your allocator exposes a "give me an arbitrarily large buffer up front to use, and I will give back what I don't need" that can beat realloc but otherwise you really do need it. I suppose on platforms without `mremap` you might want ?
The other alternative of course is "keep a list of small fragments, and join them at the end", but that just moves the `realloc` up a level, and is likely to give you fragmentation (which in some cases might even prevent the final allocation from succeeding).
This doesn't seem right. The optimal direction for a call stack to grow is ISA dependent. I'd expect bump allocation to be likewise - either it doesn't matter at all, or the specific instructions available mean one is better.
I think what has happened here is the original post chose a specific representation for the start/current/end tuple and given that representation one direction was better, then the follow up post took that representation as foundational and noticed that some of the branches can be rolled together.
There's lots of representations available for start/current/end. It should always be possible to have arithmetic followed by a single branch, where you pick the state representation to make the test cheaper for a given direction on a given ISA.
What other representations of "start/current/end" do you know of? Both versions just use 3 pointers. I am not aware of specific instructions on any architecture that would impact the direction the heap grows. They essentially boil down to adds, subtracts, and and's.
Start as void*, current and/or end as size_t offsets from start is common.
The opposite way round works too, use a void* for end and current and/or end as offsets from that. 64 bit pointer and two 32 bit offsets might appeal on x64.
Without working through the arithmetic now I'd expect storing (size-current)=remaining instead of current to work well for the out of space check.
If your program has nice boundaries, an alternative to realloc is to just calloc far more memory than you are ever likely to need. Obviously this is a bad idea in certain circumstances, but works really nicely for things like a compiler with well defined entry/exit points. With this technique, you only need one branch in the up allocator to check for an oom (or you can yolo and remove this check if you are quite sure you won't oom).
In code, I essentially implement bump allocation (for a global allocator, though this could be adapted easily to reference an arena) in the following way:
They're (effectively) the same. Bump allocation is the term in GC literature and is the more general term. Arena allocation can be slightly more nuanced as you can throw an entire arena away after you're done with it (if your problem domain allows for it). But arena allocation is just a kind of bump allocation for all intents and purposes.
Bump allocation specifically means doing nothing but moving a pointer by a displacement related to the object size.
While "arena allocator" is also used for the same thing, it doesn't exclusive have that meaning. It also refers to region-based memory management in general. An arena allocator can be versatile, allowing objects of different sizes to be freed in any order, and coalesced for new allocation. The arena part of is that the application can throw the whole arena away in one operation.
Bump allocation isn't always used inside arenas that can themselves be allocated or freed. It can be global also. Operating system kernels use such an approach for initialization-time allocation of permanent objects. The classic Unix sbrk() mimics that.
"Arena" is a heavily overloaded term. Usually arenas have more logic than a mere bump allocator though. Sometimes "arena" means "thread-local cache", so objects can be free'd to a different arena than they came from, etc. Arenas might be a single finite-size underlying allocation or contain multiple of those dynamically. Arenas might be able to answer the question "did this arena allocate this pointer originally"? Arenas might be user-facing objects or internal implementation details only.
21 comments
[ 642 ms ] story [ 1223 ms ] threadThat said, there's one useful feature that regrettably is poorly supported in most allocator discussion - where some higher alignment is wanted but not at the exact start of the object.
Microsoft has the only major allocator that I'm aware of that supports this; it uses the "align at offset" sense (which simplifies the case of prepending a header to an aligned object). GCC has some minimal support and uses the "align with offset" sense (which IMO makes literally everything else much easier). As a minimal example, if 0x4 is the low nybble of your pointer, Microsoft calls that "align 16 at offset 12", whereas GCC calls it "align 16 with offset 4".
Note that regardless of sense, you can store both the alignment and the offset in a single integer-sized variable by using your compiler's "find highest bit" or "round down to a power of 2" intrinsic. By exclusively using wrapper objects you can in fact hide the internally-chosen sense and support both publicly. This does however remove the possibility of only passing the log of the alignments, popular on BSD allocators.
Limiting `align` to positive `isize` is useful, but further restrictions can reduce the number of overflow checks you often need. I have never found a practical use (mostly: considering huge pages) for more than 3/4 of the bits to be used on alignment - that is, 6 bits (64, a typical cacheline nowadays) for 8-bit pointers, 12 bits (4K, a typical non-huge page nowadays) for 16-bit pointers, 24 bits (16M - suported on many ISAs, just not x86) for 32-bit pointers, and 48 bits (256T - theoretically available on RISC-V) for 64-bit pointers. You'll likely want a +1 when you use this, at least if you implement the logic the way I did.
Putting those together, the generic interface would be "get a pointer with minimum alignment A, with at least N bytes available before the pointer and at least M bytes available after". Usually N=0, but N=4 would give you a word to store a size before the data etc.
That's also easy to implement on a bump allocator. I think it's a reasonable choice for the implementation with convenience wrappers for the common cases.
The only thing "one function" simplifies is writing interceptor libraries, and that's not sufficiently motivating (especially given that OO is a better idea). Note that it's possible for partial interception to be detected and fall back to the generic method via `if (unlikely(interposer_detected))` in every ABI-exposed implementation function.
My initial design signature for this was:
But when I actually implemented this I ended up adding an `Allocator *this` argument, then making this an inline function with fixed logic dispatching to malloc/realloc/free-like functions (but with more arguments) as needed (including a fallback if realloc isn't implemented).Unfortunately it turns out recent versions of both GCC and Clang are gratuitously buggy regarding `malloc_usable_size` (and libcs took "advantage" of it then retroactively changed their documentation, breaking userland). Also, it turns out to be extremely useful if your libc supply a "realloc in place only" function, usually named something like "expand", but this too is not widely supported at all. Thus to make this useful I would have to implement a complete allocator, not a shim. So I kind of quit in disgust/exhaustion.
The most general allocator interface described, vmem_xalloc(), includes a "phase" parameter (their name for "align at offset"), as well as a "nocross" parameter (in case you want your oddly-aligned object to not cross a page boundary).
Anyway, added that and other flags in that paper to my central list at https://gist.github.com/o11c/6b08643335388bbab0228db763f9921...
Also realloc'ing the most recently allocated object is not a common operation, at least in my experience building memory management systems.
If your allocator exposes a "give me an arbitrarily large buffer up front to use, and I will give back what I don't need" that can beat realloc but otherwise you really do need it. I suppose on platforms without `mremap` you might want ?
The other alternative of course is "keep a list of small fragments, and join them at the end", but that just moves the `realloc` up a level, and is likely to give you fragmentation (which in some cases might even prevent the final allocation from succeeding).
I think what has happened here is the original post chose a specific representation for the start/current/end tuple and given that representation one direction was better, then the follow up post took that representation as foundational and noticed that some of the branches can be rolled together.
There's lots of representations available for start/current/end. It should always be possible to have arithmetic followed by a single branch, where you pick the state representation to make the test cheaper for a given direction on a given ISA.
The opposite way round works too, use a void* for end and current and/or end as offsets from that. 64 bit pointer and two 32 bit offsets might appeal on x64.
Without working through the arithmetic now I'd expect storing (size-current)=remaining instead of current to work well for the out of space check.
In code, I essentially implement bump allocation (for a global allocator, though this could be adapted easily to reference an arena) in the following way:
I tend to use a huge value like 1GB for max_mem, which I know is extremely unlikely to be triggered when compiling a normal sized source program.Like running your code on the most popular desktop OS in the world?
While "arena allocator" is also used for the same thing, it doesn't exclusive have that meaning. It also refers to region-based memory management in general. An arena allocator can be versatile, allowing objects of different sizes to be freed in any order, and coalesced for new allocation. The arena part of is that the application can throw the whole arena away in one operation.
Bump allocation isn't always used inside arenas that can themselves be allocated or freed. It can be global also. Operating system kernels use such an approach for initialization-time allocation of permanent objects. The classic Unix sbrk() mimics that.
Btw, some alternative GlobalAllocs:
https://github.com/lemonrock/context-allocator
https://github.com/gnzlbg/jemallocator
https://github.com/raviqqe/bdwgc-alloc
https://github.com/jmcomets/tcmalloc-rs
https://github.com/sunjay/mgc