What Is in a Rust Allocator?
blog.sulami.xyz
What Is in a Rust Allocator?
1–10 of 15 posts
Re: What Is in a Rust Allocator?
#2I 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.
Re: What Is in a Rust Allocator?
#3I 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 t…
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...
Re: What Is in a Rust Allocator?
#4I 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 t…
The growable array type would use `realloc` when growing, which can make use of this internal information without exposing it.
Re: What Is in a Rust Allocator?
#5I 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 t…
[deleted]
Re: What Is in a Rust Allocator?
#6I 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 t…
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.
Re: What Is in a Rust Allocator?
#7I 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 t…
[deleted]
Re: What Is in a Rust Allocator?
#8I 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 t…
The growable array type would use `realloc` when growing, which can make use of this internal information without exposing it.
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.
Re: What Is in a Rust Allocator?
#9I 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 t…
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.
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.
Re: What Is in a Rust Allocator?
#10I 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 t…
The APIs do tell you how many bytes are actually allocated. For instance, in the following
fn allocate(&self, layout: Layout) -> Result, AllocError>;