title: Reduce mutex overhead in multi-threading voxel algorithms
body: <p>I'm currently implementing a multi-threaded voxel game engine. As I'm going with multithreading I quickly run into performance bottleneck with mutexes.</p>
  
  <p>For clarifying my problem let's take a 2D case:</p>
  
  <pre><code>+-+-+-+
  |A|B|C|
  +-+-+-+
  |D|E|F|
  +-+-+-+
  |G|H|I|
  +-+-+-+
  </code></pre>
  
  <p>All these cells are voxel chunks (16x16 voxels).</p>
  
  <p>I do all voxel algorithms in a chunk basis using multiple threads. I have a job queue consisting of chunks to be worked on, and each worker thread just continuously picks chunks from the queue and works on it.</p>
  
  <p>Now imagine one thread needs to do some lighting calculations in chunk E. Because there may be a light source in a corner of E which will propagate to neighbouring chunks, it has to lock all nine neighbouring chunks around to avoid potential data race, using mutexes.</p>
  
  <p>However as I've experimented, the performance overhead with mutexes is not good. Currently I'm using a simple <code>for</code> loop to add the jobs. So when the game is run the initial job queue would become something like:</p>
  
  <pre><code>A, B, C, D, E, F, G, H, I, ...
  </code></pre>
  
  <p>This is really bad, as the first job A will locks A, B, D, E and makes all following eight jobs waiting for the mutexes, killing performance.</p>
  
  <p>Currently the only mitigation I can think of is to try to add jobs in a disperse way, hoping we can avoid most stalls. But I do not like this approach as it looks more like a workaround and not very flexible if the locking pattern changes.</p>
  
  <p>I have also thought of using "asynchronous mutexes". But I'm not very sure how to do it.</p>
  
  <p>EDIT:
  Just to clarify, the lighting jobs are added in runtime and not in a fixed order. For example, imagine the player moves out of currently processed chunks, then only the outside chunks should be added to the queue, which may be in an irregular boundary.</p>
  
  <p>So I think using a decent scheduler solely is not sufficient to solve this issue.</p>