Prefetch Benchmark Comparison

#include <immintrin.h>
#include <chrono>
#include <iostream>
#include <vector>
#include <random>
#include <algorithm> // for std::shuffle
#include <numeric>   // for std::iota

const size_t DATA_SIZE = 100 * 1024 * 1024; // 100 MB
const size_t ITERATIONS = 10;

// Function to generate random access pattern
std::vector<size_t> generate_access_pattern(size_t size)
{
    std::vector<size_t> pattern(size);
    std::iota(pattern.begin(), pattern.end(), 0);
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(pattern.begin(), pattern.end(), g);
    return pattern;
}

// Function to access data without prefetching
void access_data_no_prefetch(const std::vector<int> &data, const std::vector<size_t> &access_pattern)
{
    volatile int sum = 0; // Prevent optimization
    for (size_t i : access_pattern)
    {
        sum += data[i];
    }
}

// Function to access data with prefetching
void access_data_with_prefetch(const std::vector<int> &data, const std::vector<size_t> &access_pattern)
{
    volatile int sum = 0; // Prevent optimization
    for (size_t i = 0; i < access_pattern.size(); ++i)
    {
        if (i + 16 < access_pattern.size())
        {
            _mm_prefetch(reinterpret_cast<const char *>(&data[access_pattern[i + 16]]), _MM_HINT_T1);
        }
        sum += data[access_pattern[i]];
    }
}

// Function to measure execution time
template <typename Func>
double measure_time(Func func)
{
    auto start = std::chrono::high_resolution_clock::now();
    func();
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration<double, std::milli>(end - start).count();
}

int main()
{
    // Initialize data
    std::vector<int> data(DATA_SIZE / sizeof(int));
    std::iota(data.begin(), data.end(), 0);

    // Generate random access pattern
    auto access_pattern = generate_access_pattern(data.size());

    double total_time_no_prefetch = 0;
    double total_time_with_prefetch = 0;

    for (size_t i = 0; i < ITERATIONS; ++i)
    {
        total_time_no_prefetch += measure_time([&]()
                                               { access_data_no_prefetch(data, access_pattern); });
        total_time_with_prefetch += measure_time([&]()
                                                 { access_data_with_prefetch(data, access_pattern); });
    }

    double avg_time_no_prefetch = total_time_no_prefetch / ITERATIONS;
    double avg_time_with_prefetch = total_time_with_prefetch / ITERATIONS;

    std::cout << "Average time without prefetching: " << avg_time_no_prefetch << " ms\n";
    std::cout << "Average time with prefetching: " << avg_time_with_prefetch << " ms\n";
    std::cout << "Speedup: " << (avg_time_no_prefetch / avg_time_with_prefetch) << "x\n";

    return 0;
}