Multiple mutable references to elements within one vector

#1

Hi,

Got some questions and would appreciate some feedback on a possible solution to a problem I have!

Problem:
Taking two or more mutable references to separate elements within a vector at the same time is not possible. I need to do this with almost no overhead (very performance critical part of the code).

Other solutions I’ve come up with so far:

  1. split_at_mut() - however this seems to have non-trivial overhead (creating two slices and then calculating the correct indexes in the new slices).
  2. Use raw pointers. Not very pretty though.
  3. Take immutable references from the vector and wrap the elements (or the fields in the elements) in Cells. Doesn’t feel idiomatic. Is there any overhead associated with using cells?
  4. Trying to take the references at different times (in different scopes). Tried this quite a bit, but didn’t work out. Could be solved by running all the relevant code in a 200 LOC function, but that isn’t very nice.

Dream solution:
Having a type that you give a mutable reference to the vector. This type keeps track of what indexes you’ve asked for and you can ask it for a mutable reference from the vector with try_get(index: usize) -> Option<T>. If you already asked for that index, or the index is out of bounds, you get None. Otherwise you get the mutable reference that you asked for. Then there could be a version of the function that returns T directly and panicking if that index has already been used or if out of bounds, because in my case, the caller can guarantee that the indexes are unique, and this would eliminate some overhead.

Would this work? Wouldn’t this be (relatively) easy to implement as a separate library? Are there any improvements that could be made to the core language to make things like this even better?

What do you think about this in general? After all, this seems to be a common problem where there doesn’t seem to be any simple idiomatic solution. Would you recommend me on giving my “dream solution” a try?

#2

How did you measure this overhead?

#3

I can’t imagine this imposing any significant overhead. Is the overhead measurable in your case? Or are you hypothesizing?

Depends on what kind of cell - RefCell or Cell? The latter will not have overhead, but it’s limited to the types you can use it with. The former will have overhead related to dynamic borrow checking.

#4

Another solution is to use vec.iter_mut() and call next or nth on it repeatedly.

#5

If split_at_mut() is too much slow for you then you can write one or more safe functions that contain unsafe code and offer a safe API, just like split_at_mut().

Something like this, that uses raw pointers inside and verifies the given indexes are different:

let (r1, r2) = arr.get2_mut(index1, index2);
let (r1, r2, r3) = arr.get3_mut(index1, index2, index3);
#6

How did you measure this overhead?

I didn’t.

I can’t imagine this imposing any significant overhead. Is the overhead measurable in your case? Or are you hypothesizing?

Just hypothesizing. But this is one of the hottest parts in my fluid simulation, so I’m aiming very high with optimization here.

Depends on what kind of cell - RefCell or Cell? The latter will not have overhead, but it’s limited to the types you can use it with. The former will have overhead related to dynamic borrow checking.

I think I can do with Cell.

#7

The overhead of maintaining a table of indexes would almost certainly exceed the overhead of calculating indexes because of split_at_mut. You should try both split_at_mut and Cell and benchmark them.

#8

This is going to boil down to a few additions (with some values as constants) with some of them possibly being folded into memory addressing modes supported by the underlying CPU (e.g. x86 has some). Unless the rest of your code consists of 2 + 2 (:slight_smile:), I wouldn’t expect this to show up.

This would be a good option to try since the code will likely be more straightforward than with split_at_mut.

#9

I don’t know if it would work for me since I’m doing spatial partitioning and there is a complex system with multiple vectors. But if all other good solutions fails, I will look into this.

Good to hear that you recommend something like this, because that is what I’m considering.

Ok, that might be true. If I take all of those things away I guess my idea of a wrapper type is just a way to get an interface that uses unsafe code. Maybe I could just skip the wrapper type then.

Thanks, good to know!

Ok, so I guess the answer is to use unsafe raw pointers if I want zero overhead, or wrap the fields of the Particle type (that is the element in the vector) in cells. I guess using cells would save me from unsafe, but it feels like abusing the language - using unsafe seems like the most idiomatic solution then. Am I correct in this conclusion?

#10

I’m not sure why it would be an abuse of the language when Cell is provided by the language specifically to do the kind of thing you want to do.

#11

I though about wrapping each of the Particle’s fields in cells. That would be unidiomatic since the interior mutability of the Particle type is only due to the requirements of a type that happens to use it.

The other option is to wrap each particle in a refcell (the I would have a Grid<RefCell<Particle>> type. But this, to my knowledge, adds overhead. Using try_borrow() would certainly add overhead, and I think borrow() would to, or at least it would add a pointer indirection, which would increase cache-misses, I think.

#12

There’s no extra indirection - RefCell just adds a flag alongside the value. The overhead is in checking that flag.

#13

That’s good. And does borrow() skip the checking of that flag (So that there is no overhead)?

Edit: I mean borrow_mut()

#14

No. Both borrow and borrow_mut check the flag.

#15

Ok, but the overhead isn’t as bad as I thought in that case (I was mostly worried about the pointer indirection, but it turns out that isn’t the case). I will consider using RefCells then, but will try to get a clean raw pointer implementation as that feels like the most idiomatic way to do this (unsafe rust is a feature after all).

Thank you everyone for your help! :slight_smile:

#16

I don’t think it’s unidiomatic. There’s certainly nothing unsafe about it. If you think of immutable/mutable borrows as allowing shared/exclusive access, and not as “immutable means no writes” and “mutable means I can write”, then it won’t seem odd.

I’d explore this before going all raw pointer about it - that will run the risk of being, well, unsafe (maybe not now but with some future refactoring) :slight_smile: .

#17

This is a common issue I run into when working with Rust vectors however I completely understand why the borrow checker does this.

I put together a little subvert crate which lets you “steal” a mutable reference and subvert the Rust borrow checker using the steal macro. This is inherently unsafe and any use of steal will need to be in an unsafe block but if you take care with it you shouldn’t run into any problems.
Additionally since it is a macro you are using and it is just converting a ref -> ptr -> ref again the optimiser should get rid of all overhead!

Hopefully you find it helpful.

#18

Note that having multiple live &mut to a single value is undefined behavior in Rust, which means that any Rust program which does that is considered incorrect by the Rust specification, and subjected to be trashed without prior warnings by future versions of rustc’s optimizer.

That UB is important to have so that future rustc versions can fully leverage the benefit of Rust’s “every reference is noalias” model. It opens more opportunities for autovectorization in computational code, for example.

#19

You did convince me so I went with wrapping the Particle type’s fields in cells. It works, but now a immutable reference (&Particle) isn’t entirely safe to share. I guess it would even be safer to use raw pointers as I would be forced to explicitly state that the parts of the code using this struct is indeed unsafe.

However, for me this solution was much better than using raw pointers, since I don’t have much knowledge in “the dark arts of unsafe rust”. So thank you vitalyd! :slight_smile:

But now I have this nice crate that I would very much like to use! So I will give this a try too, thanks!

This scares me :slight_smile:. I don’t know what this really means and I’m compiling to wasm too, so maybe that is another source of complications in this regard? But isn’t this what split_at_mut() does?

I’m interested in hearing everyone’s opinion/thoughts on how this issue could be solved in the best way in the future? After all, as Dynisious writes, this is a common issue. Rust just feel too restrictive here. I’m starting to think again that my initially proposed solution isn’t that bad after all.

Basically, create a wrapper type that takes a mutable reference to an underlying collection and provide functions for borrowing multiple elements immutably or mutably without any restrictions except for out of bounds checks. And this type could also allow for an optional “checked” borrow function that checks whether you’ve already asked for that index (as withoutboats noted, that might be slower that split_at_mut, but just in case anyone wants it and don’t care about performance).

The point of having a wrapper type that takes a mutable reference to the collection is that you want to lock it from being mutated during the time you take mutable references to its elements. So it’s like raw pointers with a little extra safety and a nicer API.

Thoughts? Any other ideas? :slightly_smiling_face:

#20

Ok, another solution that uses no unsafe rust:

A struct that takes a mutable reference to a collection and all the indexes you want to “lend” out. This struct is returned instead of the actual references to the elements. The function that get this return value is then responsible for making sure only one mutable reference is borrowed at a time. In my case this would work and I think it might work in most situations and at the same time be nice to use. And I guess the compiler would be able to optimize away all the extra steps in the code that does so that two mutable references aren’t borrowed at the same time (first take two immutable references, do the calculation on these, then store the result in a variable, close and start a new scope, modify the first element based on this calculated variable, then modify the last element).