Great to see some movement in this area for Rust. Compared to Zig which had this from day 1 it may be hard to adjust Rust (the way it was hard for Go to adopt generics).
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).
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).
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.