title: Performance implications of a large number of mutexes
body: <p>Suppose I have an array of 1,000,000 elements, and a number of worker threads each manipulating data in this array.  The worker threads might be updating already populated elements with new data, but each operation is limited to a single array element, and is independent of the values of any other element.</p>
  
  <p>Using a single mutex to protect the entire array would clearly result in high contention.  On the other extreme, I could create an array of mutexes that is the same length as the original array, and for each element <code>array[i]</code> I would lock <code>mutex[i]</code> while operating on it.  Assuming an even distribution of data, this would mostly eliminate lock contention, at the cost of a lot of memory.</p>
  
  <p>I think a more reasonable solution would be to have an array of <code>n</code> mutexes (where 1 &lt; n &lt; 1000000).  Then for each element <code>array[i]</code> I would lock <code>mutex[i % n]</code> while operating on it.  If <code>n</code> is sufficiently large, I can still minimize contention.</p>
  
  <p>So my question is, is there a performance penalty to using a large (e.g. >= 1000000) number of mutexes in this manner, beyond increased memory usage?  If so, how many mutexes can you reasonably use before you start to see degradation?</p>
  
  <p>I'm sure the answer to this is somewhat platform specific; I'm using pthreads on Linux.  I'm also working on setting up my own benchmarks, but the scale of data that I'm working on makes that time consuming, so some initial guidance would be appreciated.</p>
  
  <hr>
  
  <p>That was the initial question.  For those asking for more detailed information regarding the problem, I have 4 multiple GB binary data files describing somewhere in the neighborhood of half a billion events that are being analyzed.  The array in question is actually the array of pointers backing a very large chained hash table.  We read the four data files into the hash table, possibly aggregating them together if they share certain characteristics.  The existing implementation has 4 threads, each reading one file and inserting records from that file into the hash table.  The hash table has 997 locks and 997*9973 = ~10,000,000 pointers.  When inserting an element with hash <code>h</code>, I first lock <code>mutex[h % 997]</code> before inserting or modifying the element in <code>bucket[h % 9943081]</code>.  This works all right, and as far as I can tell, we haven't had too many issues with contention, but there is a performance bottleneck in that we're only using 4 cores of a 16 core machine.  (And even fewer as we go along since the files generally aren't all the same size.) Once all of the data has been read into memory, then we analyze it, which uses new threads and a new locking strategy tuned to the different workload.</p>
  
  <p>I'm attempting to improve the performance of the data load stage by switching to a thread pool.  In the new model, I still have one thread for each file which simply reads the file in ~1MB chunks and passes each chunk to a worker thread in the pool to parse and insert.  The performance gain so far has been minimal, and the profiling that I did seemed to indicate that the time spent locking and unlocking the array was the likely culprit.  The locking is built into the hash table implementation we are using, but it does allow specifying the number of locks to use independently of the size of the table.  I'm hoping to speed things up without changing the hash table implementation itself.</p>