Closed Avi-D-coder closed 4 years ago
I think it would be better to add a new trait for type aware allocators, such as
trait TypedAlloc<T> {
fn alloc_array(n: usize) -> Result<NonNull<[T]>, AllocErr>;
unsafe fn dealloc_array(ptr: NonNull<[T]>);
fn alloc_one() -> Result<NonNull<T>, AllocErr>;
unsafe fn dealloc_one(ptr: NonNull<T>);
// maybe more ...
}
@KrishnaSannasi That's the API we have today in the Alloc trait see https://github.com/rust-lang/wg-allocators/issues/18#issuecomment-530322973 for why generic can't be in GlobalAlloc
(tldr linking).
Also making a separate trait without the ability to handle multiple or unsized types mean that standard collections could never use such a trait.
@Avi-D-coder
That's the API we have today in the Alloc trait see #18 (comment) for why generic can't be in GlobalAlloc(tldr linking).
Ok, but I don't think we can make any typed allocator a global allocator. So this shouldn't matter, right?
Also making a separate trait without the ability to handle multiple or unsized types mean that standard collections could never use such a trait.
I was proposing a simple solution, we could change it or make it more sophisticated to better handle the standard collections' use case. Now that I've thought about it a bit more, we could change TypedAlloc
to
trait TypedAlloc<T: ?Sized> {
type Meta;
fn alloc(meta: Self::Meta) -> Result<NonNull<T>, AllocErr>;
unsafe fn dealloc(ptr: NonNull<T>);
// maybe more ...
}
Where we could use it like this, playground. I think this should support the use cases for standard library types well enough.
@KrishnaSannasi My proposal passes type info to Global Allocators and Alloc
by replacing use cases of alloc_one<T>
and alloc_array
with a field in Layout
type_id_: Option<TypeId>
.
Even if we were to exclude the GlobalAlloc
use case in order to allow generics. Your proposal does not allow a collection to take as a type parameter a single allocator, since a collection may need to allocate multiple types. One of the design requirements on Allocators is they must handle multiple types. In other words there is no possible design where a trait takes a type parameter or an associated type indicating what it allocates.
@Avi-D-coder Oh, I misunderstood. Thanks for clarifying.
FWIW, both solutions aren't really incompatible with each other (we could have both). While currently GlobalAlloc
cannot use generic methods, a TypedAlloc
trait could offer type-generic methods.
That is, a GlobalAlloc
would need to have run-time logic for handling the TypeId
s, but a TypedAlloc
could potentially use static dispatch depending on the type to do different things for different types., e.g., using specialization.
@gnzlbg your right they are compatible, but this proposal is specifically about always passing type information from boxing one or N
of a T
, not type-specific allocators. Once specialization lands TypedAlloc: Alloc
would be interesting, but it's orthogonal to my use case.
ObjectAlloc
is very similar to TypedAlloc
.
Note that another recent RFC is proposing to allow transmutes between Vec<A>
and Vec<B>
as long as A
and B
have the same size and alignment. This would allow a Vec
's contents to be deallocated with a different TypeId than the one it was allocated with.
@comex That would forbid Vec
from using the type aware allocator API, but I don't see a reasonable Vec
implementation that would use such an API.
Adding another field to Layout could have a tiny performance cost.
Currently Layout
is two usize
s. Most ABIs allow passing and returning two usizes
s in registers, which means that returning Layout from a function is as efficient as just returning an usize
.
This proposal adds another two fields to Layout
(the enum discriminant and the u64
TypeId), changing how Layout
is passed on most ABIs, from registers, to requiring that it must be passed via memory.
I'm not sure of what the performance implications of that are, but would rather not do it I think.
@gnzlbg The proposal includes changing TypeId
from u64
to NonZeroU64
. Option<std::num::NonZeroU64>
is packed into 8 bytes. So this changes requires 8 bytes more be passed as an argument.
Most ABIs allow passing and returning two
usize
s in registers, which means that returning Layout from a function is as efficient as just returning anusize
.
Do any calling convention besides fastcall
make this restriction? I believe fastcall
is the only one. More modern conventions seem to mostly allow 4+ integer registers.
I would also suspect LTO to remove the unused argument for allocators that don't use TypeId
?
This is all likely moot, since https://github.com/rust-lang/rust/issues/26494 implies Layout
and all small structs are passed on the stack anyway. In other words, in practice there will be no measurable performance cost. If your still not convinced I could implement the change and benchmark it?
@comex If that RFC goes through, type-aware allocators will just have to account for deallocation not having an accurate TypeId
. From my perspective it's not a deal breaker, just an interesting edge case.
I would also suspect LTO to remove the unused argument for allocators that don't use TypeId?
No, this isn't possible. The arguments are always passed according to the calling convention, and the global allocator functions cannot, in general, be inlined. You can, e.g., change the allocator at run-time, using LD_PRELOAD
.
Do any calling convention besides fastcall make this restriction?
I thought actually that most ABIs make this restriction for return types (not arguments), and we have a couple of APIs that return Layouts IIRC.
This is all likely moot, since rust-lang/rust#26494 implies Layout and all small structs are passed on the stack anyway.
We pass scalars and scalar pairs in registers, and have two separate ABI classes for those in the Rust ABI (Abi::Scalar
and Abi::ScalarPair
)
@gnzlbg That could be a problem.
Is there a reason the rust ABI could not have aScalarTriple
?
Does a calling convention agnostic optimization exist to pass the first two fields of a struct in registers and not the third?
I'll have to benchmark this. Is there a possible way to provide type information to a global allocator, that does not hit this restriction? If not, it's trade off between avoiding passing a struct on the stack or ever having type-aware global allocators and all the optimizations and concurrency advantages they can provide.
I think you are focusing too much on how to implement something, and not on making a case for this feature. To me at least it is very unclear:
TypeId
)I see many fundamental problems with the approach. First:
In the rust abstract machine memory is untyped, so one can allocate memory for an Option<bool>
, and transmute that in place to a bool
, and free the bool
. A lot of correct code does this (which is why @comex probably mentioned the case of transmuting Vec<A>
to Vec<B>
above).
TypeId
s are not unique (e.g. see https://github.com/rust-lang/rust/issues/10389), so you can't rely on them for differentiating allocations of different types. (this also means that the actual layout of TypeId
is unspecified and can change).
This means that the use cases that rely on accurate type information cannot really work, and that TypeId
can at most be a hint.
So if this is a hint, would such a hint be useful?
No major allocator supports this (malloc, jemalloc, mimalloc, tcmalloc, weealloc, hurd, ...).
Some of the std::collections
might be able to use it as a hint, e.g., Vec<T>
/Deque<T>
, but most other collections use the Layout
builder methods to concatenate Layouts. It is unclear to me what would the result of concatenating two layouts with two different Option<TypeId>
s be ? Probably None
? Some of the use-cases you mention, e.g., ECS, already use their own data-structures right ?
I can imagine that one can build an allocator that exploits TypeId
, and that one could ship collections that are specifically written to use a TypeId
-aware allocator for profit, and that one might want a different TypedAlloc
trait for those, but making the standard collections exploit this would require changing their implementation, potentially significantly for the node based ones. And even then, most users using widely-used allocators won't benefit from it.
I should have real code to publish, in the next couple of weeks. I'll publish a detailed write up with it including API requirements, trade-offs, benchmarks, etc...
For my use case transmuting is not an issue. Good to know about TypeId
being a hash, it's not ideal but pretty simple to guard against in practice.
What's unclear to me is why that should be provided via GlobalAlloc
. That's a very specific use case, and it could be fulfilled by opting in to using Alloc
-aware types.
I no longer believe passing TypeId
is the correct solution. Specialization on generics is too useful a property. I'm going to need to do some more experimenting to find a better solution.
Currently this use case is supported for the
Alloc
trait, but notGlobalAlloc
.As discussed in #18 generic methods (I.e
{alloc,dealloc}_one
) cannot be used to support this use case inGlobalAlloc
and maybe removed fromAlloc
. An alternative that is consistent across both methods is needed.Type information is necessary for ECS allocators, typed Pool/Slab allocators, many GC, STM optimizations, and describable for heap profilers, and exotic heuristic guided allocators as a significant source of free information.
Today there are many slab and generational indexed allocators. They are incompatible with box, std, and each other. They all provide some version of the following: allocation and deallocation of
T: Sized
, indexing/dereferencing and usually iterating overT
s. By passing unsized allocations to an underlying or global allocator. They could easily implement the Alloc trait to take advantage of standard collections and boxes, but to do this they require knowing more than justLayout
, they requireTypeId
.I am working on a allocator for use a with both
Alloc
andGlobalAlloc
that requires typed pools ofSized
T
to support pause free optional GC. Without a method of differentiating allocations and deallocations that share the sameLayout
, but different types my use case is impossible.In order to support all the mentioned use cases
TypeId
needs to always be provided to allocations and deallocations ofSized
Types andN
Sized
Types . Layout looks like the best place to ensureTypeId
is always passed.Layout
would havetype_id_
added andTypeId
implementation would be changed toNonZeroU64
.type_id_
would not be considered byEq
, so as not to break compatibility.Drawbacks
Adding another field to Layout could have a tiny performance cost.
alternatives
Originally I had wanted a separate set of functions for this use case analogous to
Alloc::{alloc,dealloc}_array
andAlloc::{alloc,dealloc}_one
(like below), but this allows for human error (E.g calling the normal unsized set of functions when you have a sized type).