Speed up random memory access using prefetch
<p>I am trying to speed up a single program by using prefetches. The purpose of my program is just for test. Here is what it does:</p>

<blockquote>
  <ol>
  <li>It uses two int buffers of the same size</li>
  <li>It reads one-by-one all the values of the first buffer</li>
  <li>It reads the value at the index in the second buffer</li>
  <li>It sums all the values taken from the second buffer</li>
  <li>It does all the previous steps for bigger and bigger</li>
  <li>At the end, I print the number of voluntary and involuntary CPU </li>
  </ol>
</blockquote>

<p>In the very first time, values in the first buffers contains the values of its index (cf. function <code>createIndexBuffer</code> in the code just below) . </p>

<p>It will be more clear in the code of my program:</p>

<pre><code>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;limits.h&gt;
#include &lt;sys/time.h&gt;

#define BUFFER_SIZE ((unsigned long) 4096 * 100000)


unsigned int randomUint()
{
  int value = rand() % UINT_MAX;
  return value;
}


unsigned int * createValueBuffer()
{
  unsigned int * valueBuffer = (unsigned int *) malloc(BUFFER_SIZE * sizeof(unsigned int));
  for (unsigned long i = 0 ; i &lt; BUFFER_SIZE ; i++)
  {
    valueBuffer[i] = randomUint();
  }

  return (valueBuffer);
}


unsigned int * createIndexBuffer()
{
  unsigned int * indexBuffer = (unsigned int *) malloc(BUFFER_SIZE * sizeof(unsigned int));
  for (unsigned long i = 0 ; i &lt; BUFFER_SIZE ; i++)
  {
    indexBuffer[i] = i;
  }

  return (indexBuffer);
}


unsigned long long computeSum(unsigned int * indexBuffer, unsigned int * valueBuffer)
{
  unsigned long long sum = 0;

  for (unsigned int i = 0 ; i &lt; BUFFER_SIZE ; i++)
  {
    unsigned int index = indexBuffer[i];
    sum += valueBuffer[index];
  }

  return (sum);
}


unsigned int computeTimeInMicroSeconds()
{
  unsigned int * valueBuffer = createValueBuffer();
  unsigned int * indexBuffer = createIndexBuffer();

  struct timeval startTime, endTime;
  gettimeofday(&amp;startTime, NULL);

  unsigned long long sum = computeSum(indexBuffer, valueBuffer);

  gettimeofday(&amp;endTime, NULL);

  printf("Sum = %llu\n", sum);
  free(indexBuffer);
  free(valueBuffer);

  return ((endTime.tv_sec - startTime.tv_sec) * 1000 * 1000) + (endTime.tv_usec - startTime.tv_usec);

}


int main()
{
  printf("sizeof buffers = %ldMb\n", BUFFER_SIZE * sizeof(unsigned int) / (1024 * 1024));
  unsigned int timeInMicroSeconds = computeTimeInMicroSeconds();
  printf("Time: %u micro-seconds = %.3f seconds\n", timeInMicroSeconds, (double) timeInMicroSeconds / (1000 * 1000));
}
</code></pre>

<p>If I launch it, I get the following output:</p>

<pre><code>$ gcc TestPrefetch.c -O3 -o TestPrefetch &amp;&amp; ./TestPrefetch 
sizeof buffers = 1562Mb
Sum = 439813150288855829
Time: 201172 micro-seconds = 0.201 seconds
</code></pre>

<p>Quick and fast!!!
According to my knowledge (I may be wrong),  one of the reason for having such a fast program is that, as I access my two buffers sequentially, data can be prefetched in the CPU cache.</p>

<p>We can make it more complex in order that data is (almost) prefeched in CPU cache. For example, we can just change the <code>createIndexBuffer</code> function in:</p>

<pre><code>unsigned int * createIndexBuffer()
{
  unsigned int * indexBuffer = (unsigned int *) malloc(BUFFER_SIZE * sizeof(unsigned int));
  for (unsigned long i = 0 ; i &lt; BUFFER_SIZE ; i++)
  {
    indexBuffer[i] = rand() % BUFFER_SIZE;
  }

  return (indexBuffer);
}
</code></pre>

<p>Let's try the program once again:</p>

<pre><code>$ gcc TestPrefetch.c -O3 -o TestPrefetch &amp;&amp; ./TestPrefetch 
sizeof buffers = 1562Mb
Sum = 439835307963131237
Time: 3730387 micro-seconds = 3.730 seconds
</code></pre>

<p>More than 18 times slower!!!</p>

<p><strong>We now arrive to my problem</strong>. Given the new <code>createIndexBuffer</code> function, I would like to speed up <code>computeSum</code> function using prefetch</p>

<pre><code>unsigned long long computeSum(unsigned int * indexBuffer, unsigned int * valueBuffer)
{
  unsigned long long sum = 0;

  for (unsigned int i = 0 ; i &lt; BUFFER_SIZE ; i++)
  {
    __builtin_prefetch((char *) &amp;indexBuffer[i + 1], 0, 0);
    unsigned int index = indexBuffer[i];
    sum += valueBuffer[index];
  }

  return (sum);
}
</code></pre>

<p><em>of course I also have to change my <code>createIndexBuffer</code> in order it allocates a buffer having one more element</em></p>

<p>I relaunch my program: <strong>not better</strong>! As prefetch may be slower than one "for" loop iteration, I may prefetch not one element before but two elements before</p>

<pre><code>    __builtin_prefetch((char *) &amp;indexBuffer[i + 2], 0, 0);
</code></pre>

<p><strong>not better</strong>! two loops iterations? <strong>not better</strong>? Three? **I tried it until 50 (!!!) but I cannot enhance the performance of my function <code>computeSum</code>.</p>

<p>Can I would like help to understand why
Thank you very much for your help</p>