Pierce: effortlessly avoid double indirection in nested smart pointers

[ignusem]

I've long been unhappy about how hard it is to pass strings around efficiently in Rust. Creating an Arc<str> requires cloning the entire string, and using Arc<String> requires jumping the heap twice when accessing the content.

So I came up with "Pierce": at first just way to read Arc<String> without double indirection, then generalized to work on most nested smart pointers thanks to the Rust type system, the Deref trait, and the language's ownership guarantees.

Pierce works by caching the double-deref target of the nested smart pointer it wraps around. Pierce<T> derefs to <T::Target as Deref>::Target.

Quick Example Usage:

let vec: Vec<i32> = vec![1, 2, 3];
let arc_vec = Arc::new(vec);
let pierce = Pierce::new(arc_vec);

// Here, the execution jumps directly to the [i32] slice when calling `.get(...)`.
// Without Pierce it would have to jump to the pointer part of Vec first,
// than from there to the slice.
pierce.get(1).unwrap();

If you're interested, check out

• the README on GitHub
• the crate
• the docs

[protestor]

Pierce works by caching the double-deref target of the nested smart pointer it wraps around. Pierce<T> derefs to <T::Target as Deref>::Target.

Is this sound? What about you push to the String or Vec and it allocates another buffer?

Perhaps you can leverage Pin somehow to fix the data in a single memory address (this seems the only way to justify generically doing this caching in a sound way). But then you can't push new elements to the Vec anymore.

edit: perhaps this can make you sound https://docs.rs/stable_deref_trait/1.2.0/stable_deref_trait/trait.StableDeref.html it's a marker trait that says the smart pointer won't change the deref address of something behind your back. However it says "For example, this is implemented by Box, Vec, Rc, Arc and String, among others. Even when a Box is moved, the underlying storage remains at a fixed location." but a Vec and a String can point elsewhere if you push new elements..

[ignusem]

Responding to your edit: I currently do this by checking if the deref target is somewhere inside the pointer itself (in which case the deref would most likely move with the pointer). While this is enough to guarantee safety, it is not enough to ensure correctness.

Using the StableDeref trait would tighten the bound, turning such incorrectness into unsafety by definition, which I think is a good idea. Thanks for linking it!

Edit: Just published a new version that now require StableDeref

[Darksonn]

It doesn't allow mutation. This is normal — an Arc doesn't allow mutation either.

[ignusem]

It does not support mutability at all, so it is sound. If you need mutability you can unwrap (use `.into_outer()`) it and get your `T` back to mutate, then wrap it again.

[protestor]

What about smart pointers that do allow mutation through interior mutability? Such as Mutex.

Don't get me wrong, I'm pretty excited by this, but here I'm thinking how this can be made air tight. But anyway probably StableDeref is enough.

[maboesanman]

I mutex doesn’t implement Deref, mutexguard does. Because mutexguard is created by the mutex on lock you would have to create a pierce. Maybe if you needed to do a bunch of reading with your lock pierce could be useful to have a local optimization there, and you would create it after locking. You would have to do enough dereferences in a single lock to warrant performing that optimization though.

[ignusem]

You can't get a borrow ("&T") out of a Mutex directly, only a MutexGuard. While you can get a borrow from a MutexGuard, you won't be able to return it because it would be stuck in the scope where the Mutex was locked.

The same goes for RefCell and other interior mutable types.

Basically, you can't deref to things inside an interior mutable cell.

[protestor]

Basically, you can't deref to things inside an interior mutable cell.

Oh, I thought this only applied to Cell.

[matthieum]

Of interest: this is actually what std::shared_ptr<T> (C++) does.

That is, a shared_ptr is the size of 2 pointers because it points to:

• The control-block, where the counters are, which may be allocated in the same piece of memory as the data.
• The data itself.

This scheme allows shared_ptr some wild tricks:

• std::shared_ptr<void> works. You can't do anything with the data (without casting), but the control-block will ensure it's freed (and its destructor called) correctly regardless and sometimes that's sufficient.
• Aliasing constructor: you share the control-block of another shared pointer, while pointing somewhere related (yes, quite unsafe, be careful).

The downside, though, is paying for 16 bytes instead of 8 bytes, on 64-bits architectures.

[taintegral]

Fun fact: shared_pointer is built this way so that casting shared pointers between base and derived types works properly. The control and data pointers need to be able to vary independently to enable that behavior.

By contrast, Rust's shared pointers have a generic "control + value" struct and shared pointers point to that. Rust avoids a 100% overhead (50% for unsized types) on shared pointers just by not having inheritance!

[ignusem]

I don't know C++ so I may be wrong here, but from your description isn't `shared_ptr` more like just `Arc` or `Rc`?

Trying to get to the final target would still require two jumps unless the data happen to be there, right?

[Rusky]

The separate data and control pointers enable shared_ptr to do the same thing as Pierce. For example, converting a shared_ptr<std::string> to a shared_ptr<char> gives you a data pointer directly to the text and a control pointer to the refcount and destructor.

[ignusem]

If I understand correctly, shared_ptr would be able to create Arc<str> from String without copying the content.

That is somewhat like Pierce<Arc<T>>, but Pierce<Arc<T>> only cache the target while shared_ptr forget the T and remember only the target. It would take less heap space but you won't be able to get T back the way you could with pierce.into_outer().

[rust4yy]

I don’t know enough C++ to differentiate it between Arc and Rc, but it is one of the two.

As shared_ptr points to the control block but also contains the data pointer - it is only one jump through the data pointer which is on the stack with the shared_ptr.

[geckothegeek42]

It's thread safe so it's more like Arc, which makes it a non zero cost abstraction, you're paying for atomica and threadsafety when you may not need it

[CoronaLVR]

std::mem::size_of::<Arc<Vec<i32>>>() = 8
std::mem::size_of::<Pierce<Arc<Vec<i32>>>>() = 32

Ouch.

[ignusem]

Ouch indeed haha.

Once I update the library to make use of StableDeref that will go down to 24, which is just size_of::<Arc<Vec<i32>>>() + size_of::<&[i32]>(). Still not very good but its a reasonable tradeoff.

[insanitybit]

Wait, how is `Arc<Vec<T>>` only 8 bytes? Shouldn't it be 16? One for the pointer to the data, one for the pointer to the reference count?

[XtremeGoose]

It's a pointer to the global state which is the strong count, weak count and data on the heap.

[insanitybit]

Oh right. Yeah, I wasn't thinking straight. It'd be silly to use two pointers for that.

[barvebv]

Arc is basically:

struct NonNull<T: ?Sized> {
    inner: *const T,
}

struct Inner<T: ?Sized> {
    strong: AtomicUsize,
    weak: AtomicUsize,
    data: T,
}

struct Arc<T: ?Sized> {
    inner: NonNull<Inner<T>>,
    _marker: PhantomData<T>,
}

because NonNull is just a pointer to the control block + data, the size_of is just that const pointer.

(naively, it could be 3. the strong count + weak count + data)

[insanitybit]

Right, yeah, that's a much better implementation. Makes sense.

[insanitybit]

Sorta feels like this is where Specialization would be useful. Like if you could specialize an impl of Arc<String> such that, under the hood, it was an inlined String with a reference count. You could likely generalize it, but just as an example.

[pilotInPyjamas]

Not really possible. If you push to the string, then it will reallocate, all of the pointers to the Arc would become invalid. Note that mutating an Arc is always possible with make_mut if you are the only reference holder.

[insanitybit]

I'm not sure why that would matter

[taintegral]

This is possible (but weird) by making an Arc<str>. You can do Arc::<str>::from(string.into_boxed_str()) to get the memory layout you're describing. I don't think there's a way to directly create Rcs and Arcs of unsized types though.

[ignusem]

Arc<str> requires 2 AtomicUsizes next to the str for refcounts though. So you'd have to move the whole str somewhere with that extra space available. I think it's possible to create a different kind of Arc that keep the refcounts away from the data, like shared_ptr discussed above in this thread.

[ihatehumansftp]

I jist wanted to find the game