Comments for "https://os.phil-opp.com/allocator-designs/"

[utterances-bot]

This is a general purpose comment thread for the Allocator Designs post.

[senseiod]

Great!

[MikailBag]

Thanks for the post! As usual, it is very interesting!

Since the Heap type of the linked_list_allocator crate does not implement GlobalAlloc (as it's not possible without locking).

looks like typo

[engstad]

The align_up function could be improved by removing the if-test. Notice that if addr is already aligned, then (addr + align - 1) / align * align equals addr, whereas if it is not, then it equals (addr + align)/ align*align or addr/align*align + align or align_down(addr) + align.

fn align_up(addr: usize, align: usize) -> usize {
    (addr + align - 1) / align * align;
}

Or, if you use powers of two as argument instead:

fn align_up_pow2(addr: usize, align_pow2: usize) -> usize {
    (addr + align - 1) >> align_pow2 << align_pow2
}

[engstad]

I should mention that when using a BumpAllocator, that you could have extended the functionality a bit.

First, while you normally can't delete entries from the allocator, you can delete the last entry. In other words, if you know what you are doing, you can allow a reset() function that takes the address of an allocation resetting the allocation to that point. Highly dangerous if you don't know what is going on, but you can safeguard it somewhat if you know that it was the last allocation. This makes it a "stack" allocator.

Second, it is common practice to allocate from both the front and the back of the memory region. This is useful where some of the allocations are temporary. You put temporary allocations at the end, while longer-lasting allocation are put in the front.

Anyway, both these methods are quite dangerous, but in terms of raw speed, there's no comparison.

[phil-opp]

@engstad

Thanks for your comments!

The align_up function could be improved by removing the if-test.

Good point! I'll extend that section. The fastest variant I'm aware of is relying on the optimized align_offset implementation of Rust's standard library:

#[no_mangle]
fn align_up(addr: usize, align: usize) -> usize {
    let offset = (addr as *const u8).align_offset(align);
    addr + offset
}

First, while you normally can't delete entries from the allocator, you can delete the last entry. In other words, if you know what you are doing, you can allow a reset() function that takes the address of an allocation resetting the allocation to that point

One could also check in deallocate whether the end address of the freed allocation equals next. However, this way we could not recover inserted allocation bytes.

Second, it is common practice to allocate from both the front and the back of the memory region. This is useful where some of the allocations are temporary. You put temporary allocations at the end, while longer-lasting allocation are put in the front.

Good point! While this is difficult to implement for a global allocator, it definitely works for manual allocations.

I try to update the bump allocator discussion section with both your suggestions.

[phil-opp]

@engstad I prepared two updates for the post related to your comments. #721 adds more variants to implement align_up and shortly discusses their performance. #722 outlines the two bump allocator improvements you mentioned. What do you think about the changes?

[phil-opp]

@senseiod Thanks!

[phil-opp]

@MikailBag Thank you! Could you maybe clarify what the typo is? I don't see it right now…

[amosonn]

Nice comparison, thanks!

For more on bump allocation, see this post (in Rust, even):
https://fitzgeraldnick.com/2019/11/01/always-bump-downwards.html
To summarize, his rounding method is:
(size + align - 1) & !(align - 1)
(which relies on align being a power of 2 of course); and he comments that allocation arithmetic should be checked for overflows (which is the case for all allocators), and that then bumping from the end is more performant.

Also small typo in the beginning:
"This complexity is often undesired [...]"
(the "is" is missing).

[phil-opp]

@amosonn Thanks for you comment!

For more on bump allocation, see this post (in Rust, even):
https://fitzgeraldnick.com/2019/11/01/always-bump-downwards.html

I already link this post in the Dicussion section as "can be optimized to just a few assembly operations". I deliberatly decided against bumping from the end because the intention of the post is to explain a basic implementation, not to maximally optimize it. Regarding the alignment function: I think the align_offset function from the standard library should still be faster, given how optimized it is (see rust-lang/rust#50319).

allocation arithmetic should be checked for overflows (which is the case for all allocators)

Good point! I'll prepare a PR to fix this.

Also small typo in the beginning:

Thanks! Fixed in 4b8c902.