Custom Allocators in Rust
nical.github.io
nical.github.io
I know many in the Rust community will frown upon this approach, but to be honest I don't think that it is a terrible solution in the context of an advanced feature like custom allocation strategies. Tessellator does not expose an unsafe API, but it documents that if its users were to break the rules they'd simply have to make sure the allocator outlives the data structure. In any other language with this kind of control over memory management, this contract would have to be manually upheld by users of the API and it is considered normal.
… no thanks.
That being said, I don't oppose the occasional judicious use of unsafe. If 99% of your code is verified, it's not 100%, but that's still a massive improvement over a C++ codebase.
The std APIs look like this:
struct Box<T, A: Allocator = Global>
Not quite. For the most general case, you probably want allocator to be a proper parameter instead of a type parameter. For example, suppose you have a green thread that you want to have its own isolated heap. Then you can't assume that any given allocator is a singleton in its type; The struct itself must somehow be able to find to its "owner" on release. In the green thread case you can't "just use threadlocal" because a green thread might not be sticky to an os thread.
It creates a strong incentive to only write safe Rust, which is great for the vast majority of people.
e.g. "mm256_shuffle_epi8" on X64+AVX2, ARM64+NEON and plain ARM: https://rust.godbolt.org/z/7rjKE93Kn
It currently only works with constant shuffle masks but dynamic shuffles are on the to-do list.
If it's to be portable it needs an extra instruction on one platform or the other because tbl and vpshufb do different things :(
That's a pretty tricky thing to get right, and with the consequence for getting it wrong being UB, at least a little fear is warranted.
This is like applications adding artificial delay to operations so users aren't surprised they complete so quickly.
User understanding is more important than definitional correctness.
Can help in incidents like the below:
https://www.svix.com/blog/heap-fragmentation-in-rust-applica...
One of the proposed uses was for allocators.
https://tmandry.gitlab.io/blog/posts/2021-12-21-context-capa... is one of the more cogent proposals.
I don't think any of these has made substantial progreess towards being approved though.
If Rust was content to have use of custom allocators be unsafe it would be trivial to add them (since you could just add new variants of allocating methods that take an allocator as a parameter).
Generics in Go don't add anything beyond what generics already do in other languages, so the challenge with bringing generics to Go is "how do we adapt the language to support a feature that already exists in other languages and is generally well understood". Bringing generics to a language that wasn't designed with them in mind has often resulted in a sub-optimal implementation (eg. Java vs C#).
On the other hand, "safe custom allocators" are not a feature that any language (to my knowledge) has solved. It's not as though this was an oversight in Rust's initial design: using a custom allocator in an unsafe context has always been possible in Rust, and it's too early to say whether bringing this feature into the language later will result in a similarly sub-optimal design: in order to be sub-optimal there would have to exist some better solution out there, and there currently doesn't.
In theory that can be done, but the consequences for the compilation time will be extreme as the compiler becomes essentially a generic theorem prover.
Plus the noise from the proofs in the sources will be much bigger than that of type parameters.
In fact, it would probably be acceptable to insist on keeping the scope of parameterization limited to the linearly determinable set of values and operations on those values.
Perhaps it is possible to specialize for that case a generic prover, but I am sceptical that the effect on compilation timing will be minimal.
Just write
struct MyVec<T, A> { ... }
impl<T, A: Allocator> MyVec { ... }To make this compile-time safe in Rust a typical approach is to embed the Allocator reference in MyVect and use regions to ensure that allocated data do not outlive the allocator. This bloats MyVect with a reference to the allocator. To workaround this one specializes for static allocators to eliminate the need to embed the reference to those in MyVect.
An alternative that is not covered in the article is to require that a reference to the allocator can always be deduced from the allocated data. This solves the bloating problem as the overhead can be reduced to a word per allocation page which is typically at least CPU page in size.
Still even with this the result is not optimal especially with arena-style allocators when one wants to ensure the max performance of tiny allocations.
No, that kind of rust generic requires monomorphization rather than dynamic dispatch. Any given Vec must have a specific A, just like it must have a specific T.
> To make this compile-time safe in Rust a typical approach is to embed the Allocator reference in MyVect
Yeah, that was implied by the "...". It won't compile otherwise, generics have to be used (including by PhantomData).
But I understand the problem better now. You're right, there's no good way in the type system to specify "you must always provide the same instance of this allocator when calling any method on this vec". (I'm ignoring branding because I think it's not practically convenient).
This still requires to parametrize the container on the type of the allocator, but there will be no penalty on the size of the containers and the API will be safe.
But, from my own work in the field, I came to the conclusion that there is a better way than passing custom allocators: passing containers instead.
In practice this is almost the same thing (except that containers are made to be easily traversed) but semantically there is a subtle and positive difference.
The goal is to avoid confusing the allocating policy (let's say arena versus heap) with the allocator instance.
A good abstraction for passing allocators could be effect and effect handler.
In that case, the container also acts as an allocator (the feature can be embedded directly or not)
The only practical difference is that a container should provide some facilities for traversal, while the allocator is only taking care of allocating and freeing.
From my experience, I very rarely allocate things without keeping them in a kind of container, it can be something as simple as an array of references.
At best, the lifetime system could allow you to use a faster design for your library, by placing tighter compile-time constraints on allowed use cases than you could have feasibly documented in a C++ library's interface. But examples of this are not too common in my experience, since most find it acceptable for C++ libraries not to accommodate sufficiently weird use cases.
That is, Box<T, A> is a struct containing both a pointer to T and an allocator handle A.
With an arena allocator, the handle A would be a pointer to the arena. But when using an arena, you don't actually need the box to retain the A after the initial allocation. Deallocation is a no-op; storing A is just wasting 8 bytes.
To get around this, Bumpalo (a prominent arena allocator) defines it's own box type rather than using the std Box. I'm not sure how I feel about that solution.