Concurrent access to a large collection of items

Question

I'm working on a simulation project using c++ on both windows and linux.

There will be several thousand objects (Perhaps 3000-5000) in the simulation. In plan to have several threads performing actions on the objects so that it makes good use of multi core machines, for example one thread handling movement and location of the objects, one (or more) handling interaction between the objects, one handling creation of new objects.

However this will require synchronization between the threads to ensure it works properly. So I was thinking that each object should contain a (pthread mutex / CRITICAL_SECTION) depending on the platform, and then each thread can lock the objects it currently working on. Because there are a lot of objects contention should be rare so it should be fast.

So my first question is are 3000-5000 pthread mutexes or windows critical sections too many? I don't know what limits both systems have. Or is there are better way to achieve this?

My second question is about data structures to hold the objects. Because objects can be created and "die" I feel the best way is to store a "list" of active objects that the work threads can iterate through. A c++ list is not thread safe though. If one of my threads deleted an object I would need to synchronize that with another object doing "next()" on the list. Also I'd need to ensure that the "next" object was locked before moving my iterator to it so I'd need some kind of global lock on the whole collection which I'd have to obtain before inserting / deleting objects but also before moving to the next object on a thread.

This seems rather painful and potentially slow. Is there are better way?

Answer 1

Specifically on your Windows platform, you can look at Slim Reader/Writer (SRW) Locks - this will allow several concurrent readers.

Answer 2

Have a look at lock-free collections. I believe Intel's Threading Building Blocks (Open Source) have some of them.

Answer 3

There's no inherent limit in the number of pthread_mutex_ts you can create on Linux - they don't have to be registered centrally anywhere. An unlocked mutex takes up no resources other than the bytes used to store the pthread_mutex_t.

If you're going to lock each individual object, watch out for lock ordering deadlocks. You will need to define a strict order on the objects, and ensure that they are always locked in that order.

Answer 4

Instead of having the threads perform different actions on the objects, why not have each thread work on different objects? It sounds like you're doing particle collisions. I worked on a project similar to this, although mine wasn't threaded. But if you can group your objects into 'spaces', each thread can work on its own space and pass objects from one space to the other. You're going to be killing your performance if you have 1 thread doing position tracking, and 1 thread doing collision calculations, because those calculations are very tightly coupled. Thread is (generally) only good when one thread isn't directly dependent on the others.