title: Thread-safety of read-only memory access
body: <p>I've implemented the Barnes-Hut gravity algorithm in C as follows:</p>
  
  <ol>
  <li>Build a tree of clustered stars.</li>
  <li>For each star, traverse the tree and apply the gravitational forces from each applicable node.</li>
  <li>Update the star velocities and positions.</li>
  </ol>
  
  <p>Stage 2 is the most expensive stage, and so is implemented in parallel by dividing the set of stars.  E.g. with 1000 stars and 2 threads, I have one thread processing the first 500 stars and the second thread processing the second 500.</p>
  
  <p>In practice this works: it speeds the computation by about 30% with two threads on a two-core machine, compared to the non-threaded version.  Additionally, it yields the same numerical results as the original non-threaded version.</p>
  
  <p>My concern is that the two threads are accessing the same resource (namely, the tree) simultaneously.  I have not added any synchronisation to the thread workers, so it's likely they will attempt to read from the same location at some point.  Although access to the tree is strictly read-only I am not 100% sure it's safe.  It has worked when I've tested it but I know this is no guarantee of correctness!</p>
  
  <p><em>Questions</em></p>
  
  <ul>
  <li>Do I need to make a private copy of the tree for each thread?</li>
  <li>Even if it is safe, are there performance problems of accessing the same memory from multiple threads?</li>
  </ul>
  
  <p><strong>Update</strong> Benchmark results for the curious:</p>
  
  <p>Machine: Intel Atom CPU N270 @ 1.60GHz, cpu MHz 800, cache size 512 KB</p>
  
  <pre><code>Threads      real      user      sys
        0    69.056    67.324    1.720
        1    76.821    66.268    5.296
        2    50.272    63.608   10.585
        3    55.510    55.907   13.169
        4    49.789    43.291   29.838
        5    54.245    41.423   31.094
  </code></pre>
  
  <p>0 means no threading at all; 1 and above means spawn that many worker threads and for the main thread to wait for them.  I would not expect much of an improvement for anything beyond 2 threads, since it's entirely CPU bound and that's how many cores there are.  It's interesting that an odd number of threads is slightly worse than an even number.</p>
  
  <p>Looking at <code>sys</code> it's apparent that there's a cost with making threads.  Currently it's making the threads for each frame (so N*1000 thread creations).  This was easy to program (during my 15 minutes on the train this morning).  I'll need to think a bit about how to reuse threads...</p>
  
  <p><strong>Update #2</strong> I've made it use a pool of threads, synchronised with two barriers.  This has no noticeable performance advantage over recreating the threads each frame.</p>