title: Searching for the key using SIMD
body: <p>I have the following struct, which stores keys and generic user-specified values:</p>
  <pre class="lang-c prettyprint-override"><code>typedef struct {
          uint32_t  len;
          uint32_t  cap;
          int32_t  *keys;
          void     *vals;
  } dict;
  </code></pre>
  <p>now I want to create a function which iterates over the <code>keys</code> and returns corresponding <code>value</code>.</p>
  <p>The non-SIMD version:</p>
  <pre class="lang-c prettyprint-override"><code>void*
  dict_find(dict *d, int32_t k, size_t s) {
          size_t i;
          i = 0;
  
          while (i &lt; d-&gt;len) {
                  if (d-&gt;keys[i] == k) {
                          void *p;
                          p = (uint8_t*)d-&gt;vals + i * s;
  
                          return p;
                  }
  
                  ++i;
          }
  
          return NULL;
  }
  </code></pre>
  <p>I tried to vectorize the snippet above and came up with this:</p>
  <pre class="lang-c prettyprint-override"><code>void*
  dict_find_simd(dict *d, int32_t k, size_t s) {
          __m256i ymm0;
          ymm0 = _mm256_broadcastd_epi32(*(__m128i*)&amp;k);
  
          __m256i  ymm1;
          uint32_t i;
          int      m;
          uint8_t  b;
  
          i = 0;
          while (i &lt; d-&gt;len) { // [d-&gt;len] is aligned in 32 byte box.
                  ymm1 = _mm256_load_si256((__m256i*)(d-&gt;keys + i));
                  ymm1 = _mm256_cmpeq_epi32(ymm1, ymm0);
  
                  m = _mm256_movemask_epi8(ymm1);
                  b = __builtin_ctz(m) &gt;&gt; 2;
  
                  i += (8 +  b * d-&gt;len); // Artificially break the loop. 
                                          // Remember [i] stores the modified value.
          }
  
          if (i &lt;= d-&gt;len)
                  return NULL;
  
          i -= (8 + b * d-&gt;len); // Restore the modified value.
          i += b;
  
          void *p;
          p = (uint8_t*)d-&gt;vals + i * s;
  
          return p;
  }
  </code></pre>
  <p>The function seems to be working correctly (didn't test it much)?</p>
  <p>BUT, there are 2 problems:</p>
  <ul>
  <li>NOTE: I'm checking if the <code>i &gt; d-&gt;len</code> then I return the pointer. The <code>i</code> can be overflowed and it will return <code>NULL</code> there. How can I solve this issue?</li>
  <li>You might noticed that I'm using a combination of <code>_mm256_movemask_epi8</code> and <code>__builtin_ctz</code> in order to get the index of found key. Is there a better way (maybe a single instruction that does get the position of non zero value) to do this (without AVX512)?</li>
  </ul>