How to have multiple ownership on String with high performance?

help
#1

Runnable code:

use std::rc::Rc;
#[derive(Clone, Debug)]
struct State{
    pub id:Rc<String>,
}
impl State{
    pub fn id(&mut self) {
        self.id=Rc::new("".to_string());
    }
}

fn place_a_piece<'a>(dedup_ids:&mut Vec<Rc<String>>, states:&mut Vec<State>){
    let mut state=State{id:Rc::new("".to_string())};

    // In real game program, the following logics will be executed 80000+ times,
    // to simplify, shrink it just like this eliding all gaming logics.
    let  mut spawned_state=state.clone();
    dedup_ids.push(Rc::clone(&spawned_state.id));
    states.push(spawned_state);
}

fn main(){
    let size=90_000;
    let mut dedup_ids:Vec<Rc<String>>=Vec::with_capacity(size);
    let mut state:Vec<State>=Vec::with_capacity(size);
    let now = std::time::Instant::now();
    for _ in 0..90_000 {
        place_a_piece(&mut dedup_ids, &mut state);
    }
    println!("{:?}", now.elapsed());
}

Expectations:

  1. Let State be real owner of State.id's content.
  2. Anywhere else containers like 'dedup_ids' only holds some kind of reference pointing to State.id without copying its content around.

What I did:

  1. Using Rc instead of String.clone() in function place_a_piece().

What I found:

  1. It turns out Rc does not make big difference at all.

Issues:

  1. Is lifetime a faster solution? How?
  2. What could be the speedy way to fulfill the expectation? I'm desperate for speed.
  3. Is the manual way of cloning State is a faster way to do the same job than simply using Clone in attributes as the code does?
#2

"".to_string() won't make any heap allocation because it's an empty string, so your Rc solution is actually making more heap allocations. Also, Rc<String> allocates at least 56 bytes, so it might still be worse than having two Strings with less than 56 ascii characters.

Consider using normal references if you can, they're always faster. The downside is that you'll have to deal with lifetimes.

You may also consider to use smallstrings if you think you're allocating a lot of small sized (like, less than 20 bytes/ascii character) Strings, or even a fixed sized array if you know your id has a fixed size. In these cases cloning/copying them should be pretty cheap.

Finally there's Rc<String> if none of the above works. This generally the case for when references are not an option and you need to share many big Strings.

#3

…and if OP doesn't need to mutate the string, then Rc<str> is probably better than Rc<String>, because it's only one level of indirection instead of two.

3 Likes
#4

I'm not getting my head around lifetime yet. Maybe fix sized array is a choice, but I need State.id to be de-duplicated, that relates to determining if one array is equal to another, I'll try harder on lifetime and array.

#5

Actually lelt State.id() method return &str is my first choice, it works even without Rc, but previously I posted the codes of State.id() method for optimization (topic='Focus on String, Rust vs Java, 5.23 seconds vs 464 milliseconds?'), it turns out that guys here suggested State.id() should return String to reduce the time complexity, this is where this post comes from.

#6

Hi, where did you get '56 bytes'. Here is what I tried:

impl State{
    pub fn id(&mut self) {
        self.id=Rc::new("123456789".to_string());
        println!("a={}", std::mem::size_of_val(Rc::get_mut(&mut self.id).unwrap()));
        println!("b={}", std::mem::size_of_val(&self.id));
        println!("c={}", std::mem::size_of::<Rc<String>>());
    }
}

Prints:
a=24
b=8
c=8

BTW: How to explain 2=24?

#7

The Rc is 8 bytes stored inline. It points to its allocation, which contains a strong count (8 bytes), a weak count (8 bytes) and a String (24 bytes for pointer, length and capacity). So it's only 48 bytes, but if the string actually allocates it'll be more.

#8

Arrays implement both Eq and Hash if their elements do.

In that thread and the suggestion was to return a String because you weren't storing it anywhere and leaking without a reason is really bad. However if your State struct owns the String then you can return a &str that points to it.

a is the size of a String. It consists of a pointer, the length and the capacity, all of them are the same size of usize, which on a 64bit machine is 8 byte. 3*8 = 24 bytes total
b is the size of of a Rc<String>, which is just a pointer, 8 bytes
c is the same as b

However these sizes ignore what is allocated on the heap. As @Kestrer showed an Rc<String> allocates 40 bytes (yeah, I messed up a bit there) on the heap.

2? Do you mean a?

2 Likes
#9

Sorry, I mean how to explain a=24

#10

Oh, thank you very much, String consists of two parts spatially, I forgot that, that is often the way Rust is working, I should always keep that in mind. So actually, what I'm sizing is all about what's sitting in the stack rather than the data content on the heap as you clearly pointed out.

#11

But that leads to the cost of converting String to &str.

#12

That "cost" is just a cost of copying a pointer-length pair.

1 Like
#13

Followed @SkiFire13's idea as he mentioned before, "cloning array is cheap", now I let State.id be [usize;20], it turns out really fast, but with one not-good-enough, cloning. Do you (@SkiFire13 ) think Rc<[usize;20]> will be faster than [usize;20] alone with no cloning? Thanks to @Cerberuser, I think [usize;20] is faster than growing String then converting it into &str.

Sorry, accidentally reply to myself, don't know how to change.

#14

My experiment shows that sharing reference with Rc<[usize;20]> is slower than cloning [usize;20].

#15

[usize; 20] has a size of 160 bytes (on a 64bit machine) which sounds like a lot of bytes for an id. For comparison, GUIDs and UUIDs are both just 16 bytes and even that may be a bit too much depending on what you're doing. You could consider reducing the size of the id to speed up copying it. For example just brining it down to [usize; 16] will allow to skip a call to memcpy (godbolt link), but if you're using incremental ids a u64 will be even better.

2 Likes
#16

My experiment shows that sharing reference with Rc<[usize;20]> is slower than cloning [usize;20].

Makes sense. When you clone a Rc, it's doing arithmetic, comparison, branching, and using pointers. When you clone a [usize; 20], it's just copying bytes from one location to another.