Iterate through hashmap while mutating it


#1

I am writing a game server and I have a player list defined as follows:

player_list: HashMap<Uuid, Player>

Every tick, I iterate through them and call their update function which takes self by mut reference.

for p in player_list.values_mut() {
	p.update();
}

The problem now is that there’s no way for one player to know about the state of another player. If this was C# or java, I could pass the player_list
to the update method and have players know about everyone else.

I’ve thought of a solution and came up with using 2 player lists. One for iterating, and other for passing to update. It will look like this:

player_iter_list: HashMap<Uuid, Rc<RefCell<Player>>,
player_list: HashMap<Uuid, Rc<RefCell<Player>>,

I’ll keep both lists synced.

I can’t help but feel this is kinda overkill and ugly (with .borrow() or .borrow_mut() everywhere).

Is there a better way I’m missing?


#2

I’m working on porting a simulator at the moment, and had a similar issue. I solved it by completely redesigning the data structures from scratch.

I’m afraid “mutate while reading” patterns are never going to fit nicely with Rust.

In my case, I restructured the tick loop such that the entire state of the world from the last tick is immutable, and passed into all tick functions. Depending on what they’re doing, tick functions return bits of modified state. In some cases, it’s a new version of some state table. In others, it’s a list of changes that need to be made.

Once all the tick functions are done, the return values are integrated back into the world state all at once. New tables replace old ones, lists of changes are processed serially.

As a consequence of this design, it’s also incredibly easy to parallelise with rayon.

The one aspect of the design I’m not currently happy with is that it doesn’t re-use any of the intermediate allocations. It’s less clear how to make this work with rayon, but it should be doable.


#3

That’s a very interesting way of doing things. How do you represent the changes? If I have a player like this: Player {name: String, pos: Vec3, etc..} what kind of datastructure do you use to represent the changes?


#4

Depends. Typically, I have all the fields that change frequently in one table, stuff that never changes in another. Structures are also divided up based on how they’re updated; so, all the navigation stuff for an entity is in one table, all the scheduling stuff in another. The navigation tick function, then, basically just produces a completely new Table<NavState>.

Other updates are done through an Action data structure that’s essentially just an enum that describes what to change. So some tick functions will produce a list of actions, which are then invoked individually on a mutable world state.


#5

Wouldn’t that require iterating through entities twice? One for getting updates and then applying it later? Wouldn’t that hurt performance?


#6

Your attempt seems close to what I’d do, but instead try something like:

fn tick_all_players(player_data: &mut HashMap<Uuid, Player>) {
    let player_list: Vec<Uuid> = player_data.keys().collect();
    for key in &player_list {
        player_data[key].update();
    }
}

Now if you need to do this very frequently, you’d want to maintain the player_list alongside the player_data instead of building a new vec all the time, but it’s the same core loop:

fn tick_players(player_list: &Vec<Uuid>, player_data: &mut HashMap<Uuid, Player>) {
    for key in player_list {
        player_data[key].update();
    }
}

#7

But this still wouldn’t let you see the state of other players in the update method, because the HashMap is still borrowed here as well.


#8

Oh, I see, sorry.

Well you can solve it with unsafe :stuck_out_tongue:


#9

RIP. I think I’ll go with Rc RefCell for now, although Daniel’s method is also interesting. But that would require a lot of changes and a paradigm shift.


#10

Aw comeon, it’s not that dangerous, you only have to lie to the compiler a tiny bit :stuck_out_tongue_winking_eye:

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


#11

Creating an aliased &mut is Undefined Behavior. It might work as you’d hope, but absolutely nothing is guaranteed about this.


#12

One option might be to remove the player from the map, do the update, and then put it back. It has perf cost and you need to consider what happens if some code panics, but it would let you do what you want. It has the added benefit that the update player can’t find itself in the map.


#13

Not really. The big batch updates just involve replacing one table with another. The action updates are things like "set behaviour to X", which involves directly changing a specific value in a particular table that wasn’t being updated every tick anyway.


#14

Yeah, the unsafe version of things is only safe because HashMap has no interior mutability, and also relies on Player having no interior mutability. Also you still probably should not look at “yourself” through the map because writes to your &mut self ref are theoretically re-orderable to before or after the time when you’re reading through the map. Other than that, if you start with the unique access to the hashmap, each pass of the loop will have unique assess to that particular player value for that iteration.


#15

This may be more complex than you think, doing updates like this is going to have some issues with players seeing some other players updated and some not depending on if you got to updating them before you update current player…

In fact, every player should probably see the state of other players BEFORE update to be consistent.
If you let players somehow react to in-progress changes in other players you will run into dependency loops where players react to change in each other forever or one of them gets stale data and loses

I would suggest passing list of player data from previous tick to the update loop