Const flags describing allocator properties

[the8472]

It would be useful if allocators had an associated constant of flags describing their properties, such as

• support for alignment-changing realloc (posix realloc doesn't, jemalloc does)
• does realloc try to avoid memcpy (doing virtual memory schenanigans)
• whether deallocation does anything (vs. an arena that drops all allocations at once)
• support for zero-length allocations
• if alloc_zeroed is any different from allocate
• do realloc/dealloc care about the layout information being correct
• etc.

Containers can then choose to optimize their behavior based on those properties.

(from #120 (comment))

[Amanieu]

Can you give examples of how generic code (e.g. Vec) could make use of these properties?

[the8472]

support for alignment-changing realloc

Would allow the in-place collect code in vec to apply in more cases.
Currently GlobaAlloc does this: https://doc.rust-lang.org/nightly/src/alloc/alloc.rs.html#302-321
which means shrinking efficiency depends on the layouts, but some allocators can do better than that

does realloc try to avoid memcpy

can help picking between new-allocation-and-grow vs. reuse-allocation-and-shrink strategies. I.e. when shrinking incurs memcpy costs then it's better to use a fresh allocation from the beginning.

It would also let us pick between realloc vs. alloc-manually-copy-dealloc when there's a huge discrepancy between capacity and length.

do realloc/dealloc care about the layout information being correct

lets in-place-collect skip some realloc calls

whether deallocation does anything

for non-drop T we can turn Container's Drop into a noop

And that's just examples. The list should be extensible of course. Flags would need to have conservative defaults.

[the8472]

Another useful property would be if the allocator could indicate support for zero-sized allocations, e.g. by always returning NonNull::dangling.
With this knowledge we would be able to optimize out some branches in alloc code that check the requested allocation size and always call the allocator instead. This would simplify things for LLVM since it would see a straight, branch-free path from allocation, use, deallocation, which can help optimizing temporaries

[the8472]

Having an associated const would be incompatible with dyn trait allocators (#83) 🙁

A regular subtrait can't be used since it wouldn't be available to collections. And min_specialization also wouldn't help here since specialization traits can't have consts either.

So there seems to be a conflict between dyn allocators and allocators describing their behavior at compile time.

[CAD97]

if the allocator could indicate support for zero-sized allocations,

The story is interesting here; Allocator allows requesting zero-sized allocations, but std code still wants to avoid calling into the allocator, as an actually allocated ZST has more restrictions than a dangling() pointer. E.g. Vec::new can't be const if it requires calling into the allocator.

A regular subtrait can't be used since it wouldn't be available to collections.

Not strictly; it's theoretically possible to have a general generic dyn-compatible trait and a trait with constant functionality indicators, such that collections always use A: SpecAllocator and it also holds that dyn Allocator: SpecAllocator.

We could also "just" have e.g. ZstNopAllocator be a specializable subtrait of Allocator, instead of using associated const values. It's currently more ceremony to utilize specialization than an if CONST branch, but being able to write specialization in a more procedural style is desirable for other reasons as well.

[the8472]

E.g. Vec::new can't be const if it requires calling into the allocator.

If the allocator makes the right promises we could actually use const_eval_select for that.

We could also "just" have e.g. ZstNopAllocator be a specializable subtrait of Allocator, instead of using associated const values.

Well, possible, yes, but having dozens of specialization traits to represent boolean flags is quite cumbersome. And far from stabilization. If possible consts would be more practical.

[chorman0773]

What about:

pub unsafe trait AllocatorProperties : Allocator {
     const ...: bool = false;
}

impl<A: AllocatorProperties> AllocatorProperties for &'_ A{ 
     const ...: bool = A::...;
}

// And Box/Rc/Arc/etc.

impl<'a> AllocatorProperties for dyn Allocator + 'a {}

// And `dyn Allocator + $(Send, Sync, Unpin)\++`

So type erased allocators don't support any of the flags, because nothing can be assumed. A third-party crate could then provide for type-erasing allocators with any given properties.

Collections that want this subtrait have to require it, but most allocators should implement it anyways (even if with just the defaults).

[CAD97]

The main issue with AllocatorProperties as a subtrait of Allocator is that you can have a type which is Allocator but not AllocatorProperties. So library types would have to choose between using Allocator and working with all allocators but without being able to specialize behavior, or being able to specialize with AllocatorProperties and excluding some allocators which didn't provide that informational implementation.

I believe there's some preliminary support (as in people, not in code) for making it possible to have dyn Trait on a trait with associated consts without specifying the consts which provides the functions but not the associated const access, though. It just breaks the dyn Trait: Trait expectation, so it's not a simple add.