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

21–30 of 74 posts

Re: Always Bump Downwards (2019)

#21

Post by dev_dwarf »

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…

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

Re: Always Bump Downwards (2019)

#22

Post by ridiculous_fish »

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.

Re: Always Bump Downwards (2019)

#23

Post by justin_oaks »

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 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/

Re: Always Bump Downwards (2019)

#24

Post by ridiculous_fish »

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

Re: Always Bump Downwards (2019)

#25

Post by pizlonator »

It’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).

Re: Always Bump Downwards (2019)

#26

Post by sltkr »

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

Re: Always Bump Downwards (2019)

#27

Post by dev_dwarf »

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.

Interesting 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

Update: NVM, definitely not being handled correctly. https://godbolt.org/z/cMTe1o979

Re: Always Bump Downwards (2019)

#28

Post by [deleted] »

dev_dwarf wrote: post #27
ridiculous_fish wrote: post #22

Earlier quoted context omitted.

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.

Interesting 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 Update: NVM, defi…

[deleted]

Re: Always Bump Downwards (2019)

#29

Post by ph4evers »

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 is also used in WASM. I guess to increase memory safety

Re: Always Bump Downwards (2019)

#30

Post by sltkr »

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 + alignment_needed;
    ptr += space_needed;
    return result;
Post reply on HN