ThinBox::new_unsize should not allocate

Rust issue tracker suggested I should post feature request here.

The problem is:

ThinBox::<[u32]>::new_unsize([0; 0]);
ThinBox::<dyn Debug>::new_unsize([0; 0]);

both allocate 8 bytes in the heap to store the pointer.

However, there's no need. Ideally, new_unsize function should statically allocate pointer metadata, and return pointer to it. That's it.

I tried to implement it, and encountered this problem. I can create pointer metadata for T like this:

    pub fn new_unsize<T>(value: T) -> Self
    where
        T: Unsize<Dyn>,
    {
        if mem::size_of_value(&value) == 0 {
          // Here I create pointer metadata, with only type,
          // no value, this is const expression
          const { ptr::metadata(NonNull::<T>::dangling().as_ptr() as *mut Dyn) }
          // But there is no way to tell the rust compiler to put it into a static variable
          // to return it from this function.
        }
        ...
    }

Or an I missing something?

Why it is important

Because, Box<[String]> is cheap for empty strings, but ThinBox<[String]> is not.

It can be partially worked around by storing it an option, like:

struct MyThinSlice<T>(Option<ThinBox<[T]>>); // None means empty

But this makes Option<MyThinSlice<T>> as big as Option<Box<[T]>> making ThinBox less efficient than just Box.

CC @yaahc

2 Likes

Note that the pointer should be directly on the value, with the metadata at a negative offset. That will be at the end of your "allocation" for a ZST, but they can also require greater alignment, so your static may need some padding.

Right. It could be something like:

#[repr(C)]
struct StaticZst<Dyn, T> {
  metadata: <Dyn as Pointee>::Metadata,
  data: [T; 0],
}

static ZST<Dyn, T: Unsize<Dyn>>: StaticZst<Dyn, T> = StaticZst {
  metadata: ptr::metadata(NonNull::<T>::dangling().as_ptr() as *Dyn),
  data: [],
};

Everything is doable except generic statics.

No generic statics required:

const fn make<Dyn: ?Sized, T: Unsize<Dyn>>() -> &'static StaticZst<Dyn, T> {
    const {
        &StaticZst {
            metadata: ptr::metadata(NonNull::<T>::dangling().as_ptr() as *mut Dyn),
            data: [],
        }
    }
}

except that still doesn't work because

error[E0492]: constants cannot refer to interior mutable data
  --> src/lib.rs:17:9
   |
17 | /         &StaticZst {
18 | |             metadata: ptr::metadata(NonNull::<T>::dangling().as_ptr() as *mut Dyn),
19 | |             data: [],
20 | |         }
   | |_________^ this borrow of an interior mutable value may end up in the final value

... so yeah, putting it in a static would allow the ?Freeze value. But we don't need the uniqueness guarantee of static (which at best requires linker shenanigans for generic statics), so what we really want is a Freeze bound on the pointee metadata. (It holds for the only current pointee kinds, with (), usize (slices), and DynMetadata.)

(I'm kind of surprised that this just works; for some reason I thought inline const wasn't allowed to use outer generics; perhaps from using the stable approximation using a const item which does have that restriction.)

The other alternative is just to #[repr(align(128))] and only do the zero-alloc opt for ZST where that alignment is sufficient.

This is also making the assumption that unsizing from a dangling pointer will get you the same result as unsizing the concrete value. This is true for all current pointee kinds and might be necessarily true for any future custom DST using, but also might not necessarily be true.

If you want to implement this, the way to go about it is probably by utilizing specialization, so it's tied to the pointee kind. And in that case, the inline const will work just fine since the metadata is known not to contain UnsafeCell.

The more appropriate stable approximation is using an associated const on a type; those can be generic.

struct HelperStruct<…generics…>;
impl<…generics…> HelperStruct<…generics…> {
    const TheConstant = /* expression here! */;
}

Another adjustment would be in the drop implementation. Presumably introducing a new branching (in the optimized code) that will need to check the zero-sizedness at run-time. Since this only negatively affects code that subsequently deallocates, this single additional check is probably negligible.

TL;DR: it may work if we add + Freeze + 'static on Pointee::Metadata.

OK, I think I got it.

Pointee::Metadata needs to be marked Freeze.

(Freeze needs to be made public, but that's probably OK).

Even if I do

unsafe impl Freeze for StaticZst<...> {}

I failed to tell rust to allocate it statically (it tells something about Dyn need to be 'static). But that's good enough for now.

::Metadata also needs to have 'static bound, otherwise it doesn't work.

And since we cannot have StaticZst struct with empty [T; 0] field in it, we place metadata in a struct which is repr(align(128)), and do this optimizations only for such types.

I got some code which compiles (and even alloc tests pass).

1 Like