Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Always Bump Downwards (2019)

fitzgeraldnick.com

Post reply on HN
Print view View original

31–40 of 74 posts

Re: Always Bump Downwards (2019)

#31

Post by dev_dwarf »

sltkr wrote: post #30

You 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 + align…

Nice. Seems to work for case you mentioned under my comment: https://godbolt.org/z/TYorcd8b6

Re: Always Bump Downwards (2019)

#33

Post by loeg »

sltkr wrote: post #30

You 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 + align…

Yeah, 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.

Re: Always Bump Downwards (2019)

#34

Post by loeg »

ridiculous_fish wrote: post #22
dev_dwarf wrote: post #12

In 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 . *edited to update the example, realized I messed up the comparison logic.

I 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.

The straightforward answer is: don't tolerate ridiculous alignments.

Re: Always Bump Downwards (2019)

#35

Post by loeg »

sltkr wrote: post #26
dev_dwarf wrote: post #12

In 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 . *edited to update the example, realized I messed up the comparison logic.

That version is unsafe: what if size == 0xfff..fff and alignment is needed? You will end up with ptr edit : code moved to a toplevel comment

No allocator can be expected to allocate usize::MAX, so it doesn't really matter.

Re: Always Bump Downwards (2019)

#36

Post by loeg »

justin_oaks wrote: post #23

I 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 a…

It's great when you don't need destructors and have a bunch of small objects to allocate with similar lifetimes.

Re: Always Bump Downwards (2019)

#37

Post by lowbloodsugar »

tel wrote: post #17
kazinator wrote: post #9

Earlier quoted context omitted.

It'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 e…

I would definitely be in favor of an even faster `SmallBump` variant which assumes that the allocations are small w.r.t. usize::MAX for some additional speed. I also wouldn't mind the a default "fast" bump allocator library to do all tricks it can without sacrificing safety.

And maybe the heap has fixed alignment so you have one that only needs 4 and one that needs 16. Indeed maybe you grow from top and bottom depending. And maybe this is all a giant premature optimization - including the panic about up vs down. My previous career was console video games and maybe this kind of handwringing isn’t required for whatever the fuck this is.

Re: Always Bump Downwards (2019)

#38

Post by dev_dwarf »

loeg wrote: post #35
sltkr wrote: post #26

Earlier quoted context omitted.

That version is unsafe: what if size == 0xfff..fff and alignment is needed? You will end up with ptr edit : code moved to a toplevel comment

No allocator can be expected to allocate usize::MAX, so it doesn't really matter.

Agreed. The question really is if you should demand the user to enforce that constraint on the size they pass to you, or if the function itself should signal an error in that case.

Re: Always Bump Downwards (2019)

#39

Post by dzaima »

sam_bishop wrote: post #32

I'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.

For 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;

Re: Always Bump Downwards (2019)

#40

Post by svat »

chrchang523 wrote: post #20
dev_dwarf wrote: post #16

Earlier quoted context omitted.

This 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.

No, 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 o…

> 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 (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…)

Post reply on HN