title: Java performance: Search and removal speed on removeAll()
body: <p>I had some fun comparing the speed of the <code>removeAll(Collection&lt;?&gt; c)</code> call declared in <code>Collection</code>. Now I know that micro-benchmarks are difficult to do right, and I won’t look at a few milliseconds difference, but I believe my results to be valid, since I ran them repeatedly and they are very reproducible.</p>
  
  <p>Let’s assume I have two collections that are not too tiny, say 100,000 consecutive integer elements, and also that they mostly overlap, for instance 5,000 are in the left but not the right. Now I simply call:</p>
  
  <pre><code>left.removeAll(right);
  </code></pre>
  
  <p>Of course this all depends on the types of both the left and the right collection. It’s blazingly fast if the right collection is a hash map, because that’s where the look-ups are done. But looking closer, I noticed two results that I cannot explain. I tried all the tests both with an <code>ArrayList</code> that is sorted and with another that is shuffled (using <code>Collections.shuffle()</code>, if that is of importance).</p>
  
  <hr>
  
  <p>The first weird result is:</p>
  
  <pre><code>00293  025%   shuffled ArrayList, HashSet
  00090  008%     sorted ArrayList, HashSet
  </code></pre>
  
  <p>Now either removing elements from the sorted <code>ArrayList</code> is faster than removing from the shuffled list, or looking up consecutive values from the <code>HashSet</code> is faster that looking up random values.</p>
  
  <hr>
  
  <p>Now the other one:</p>
  
  <pre><code>02311  011%     sorted ArrayList, shuffled ArrayList
  01401  006%     sorted ArrayList,   sorted ArrayList
  </code></pre>
  
  <p>Now this suggests that the lookup in the sorted <code>ArrayList</code> (using a <code>contains()</code> call for each element of the list to the left) is faster than in the shuffled list. Now that would be quite easy if we could make use of the fact that it is sorted and use a binary search, but I do not do that.</p>
  
  <hr>
  
  <p>Both results are mysterious to me. I cannot explain them by looking at the code or with my data-structure knowledge. Does it have anything to do with processor cache access patterns? Is the JIT compiler optimizing stuff? But if so, which? I performed warming up and run the tests a few times in a row, but perhaps there is a fundamental problem with my benchmark?</p>