Почему комбинированные структуры данных в c ++ имеют более низкую производительность, чем независимые массивы

Question

Вот мой тестовый код, скомпилированный в Linux с помощью команды

g ++ main.cpp -O3 -o stest

Я пробовал два способа объединения данных ( test2 test3 ).Но оба эти способа не смогли добиться лучшей производительности, как я ожидал.На мой взгляд, комбинированные данные должны иметь лучшую производительность, чем независимые массивы, потому что более высокий кэш загружает данные из более низкого кэша за блоком.Таким образом, объединенные данные имеют больше шансов быть загруженными в один доступ к памяти.Однако независимым массивам ( test1 ) требуется три обращения к памяти.Но результаты испытаний показали, что test1 имеет лучшую производительность.Это слишком странно для меня.И я не знаю почему.Если вы знаете, пожалуйста, скажите мне.Заранее спасибо.

#include <iostream>
#include <cstdlib>
#include <unistd.h>
#include <string.h>
#include <sstream>
#include <sys/times.h>
#include <cmath>
using namespace std;

tms start, tEnd;

long long test1(int n) {
    int *a = new int[n];
    int *b = new int[n];
    int *c = new int[n];


    times(&start);
    for (int i = 0; i < n; i++) {
        a[i] = b[i] = i;
    }

    for (int i = 0; i < n; i++) {
        c[i] = a[i] + b[i];
    }
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += c[i];
    }

    times(&tEnd);

    double elap_time = double(tEnd.tms_utime - start.tms_utime + tEnd.tms_stime - start.tms_stime) / sysconf(_SC_CLK_TCK);
    cout << "test1: " << elap_time << "ms  result=" << sum << " " << endl;
    delete[] a;
    delete[] b;
    delete[] c;
    return sum;
}

struct D {
    int a, b, c;
};

long long test2(int n) {
    struct D *d = new D[n];

    times(&start);
    for (int i = 0; i < n; i++) {
        struct D &di = d[i];
        di.a = di.b = i;
    }

    for (int i = 0; i < n; i++) {
        struct D &di = d[i];
        di.c = di.a + di.b;
    }
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += d[i].c;
    }

    times(&tEnd);
    double elap_time = double(tEnd.tms_utime - start.tms_utime + tEnd.tms_stime - start.tms_stime) / sysconf(_SC_CLK_TCK);
    cout << "test2: " << elap_time << "ms  result=" << sum << " " << endl;
    delete [] d;
    return sum;
}

long long test3(int n) {
    int *abc = new int[3 * n];

    times(&start);
    for (int i = 0; i < n; i++) {
        int base = 3 * i;
        abc[base] = abc[base + 1] = i;
    }

    for (int i = 0; i < n; i++) {
        int base = 3 * i;
        abc[base + 2] = abc[base] + abc[base + 1];
    }

    long long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += abc[3 * i + 2];
    }

    times(&tEnd);
    double elap_time = double(tEnd.tms_utime - start.tms_utime + tEnd.tms_stime - start.tms_stime) / sysconf(_SC_CLK_TCK);
    cout << "test3: " << elap_time << "ms  result=" << sum << " " << endl;
    delete [] abc;
    return sum;
}


int main(int argc, char *argv[]) {
    int n = 9999999;
    sscanf(argv[1], "%d", &n);
    test1(n);
    test2(n);
    test3(n);

    cout<<"after changing order"<<endl;

    test2(n);
    test3(n);
    test1(n);

    cout<<"after changing order"<<endl;
    test3(n);
    test1(n);
    test2(n);

    return 0;
}

Я тестировал stest на компьютере с четырьмя процессорами i5-4460 и 8 ГБ памяти.Вот команда, которую я использовал для тестирования программы, и я уверен, что с параметром 399999999 компьютер не выйдет из памяти:

q@q-lab:~/Desktop$ ./stest 399999999
test1: 1.61ms  result=159999998800000002 
test2: 2.38ms  result=159999998800000002 
test3: 2.37ms  result=159999998800000002 
after changing order
test2: 2.38ms  result=159999998800000002 
test3: 2.38ms  result=159999998800000002 
test1: 1.61ms  result=159999998800000002 
after changing order
test3: 2.38ms  result=159999998800000002 
test1: 1.61ms  result=159999998800000002 
test2: 2.39ms  result=159999998800000002

Answer 1

Объединение данных требует больше времени для адресации или вычисления смещения данных.Кроме того, кэш процессора непредсказуем и его трудно оптимизировать.Лучше не пытаться оптимизировать кэш процессора.