Mimic Arc with no heap, maybe 'static

help
1

I have a library that uses Arc in defining, what is essentially an AST, I'm using a type to

roughly something like:

pub type ShrPtr<T> = std::sync::Arc<T>;
pub struct GetClampAbove<T, B, Min> {
    binding: ShrPtr<B>,
    min: ShrPtr<Min>,
    _phantom: PhantomData<fn() -> T>,
}
...
let input = .. get some input;
let min = ShrPtr::new(20);
let above = ShrPtr::new(GetClampAbove::new(input, min));
let mul = ShrPtr::new(GetMul::new(above, ShrPtr::new(20)));

I'm trying to make a no_std compatible version of my library and I'd like to be able to build these AST like structures with entirely statically allocated data... no heap.

Arc::new takes ownership of its argument, allocates space for it on the heap, copies it there, and then keeps track of it, so we know that the data lives as long as the Arc. I'm not sure how to mimic this 'take ownership' but then also be able to create clones that have access to the same data. I have an initial approach here: Rust Playground

This doesn't mimic Arc exactly because it takes a reference in new but I'm fine with modifying how I create the AST if I can use it in the same manner as with the dynamic, Arc based approach. It doesn't work because to use it I have to modify anything that holds my Src wrapper to indicate T: 'static which would mean the stucts that hold these wouldn't be compatible with Arc anymore.

I'm wondering if anyone has any advice for an approach?

3

You can be generic over <'a, T: 'a> everywhere. Then you can use &'a T and Arc<T> interchangeably. Only when instantiating and storing your data do you fill in 'static for 'a.

1 Like
4

hmm, @jethrogb is there a way i can make an interchangeable type alias for:
&'a T vs. Arc<T>

#[cfg(feature = "no_std")]
pub type SharedPtr<'a, T> = &'a T;`
#[cfg(not(feature = "no_std"))]
pub type SharedPtr<'a, T> = Arc<T>; //not sure what to do here

pub struct Container<'a, T: 'a> {
    src: SharedPtr<'a, T>
}
5

There's the possibility of being generic over the container type. It can make your use of generic bounds grow very quickly, but it's a possibility and will produce nice output for everyone using them:

pub struct GetClampAbove<T, BC, MinC> {
    binding: BC,
    min: MinC,
    _phantom: PhantomData<fn() -> T>,
}

impl<T, B, Min, BC, MinC> GetClampAbove<T, BC, MinC>
where
    BC: Deref<Target = B>,
    MinC: Deref<Target = Min>,
{
    fn new(binding: BC, min: MinC) -> Self {
        GetClampAbove { binding, min, _phantom: PhantomData }
    }
}

(full playground: Rust Playground)

I would recommend doing this rather than a #[cfg(feature)] just because feature flags must be purely additive.

This has a large disadvantage of code size, though, and requires use of complicated generics everywhere you want to use your types.

The other alternative I know of is to have an enum with either possibility, and pay a small runtime cost. This can result in much cleaner code, though, and has the advantage of allowing interop between the version using Arcs and the version using &'static T.

It'd look something like this:

enum SharedPtr<T: 'static> {
    #[cfg(feature = "use_std")]
    Arc(Arc<T>),
    Static(&'static T),
}

impl<T> Deref for SharedPtr<T> {
    type Target = T;

    fn deref(&self) -> &T {
        match self {
            #[cfg(feature = "use_std")]
            SharedPtr::Arc(x) => x,
            SharedPtr::Static(x) => x,
        }
    }
}

(playground with it being used: Rust Playground)

This requires marking B/Min as 'static only, but that shouldn't be too much of a disadvantage. Having an Arc of non-'static data doesn't make much sense anyways in most cases.

This is somewhat like std::borrow::Cow, but using Arc rather than straight up owning the data. The #[feature] attribute can then include the Arc variant only while having std. I have this again as a positive feature because cargo expects all feature flags to be positive.

It has a runtime cost but it does avoid the huge generics mess from being generic over the container type. Among the other things possible that I'm sure I'm not thinking of, I think these two are still both usable solution.

1 Like
6

@daboross Thanks a ton for your help!

I'm gonna have to try both approaches and see how it impacts my code-base.
I'm using Arc elsewhere with dyn TraitName so I'm gonna have to see how that works out as well.

As far as features being only additive, I guess it makes sense that I'd make the feature "use_std" and not "dont_use_std" and I guess I should be using the no_std compatible use statements in the shared code.

Thanks again!

1 Like
7

Alright, hope the testing goes well!

I wasn't as specific as I meant to be, apologies for that. There is pretty much one strategy here that most crates optionally supporting no_std use. That is, having a "std" (or "use_std") feature which adds in std features and is included as a default feature (see manifest format), then just have #![cfg_attr(not(feature = "std"), no_std)] in the crate root.

Then no_std users simply have default_features = false, and if any crate depends on std features, they can just depend on the crate without any specific notation and cargo will enable the default features since features are additive.

See also descriptions of this strategy (from a user's persective) for serde, smallvec, or most other crates on https://crates.io/keywords/no_std.

Just had to mention that, in case it's useful! Hope one of these solutions in general can work.

1 Like
8

@daboross

The feature explanation is very helpful, thanks so much!

1 Like
9

@daboross I guess one thing I failed to specify is that I want to be able to use <dyn Trait>, I'm not sure if that is compatible with the enum approach?

I've started with the generic struct approach here.. maybe being a little more clear on what I'm trying to do:

What I can't seem to figure out is a way to disambiguate the impl of Get<T> for T and dyn Get<T> so that I can use Arc<GetClampAbove<_, usize,_,_>> in place of Arc<usize> inside another GetClampAbove [or some other struct in my AST].

1 Like
10

There's a way to solve this, but it involves a tradeoff. If you get rid of the blanket implementation of Get<T> for T where T: Copy, then you can have other blanket implementations, like impl<T, U> Get<T> for Arc<U> where U: Get<T>.

Rust Playground has this strategy.

This requires manually implementing Get for every Copy primitive, which is unfortunate but can be put behind a macro. If I understand the question correctly, I can't think of any better way to solve this?

If specialization is implemented in the future, it might allow these two implementations to co-exist, but that's quite a ways away in my understanding.

1 Like
11

Instead of monomorphizing it, you could use dynamic dispatch to solve this

impl<T> Get<T> for Arc<dyn Get<T>>
where
    T: Sync + Send,
{
    fn get(&self) -> T {
        Arc::deref(self).get()
    }
}

impl<T> Get<T> for Arc<T>
where
    T: Sync + Send + Get<T>,
{
    fn get(&self) -> T {
        Arc::deref(self).get()
    }
}


impl<T> Get<T> for T
where
    T: Copy + Send + Sync,
{
    fn get(&self) -> T {
        *self
    }
}

Instead of

impl<T, U> Get<T> for Arc<U>
where
    T: Sync + Send,
    U: ?Sized + Get<T>,
{
    fn get(&self) -> T {
        self.deref().get()
    }
}

This way you can have a blanket impl for Copy types and if you need some indirection with Get<_>, you can use dynamic dispatch.

2 Likes
12

@RustyYato ahh nice!

I had to add the type to c to get it to work let c: Arc<dyn Get<usize>> but that is great!

I'm curious why the Arc<dyn Get<T>> implementation isn't enough and we need the 2nd Arc<T> where T: Sync + Send + Get<T> does Arc<dyn Get<T>> not match Arc<usize> ?

Thanks!!

13

@daboross fantastic! once again, really appreciate the help!
It seems like @RustyYato 's approach does away with the manual Copy primitive implementation needs.. I guess there is a small performance cost for dynamic dispatch?

14

Yay :smile:! It is unfortunate that you need the let, would as Arc<dyn Get<usize>> work for one-offs? If you are going to use it multiple times then making a new binding would be better.

That is correct, Arc<dyn Get<T>> does not match Arc<usize>. This is because dyn Get<usize> != usize, even though usize coerces to dyn Get<usize>.

Yes there is, but unless you are doing it in a tight-ish loop, it shouldn't matter too much. That said it is always good to profile your code to see if dynamic dispatch is causing problems. If it does cause problems, then you can shift over to @daboross's approach

2 Likes
15

Worth noting that my suggested solution with impl<T, U> Get<T> for Arc<T>> where U: Get<T> would also just delegate to dynamic dispatch if Arc<dyn Get<T>> is used (and since it was mentioned, I assume it will be used). Using it with Arc<dyn Get<T>> will have just as much overhead.

Overall I think @RustyYato's solution implementing for Arc<dyn Get<T>> is pretty great, though! I hadn't thought of that at all.

16

Yeah, it's one of the few places where you can use negative trait reasoning in Rust. So it tends to be easy to miss.

Also, yours can't delegate to Arc<dyn Get<T>> unless you add U: ?Sized bounds.

1 Like