title: Any optimization for random access on a very big array when the value in 95% of cases is either 0 or 1?
body: <p>Is there any possible optimization for random access on a very big array (I currently use <code>uint8_t</code>, and I'm asking about what's better)</p>
  
  <pre><code>uint8_t MyArray[10000000];
  </code></pre>
  
  <p>when the value at any position in the array is </p>
  
  <ul>
  <li><strong>0</strong> or <strong>1</strong> for <em>95%</em> of all cases, </li>
  <li><strong>2</strong> in <em>4%</em> of cases,  </li>
  <li>between <strong>3</strong> and <strong>255</strong> in
  the other <em>1%</em> of cases?</li>
  </ul>
  
  <p>So, is there anything better than a <code>uint8_t</code> array to use for this? It should be as quick as possible to loop over the whole array in a random order, and this is very heavy on RAM bandwidth, so when having more than a few threads doing that at the same time for different arrays, currently the whole RAM bandwidth is quickly saturated.</p>
  
  <p>I'm asking since it feels very inefficient to have such a big array (10 MB) when it's actually known that almost all values, apart from 5%, will be either 0 or 1. So when 95% of all values in the array would only actually need 1 bit instead of 8 bit, this would reduce memory usage by almost an order of magnitude. 
  It feels like there has to be a more memory efficient solution that would greatly reduce RAM bandwidth required for this, and as a result also be significantly quicker for random access.</p>