Modifying items in a collection I am iterating over

Hi, I have a question about iterating over mutable collections. I'm quite proud of myself, as I understood the issue that the compiler was complaining about :slightly_smiling_face: But I'm comfortable that my usage is actually safe here, I just can't work out how to convince the compiler of that fact. So I'd appreciate any suggestions - I'm fairly sure this is a common enough pattern, so I'm hoping there's an idiomatic Rust way of expressing it.

I have a collection of items - players = Vec<Player> which I'm iterating over. Each player has a set of items, and on their turn they pass one of their items to another player. The basic code is

for player in players.iter_mut() {
    for item in &player.items {
        let target = player.dest;
        players[target].items.push(*item);
    }
    player.items.clear();
}

The compiler is complaining "cannot borrow `players` as mutable more than once at a time", and that's entirely fair, as I'm taking a mutable borrow of the player I'm processing, and while I have that, I need to modify the target player. I know, from the data, that the target will never be the same player as I'm working on - and I could add an assert to that effect, to make sure - but the compiler can't know that.

So is there a way for me to tell the compiler that what I'm doing is safe? Ideally, with no runtime cost, but that's mainly because I don't see why I should have to check again, if I've already checked when I built the data structure that everything is consistent.

I tried searching for ideas, but everything I could find was about using iter_mut to allow modifying the element I'm working on. As you can see from the code, I found that for myself (the compiler errors are very helpful if you take the time to understand what they are saying - which to be fair, isn't always easy!) But I couldn't find anything related to my specific issue above.

2 Likes

Yeah, no it isn’t. Iterating over a Vec or slice in Rust is quite efficiently implemented, where at the start of iteration, pointers to the start and end of the Vec's or slice's memory are created, and then iteration increments the pointer until one reaches the other.

This kind of optimization (and similarly other optimizations for other data structures’ iterators) are becoming problematic – in principle – when the data structure is mutated while being iterated. In particular, Vec::push can increase the size of the allocation, i.e. move everything to a totally different place in memory, so that after that, using the pointers created when iteration was started is actually going to access freed memory (= a pretty bad thing). Other languages might solve this problem by avoiding such dangerous optimizations to the iterator, (though – particularly for more complex data structures like sets or maps – even without the danger of memory unsafety, adding/removing elements while iterating can still have surprising effects). Rust solves the issue by ruling out the problem for occurring in the first place via its strict rules against mutation without exclusive access. (With the effect that while an iterator on a data structure exists, you can’t modify it.)

In your concrete case now, if any player’s dest pointed to the player themself, your loop over &player.items would modify that same .items vector inside the loop, the problem described above.

In other words, your code is only fine in principle, if dest is explicitly double-checked to always refer to a different player.

Now, with this insight, let’s see how to modify the code. Well for one thing, for player in players.iter_mut() makes players completely unaccessible during iteration, so this needs to change. Sometimes, as is the case here, we can gain a benefit by iterating over indices instead, though. There is some potential overhead involved in this from additional checks whether the index is in-bounds, but that’s not extremely dramatic, and with some luck, we can even make sure to get most or all of those optimized away.

The re-write lets us start with

for player_ix in 0..players.len() {
    let player = &mut players[player_ix];
    …

and leads right into the next question: How to access two elements of a Vec at the same time? The standard-library approach here is slightly tedious until we stabilize API like this (->link). Maybe, we should just use a helper function for the time being, one possible (safe Rust) implementation could use split_at_mut as follows

/// Panics when `x == y` or either is out of bounds 
fn two_slice_indices<T>(x: usize, y: usize, slice: &mut [T]) -> (&mut T, &mut T) {
    if x < y {
        let (_, [a, bs@..]) = slice.split_at_mut(x)
        else { panic!("index out of bounds in `two_slice_indices`") };
        (a, &mut bs[y-x-1])
    } else if y < x {
        let (_, [a, bs@..]) = slice.split_at_mut(y)
        else { panic!("index out of bounds in `two_slice_indices`") };
        (&mut bs[x-y-1], a)
    } else {
        panic!("equal indices in `two_slice_indices`")
    }
}

Now we can write the whole code successfully, and the code will panic if any dest refers to the player itself.

for player_ix in 0..players.len() {
    let player = &mut players[player_ix];
    let target_ix = player.dest;
    let (player, target) = two_slice_indices(player_ix, target_ix, &mut players);
    for item in &player.items {
        target.items.push(*item);
    }
    player.items.clear();
}

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


Now, the result looks funny though, doesn’t it?

[src/main.rs:40] players = [
    Player {
        items: [
            7,
            8,
            9,
            4,
            5,
            6,
            1,
            2,
            3,
        ],
        dest: 1,
    },
    Player {
        items: [],
        dest: 2,
    },
    Player {
        items: [],
        dest: 0,
    },
]

If this is what you expected, great, feel free to ignore anything beyond this point (might still want to read it though nonetheless),
otherwise, if this result is surprising, well… let me quote myself

even without the danger of memory unsafety, adding/removing elements while iterating can still have surprising effects

In case you expected each player to have, again, exactly 3 items now, then you’ll need to re-work the whole algorithm. Which is a questionably behaving algorithm IMO anyways, even if the result is not unexpected, because the result is clearly dependent on the order of the players. One approach that could work is to work with two vectors of players, back and forth (so you can re-use them, saving some allocation), to – essentially, but slightly optimized – always generate a new list of players. Or you could use (and also keep re-using) a helper structure containing just the new list of items vectors. Maybe start out with a simple version that just always creates new vecs anyways; allocation is not extremely expensive either, anyways.

In case you do want/try to re-write the logic into such an approach, you’ll most likely notice that there’s no longer any hard borrow-checking related errors. I.e. the more predictably behaving code is the one that’s also more easily written.

12 Likes

Understood. But I'm not modifying the players vector at all - just elements of it. So looping from start to end should still be perfectly valid (I believe). You make a good point that optimisers can do some crazy things with the code I write, but I don't believe that's the problem here.

Of course, it's entirely possible I'm being naĂŻve here - I still have a bad habit of thinking in terms of C-like pointers everywhere, forgetting that the Rust compiler is allowed to (and does, I think!) completely eliminate allocations where they aren't needed. But what I want to avoid is questioning my intuition so much that I end up not trusting anything I thought I knew, and simply taking compiler suggestions without any understanding. That doesn't feel like I'm learning the language properly, to me.

As I said (but didn't show in the code I posted) I can guarantee this won't happen - by validating the data structure at runtime. So I think what you're saying here is that my understanding is right, but there's no way to express the necessary guarantee at compile time, so we have to rewrite in a way that the compiler won't object to.

I'd sort of come to that conclusion, but was blocked because I couldn't see how to proceed. And throwing everything away and starting from scratch, apart from feeling like a huge waste, didn't seem like it would offer any insights either.

Eww, I thought I'd left indexes behind when I ditched C :slightly_smiling_face:

More seriously, I tend to think of pointers (which is what my intuition comes up with when considering Rust references) as being more straightforward/efficient than array/index pairs (because there's only one thing to keep track of with a pointer, and there's no addition needed). And I generally prefer pointers over indexes in C (in spite of my joking comment above). Is using an index more idiomatic in Rust than it is in C?

Ooh. I'd never have worked that out myself. I'll need to study this, there's a lot in there to unpack. One thing that immediately strikes me - how efficient is this? Performance isn't critical for my use case, but longer term I am looking at Rust because I want to write code that's as efficient as C, without being as buggy/sloppy as the C I write usually is. And in that context, I look at this and it feels like something I'd normally avoid in an inner loop...

Cool, that's fantastic. Thanks for spending the time helping me with this :slightly_smiling_face:

Sorry, that's my fault, the code I posted was misleading. I extracted the essentials to demonstrate the issue (the code I'm actually writing is for Advent of Code day 11) and didn't work too hard to make the simplified code do something reasonable when run. The actual problem statement does say that the players go in order, and the results of one player's turn can change a later player's (the example given is that a player with no items at the start of a round could receive them during the round and is expected to process what was received).

But you make a good point nevertheless, that there may be a different design that doesn't need the problematic borrowing pattern. That's definitely something I'll think about.

1 Like

The only question here whether that stopped being true 10 years ago or 20 years ago.

Yes. Use of pointers instead of indexes is a microoptimization that became enshrined as something sacred.

You always have to keep in mind that it doesn't matter whether you are using pointers or indexes difference is minimal: when CPU can either process thousand instructions or go to the main RAM one time… whether you are using indexes or pointers matters much less than whether you are keeping data accesses sequential or random.

And because that's what laws of physics dictate that's something that you have to deal with for the foreseable future.

Why wouldn't it be efficient? There are no pointer chasing, everything is pretty localized, compiler should optimize it well, just look on the generated code.

Do you want to be that code efficient when executed on PDP-11 or on contemporary hardware?

Half-century ago memory was so fast and CPUs so slow that, at times, it was even beneficial to precompute functions and put tables in memory.

Change was gradual, yet… today CPUs are speed daemons, beasts, they are insanely powerful, but…

Y-MP C90: Storage for data and check bits is provided by 256 Kbyte x 4 bit bipolar complementary metal oxide semiconductor (BiCMOS) chips with a 15-ns access time.

DDR5-6400: If we look at SK Hynix’s announcement of DDR5-4800, this could be DDR5-4800B which supports 40-40-40 sub-timings, for a theoretical peak bandwidth of 38.4 GB/s per channel and a single access latency of 16.67 nanoseconds.

Why? You want to avoid pointers in the inner loop, not calculations. That's why moving from one set of players to another may be faster than doing what you have done here: adding indirection for each and every player.

Sure, if your data reorganisation which would attempt to avoid pointer chasing would make the whole thing 10 or 100 times less memory efficient then the fact that calculations even on fastest CPU are “fast but not instant” would bite you, but 2x memory consumption in exchange for one less indirection? That's not even a contest.

Rust is as much result of today's hardware as it's result of last century language research. Typical Rust program does insane amount of memory copies compared to typical C program yet in a world where memory copy is cheap but random access is expensive… they achieve approximately same speed.

2 Likes

That's true, but there is still the rule that no &mut may alias with any other, which in this case is by-default enforced by a borrow of an element being counted as derived from a borrow of the whole vector, which means that modifying multiple elements requires extra work. If you want to pursue the path of making the compiler acknowledge this distinction between modifying the vector and modifying one of its elements, the way to do that is to use a Vec<RefCell<Player>>. Then, you can have multiple & borrows of the vector's elements, and use the RefCells to get from there to multiple &mut Players as long as they don't overlap.

(In a situation where you were modifying the vector, the same idea can still work but you would also need to introduce shared ownership — Vec<Rc<RefCell<Player>>>.)

4 Likes

Wanted to address a few points, since I liked the follow-up questions; didn’t have time before to answer earlier; I haven’t read through the previous two answers, so there might be duplication.

Yes. I provided the context nonetheless on one hand to explain why Rust’s restrictions are useful, and on the other hand to explain why this concrete piece of code can lead to use-after-free if the invariant about the dest never pointing to the player themself was violated. (Which is not to say that the original code would be UB-free without modification if – say – unsafe code was used to make the lifetime problems go away, since aliasing a mutable reference in and by itself is already UB.)

Ah you do say that. I must admit, I read your original post rather quickly.

Well, as you figured out yourself, this operation relies on an invariant about (player) indices you explicitly store in the struct in order to work in the first place, so with that in mind I’m not really finding it all that surprising that we need to explicitly handle the player indices here.

Naturally, since idiomatic Rust is safe Rust, and pointers can only be used in unsafe Rust, if the choice is between indices and pointers, then indices are preferred. Of course, there are some technical benefits to using pointers, and the corresponding practice in Rust is to use pointers encapsulated in safe abstractions whenever possible. Rust’s shared and mutable reference types are examples of such safe abstractions, and iterators over slices are another such exception. Wanna use the same element multiple times in a row? In C, you’d save the pointer instead of repeatedly indexing; in Rust you save the reference. Want to use the (often easier to optimize) way of iterating an array by incrementing a pointer and comparing against the end? Rust allows it using iterators; the second benefit of those being that the repeated bound-checks of repeated (safe) indexing are gone for good, too. But you’re probably aware of this.

In conclusion thus, idiomatic Rust generally prefers safe over unsafe, and then prefers pointers over indices, so existing safe (often pointer-based) abstractions are preferred over using indices, which in turn is preferred over unsafe code using raw pointers, … and I guess, unsafe code using indices comes last :sweat_smile:? Of course, this guideline relies on “safe abstractions” which are actually unsafe code internally; in other words the guideline applies to code where a high-quality safety code review is too tedious (especially as a trade-off against how important performance is); and to code where the existing safe solution doesn’t have any (performance) disadvantages over unsafe alternatives.

It’s mostly a useful exercise of learning about split_at_mut and how powerful it is (and about similar methods; feel free to search for everything saying “split”), I’m also using pattern matching on slice patterns and the new let … else {…}; syntax.

I think the answer is, better than one might pessimistically expect[1], but also not as optimal as you’d want in really tight loops. In the long time, the get_many_mut API I linked will solve that problem anyways, since that is implemented in a more straightforward “first check bounds and inequalities, then use unsafe code and pointers to access” implementation.


  1. and there’s also always possibilities of micro-optimizing against the optimizer (inspecting the assembly for things like e.g. branching disappearing, etc…, sometimes some cleverly placed asserts can improve performance; as said, my main point here was getting a working implementation at all ↩︎

3 Likes

Thank you. While I'm not as naĂŻve about modern hardware as you suggest (and to be fair, my oversimplified comments implied) a lot of what you said was, if not new to me, certainly something I haven't internalised as much as maybe I need to.

I'll be honest, I don't need performance here, my interest is more about trying to update my intuitions. So your comments are helpful in that context.

1 Like

Actually, there's a much simpler way of handling this. I was led down the wrong path by my C background, where copying data that's on the heap, and anything that feels like a malloc(), is something I avoid as much as possible, because ownership is such a mess to manage. But Rust handles ownership just fine for me, so I can simply clone the vec of items. (Yes, I know I'm going back and forth over whether I care about efficiency here - my insight is that what I actually care about more, is ownership tracking, which Rust handles for me).

When I clone the items, everything else just works:

    for player_ix in 0..players.len() {
        let items = players[player_ix].items.clone();
        let target_ix = players[player_ix].dest;
        for item in items {
            players[target_ix].items.push(item);
        }
        players[player_ix].items.clear();
    }

That's the clean and understandable version I was looking for :slight_smile:

As you said, "you’ll most likely notice that there’s no longer any hard borrow-checking related errors. I.e. the more predictably behaving code is the one that’s also more easily written". Lesson learned (I hope!)

Thanks again for your help.

5 Likes

I would probably write this as something like

    for player_ix in 0..players.len() {
        let items = std::mem::take(&mut players[player_ix].items);
        let target_ix = players[player_ix].dest;
        players[target_ix].items.extend(items);
    }

Which avoids the clone+clear combination in favor of take, and avoids the need for an explicit .push loop in favor of .extend.

4 Likes

Cool, I like that. I wasn't aware of take. In my real example, there's more than one target, so extend doesn't work directly, but I might be able to partition items by the appropriate targets and then use extend with the partitions. But I think that ends up either creating temporary vectors of the partitions, or scanning the items vector twice.

None of this matters much in reality, of course - the item lists are probably all under 10 items long...

1 Like

That was my main point, pointing out API you might not have been aware of. The performance is probably fine either way. But mem::take can be useful in general, in more situations: in particular once some types involved are not Clone. The mem::take function is mainly a convenience abbreviation of mem::replace(…, Default::default()); and beyond those two, the third (somewhat related[1]) convenience function for useful ownership transfer functions is mem::swap.

Similarly, I know .extend is sometimes hard to find since it’s a trait method, so somewhat poorly documented in terms of ease of discovery. Maybe you were aware of it already, if not, feel free not to use it if your concrete use case doesn’t fit, no problem; I just wanted to make sure that you’ve seen it before.


  1. mainly since mem::replace could [but AFAIR isn’t] be implemented using mem::swap so mem::swap is in a sense the most general of the tree ↩︎

7 Likes

My knowledge is far behind from people who already answered so I feel a bit uneasy to step in, and I'm not sure I should even add anything to this discussion since it's already solved, but there's also a simple way to get the job done by droping the monkey (borrowed mutably) whose turn is been processed once all decisions have been made, and before throwing items to the other monkeys (borrowing mutably a second time).
Like this for example : AoC day 11. This is far from being elegant or optimized, but it works.

2 Likes

Thank you. That's a really useful insight - I'd seen some mentions of drop in the docs, but hadn't really understood the point, or how it might relate here. So I've definitely learnt something from your suggestion, which (as far as I'm concerned) is the main point here :slightly_smiling_face:

2 Likes

Sometimes the hyper smarties (from whom I learn and appreciate a great deal :)), overthink it, thus making your “why not this?” useful and sometimes, exactly what was needed :))

Well I also love the previous provided answers because these personally allows me to better grasp the lower level concepts that are on my "next steps to-learn" list :slight_smile: