14 ms·
Always Bump Downwards (2019)
- gjm11 3y agoSince the title is less than perfectly perspicuous: It's about "bump allocators", where you allocate memory just by incrementing/decrementing a pointer (and don't free it until you're ready to free up all the memory all at once). These can either allocate "upwards", starting at low addresses and giving you memory at higher addresses for successive allocations, or "downwards", going the other way. The claim being made is that "downwards" is better, because the bounds checks you need to do turn out to be more efficient that way; allocation ends up using fewer instructions, fewer registers, and fewer conditional jumps.
- chrchang523 3y agoIncidentally, you can choose to bump in both directions. It's more complicated (you need to keep track of which end you allocated each data structure on), but in exchange, the allocator becomes sufficient for many more use cases. Given a choice, the OP implies that you should position small-but-numerous allocations next to the top, and larger infrequent allocations next to the bottom.
- dev_dwarf 3y agoThis sounds like it would make the alloc logic much more complicated and branch-y, defeating the purpose of bumping down anyway, unless your implying some compile-time way to do this.
- chrchang523 3y agoNo, the idea is that you manually make some allocations downward from the top and some allocations upward from the bottom. The bumping code is as simple as in the unidirectional case. The tricky part is choosing in a way that puts you noticeably ahead of the unidirectional allocator re: what problems you can solve, without putting excessive mental load on yourself. I've found a pattern of "long-lived allocations on one end, short-lived allocations on the other" to work well here (which, yes, doesn't always coincide with the numerous vs. infrequent axis mentioned in my previous comment).
- dev_dwarf 3y agoOk, I get it now. It would add an extra ptr to the struct, but wouldn't be significant overhead. I do wonder what benefit there is for you over just having two separate allocators, one for long term and one for short term. I imagine there could be benefits in very memory constrained scenarios.
- Conscat 3y agoA double ended stack allocator is not an uncommon primitive in video games.
- toast0 3y agoBEAM (Erlang) uses something similar for process memory; a process gets a chunk of memory, heap grows up, stack grows down; when they meet, trigger GC, and if that doesn't reclaim enough, allocate a larger chunk of memory. More details if you're interested [1]. In general, I'd think anywhere that the combined size of two allocators should be a consideration, one going up and one going down would make a lot of sense. [1] https://www.erlang.org/doc/apps/erts/garbagecollection https://www.erlang.org/doc/apps/erts/garbagecollection
- dev_dwarf 3y agoThats an interesting idea. I'm not sure I'm sold on it v.s. just having two seperate allocators and growing them seperately. The arena allocators I use take advantage of virtual memory to grow which might change my perception of the tradeoffs involved, as I wouldn't typically need to resize one of my allocators (you can just aggressively over-reserve memory and then only commit what is actually used).
- svat 3y ago> manually make some allocations downward from the top and some allocations upward from the bottom Incidentally, this is what Knuth does in TeX, if I understand correctly: http://mirrors.ctan.org/info/knuth-pdf/tex/tex.pdf#page=43 http://mirrors.ctan.org/info/knuth-pdf/tex/tex.pdf#page=43 (section 116): > The mem array is divided into two regions that are allocated separately, but the dividing line between these two regions is not fixed; they grow together until finding their “natural” size in a particular job. Locations less than or equal to lo_mem_max are used for storing variable-length records consisting of two or more words each. […] Locations greater than or equal to hi_mem_min are used for storing one-word records… (Different allocators are used for the two regions and neither seems to be a bump allocator, so it's probably not very relevant to this thread, but I was reminded of it so just sharing…)
- benmanns 3y agoSomewhat aside, I love the graphical display of the benchmark results: https://fitzgeraldnick.com/media/bumpalo-switch-to-downwards-bumping-criterion-report.svg https://fitzgeraldnick.com/media/bumpalo-switch-to-downwards... --I think I'll start doing that when I run benchmarks in the future.
- thethirdone 3y agoNotably, that graph starts at 25 which seems misleading.
- lowbloodsugar 3y agoSo lesson is don’t use safe Rust code when writing something like a memory allocator where an overflow check is deemed by the author to be too slow? Update: >To handle both these cases, we will use checked addition and return a null pointer if either addition overflows. Here is the new Rust source code: I’m still filling this under “Author made arbitrary decision and result is arbitrary solution is slower as a result of arbitrary decision”.
- pavon 3y agoI don't think Rust is the issue here. The same integer overflow can occur in any language and should be checked. Integer overflow and underflow is one of the most common security bugs after memory access errors. It is more that bump allocators are so efficient that a relatively inexpensive overflow check can be a significant fraction of their runtime.
- kazinator 3y agoIt's not integer overflow but pointer overflow. If you're doing small bump allocations and you're anywhere near pointer overflow, it means you're way out of bounds already; the bump allocations you already made were wrong. You need to check whether the allocation increment is out of the zone from which you're allocating, and you need that no matter which direction you go. If the requests are small, you will hit the end of your arena long before you worry about pointer overflow at the zero address or at address 0xFF..FF! That said, aligning down is a shade faster than up. To align down to a boundary divisible by ALIGN_MASK + 1 we just truncate some low order bits to zero: addr &= ~ALIGN_MASK; If the bits are already zero, the address doesn't move; all is cool. but aligning up, where we don't care about overflow, requires handling the case where the address is already aligned and doesn't have to move: if (addr & ALIGN_MASK) { addr |= ALIGN_MASK; addr++; } Or a trick like this where we bias the address with an offset of -1 during the masking calculation: addr = ((addr - 1) | ALIGN_MASK) + 1; (We could get underflow here if addr is the zero address (null pointer on most systems), but it's reversible if the pointer arithmetic is done as unsigned. Zero aligns to zero: it goes to 0xFFF..FFF which stays the same after | 7, and then increments back to zero.) Either of these is worse than just addr &= ~7.
- dev_dwarf 3y agoIn the "bump up" version you could remove both the checked_add branches and replace them with a single check at the end, making the amount of branches the same. Quick example: https://godbolt.org/z/rdv4qnrs8 https://godbolt.org/z/rdv4qnrs8. *edited to update the example, realized I messed up the comparison logic.
- ridiculous_fish 3y agoI think this doesn't work because `aligned + size` may wrap all the way around into the valid region again. For example if aligned == ptr + 1, and size is usize::MAX, we will end up with new_ptr == ptr and the allocation will wrongly succeed.
- loeg 3y agoThe straightforward answer is: don't tolerate ridiculous alignments.
- dev_dwarf 3y agoInteresting point. I modified my example to test what you described. I had to play with the compilation flags to get the allocs to not be optimized out and to not panic when the integer overflow happens, but otherwise I didn't change the logic. I'm pretty sure my implementation is correctly handling the case you mention, evidenced by it returning a null pointer. Link: https://godbolt.org/z/f1jGW6Pa3 https://godbolt.org/z/f1jGW6Pa3 Update: NVM, definitely not being handled correctly. https://godbolt.org/z/cMTe1o979 https://godbolt.org/z/cMTe1o979
- justin_oaks 3y agoI only recently learned about bump allocators. I was very confused as to how such an allocator could be useful. In reading the author's bumpalo crate [1] documentation, he cleared up my confusion. For one thing, this particular allocator is separate from the general allocator so the calling code can choose when to use the bump allocator. Quoting the crate doc: > [B]ump allocation [is] well-suited for phase-oriented allocations. That is, a group of objects that will all be allocated during the same program phase, used, and then can all be deallocated together as a group. I can see this being useful as a way to optimize allocation/deallocation speed for specific use-cases. [1] https://docs.rs/bumpalo/latest/bumpalo/ https://docs.rs/bumpalo/latest/bumpalo/
- ph4evers 3y agoIt is also used in WASM. I guess to increase memory safety
- saagarjha 3y agoBump allocators are very simple in an environment where everything you want must be brought with you.
- loeg 3y agoIt's great when you don't need destructors and have a bunch of small objects to allocate with similar lifetimes.
- ridiculous_fish 3y agoThe insight here is that, for unsigned values, rounding down to a multiple of N is cheaper than rounding up to a multiple of N. In addition to simpler arithmetic, rounding down always succeeds - 0 is a multiple of all N - while rounding up may fail if a larger multiple does not exist. So you need to check in the round-up case.
- pizlonator 3y agoIt’s possible to write many other bump algorithms, including ones that bump upwards but generate much much better code than OP’s forward upward bump. In particular, no overflow checks are needed if you write it carefully enough. My favorite is one where I only use subtraction but the direction of allocation is in the positive direction (I subtract a `remaining` counter, and the returned address is `end - remaining`). But I have seen many others. A few of my colleagues have similarly geeked out on this and come up with splendid bumpers (ggaren wrote a great one in bmalloc, and I remember the MMTk folks put hella thought into theirs).
- titzer 3y agoIn most situations, the allocation size is a constant and bumping upwards can be done without an overflow check because the region cannot be close enough to the upper part of memory to wrap around. I'm surprised that there was no discussion of memory system performance. There are tons of OS-level and hardware prefetcher optimizations for forward-marching pointer references and zero-page allocation.
- pizlonator 3y agoYou can bump upwards without an overflow check even if the size is variable. I’ve seen multiple ways to do it. And I’ve lost days of my life to coming up with pointlessly amusing variants that get there in weird ways. Yeah I’m also amused that they didn’t get into the fact that downward bump is just not what the HW expects you to do. You’d need a real benchmark to see that effect. And, it’s an open question whether this would matter unless your allocation rate was obscene (if it isn’t then most scans of memory will be normal loops and not the allocator).
- zeusk 3y ago> fact that downward bump is just not what the HW expects you to do. Where do you get this fact from? ARM and x86 have a descending stack (<= ARMv7 supported stack growing in either direction).
- sltkr 3y agoYou can also implement BumpUp() with only two conditionals and no overflow like this (in C, because I don't know Rust, but the logic is identical): size_t alignment_needed = align - (ptr & (align - 1)); if (alignment_needed > SIZE_MAX - size) return nullptr; size_t space_needed = size + alignment_needed; size_t space_remaining = end - ptr; if (space_needed > space_remaining) return nullptr; char *result = ptr + alignment_needed; ptr += space_needed; return result;
- dev_dwarf 3y agoNice. Seems to work for case you mentioned under my comment: https://godbolt.org/z/TYorcd8b6 https://godbolt.org/z/TYorcd8b6
- loeg 3y agoYeah, and you only need one check if you can restrict the allocation pointer to be at least max alignment away from SIZE_MAX, which is very easy to do in practice. Max alignment needed is usually no more than 64 bytes, but even 4kB isn't especially burdensome. On Linux/amd64, you don't even need to do anything special -- the high virtual address space is likely reserved for the kernel anyway.
- sam_bishop 3y agoI've heard that the Hotspot JVM uses a bump allocator but don't know the details. I'm sure it's heavily optimized though, so I'm curious about how this compares.
- dzaima 3y agoFor most specific purposes, a specialized bump allocator can be significantly more optimized. Hard-coding the alignment simplifies many questions (especially if you can guarantee the allocation size being a multiple of the alignment, at which point it becomes a complete non-issue). And if you have an upper bound on the requested allocation size, the integer overflow checks can be dropped too (e.g. in a Java "new int[n]", "n" is an int, which has a max value of 2^31-1, which can safely be added to a bump pointer, provided it's further than that away from the address space end (which it's gonna be due to the kernel reserving the upper half of the address space)). And for constant-size objects, your entire bump allocator can become just if (ptr > precomputedEndMinusObjectSize) fallback(); result = ptr; ptr += size;
- saagarjha 3y agoI believe HotSpot can move allocations out of the arena when garbage collection happens, which means fragmentation is less of an issue.
- tjalfi 3y agoHere's an article[0] with some information on Hotspot's bump allocators. [0] https://shipilev.net/jvm/anatomy-quarks/4-tlab-allocation/ https://shipilev.net/jvm/anatomy-quarks/4-tlab-allocation/
- asalahli 3y agoThe rust code for rounding down is given as let new_ptr = new_ptr & !(align - 1); But I don't see rdx decremented before being negated and AND'ed with rax, in the assembly. What am I missing?
- conradludgate 3y agoIt's being converted into `-align` which is equivalent under twos compliment
- asalahli 3y agoI don't follow. Are you saying `new_ptr & -align` is equivalent to `new_ptr & !(align - 1)`? Edit: I get it now. My brain was interpreting NEG as NOT for some reason.