r/rust • u/CorgiApprehensive159 • 1d ago
📸 media Safe pattern for mutable + immutable access to the same HashMap in a tick loop?
I have a `HashMap<Coord, Box<dyn BlockEntity>>`. During a tick I need to iterate over entities and, for each one, get a mutable reference to it while also getting immutable references to other entities in the same map.
Performance is critical here, so I want to avoid Mutex, RwLock, RefCell. Right now I use UnsafeCell. I'm rebuilding something like Minecraft's block-entity tick loop (you've probably heard of it).
I've also considered a smarter iterator that marks an entry as "taken" and returns `Option` on conflicting access — something like `(&mut elem, &mut NonGrowingHashMap)` from `HashMap::smart_values_mut()` — but I'm not sure whether such a pattern exists in the ecosystem or whether it's worth building. Are there other known patterns or approaches in Rust for dealing with this kind of access?
17
u/STSchif 1d ago
I wonder if you can cow it and write changes back later.
Have you tested just running with some simple form of sync? It can be surprisingly performant. Premature optimizations, yada yada.
3
u/CorgiApprehensive159 1d ago edited 1d ago
I wouldn’t call this "premature optimization." I just want to know the right approach so I can design with it in mind even before it’s actually implemented. This approach actually saved me a lot of time
2
u/CorgiApprehensive159 1d ago
Not sure COW helps if the change happens later. 2. Yes, I tested Mutex and RwLock — no formal benchmarks, but the drop was noticeable. RefCell is out because I need multi-threading.
2
u/Konsti219 1d ago
What kind of multi threading? Do you want to run the loop you described in your post multi threaded?
1
u/CorgiApprehensive159 1d ago
Several of these loops can run independently, one per chunk, taking neighboring chunks into account
3
0
u/obedient_wealth 1d ago
tick loops with unsafe are a dark art but sometimes the overhead of the safe alternatives just kills your frame time
that cow idea is interesting though, if you're only reading a few neighbors per entity you could snapshot the world state at the start of the tick and read from the snapshot while mutating the live map
1
7
u/Konsti219 1d ago
This is kinda what ECS (like bevy) solves. But for such a constraint environment a small wrapper with a bit of internal unsafe should be fine.
3
u/CorgiApprehensive159 1d ago
Not sure ECS is a good fit here. Are there examples of something similar?
1
u/stumblinbear 1d ago
I don't think they were recommending an ECS, just that bevy does a lot of work to solve a similar problem
The most performant option is likely a bit of unsafe. If you can make a data structure or ensure accesses don't overlap, you can drop into unsafe and just get mutable access to the things you need
1
u/CorgiApprehensive159 1d ago edited 1d ago
Sorry, my post is probably misleading. I'd like to avoid RefCell, but it wouldn't be a disaster if I used it or something less optimal. I understand that benchmarks are the foundation of performant code, but unfortunately I can't profile the future. I should add that the project is at a stage where making the wrong decision would cost me too much rework. A better question would have been: "What architectures exist for solving something like this, with performance in mind?"
5
u/scook0 1d ago
Here’s a potential design for a safe abstraction around unsafe code:
-
Store each entity in UnsafeCell, inside a hashmap.
-
For your outer data structure, have a method
fn get_with_eyepatch(&mut self, key: Coord) -> (&mut Entity, EyepatchMap<'_>), where EyepatchMap holds a copy of the key and a reference to the underlying hashmap. -
Add lookup methods to EyepatchMap that will look up an entry by key and return a shared reference, but will refuse to return anything for the original key.
2
u/Gabe__H 1d ago
Note: for a map where the key type is known this is fine, but I think this would have unsoundness if using generics, due to a potentially malicious eq/hash implementation?
2
u/scook0 1d ago
Yeah I think the straightforward implementation would be unsound for arbitrary key types.
If necessary it might be possible to avoid that problem by comparing hashtable indices instead, but that would require finer control of the underlying hashtable.
2
u/Gabe__H 20h ago
Yup, I think hashbrown's Hashtable bucket api would work?
1
u/scook0 10h ago
Having thought about it some more, it might be sufficient to just save a
*const UnsafeCell<V>to the forbidden slot, and then compare pointer addresses after resolving a subsequent key to&UnsafeCell<V>but before materializing a&V.That should (hopefully) be sound even with a stock HashMap and a noncompliant key type.
4
u/Excession638 1d ago edited 1d ago
What you describe in your last paragraph sounds quite reasonable to me. It could be written safely using HashMap<Coord, RefCell<dyn BlockEntity>>, but would probably be faster with HashMap<Coord, UnsafeCell<dyn BlockEntity>>. Whatever key is mutable at the time just needs to be marked as inaccessible to everything else. Use a guard type that implements Drop to clear that state perhaps.
I suspect that getting rid of the boxed dyn trait would be more important for performance. Using an enum instead could massively reduce the total number of allocations, and improve locality of reference, at the cost of hash-map resizes being more expensive. If some entities are too large then just those ones could use a inner: Box<EntityInner> field internally rather than needing an allocation for everything.
1
u/muffinluff 1d ago
Why aren't we doing HashMap<Coord, Option<Box<dyn BlockEntity>>>.While iterating you can call let mut entity = item.take()? on each item and when you are done mutating the entity you do map.get_mut(coor).replace(entity)
1
3
u/vlovich 1d ago
Since you mentioned multiple running concurrently doing updates, what's unclear is what you want happening at the boundary (e.g. where it crosses into the next cell which might be updated by a concurrent thread or might not be and that's purely a race condition). Something like rcu.rs is great in terms of being a high performance concurrency primitive to allow efficient reading from all threads in the face of slightly more expensive writes but it has the downside of being LInux-only which may not fit your needs. ArcSwap is an alternative but isn't as low-cost for reads.
It's a little worrying that you're mentioning RefCell, UnsafeCell, Mutex, and RwLock in the same breath - it indicates you haven't formally defined how the multithreading is supposed to work, because RefCell isn't thread-safe, UnsafeCell almost certainly isn't unless you're super careful and have verified it with Miri, and Mutex and RwLock suck for concurrent access.
3
u/SkiFire13 1d ago
You could use a indexmap::IndexMap, then get the index of elements and from there it's as if you were working with a Vec/slice.
3
u/Guardian-Spirit 1d ago
First of all, benchmark.
Second of all, RefCell is extremely cheap, this isn't something that could really cause any issues. What I feel could cause issues in your design:
-
Multi-core support. Mutex/RwLock, and even lock-free atomic operations, are likely to severely damage horizontal scaling if used wrong. Just a single atomic could cause some form of degradation due to cache bouncing, if you access if from multiple cores. Generally, you really want to avoid contention as much as possible. Take a look at Thread-per-Core architecture. If you can, use RefCell, not Mutex/RwLock/...
-
Box: it's indirection, and requires allocations. Consider usingenum, or have multiple separate storages for data of different archetypes, the way it's typically done in ECS. -
FxHashMapis nice, but I'd honestly be suspicious towards it being the main container. My beef with it is, again, allocations & unpredictable performance. Take a look at arenas such asslotmapinstead as a primary container for your entities if you can avoid Coord-based lookup in favour of opaque-id-based. Slotmap does support the access pattern you're looking for (get_disjoint_mut, it performs a runtime check).
Overall:
-
Benchmark/profile. Any given advice could be wrong in this case.
-
It feels like you're reinventing ECS anyway. Consider looking at how Bevy and other ECS work.
1
u/creeper6530 1d ago edited 1d ago
Mate the golden rule of performance is "measure, measure, measure".
RefCell is literally just an UnsafeCell with an integer counter shoved into a Cell. As long as you don't need multithreaded access, I'd give it a try and measure whether it has an effect.
Also, dynamic dispatch has far greater impact than a Cell ever will, because you need two pointer dereferences and two chances for a cache miss.
1
1
u/karasawa_jp 23h ago
I think the right approach is buffering mutations, grouping them by chunk, and applying them in batch at the end of the tick.
If you group data by chunks, you can replace the fine-grained per-block HashMap lookups with direct array indexing:
// Use Box if Chunk is large to avoid expensive reallocs
HashMap<ChunkCoord, Box<Chunk>>
struct Chunk {
blocks: [Option<BlockEntity>; 16 * 16 * 16],
}
// Avoid Box<dyn ...> to eliminate dynamic dispatch and pointer chasing
enum BlockEntity {
Chest(ChestData),
Furnace(FurnaceData),
// ...
}You can process chunks in parallel.
If you need simultaneous mutable access across different chunks, you can use HashMap::get_disjoint_mut()
66
u/lpghatguy 1d ago
If you can, buffer your mutations until after the loop is over. That has the advantage that you can potentially run the loop in parallel because you won't be interspersing your reads and writes.
Other than that, `RefCell` may not be as big of a burden as you might expect. It's worth profiling.