Pre-Pre-RFC: A Box reinitialization interface

In reference to this comment, it would sometimes be more efficient to reuse a Box than to reallocate a new one. While the compiler may at some point become smart enough to figure this out, a safe interface that guarantees it can already be written.

Possible interface 1

At least for N: Sized I would have expected a signature that allows access to the replaced value like in mem::replace. Otherwise it can not retrieve the current item by value and so doesn't fully parallel *x. Since the pre-conditions can be checked outside in user code it might be sensible to panic similar to mem::transmute if the layout of the replacement differs from the current value. An interface that accomplishes this purely with Box<T> is:

impl Box<T> {
    fn reuse<N>(b: Self, val: N)-> (Box<N>, T) {
        use std::alloc::Layout;
        let layout = Layout::for_value(&*self);
        assert!(layout == Layout::new::<N>());

        let reboxed;
        unsafe {
            let ptr = Box::into_raw(self);
            let previous = ptr::read(ptr);

            let ptr = ptr as *mut N;
            ptr::write(ptr as *mut N, val);
            reboxed = Box::from_raw(ptr);
        }
        (reboxed, previous)
    }
}

Possible interface 2

Another way would be to be broken into two operations. This could allow both unsized values and the computation of N to involve a value of T instead of only a reference.

struct RawBox(Unique<u8>, Layout);

impl<T: ?Sized> Box<T> {
    /// Drop the value in the box but keep the allocation.
    /// This is slightly more efficient than `take` and works on
    /// unsized values.
    pub fn drop(own: Self) -> RawBox {
        let layout = Layout::for_value(&*own);
        let unique = Box::into_unique(own);
        unsafe {
            ptr::drop_in_place(unique.as_mut());
        }
        RawBox(inner.cast(), layout)
    }

    /// Take a sized value from the box.
    pub fn take(own: Self) -> (RawBox, T) where T: Sized {
        let unique = Box::into_unique(own);
        let val = unsafe {
            ptr::read(unique.as_ptr())
        };
        let raw_box = RawBox(unique.cast(), Layout::new::<T>());
        (raw_box, val)
    }
}

impl RawBox {
    pub fn layout(&self) -> Layout {
        self.1
    }

    pub fn init<N>(self, val: N) -> Box<N> {
        assert!(self.layout() == Layout::new::<N>());
        let unique = RawBox::into_unique(self);
        unsafe {
            ptr::write(unique.as_mut(), val);
        }
        Box::from(unique)
    }

    pub fn into_unique<T>(b: RawBox) -> Unique<T> {
        let mut unique = b.0;
        mem::forget(b);
        unsafe { Unique::new_unchecked(unique.as_mut() as *mut T) }
    }
}

Unresolved questions

Choose an interface with RawBox or not?

Handling initialization for unsized values?

1 Like

I like the RawBox interface, when I reimplemented Box for learning purposes a while back I used a similar interface and it works rather nicely. reuse can then be written as,

impl<T: ?Sized> Box<T> {
    fn reuse<N>(b: Self, new: N)-> (Box<N>, T) {
        let (raw, old) = Box::take(b);
        (raw.init(new), old)
    }
}
2 Likes

On the same note, can we map over Vec in place? i.e.

impl<T> Vec<T> {
    fn map<U, F: FnMut(T) -> U>(self, f: F) -> Vec<U> {
        ...
    }
}

This way we can reuse the allocation of the Vec<_> while still using owned values in the map.

Here's how to do that on playground

We could do something similar in the case of VecDeque to get in place mapping.

2 Likes

This is one of those situations where it would be really nice to have compile-time expressions in where clauses... though I'm pretty sure that invites EXCITING compatibility concerns? It's somewhat unfortunate that the layout of a type is nominally API-private information, even though it's ABI-crucial.

This seems related

I'd suggest to change RawBox into RawBox<T> and add a method that can convert it to a RawBox<U> with no allocation if the layouts are compatibile, and reallocating otherwise, and also adding a way to create a RawBox directly.

This can also be used to do a "placement box" by creating a RawBox and then filling it with an inline function.

Maybe it should be called UninitBox or BoxPlace instead of RawBox though.

Possible Interface 3

impl Box<T> {
    fn map<U, F> (this: Box<T>, map: F)
        -> Box<U>
    where
        F : FnOnce(T) -> U,
    {
        use ::std::alloc;
        let layout = alloc::Layout::new::<T>();
        assert_eq!(
            layout,
            alloc::Layout::new::<U>(),
        );
        let ptr: NonNull<T> = this.into_raw_nonnull();
        let value: T = unsafe { ptr.as_ptr().read() };
        let guard = ::scopeguard::guard_on_unwind(
            ptr,
            // if the code unwinds, do:
            move |ptr| unsafe {
                alloc::dealloc(ptr.cast::<u8>().as_ptr(), layout);
            },
        );
        let value: U = map(value);
        let ptr: NonNull<U> = guard.into_inner().cast::<U>();
        ptr.as_ptr().write(value);
        Box::from_raw(ptr.as_ptr())
    }
}
  • (where the helper NonNull could be upgraded to Unique)
3 Likes

I like the idea of map, but I wouldn’t assert that T and U have the same layout. Just reallocate if necessary. It also makes me think that we could do something similar for Vec (allowing Vec.into_iter().map().collect() where the final collect() reuses the original memory if possible).

3 Likes

Yes, that is a good idea.

Here is the updated Vec::map and Vec::try_map, this one won't panic on it's own.


edit: now added try_map for fallible operations!

1 Like

FWIW, I think ideally:

  • RawBox should carry the Layout its allocation was allocated with statically as a const generic, and have safe methods both to guarantee reuse of the allocation (with transmute-like magic checking or const generic magic) and to relocate if necessary (but reuse if possible). The reuse would be allowed to lower the guaranteed alignment but not otherwise change the layout.
  • Safe methods interchanging RawBox and Box<MaybeUninit<_>>. Maybe even just spell RawBox<T> as Box<MaybeUninit<T>>?
  • RawBox is implemented in std and Box is implemented in terms of RawBox. Box is no longer special and is purely a library type, RawBox inherits only some of today's Box's specialness. (I.e. they're no longer a completely unique kind of type.)
  • All of this is carefully done to still work with ?Sized types the whole way through.

Big unknowns:

  • box syntax.
  • Raw forms of other alloc types.
  • "DerefMove" (i.e. why Box is still special).
    • Along with that but partial.
2 Likes

Layout can't be a const generic due to DSTs not having a specified layout till runtime, and RawBox can't be Box<MaybeUninit<T>> due to DSTs being incompatible with unions. Box will have to stay special in order to support deref moves out of a box.

Other alloc types, like Vec may benefit from a similar api. But HashMap and other types that need other properties of T won't.

1 Like

That is definitely not safe. The owner must remember the layout passed to alloc and pass it dealloc. Somewhat tragically realloc also does not allow changing the alignment, even though I imagine that many allocators would permit lowering the alignment of the layout without additional costs by calling realloc, or at least require actual reallocation in only few cases.

4 Likes

I have done it again! Now, I have added try_zip_with and zip_with. These take an additional vec and try and use the capacity of either one! I have also make the code more robust, now it will clean up it's mess even if you panic in the drop.

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=8655604d47b5a128ab306b1a5c87589a

In the interest of not polluting this thread even more with these updates, I have published this as a minimal crate so that you can track it's progress there and contribute if you would like to!

https://crates.io/crates/vec-utils

6 Likes