title: false sharing in boost::detail::spinlock_pool?
body: <p>I came across this SO <a href="https://stackoverflow.com/questions/8007186/read-write-thread-safe-smart-pointer-in-c-x86-64">question</a> and reading it over eventually led me to look at <code>boost::detail::spinlock_pool</code>.</p>
  
  <p>The purpose of <code>boost::detail::spinlock_pool</code> is to reduce potential contention for a global spinlock by choosing from an array of <code>spinlock</code>s by hashing over the <code>shared_ptr</code>'s address.  This seems like a reasonable solution but there seems to be a problem with the current (Boost v1.49) version's implementation.</p>
  
  <p><code>spinlock_pool</code> manages a statically allocated array of 41 <code>spinlock</code> instances.  It appears that <code>sizeof(spinlock)==4</code> for the platforms I looked at -- which means on, say x64 with 64-byte cachelines, there will be 16 <code>spinlock</code>s per cache line.  </p>
  
  <p><strong>I.e. the whole array spans all of 2 1/2 cache lines.</strong></p>
  
  <p><strong>I.e. there's a 40% chance of one random spinlock false sharing with another.</strong></p>
  
  <p>... which almost completely defeats the purpose of the pool in the first place.</p>
  
  <p>Is my analysis correct or am I missing something important?</p>
  
  <p><strong>UPDATE:</strong>  I did finally write a small benchmark program:</p>
  
  <pre><code>#include &lt;boost/shared_ptr.hpp&gt;
  #include &lt;boost/thread.hpp&gt;
  #include &lt;boost/timer.hpp&gt;
  #include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;stdlib.h&gt;
  
  using namespace std;
  
  enum { BufferSize = 1&lt;&lt;24,  SLsPerCacheLine = 1 };
  
  int          ibuffer[BufferSize];
  
  using boost::detail::spinlock;
  size_t nslp = 41;
  spinlock* pslp = 0;
  
  spinlock&amp; getSpinlock(size_t h)
  {
    return pslp[ (h%nslp) * SLsPerCacheLine ];
  }
  
  
  void threadFunc(int offset)
  {
    const size_t mask = BufferSize-1;
    for (size_t ii=0, index=(offset&amp;mask); ii&lt;BufferSize; ++ii, index=((index+1)&amp;mask))
    {
      spinlock&amp; sl = getSpinlock(index);
      sl.lock();
      ibuffer[index] += 1;
      sl.unlock();
    }
  };
  
  
  int _tmain(int argc, _TCHAR* argv[])
  {
    if ( argc&gt;1 )
    {
      size_t n = wcstoul(argv[1], NULL, 10);
      if ( n&gt;0 )
      {
        nslp = n;
      }
    }
  
    cout &lt;&lt; "Using pool size: "&lt;&lt; nslp &lt;&lt; endl;
    cout &lt;&lt; "sizeof(spinlock): "&lt;&lt; sizeof(spinlock) &lt;&lt; endl;
    cout &lt;&lt; "SLsPerCacheLine: "&lt;&lt; int(SLsPerCacheLine) &lt;&lt; endl;
    const size_t num = nslp * SLsPerCacheLine;
    pslp = new spinlock[num ];
    for (size_t ii=0; ii&lt;num ; ii++)
    { memset(pslp+ii,0,sizeof(*pslp)); }
  
    const size_t nThreads = 4;
    boost::thread* ppThreads[nThreads];
    const int offset[nThreads] = { 17, 101, 229, 1023 };
  
    boost::timer timer;
  
    for (size_t ii=0; ii&lt;nThreads; ii++)
    { ppThreads[ii] = new boost::thread(threadFunc, offset[ii]); }
  
    for (size_t ii=0; ii&lt;nThreads; ii++)
    { ppThreads[ii]-&gt;join(); }
  
    cout &lt;&lt; "Elapsed time: " &lt;&lt; timer.elapsed() &lt;&lt; endl;
  
    for (size_t ii=0; ii&lt;nThreads; ii++)
    { delete ppThreads[ii]; }
  
    delete[] pslp;
  
    return 0;
  }
  </code></pre>
  
  <p>I compiled two versions of the code, one with <code>SLsPerCacheLine==1</code>, and one with <code>SLsPerCacheLine==8</code>.  32bit optimized using MSVS 2010, run on a 4-core Xeon W3520 @ 2.67Ghz (HyperThreading disabled).</p>
  
  <p>I had trouble getting consistent results out of these tests -- spurious timing variations up to 50% were occasionally observed.  On average however, it appears the <code>SLsPerCacheLine==8</code> version was ~25-30% faster than the <code>SLsPerCacheLine==1</code> version with a spinlock table of size 41.</p>
  
  <p>It would be interesting to see how this scales with larger number of cores, NUMA, HyperThreading, etc.  I don't presently have access to that sort of hardware.</p>