What Is in a Rust Allocator? (opens in new tab)

(blog.sulami.xyz)

94 pointssulami1y ago12 comments

12 comments

I have never investigated why, but each time I look at this API it strikes me that the allocator isn't allowed to tell you how much space it actually gave you.

Suppose I'm an allocator which only has power-of-2 sized spaces to hand out, and you're a growable array type and you want enough space for 20 of your 52 byte entries. So that's 20x52 = 1040 bytes, but my smallest suitable space is 2048 bytes. I can give you that space, but it seems like it'd be nice for me to say oh, here's 2048 bytes, and now the growable array type knows its new total capacity is not 20 but 39.

pitaj1y ago

The APIs do tell you how many bytes are actually allocated. For instance, in the following

    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError>;

You can get the length of the returned byte slice (`[u8]`) to know how many bytes were actually allocated.

tialaramex1y ago

That's the (nightly) Allocator::allocate, but the API we were looking at is (stable) GlobalAlloc::alloc

Yes I'm aware that I can ask how long a slice is.

1 more reply

filmor1y ago

The growable array type would use `realloc` when growing, which can make use of this internal information without exposing it.

wongarsu1y ago

Like most implementations, if you add items to a rust `Vec` one item at a time it doubles in size each time it hits its capacity (to make sure insert is amortized to O(1) even though each realloc potentially requires an O(n) memcpy). With the described allocator that would never lead to a cheap realloc.

It's even worse for types like HashMaps where reallocs can be much more expensive than just a big memcpy.

2 more replies

hawski1y ago

You may be familiar, but I just wanted to show how it is available in many C implementations and is used, for example, in QuickJS: https://github.com/bellard/quickjs/blob/0c8fecab2392387d76a4...

khuey1y ago

Things like malloc_usable_size() exist but you're not supposed to use the overage it tells you about so they're not very useful APIs.

darby_eight1y ago

This can be instrumented by the compiler or more likely runtime to detect buffer overruns. Imperfectly of course if you share the page(s) with other allocations but it's worth considering.

j / k navigate · click thread line to collapse

12 comments

tialaramex1y ago

I have never investigated why, but each time I look at this API it strikes me that the allocator isn't allowed to tell you how much space it actually gave you.

pitaj1y ago

The APIs do tell you how many bytes are actually allocated. For instance, in the following

    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError>;

You can get the length of the returned byte slice (`[u8]`) to know how many bytes were actually allocated.

tialaramex1y ago

That's the (nightly) Allocator::allocate, but the API we were looking at is (stable) GlobalAlloc::alloc

Yes I'm aware that I can ask how long a slice is.

1 more reply

filmor1y ago

The growable array type would use `realloc` when growing, which can make use of this internal information without exposing it.

wongarsu1y ago

It's even worse for types like HashMaps where reallocs can be much more expensive than just a big memcpy.

2 more replies

hawski1y ago

You may be familiar, but I just wanted to show how it is available in many C implementations and is used, for example, in QuickJS: https://github.com/bellard/quickjs/blob/0c8fecab2392387d76a4...

khuey1y ago

Things like malloc_usable_size() exist but you're not supposed to use the overage it tells you about so they're not very useful APIs.

darby_eight1y ago

This can be instrumented by the compiler or more likely runtime to detect buffer overruns. Imperfectly of course if you share the page(s) with other allocations but it's worth considering.

j / k navigate · click thread line to collapse