Pre-RFC: Rc and Arc with only strong count

libs
1
  • Feature Name: strong_shared_ptr
  • Start Date: 2017-08-28
  • RFC PR: (leave this empty)
  • Rust Issue: (leave this empty)

Summary

Add a version of Rc and Arc without weak counts.

Motivation

There are some situations where you want to use Rc and Arc for caching purposes. One such example is storing a string in a HashSet to avoid duplication of allocation (string interning). In such situations, and when caching a lot of data, you pay an unnecessary std::mem::size_of::<usize>() cost on the heap, making the abstraction a non-zero cost one.

This also makes .clone() somewhat cheaper - which while probably always negligible in the case of Rc can have some measurable effect when it comes to Arc.

Such strong-only smart pointers, hence StrongRc and StrongArc, could be implemented in a crate. However, as of 2017-08-28, the implementations of Arc and Rc require a lot of unstable features making the use of such a crate in stable Rust only possible far into the future.

Detailed design

Take the implementations of Rc and Arc and remove all logic pertaining to the weak count.

Name the new types StrongRc and StrongArc. Alternative possible names are StrongOnlyRc and StrongOnlyArc to avoid confusion with the strong counterparts of std::rc::Weak and std::sync::Weak.

How We Teach This

Teach it as Rc and Arc but negate the teachings pertaining to the weak count. A note should be added that for tree-like data structures, and other cyclical data structures, Rc and Arc should be used instead.

Drawbacks

  1. Bloating the size of the standard library.

Alternatives

  1. Work on stabilizing the features needed to implement this in a crate.
  2. Add a version of Arc and Rc bitmasking the strong and weak counts into a single usize.
  3. Add a type parameter C: Add<Output = C> + ... to Rc, RcBox and Arc, ArcInner defaulting to usize thereby enabling C = u32, which fit into 8 bytes together. This is essentially the same as bitmasking but less manual.
  4. Add a type parameter W: RcWeakMode / W: ArcWeakMode which governs if Rc / Arc are WithWeak mode or NoWeak mode respectively. Strong and weak interaction logic is moved into WithWeak. The std::mem::size_of::<NoWeak> is 0. The benefit of this is less code bloat - the downside is potentially lower teachability - however, on the documentation of NoWeak the documentation details should still be providable.
struct RcBox<T: ?Sized, W : RcWeakMode = WithWeak> {
    strong: Cell<usize>,
    weak: W,
    value: T,
}

// or, maybe:

struct RcBox<T: ?Sized, W: RcWeakMode<T> = WithWeak<T>> {
    strong: Cell<usize>,
    weak: W,
    value: T,
}

Unresolved questions

None, as of yet.

4 Likes
2

Alternatives

  1. Implement an optimisation so that if Weak<T> is not used for the given T then Rc automatically loses the unused field.
  2. Add additional type parameter to Rc/Arc with a default value that allows Weak, but with most custom value that forbids it.
3

Name the new types StrongRc and StrongArc.

Maybe StrongOnlyRc/StrongOnlyArc to avoid confusion with strong counterpart of std::rc::Weak/std::sync::Weak?

1 Like
4

StrongOnlyRc seems a bit long, but sure - I don’t mind it =)

5

Will removal of that weak counter field actually reduce the memory usage or it will be allocated as some padding anyway?

1 Like
6

Will removal of that weak counter field actually reduce the memory usage or it will be allocated as some padding anyway?

The current layout of Rc is:

struct RcBox<T: ?Sized> {
    strong: Cell<usize>,
    weak: Cell<usize>,
    value: T,
}

Removing an usize will remove usize bytes from the heap since usize is the alignment for both 64-bit and 32-bit machines, given that usize is the size of a pointer, iirc.

7

Would be neat if possible - this would require adding type parameters to RcBox/ArcInner and Rc/Arc for the weak and strong counts each. While I can see how you can allow customization of the weak and strong counts from usize to u32, saving 8 bytes in the process, I don't see how you can completely remove the weak count, given that the weak and strong counts interact in a non-trivial way.

Could you elaborate on how the latter is possible?

8

Something like

struct RcBox<T: ?Sized, W : RcWeakMode = WithWeak> {
    strong: Cell<usize>,
    weak: W,
    value: T,
}

(or maybe W: RcWeakMode<T> = WithWeak<T>)

and all code that needs weak counter is moved into WithWeak or NoWeak.

(I didn’t though out the design in depth)

1 Like
9

Sounds good, I'll add to "Alternatives" for now. I might move it to "Detailed design" later as the RFC develops.

10

There’s a currently-dormant pull request to move Rc and Arc to 32-bit counts which seems like it could be merged with a little bit of extra work. https://github.com/rust-lang/rust/pull/41005

3 Likes
11

Servo contains a (currently) unpublished crate called servo_arc (src) that is a version of Arc with no weak count. It uses no unstable features, but it has a slightly complex hack to get around the lack of NonZero<T> or Shared<T> in stable Rust. We’re hoping that Shared will be stabilized before too long so we can get rid of this extra code.

12

I like the idea of customizing using type parameters. I’d like a 32-bit no-weak Rc.

:bike: ThinRc may be good name for the smaller variant of Rc.

1 Like
13

glaebhoerl: sounds like a feasible idea - I get that it is very unlikely to clone a single pointer 2^32, but still - it’s a breaking change even if just for one developer.

mbrubeck: usage of some new unstable things were added to both Arc and Rc with the shared_from_slice RFC, https://github.com/rust-lang/rfcs/pull/1845

kornel: are you referring to vi0’s suggestion? If so - yeah, I like the proposal a lot too =) You could possibly also add a trait for “strong” and “weak” capabilities so that you can write generic functions that work as long as the arc supports strong.

14

Personally I’m only in favor of this iff. it is a new type. Altering the existing types would wreak all sorts of havoc in the ecosystem I think.

15

If removing an usize still puts the particular RcBox<T> in the same size bin among the allocator’s allocations cache, then the memory use is effectively the same.

For example, reducing the box size from 48 bytes to 40 bytes is not necessarily a win in memory use; it depends on the allocator.

16

This is a long standing issue I’ve had (I think there are open github issues about this, so other people have had the same request).

Here is a real world example I ran into where removing the weak counts was important to improving performance.

2 Likes
17

But we can’t know the size of T - it may even be a DST as with Rc<str>. So we can only speak statistically about in how many % of cases it will be beneficial. In any case, this never hurts performance, so why not do it even if only for the benefit of a minority of cases?

18

Why wouldn’t altering Rc and Arc by adding type parameters with a default implementation set to the current functionality of Rc and Arc work? From the POV of someone using just Rc<T>, it will behave as the type was before the change if they happen to compile on a rust version after the change…

3 Likes
19

It seems like that should work, but my intuition is that Rust’s type system is complex enough that any change to the signature of a core type will break some user somewhere that is using Rc in the middle of hairy generics.

20

Type parameter defaults as they exist in stable Rust are basically syntactical and don’t influence inference.

Syntactical defaults mean that when we have struct Foo<T, U = i32> { ... }

  1. Foo<T> always means exactly Foo<T, i32>.
  2. It does not mean “infer U and fall back to i32”

the emphasis for clarity.

1 Like