title: Parallelization: What causes Java threads to block other than synchronization & I/O?
body: <p>Short version is in the title.</p>
  
  <p>Long version:
  I am working on a program for scientific optimization using Java.  The workload of the program can be divided into parallel and serial phases -- parallel phases meaning that highly parallelizable work is being performed.  To speed up the program (it runs for hours/days) I create a number of threads equal to the number of CPU cores on the machine I'm using -- typically 4 or 8 -- and divide the work between them.  I then start these threads and join() them before proceeding to a serial phase.</p>
  
  <p>So far so good.  What's bothering me is that the CPU utilization and speedup of the parallel phases is nowhere near the "theoretical maximum" -- e.g. if I have 4 cores, I expect to see somewhere between 350-400% "utilization" (as reported by top) but instead it bounces around between 180 and about 310. Using only a single thread, I get 100% CPU utilization.</p>
  
  <p>The only reasons I know of for threads not to run at full speed are:
      -blocking due to I/O
      -blocking due to synchronization</p>
  
  <p>No I/O whatsoever is going on in my parallel threads, nor any synchronization -- the only data structures shared by the threads are read-only, and are either basic types or (non-concurrent) collections.  So I'm looking for other explanations.  One possibility would be that several threads are repeatedly blocking for garbage collection, but that would only seem to make sense in a situation with memory pressure, and I am allocating well above the required maximum heap space.  </p>
  
  <p>Any suggestions would be appreciated.</p>
  
  <p><b>Update:</b> Just in case anyone is curious, after some more investigation I tweaked the code for general performance and am seeing better utilization, even though nothing I changed has to do with synchronization.  However, some of the changes should have resulted in fewer new heap allocations in particular I got rid of some use of <b>iterators</b> and <b>termporary boxed numbers</b> (The CERN "Colt" library for high-performance Java computing was useful here: it provides collections like IntArrayList, DoubleArrayList etc for basic types.).  So I think garbage collection was probably the culprit.  </p>