title: Fastest way to compare one byte array with many others?
body: <p>I have a loop with the following structure :</p>
  
  <ul>
  <li>Calculate a byte array with length k (somewhere slow)</li>
  <li>Find if the calculated byte array matches any in a list of N byte arrays I have.</li>
  <li>Repeat</li>
  </ul>
  
  <p>My loop is to be called many many times (it's the main loop of my program), and I want the second step to be as fast as possible.</p>
  
  <p>The naive implementation for the second step would be using <code>memcmp</code>:</p>
  
  <pre><code>char* calc;
  char** list;
  int k, n, i;
  for(i = 0; i &lt; n; i++) {
    if (!memcmp(calc, list[i], k)) {
      printf("Matches array %d", i);
    }
  }
  </code></pre>
  
  <p>Can you think of any faster way ? A few things :</p>
  
  <ul>
  <li>My list is fixed at the start of my program, any precomputation on it is fine.</li>
  <li>Let's assume that k is small (&lt;= 64), N is moderate (around 100-1000).</li>
  <li>Performance is the goal here, and portability is a non issue. Intrinsics/inline assembly is fine, as long as it's faster.</li>
  </ul>
  
  <p>Here are a few thoughts that I had :</p>
  
  <ul>
  <li>Given k&lt;64 and I'm on x86_64, I could sort my lookup array as a long array, and do a binary search on it. O(log(n)). Even if k was big, I could sort my lookup array and do this binary search using <code>memcmp</code>.</li>
  <li>Given k is small, again, I could compute a 8/16/32 bits checksum (the simplest being folding my arrays over themselves using a <code>xor</code>) of all my lookup arrays and use a built-in <code>PCMPGT</code> as in <a href="https://stackoverflow.com/questions/12558729/how-to-compare-more-than-two-numbers-in-parallel">How to compare more than two numbers in parallel?</a>. I know SSE4.2 is available here.</li>
  </ul>
  
  <p>Do you think going for vectorization/sse is a good idea here ? If yes, what do you think is the best approach.
  I'd like to say that this isn't early optimization, but performance is crucial here, I need the outer loop to be as fast as possible.
  Thanks</p>
  
  <p><strong>EDIT1:</strong> It looks like <a href="http://schani.wordpress.com/tag/c-optimization-linear-binary-search-sse2-simd/" rel="nofollow noreferrer">http://schani.wordpress.com/tag/c-optimization-linear-binary-search-sse2-simd/</a> provides some interesting thoughts about it. Binary search on a list of <code>long</code> seems the way to go..</p>