CODEWITHSUNDEEP
rust
Swordelf
Swordelf

Reputation: 74

How to hold multiple references to different elements inside a container?

Consider this simple example: Having v: Vec<Vec<i32>> I want to add v[1] to v[0].

I'm not even considering sacrificing performance, so cloning any of the vectors is not an option. Thus, no matter how exactly we are going to implement the addition of the vectors, we would need simultaneous references inside v: &mut v[0] and &v[1]. Obviously the problem here is that indexing borrows v and indexing in mutable context borrows v mutably so the borrow checker would not allow this.

This example leads to a more general problem: how can we hold simultaneous references to different elements of a container if all methods that return (mutable) references to elements (mutably) borrow the container itself?

Note that I do understand the origin of the problem and why in compile time the borrow checker cannot see that we are referencing different elements. The question is how do we tell the compiler we are doing the right thing without sacrificing performance and/or safety?

Currently I'm aware of 3 possible solutions without a noticeable performance overhead:

  1. slice::split_at_mut is a decent workaround but unfortunately works only for sequential/slice-like containers. Note that this function utilizes unsafe code in the implementation.
  2. Using iterators: yes, we can hold simultaneous references returned from an iterator, but in many cases using an iterator is not correct, for example, map: HashMap<i32, Vec<i32>> and I again want to add map[1] to map[0]. Note that (to my knowledge) iterators also use unsafe code (directly or indirectly).
  3. And finally the solution that works for every container: RefCell<T>, that is, wrapping elements of containers in a RefCell. (Well, or Cell<T> in some cases). There are two problems with this one though. The first is the slight performance overhead for runtime borrow checking. The second one is that if, for example, I'm writing a function which returns a container, I would either have to make the caller use my RefCell-wrapped container or have the whole container essentially copied in order to remove the RefCell wrapping (Is there a way to unwrap a RefCell inside a container for free?) And yet again, RefCell uses unsafe code.

All of these solutions use unsafe code. Is it really the only way? I'm also quite sure there is a solution that uses unsafe code directly, but as a beginner I'm a little afraid to delve into unsafe Rust yet. Though, if it happens to be a good solution, please point me to the topics I would need to study.

Are there any other solutions and which one is more practical? Please correct me wherever I don't understand something or understand it wrong.

Edit: As Sven Marnach pointed out, my question is too broad, so I'm narrowing the problem down.
I have a map: HashMap<i32, Vec<i32>> and I want to assign map[0] + map[1] (element-wise addition) to map[0] with zero performance overhead. Here, repetitive indexing as suggested by matiu would not be optimal because it would involve multiple searches on the same key. So, is it possible? If not, what is the best solution for this case?

Upvotes: 2

Views: 426

Answers (1)

matiu
matiu

Reputation: 7725

So the goal is to overwrite vec[0] with vec[0] + vec[1] ?

I think the trick is to use indexes into the Vec, instead of holding the references open.

Does this meet the goal ?

fn main() {
    let mut vec = vec![
        vec![1, 2, 3],
        vec![10, 20, 30],
    ];
    let ln = vec[0].len();
    for i in 0..ln {
        vec[0][i] += vec[1][i];
    }
    println!("{:?}", vec);
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=ea1900726ff07b5d2bd0ad39f15e1bba

I also wanted to test if doing it in place was actually faster than creating a new array. "Perhaps the compiler is smart enough to do internal memory re-use" I thought. Turns out the compiler is not that smart.

The for loop with indexes is the fastest way.

Code: https://play.rust-lang.org/?version=nightly&mode=release&edition=2018&gist=1d57a0e5bbb21b3bb87dfc5a7735335f

Results (on my laptop):

running 7 tests
test bench_create_new_array   ... bench:         230 ns/iter (+/- 0)
test bench_for_indexes        ... bench:         174 ns/iter (+/- 0)
test bench_new_array_borrow   ... bench:         231 ns/iter (+/- 0)
test bench_to_owned1          ... bench:       1,097 ns/iter (+/- 4)
test bench_to_owned_in_place  ... bench:         240 ns/iter (+/- 1)
test bench_to_owned_in_place2 ... bench:       1,080 ns/iter (+/- 159)
test bench_to_owned_in_place3 ... bench:       1,037 ns/iter (+/- 2)

Upvotes: 2

Related Questions