> This one is probably closest to what one would write in languages like C++. The data structure just assumes the allocator will outlive it, and it is up to the user to either use an static allocator, or pretend to using unsafe code to cast away the lifetime while making sure that the allocator outlives the data structure without the compiler's support.
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.
The value proposition of Rust is precisely having zero-cost abstractions and highest-performance code with compile-time verification of correctness.
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.
We can talk in specifics: this example was about making people use unsafe to avoid having to type <'static> in the general case. The author had been trying for a number of paragraphs to avoid polluting the type name with generics or lifetimes. This is what going too far looks like.
The std APIs look like this:
struct Box<T, A: Allocator = Global>
And it’s been this way in stable releases for the last year or so. The same has been done for Vec and all the other std::collections. What percent of Rust programmers do you think even noticed at all? 1%? The most flexible design and the least impacting on regular users. You can use A = &'a dyn Allocator if you like, equally you can choose a ZST and not pay for 16 bytes of storage. The library author has no need to choose in advance at all, which is great if they’re determined to make weirdly constrained choices, ultimately forcing most uses of the API to be unsafe. I stopped reading after that so I don’t know which design they went for.
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.
Rust already has almost exactly this problem with keeping track of the current task in the async framework. As far as I know, the solution is indeed to use a thread local, and be scrupulous about updating it on task entry. It's ugly but it seems to work.
And if the generated documentation is really the main sticking point, it would be perfectly possible to special case the allocator type parameter in rustdoc so that it hides or otherwise deemphasizes it.
As someone who mainly uses higher level languages, doesn't care for C/C++ and really likes Rust, I'm glad it was named so strongly and that safety and correctness is very important in the community.
It creates a strong incentive to only write safe Rust, which is great for the vast majority of people.
In this case it would be nice if operations that are type-safe and don't read or write memory at all, such as mm256_shuffle_epi8, were available in safe rust.
This is helpful for the use cases that want to rearrange bytes in a fixed pattern, but it cannot yet express a stream vbyte decoder (out = pshufb(in, shuffle_patterns[len_mask])) or a check for which bytes are in small set of bytes with distinct lower nibbles and the high bit not set (eq(in, pshufb(set, in))) yet.
If it's to be portable it needs an extra instruction on one platform or the other because tbl and vpshufb do different things :(
I think the incentive to write compiler verifiable Rust would be the same as safe Rust, but with less fear for the situations where you do need to bypass the borrow checker such as with cyclical references in graphs (currently doing this right now by re-writing a basic NN in Rust). Even the standard library uses unsafe for certain situations.
I don’t understand why you want people to be afraid of code though. It’s just code. We don’t need a scary connotation to make people think they should shoot for completely compiler verifiable rust in every line they can write.
What it boils down to is "Users who don't even know what a trigger is should be discouraged from handling footguns". Sure, if you don't have the resources to learn about the subject, you might miss out on some fun, but it's much more likely that you'd blow off your foot instead, which would be much less fun.
User-friendly is subjective. I think it would be more user friendly to tell users "hey, this code you're writing can't be verified by the compiler" rather than "hey, this code is unsafe. beware"
You can already do custom allocation in Rust. These efforts are about bringing support for custom allocators to the types in `std` so that you can combine use of a normal `Vec` with a custom allocator, instead of needing to definte your own `Vec` (or at least pull one in from a 3rd party crate).
You might want custom local allocators. You can already replace the global allocator with one designed to reduce fragmentation, as described in the article.
There's been some side work towards defining dynamic scoping for rust. E.g., allow functions to declare a dependency on some value or type, and then require callers to either pass that dependency explicitly, or have it on their dependencies.
That’s pretty neat. Seems very similar to Jai’s implicit context. I’m definitely a fan of context objects. It solves so many painful problems related to allocators, logging, etc.
Yeah, I think this is a really nice thing to have in a language, purists may not like it, but being able to flexibly pass something through layers is a cheat code for coding.
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).
I think most of the challenges are around making custom allocators safe without harming the ergonomics, which Zig hasn't solved.
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).
Are you just reminding us that Rust does some checks that Zig doesn't, or are you saying that there's some particular footgun in their allocators above and beyond the fact that UAF and other memory bugs are writeable in general?
Neither, I was disagreeing with the comparison to Go and generics.
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.
Zig approach essentially parametrizes instances of containers on the instance of the allocator. To properly support that in the type system one needs dependent types.
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.
I’m pretty sure the ‘logic’ require for paramterizing container types over allocators can be restricted in a wide majority of cases to a linear set which would allow for refinement types to be used. This would eliminate the requirement for full theorem proving.
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.
Are you sure? I have no type theory experience but that sounds trivially expressible in Rust. The issues around making the stdlib allocactor-parametric have been about optimal api design, not theoretical possibility.
That just restricts A to implement Allocator trait and will allow to pass any instance of Allocator when calling methods of MyVect. This is unsafe. What is required for safety is to state that all methods of MyVec that receives the allocator reference can only work with one particular instance of Allocator.
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.
> That just restricts A to implement Allocator trait and will allow to pass any instance of Allocator when calling methods of MyVect.
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).
I think realistically if you want to prove safety of memory provenance in zig, you assume that allocators are sound, and you just track the lifetime of the memory from alloc/create to free/destroy and call it a day. This is probably "good enough", and in rust you're assuming the allocation is sound as well, it's just implicit.
What you get for free with the global allocator is a guarantee that you will use the same allocator for each operation on an allocation. That is the property that is claimed to be difficult to keep if you literally do the Zig thing and have e.g. ArrayListUnmanaged which requires you to pass in the allocator again to free the backing slice.
Ok so those are 'unsafe'. Plenty of safe (when statically checked) data structures in zig, like the managed array list, where the associated allocator is attached to the object.
The article assumes that storing an allocator together with a container inevitably bloats the container by 1-2 CPU words. This is not necessary so. One can require that it should be possible to get the allocator from a pointer it allocates. With many allocator designs this will costs like one CPU word per CPU page which is trivial.
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.
I think that avoiding global allocation and lifetime management is good design and a way to make memory management as simple and flexible as it should.
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 container is basically a structure holding a collection.
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.
How much better is Rusts default than C++? I would expect it to be better since they have all that nice lifetime information on every piece of data. It seems like some nice things could be done with that. Are they?
By default, Rust just delegates to the ordinary libc malloc(), realloc(), and free(). In safe code, allocations are managed through RAII, just like in modern C++. Box works like unique_ptr, Arc works like shared_ptr, Vec works like vector, and so on. Lifetime annotations are just a way for the programmer to tell the compiler that none of the rules are being broken: they don't actually affect the semantics of the compiled program, they just make it fail to compile if there is an error. The underlying UB rules (except for those around unique references) are not much stricter than those required by C++; meanwhile, the lifetime rules are fairly strict, but the compiler cannot optimize based on them.
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.
My problem with the allocaor-api is the "big box" problem.
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.
Does anyone know a custom allocator that allocates memory for the same pattern usage? I am trying to find a good allocator for tensor operations used in Burn's framework (https://github.com/burn-rs/burn). It uses the same vectors without any varying size changes.
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.