Somewhat aside, I love the graphical display of the benchmark results: https://fitzgeraldnick.com/media/bumpalo-switch-to-downwards... --I think I'll start doing that when I run benchmarks in the future.

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

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/

So 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”.

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.

The rust code for rounding down is given as

    let new_ptr = new_ptr & !(align - 1);

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.

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;

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.

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