title: 20x performance difference Interlocked.Read vs Interlocked.CompareExchange though both implemented with lock cmpxchg
body: <h2>Question</h2>
  <p>I wanted to write a small profiler class that allows me to measure the run time of hot paths throughout the application. In doing so, I discovered and interesting performance difference between two possible implementations that I cannot explain, but would like to understand.</p>
  <h2>Setup</h2>
  <p>The idea is as follows:</p>
  <pre><code>// somewhere accessible
  public static profiler HotPathProfiler = new HotPathProfiler(&quot;some name&quot;, enabled: true);
  
  // within programm
  long ticket = profiler.Enter();
  ... // hot path
  var result = profiler.Exit(ticket: ticket);
  </code></pre>
  <p>As there aren't much of these hot paths running in parallel, the idea is to implement this via an array that holds the timestamp (0 when slot is free) and returning the index (called ticket) when calling <code>Enter()</code>. So the class looks like the following:</p>
  <pre><code>public class HotPathProfiler
  {
      private readonly string _name;
      private readonly bool _enabled;
      private readonly long[] _ticketList;
  
      public HotPathProfiler(string name, bool enabled)
      {
          _name = name;
          _enabled = enabled;
          _ticketList = new long[128];
      }
  }
  </code></pre>
  <p>If code <code>Enter()</code>s and none of the 128 tickets is available, <code>-1</code> will be returned which the <code>Exit(ticket)</code> function can handle by returning early.</p>
  <p>When thinking about how to implement the <code>Enter()</code> call I saw the <a href="https://docs.microsoft.com/en-us/dotnet/api/system.threading.interlocked.read?view=net-5.0" rel="nofollow noreferrer">Interlocked.Read</a> method that can atomically read values on 32bit systems, while, according to the documentation, it is unnecessary on 64bit systems.</p>
  <p>So I went on an implemented various types of <code>Enter()</code> methods, including one with <code>Interlocked.Read</code> and one with <code>Interlocked.CompareExchange</code>, and compared them with <a href="https://benchmarkdotnet.org/articles/overview.html" rel="nofollow noreferrer">BenchmarkDotNet</a>. That's where I discovered an enormous performance difference:</p>
  <pre><code>|       Method |      Mean |    Error |   StdDev | Code Size |
  |------------- |----------:|---------:|---------:|----------:|
  |    SafeArray |  28.64 ns | 0.573 ns | 0.536 ns |     295 B |
  | SafeArrayCAS | 744.75 ns | 8.741 ns | 7.749 ns |     248 B |
  </code></pre>
  <p>The benchmark for both look pretty much the same:</p>
  <pre><code>        [Benchmark]
          public void SafeArray()
          {
              // doesn't matter if 'i &lt; 1' or 'i &lt; 10'
              // performance differs by the same factor (approx. 20x)
              for (int i = 0; i &lt; 1; i++)
              {
                  _ticketArr[i] = _hpp_sa.EnterSafe(); 
  
                  // SafeArrayCAS:
                  // _ticketArr[i] = _hpp_sa_cas.EnterSafe(); 
              }
          }
  </code></pre>
  <h2>Implementations</h2>
  <p>Again, free slots hold value <code>0</code>, occupied slots some other value (timestamp). <code>Enter()</code> is supposed to return the index/ticket of the slot.</p>
  <h3>SafeArrayCAS (slow)</h3>
  <pre><code>        public long EnterSafe()
          {
              if (!_enabled)
              {
                  return -1;
              }
              long last = 0;
              long ts = Stopwatch.GetTimestamp();
              long val;
              do
              {
                  val = Interlocked.CompareExchange(ref _ticketList[last], ts, 0);
                  last++;
              } while (val != 0 &amp;&amp; last &lt; 128);
              return val == 0 ? last : -1;
          }
  </code></pre>
  <h3>SafeArray (fast)</h3>
  <pre><code>        public long EnterSafe()
          {
              if (!_enabled)
              {
                  return -1;
              }
              long last = 0;
              long val;
              do
              {
                  val = Interlocked.Read(ref _ticketList[last]);
                  last++;
              } while (val != 0 &amp;&amp; last &lt; 128);
              if (val != 0)
              {
                  return -1;
              }
              long prev = Interlocked.CompareExchange(ref _ticketList[last], Stopwatch.GetTimestamp(), 0);
              if (prev != 0)
              {
                  return -1;
              }
              return last;
          }
  </code></pre>
  <h2>Enter rabbit hole</h2>
  <p>Now, one would say that it's no surprise to see a difference, since the slow method always tries to CAS an entry, while the other one only lazily reads each entry and then only tries a CAS once.</p>
  <p>But, beside the fact that the benchmark only does 1 <code>Enter()</code>, i.e. only one <code>while{}</code> run that shouldn't make that (20x) much difference, it is even harder to explain once you realize the atomic read is implemented as CAS:</p>
  <h3>SafeArrayCAS (slow)</h3>
  <pre><code>        public long EnterSafe()
          {
              if (!_enabled)
  [...] // ommited for brevity 
              {
                  return -1;
  [...] // ommited for brevity   
              }
              long last = 0;
  00007FF82D048FCE  xor         edi,edi  
              long ts = Stopwatch.GetTimestamp();
  00007FF82D048FD0  lea         rcx,[rsp+28h]  
  00007FF82D048FD5  call        CLRStub[JumpStub]@7ff82d076d70 (07FF82D076D70h)   
  00007FF82D048FDA  mov         rsi,qword ptr [rsp+28h]  
  00007FF82D048FDF  mov         rax,7FF88CF3E07Ch  
  00007FF82D048FE9  cmp         dword ptr [rax],0  
  00007FF82D048FEC  jne         HotPathProfilerSafeArrayCAS.EnterSafe()+0A6h (07FF82D049046h)  
              long val;
              do
              {
                  val = Interlocked.CompareExchange(ref _ticketList[last], ts, 0);
  00007FF82D048FEE  mov         rbx,qword ptr [rsp+50h]  
  00007FF82D048FF3  mov         rax,qword ptr [rbx+10h]  
  00007FF82D048FF7  mov         edx,dword ptr [rax+8]  
  00007FF82D048FFA  movsxd      rdx,edx  
  00007FF82D048FFD  cmp         rdi,rdx  
  00007FF82D049000  jae         HotPathProfilerSafeArrayCAS.EnterSafe()+0ADh (07FF82D04904Dh)  
  00007FF82D049002  lea         rdx,[rax+rdi*8+10h]  
  00007FF82D049007  xor         eax,eax  
  00007FF82D049009  lock cmpxchg qword ptr [rdx],rsi  
                  last++;
  00007FF82D04900E  inc         rdi  
              } while (val != 0 &amp;&amp; last &lt; 128);
  00007FF82D049011  test        rax,rax  
  00007FF82D049014  je          HotPathProfilerSafeArrayCAS.EnterSafe()+084h (07FF82D049024h)  
  00007FF82D049016  cmp         rdi,80h  
  00007FF82D04901D  mov         qword ptr [rsp+50h],rbx  
  00007FF82D049022  jl          HotPathProfilerSafeArrayCAS.EnterSafe()+04Eh (07FF82D048FEEh)  
       
  </code></pre>
  <h3>SafeArray (fast)</h3>
  <pre><code>        public long EnterSafe()
          {
              if (!_enabled)
  [...] // ommited for brevity 
              {
                  return -1;
  [...] // ommited for brevity
              }
              long last = 0;
  00007FF82D046C74  xor         esi,esi  
              long val;
              do
              {
                  val = Interlocked.Read(ref _ticketList[last]);
  00007FF82D046C76  mov         rax,qword ptr [rcx+10h]  
  00007FF82D046C7A  mov         edx,dword ptr [rax+8]  
  00007FF82D046C7D  movsxd      rdx,edx  
  00007FF82D046C80  cmp         rsi,rdx  
  00007FF82D046C83  jae         HotPathProfilerSafeArray.EnterSafe()+0DCh (07FF82D046D2Ch)  
  00007FF82D046C89  lea         rdx,[rax+rsi*8+10h]  
  00007FF82D046C8E  xor         r8d,r8d  
  00007FF82D046C91  xor         eax,eax  
  00007FF82D046C93  lock cmpxchg qword ptr [rdx],r8  
                  last++;
  00007FF82D046C98  inc         rsi  
              } while (val != 0 &amp;&amp; last &lt; 128);
  00007FF82D046C9B  test        rax,rax  
  00007FF82D046C9E  je          HotPathProfilerSafeArray.EnterSafe()+059h (07FF82D046CA9h)  
  00007FF82D046CA0  cmp         rsi,80h  
  00007FF82D046CA7  jl          HotPathProfilerSafeArray.EnterSafe()+026h (07FF82D046C76h)  
              if (val != 0)
  [...] // ommited for brevity   
              {
                  return -1;
  [...] // ommited for brevity  
              }
              long prev = Interlocked.CompareExchange(ref _ticketList[last], Stopwatch.GetTimestamp(), 0);
  00007FF82FBA6ADF  mov         rcx,qword ptr [rcx+10h]  
  00007FF82FBA6AE3  mov         eax,dword ptr [rcx+8]  
  00007FF82FBA6AE6  movsxd      rax,eax  
  00007FF82FBA6AE9  cmp         rsi,rax  
  00007FF82FBA6AEC  jae         HotPathProfilerSafeArray.EnterSafe()+0DCh (07FF82FBA6B4Ch)  
  00007FF82FBA6AEE  lea         rdi,[rcx+rsi*8+10h]  
  00007FF82FBA6AF3  mov         qword ptr [rsp+28h],rdi  
  00007FF82FBA6AF8  lea         rcx,[rsp+30h]  
  00007FF82FBA6AFD  call        CLRStub[JumpStub]@7ff82d076d70 (07FF82D076D70h)  
  00007FF82FBA6B02  mov         rdx,qword ptr [rsp+30h]  
  00007FF82FBA6B07  xor         eax,eax  
  00007FF82FBA6B09  mov         rdi,qword ptr [rsp+28h]  
  00007FF82FBA6B0E  lock cmpxchg qword ptr [rdi],rdx  
  00007FF82FBA6B13  mov         rdi,rax  
  00007FF82FBA6B16  mov         rax,7FF88CF3E07Ch  
  00007FF82FBA6B20  cmp         dword ptr [rax],0  
  00007FF82FBA6B23  jne         HotPathProfilerSafeArray.EnterSafe()+0D5h (07FF82FBA6B45h)  
              if (prev != 0)
  [...] // ommited for brevity 
  </code></pre>
  <h1>Summary</h1>
  <p>I run all on Win10 x64 Release build, on a <a href="https://ark.intel.com/content/www/us/en/ark/products/134860/intel-xeon-e-2176g-processor-12m-cache-up-to-4-70-ghz.html" rel="nofollow noreferrer">Xeon E-2176G</a> (6-core Coffee Lake) CPU. Assembler output is from Visual Studio, but equals the <a href="https://benchmarkdotnet.org/articles/features/disassembler.html" rel="nofollow noreferrer">DisassemblyDiagnoser</a> of BenchmarkDotNet.</p>
  <p>Beside the hows and whys on why I'm doing this at all, I simply cannot explain the performance difference between these two methods. It shouldn't be this much I would guess. Can it be BenchmarkDotNet itself? Am I'm missing something else?</p>
  <p>Feels like I have a black spot in my understanding about this lowlevel stuff that I'd like to shine some light on...thanks!</p>
  <p>PS:</p>
  <p>What I've tried so far:</p>
  <ul>
  <li>Rearraging order of Benchmark runs</li>
  <li>Defer <code>GetTimestamp()</code> call in the slow method</li>
  <li>Doing some initialization/test calls before the benchmark run (though I guess that's covered anyways by BenchmarkDotNet)</li>
  </ul>