Parallel write to array

Question

I have a huge array of data where I need to read/write from/to random place from different threads. Having one mutex obviously will kill the performance. My idea is to have many mutexes each one is responsible for particular range in array. This way before writing I can lock a correct mutex based on index in array where I'm gonna to write. In theory it can reduce the race. But I wonder - maybe there's a better way?

Answer 1

That sounds like a reasonable way to go.

There are a number of things to consider, though:

1. You state that your idea is to have "many mutexes, each one is responsible for particular range in array". You should probably consider the access patterns to decide how to assign entries to mutexes. If threads will tend to work on close-by entries, you might consider assigning entries to mutexes using a different scheme, e.g., the entry index modulo the number of mutexes.

2. From experience, note that the number of mutexes should be determined by the number of threads, not the range's size. I wrote on this more in this question (it is the accepted answer, at the time of writing this).

3. Again depending on the usage pattern, you should consider using read/write locks to avoid needless serialization for multiple readers on the same entry. YMMV.