Multiple threads accessing std::map in c++

Question

I'm writing a Minecraft clone of sorts and I really want to implement multithreading for things like world generation, updating blocks, light propagation etc. I store all the loaded chunks in a hash map "chunk_map".

Putting a mutex on a chunk_map would defeat the whole purpose of multithreading since most of each thread's work is iterating over chunk_map.

If what i'm thinking is correct, inserting a new chunk into the map shouldn't be problem (in the worst case scenario a thread might skip a chunk that has just been added) But deleting a chunk would definitely be a problem.

Would making a hash map implementation that uses shared_ptr instead of iterator_type solve the problem of removing am element from the map while other thread iterates over that map? Or is there some different, easier approach?

Edit: I want to avoid synchronizing threads entirely as I don't want the world generation, block updates, etc. to cap the rendering performance.

I want the main thread to render all the chunks that are currently loaded. Also I want the "updater thread" to update each block in every loaded chunk, etc. And the "world thread" to load and deload chunks.

Answer 1

Your question is, unfortunately, based on a false premise:

If what i'm thinking is correct, inserting a new chunk into the map shouldn't be problem (in the worst case scenario a thread might skip a chunk that has just been added) But deleting a chunk would definitely be a problem.

No, you're wrong. The worst case is much worse than that. Consider:

1. Thread A constructs a new chunk.
2. Thread A adds that chunk to the map.
3. Thread B sees the entry for the new chunk in the map.
4. Thread B tries to access the chunk, but it doesn't see the writes thread A made in step 1 due to optimizations in the code and in the hardware that re-order the writes.

Boom, your program just crashed.

The key flaw in your reasoning, and this is very common flaw that you absolutely must fix in your reasoning if you want to be a successful programmer, is thinking that if you break explicit rules, the only things that can go wrong are things you can foresee. This line of reasoning is absolute death in the computer programming field.

So, in fact, the absolute worst case is even worse than what I said above. You are violating the requirements of a class you are using, a class whose implementation will vary across platforms. There is absolutely no way you can know what will go wrong.

Answer 2

Deep reading of the container specs is required for the containers to work out what write operations need to be mutexed, and what read operations should be safe even during a write operation.

[Ah you said hashmap]

In a nutshell:

Hashmaps, vectors, and strings are a total pain. It is possible to do stuff that keeps your object pointers good (like pre-allocation), but even single threaded it is hard work to keep references after an insert or delete.

For the traditional maps, sets, lists:

Construction and destruction of the container has to be exclusive, obviously.

If you aren't doing any mods to your map, you can multithread as many reads as you like, of course. As long as you use find() and not operator[] you will be fine.

The behaviour of map and list If you are inserting new objects, then any existing iterators remain valid, but you can't find() or next() (or other iterator arithmetic) during the insert() (assuming the insert() succeeds, so it is often worth doing a find before the insert), and you can't do multiple (successful) inserts in parallel. So you need a 1 writer multi reader locking model: This can be as simple as an atomic find/iterator++ counter and a first/last find vs any insert/delete mutex.

If you are deleting, then , then any iterator pointing to the deleted object becomes invalid, which is also true in single-threaded, but the parallel usage becomes more problematic. Your code needs to have absolute certainty that you don't have any iterators to the deleted element. Depending on your use-case for delete this may not be an issue, or it may be a design killer. I don't see why you would want to delete a resource that you still need/use in another thread, but then I also don't know how your code will know if it is needed. You might need atomic usage counters in each instance, for example, to know which instances are safe to delete at any moment.

If you are doing other mutate operations, you will have to make your own design decisions. These are the main operations, and how I feel they are safe to use.

You can cut it tighter than this with deeper understanding, but these are good performance vs complexity compromises generally.

This applies to most of the containers except vector and string -also hashmap, but for different reasons. But that is because even in single threaded in both cases, insert operations will invalidate existing iterators completely if the storage is moved, and insert and delete operations invalidate any iterators at a higher index. With hashmap the issue is following a rebucket operation pretty much everything you knew before is invalid.

Use of map rather than hashmap in this case can be easier to efficiently lock, but you then have to decide whether the log(n) general performance hit is worth the general low-locking benefit. Alternatively, arrange that your hashmap only contains pointers, so that your code can safely keep pointers to the actual objects rather than iterators or pointers to the contained objects - whicgh are not safe in hashmaps, and blind lock all indexing calls.

Answer 3

You can generate your chunks (Update blocks or whatever) on multiple threads (using std::packaged_task or std::async), and then copy the results into your map using the main thread.

The longest part in your case isn't the map access, it's the data processing.