Impl From<String> for Rc<str> copies the underlying buffer

std implementation:

#[cfg(not(no_global_oom_handling))]
#[stable(feature = "shared_from_slice", since = "1.21.0")]
impl<T: Clone> From<&[T]> for Rc<[T]> {
    /// Allocate a reference-counted slice and fill it by cloning `v`'s items.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::rc::Rc;
    /// let original: &[i32] = &[1, 2, 3];
    /// let shared: Rc<[i32]> = Rc::from(original);
    /// assert_eq!(&[1, 2, 3], &shared[..]);
    /// ```
    #[inline]
    fn from(v: &[T]) -> Rc<[T]> {
        <Self as RcFromSlice<T>>::from_slice(v)
    }
}

#[cfg(not(no_global_oom_handling))]
#[stable(feature = "shared_from_slice", since = "1.21.0")]
impl From<&str> for Rc<str> {
    /// Allocate a reference-counted string slice and copy `v` into it.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::rc::Rc;
    /// let shared: Rc<str> = Rc::from("statue");
    /// assert_eq!("statue", &shared[..]);
    /// ```
    #[inline]
    fn from(v: &str) -> Rc<str> {
        let rc = Rc::<[u8]>::from(v.as_bytes());
        unsafe { Rc::from_raw(Rc::into_raw(rc) as *const str) }
    }
}

#[cfg(not(no_global_oom_handling))]
#[stable(feature = "shared_from_slice", since = "1.21.0")]
impl From<String> for Rc<str> {
    /// Allocate a reference-counted string slice and copy `v` into it.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::rc::Rc;
    /// let original: String = "statue".to_owned();
    /// let shared: Rc<str> = Rc::from(original);
    /// assert_eq!("statue", &shared[..]);
    /// ```
    #[inline]
    fn from(v: String) -> Rc<str> {
        Rc::from(&v[..])
    }
}

#[cfg(not(no_global_oom_handling))]
#[stable(feature = "shared_from_slice", since = "1.21.0")]
impl<T: ?Sized, A: Allocator> From<Box<T, A>> for Rc<T, A> {
    /// Move a boxed object to a new, reference counted, allocation.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::rc::Rc;
    /// let original: Box<i32> = Box::new(1);
    /// let shared: Rc<i32> = Rc::from(original);
    /// assert_eq!(1, *shared);
    /// ```
    #[inline]
    fn from(v: Box<T, A>) -> Rc<T, A> {
        Rc::from_box_in(v)
    }
}

The String is first borrowed as &str, then converted to &[u8], and copied byte by byte to construct the new buffer managed by the returned Rc<str>. The original String is then dropped.

Why doesn't impl From<String> for Rc<str> just move the String and reuse its underlying buffer?

And that means it's more sensible to use:

fn consume_string(owned_string: String) {
    let rc_str: Rc<str> = owned_string.into_boxed_str().into();

instead of:

fn consume_string(owned_string: String) {
    let rc_str: Rc<str> = owned_string.into();

Because the latter, although works as documented, doesn't work as expected?


PS: impl From<String> for Arc<str> shares the same issue.

1 Like

Why doesn't impl From<String> for Rc<str> just move the String and reuse its underlying buffer

An Rc<str>'s allocation must have a size which fits the string exactly, plus two usize for the strong and weak reference counts. It is unlikely that a String would happen to have exactly that capacity. Even if it did, the text would still have to be copied to make room at the beginning for the reference counts.

(Arguably, std should do this anyway, so that it's possible to create an Rc<str> with zero extra allocations. But the "two usize" part is an implementation detail, so properly it ought to be some kind of way to create an Rc<str> directly from a formattable value, like ToString does, rather than requiring the caller to know what string capacity to allocate.)

And that means it's more sensible to use:

No, .into_boxed_str().into() will cause either one or two reallocations and copies:

  1. String::into_boxed_str() must discard extra capacity to ensure the allocation is right-sized for Box.
  2. From<Box<T>> for Rc<T> must add space for the reference counts.
1 Like

Creating a smart pointer with more internal fields from an existing smart pointer does add space, but both pointers themselves are Sized which means they can live on the stack (most of them do). So no heap allocation necessary except for the shared reference counter (which is needed anyway).

Still more sensible than creating a brand new buffer and copying the original one's data before dropping it.

In the implementation of Rc and Arc, the reference counts are stored next to the data. The allocation we're discussing is the allocation for the shared reference counter, as well as for the data. (I understand that C++'s shared_ptr uses a separate allocation, unlike Rust.)

Sorry, I didn't write it out clearly: by “discarding extra capacity”, I mean reallocating and copying to a smaller allocation (unless the capacity happens to be an exact fit). .into_boxed_str().into() will always perform at least one more reallocation and copy than necessary, so you should not use it.

3 Likes

Ah, I thought that Vec::shrink_to_fit() shrinks in-place, which is actually not the case.

Constructing a new buffer (with additional reference counters) with copying makes a lot more sense when shrinking involves copying anyway.

Plus the implementation detail that the shared underlying T (in Rc<T>) and the shared reference counters are allocated together instead of separately.

Got it.

Big misunderstanding: impl<T, A> From<Box<T, A>> for Rc<T, A> being O(1) because it just "adds an extra layer of wrapping" and String:into_boxed_str being O(1) because it just "peels off unnecessary parts". Both are not true.

By the way, does the default allocator never shrink in-place?

Do you mean...

It can, but is not guaranteed to. (The allocator might not support shrinking, or might only support it for some sizes — for an example, an allocation might be located in a dedicated region for 1024-byte allocations, so that if it is to be shrunk it must be moved.)

If you want the characteristics of the extra layer, then you can have it: simply create an Rc<String> instead of an Rc<str>. This requires an extra indirection when reading the string, but in exchange, the text will not be copied.

3 Likes

Yeah I'm asking for the details.

As long as the required alignment of the data is less than the guaranteed alignment of the platform’s allocation functions, which is typically 16 bytes on a 64-bit system, the Rust allocator will call realloc from the C library or HeapReAlloc from kernel32.dll. Whether that function shrinks in place is unspecified by the POSIX.1 standard or the Win32 API.

Another interesting question is why it'a done like that.

i recommend you to read either the Myth of RAM (less technical, more fun approach) or What Every Programmer Should Know About Memory (more detailed and deep but larger and harder to read) if you want to know why in today's world talking about something being O(1) almost never makes sense.

Otherwise it's hard to understand why Rust picked “worse” solution that C++…

TL;DR version: in a world where one, single mispredicted pointer access (where you actually hit RAM, not L1/L2/L3/L4 cache) takes about as much time as memcpy for approximately 1K of data… pointer chasing is far from being O(1).

That's why no one, today, uses AVL-trees or RB-trees if they care about speed (Rust doesn't even have them in a standard library!), e.g.

They made tons of sense back when they were introduced, but times… computers hit the physical limits and math had to adapt.

C++ standard library was also changed a tiny bit to better work in today's world when CoW strings became deprecated in C++11, but that experience was so painful that after that no similar attempts were tried — but Rust did things in a way that makes sense in today's world, not in a world that no longer exists.

4 Likes

Theoretically with associated type specialization it might be possible to put those usizes at the end for Rc<str> which means the payload won't have to be moved and the resizing might end up being in-place. But currently specialization is not powerful enough.

I'm trying to understand the difference between Rc<str> and Rc<String>, but am having trouble understanding their layouts.

I don't know if Rc<str> has a buffer or a pointer to a buffer.

Is Rc<str> represented as follows?

| strong | weak | ptr | len |
                  |
                  +--> | utf-8 bytes... |

Or is it something like this?

| strong | weak | utf-8 bytes... | len |
or
| strong | weak | len | utf-8 bytes... |

It’s like this:

| ptr | len |
  |
  +--> | strong | weak | utf-8 bytes... |

A pointer to an unsized type is a fat pointer, with the metadata (in this case len) living alongside the data pointer. (This lets you construct such pointers by coercing from pointer-to-sized to pointer-to-unsized, for example Rc<[u8; N]> to Rc<[u8]>, or Rc<MyType> to Rc<dyn MyTrait>.)

Meanwhile, the strong/weak refcounts have to live in the Rc’s heap allocation, so they exist in just one place even if there are multiple Rc pointers sharing this data.

6 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.