Prefetch test...

prefetch.cpp

#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <sys/time.h>

typedef int Type;

struct Measurement
{
    double Value;
    double Error;
};

double average(const unsigned long* seq, const unsigned long n)
{
    unsigned long Total = 0;
    for(unsigned long i = 0; i < n; i++)
    {
        Total += seq[i];
    }
    return double(Total) / double(n);
}

double stdDev(const unsigned long* seq, const unsigned long n,
              const double avg)
{
    unsigned long Total = 0;
    for(unsigned long i = 0; i < n; i++)
    {
        Total += seq[i] * seq[i];
    }
    double AvgOfSquare = double(Total) / double(n);
    return sqrt(AvgOfSquare - avg * avg);
}

unsigned long randInt(const unsigned long min, const unsigned long max)
{
    return min + (random() % (int)(max - min + 1));
}

Measurement test(const unsigned long n_data, const unsigned long n_run,
                 const unsigned long* indices)
{
    Type* Data = new Type[n_data];
    unsigned long Times[n_run];
    timeval Begin, End;
    for(unsigned int Run = 0; Run < n_run; Run++)
    {
        Type a;
        gettimeofday(&Begin, 0);
        for(unsigned long i = 0; i < n_data; i++)
            a += Data[indices[i]];
        gettimeofday(&End, 0);
        Times[Run] = (End.tv_sec - Begin.tv_sec) * 1000000 +
            (End.tv_usec - Begin.tv_usec);
        // Explicit side effect so that the loop will not be optimized
        // out by the compiler.
        std::cerr << a;
    }
    delete[] Data;

    double Avg = average(Times, n_run);
    double Err = stdDev(Times, n_run, Avg);

    Measurement Result;
    Result.Value = Avg / 1000.0;
    Result.Error = Err / 1000.0;
    return Result;
}

int main()
{
    srandom(time(0));
    const unsigned long NElements = 100000000;
    const unsigned int NRuns = 100;

    const unsigned int SizeInMB = NElements * sizeof(Type) / 1024 / 1024;
    std::cout << "Size of structure: " << SizeInMB << "MB" << std::endl;

    unsigned long* Indices = new unsigned long[NElements];

    // Reference in order
    for(unsigned long i = 0; i < NElements; i++)
        Indices[i] = i;
    Measurement Result = test(NElements, NRuns, Indices);
    std::cout << "Time of reference in order: " << Result.Value
              << " ± " << Result.Error << "ms ("
              << NRuns << " samples)" << std::endl;

    // Reference at random
    for(unsigned long i = 0; i < NElements; i++)
        Indices[i] = randInt(0, NElements - 1);
    Result = test(NElements, NRuns, Indices);
    std::cout << "Time of reference at random: " << Result.Value
              << " ± " << Result.Error << "ms ("
              << NRuns << " samples)" << std::endl;

    delete[] Indices;
    return 0;
}

Clang++ No optimization:

Size of structure: 381MB
Time of reference in order: 316.566 ± 20.6304ms (100 samples)
Time of reference at random: 2141.42 ± 92.7087ms (100 samples)

Clang++ O1:

Size of structure: 381MB
Time of reference in order: 36.4864 ± 0.494226ms (100 samples)
Time of reference at random: 36.3851 ± 0.536255ms (100 samples)

Clang++ O2:

Size of structure: 381MB
Time of reference in order: 36.5628 ± 0.509474ms (100 samples)
Time of reference at random: 36.3367 ± 0.355297ms (100 samples)