[HN Gopher] Bump Allocation: Up or Down?
___________________________________________________________________
Bump Allocation: Up or Down?
Author : celeritascelery
Score : 69 points
Date : 2024-03-25 12:24 UTC (10 hours ago)
(HTM) web link (coredumped.dev)
(TXT) w3m dump (coredumped.dev)
| o11c wrote:
| 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.
| JonChesterfield wrote:
| 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.
| bewaretheirs wrote:
| See Bonwick & Adams, "Magazines and Vmem: extending the slab
| allocator to many CPUs and arbitrary resources" from 2001:
| https://www.usenix.org/conference/2001-usenix-annual-technic...
|
| 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).
| JonChesterfield wrote:
| 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.
| norir wrote:
| 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: static unsigned char
| *__mem_base = 0; static unsigned char *__mem_limit =
| 0; static unsigned char *__mem_current = 0;
| void init (size_t max_mem) { __mem_base = (unsigned
| char*) calloc(1, max_mem); __mem_current = __mem_base;
| __mem_limit = __mem_base + max_mem; } #define
| ALLOC(name, type) \ type *name = (type *) __mem_current;
| \ __mem_current += (sizeof(type) + 0x7) & ~0x7; \
| if (__mem_current >= __mem_lim) { fprintf(stderr, "OOM %d",
| __LINE__); exit(1) }
|
| 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.
| IshKebab wrote:
| > Obviously this is a bad idea in certain circumstances
|
| Like running your code on the most popular desktop OS in the
| world?
___________________________________________________________________
(page generated 2024-03-25 23:01 UTC)