Rc<T> borrow impl should be changed

libs
1

Right now Rc<T> implements Borrow<T> but it would be easier to make composed types if it implemented Borrow<U> where U: Borrow<T>. This came up because I was trying to make a BTreeSet<Rc<Box<str>>> but Rc<Box<T>> doesn't implement Borrow<str>

2

This would conflict with the implementation of Borrow<T> for T.

2 Likes
3

Why aren't you using Rc<str>?

8 Likes
4

Yeah, you should probably just convert from Box<str> to Rc<str> using impl<T> From<Box<T, Global>> for Rc<T>

5

Converting Box<str> to Rc<str> has to reallocate the whole string, while wrapping to Rc<Box<str>> only has to perform a small allocation.

2 Likes
6

Then again, on the other hand, at the time of creating the Box<str>, one could have probably directly created a Rc<str> instead. (The same isn’t necessarily true for String, as that type supports efficiently growing, thus allowing creation patterns that Rc<str> or Box<str> couldn’t offer without one extra step of re-allocation at the end [in the form of a conversion from String]; so Rc<String> may sometimes be desired.)

1 Like
7

When starting with a String, Rc<Box<str>> is more efficient to create:

  • String -> Box<str> -> Rc<Box<str>> does on allocation shrink, and one 3*usize allocation
  • String -> Rc<str> goes through From<str>, so it does on string-length allocation, one string-length copy, one 3*usize allocation, and one string-length deallocation[1]

Accessing the strings will be one additional deref, but if these are big strings the cheaper construction might still be worth it.

For str it probably doesn't matter:

  • &str -> Box<str> -> Rc<Box<str> does one string-length allocation, one string-length copy, and one 3*usize allocation
  • &str -> Rc<str> does one string-length + 3*usize allocation, and one string-length copy

  1. I wonder whether there should be a fast path in From<String> and From<Vec<T>> that reuses the allocation if the alignment allows it. ↩︎

1 Like
8

I don’t see why your description of “String -> Rc<str>” looks more complicated than the one of “&str -> Rc<str>” (except for the additional deallocation). It should simply be: string-length + 2*usize allocation, one string-length copy, and one string-length deallocation.

(Incidentally, it’s also “string-length + 2*usize”, not “string-length + 3*usize” for the str case; whereas Rc<Box<str>> does 4*usize, not 3*usize – for the two reference counts (string & weak) plus the fat pointer Box<str>.)

Admitted, if the String already is at zero additional capacity, then String -> Box<str> -> Rc<Box<str>> is beneficial. Otherwise, as far as I’m aware the shrink might commonly be essentially the same effort as allocation+copy+deallocation. Though maybe also in some cases where the additional unsized capacity was low, allocators will be able to shrink in-place. I’m not too familiar of how our standard allocator(s) actually operate :innocent:

A significant benefit of Rc<str> over Rc<Box<str> that makes it better in the &str->… case is that it’s no double indirection, so accessing the data can be faster.

On the other hand… Another benefit of Rc<Box<str>> or Rc<String> over Rc<str> is that you can get back out an owned Box<str> or String, respectively, with little cost, when you’re holding onto the last copy of the Rc.

I guess most of this discussion is atleast somewhat off-topic, so let’s not go too deep :grin:

Regarding the BTreeSet use-case, one can always quite easily build a newtype wrapper that has the required Borrow implementation using BTreeSet<RcBorrowStr<Box<str>>> with something like, say…

struct RcBorrowStr<T>(pub Rc<T>);
impl<T: Borrow<str>> Borrow<str> for RcBorrowStr<T> {
    fn borrow(&self) -> &str {
        (*self.0).borrow()
    }
}
9

Yeah that's a good point actually, I had forgotten that Rc is heap-allocated