Массив объектов и массивы свойств объекта, скорость доступа

#cpp #массивы #производительность

Здравствуйте.
Ниже два примера: в первом создаётся массив объектов со свойствами, во втором создаётся
один объект, но на каждое св-во по массиву. Что-то мне подсказывает, что в обоих случаях
скорость доступа к данным должна быть одинаковой, но в реальности она отличается и
зависит от кол-ва свойств. Подскажите, пожалуйста, есть ли ошибка в медленной версии
и, если есть, как сделать правильно.
Пример 1, скорость выполнения 300 мс:
struct Item
{
    unsigned int p1;
    unsigned int p2;
    unsigned int p3;
    unsigned int p4;
    unsigned int p5;
    unsigned int p6;
    unsigned int p7;
    unsigned int p8;
    unsigned int p9;
    unsigned int p10;
};

void main()
{
    cout << "Start" << endl;

    clock_t time;

    unsigned int itemsAmount = 100000000;

    Item *items = new Item[itemsAmount];

    for (unsigned int i = 0; i < itemsAmount; i++)
    {
        items[i].p1 = 1;
    }

    time = clock();

    unsigned int count = 0;
    for (unsigned int i = 0; i < itemsAmount; i++)
    {
        count += items[i].p1;
    }

    cout << (clock() - time) << endl;
    cout << count << endl;

    system("pause");
}

Пример 2, скорость выполнения 30 мс:
struct Item
{
    unsigned int *p1;
    unsigned int *p2;
    unsigned int *p3;
    unsigned int *p4;
    unsigned int *p5;
    unsigned int *p6;
    unsigned int *p7;
    unsigned int *p8;
    unsigned int *p9;
    unsigned int *p10;
};

void main()
{
    cout << "Start" << endl;

    clock_t time;

    unsigned int itemsAmount = 100000000;

    Item *items = new Item;
    items->p1 = new unsigned int[itemsAmount];
    items->p2 = new unsigned int[itemsAmount];
    items->p3 = new unsigned int[itemsAmount];
    items->p4 = new unsigned int[itemsAmount];
    items->p5 = new unsigned int[itemsAmount];
    items->p6 = new unsigned int[itemsAmount];
    items->p7 = new unsigned int[itemsAmount];
    items->p8 = new unsigned int[itemsAmount];
    items->p9 = new unsigned int[itemsAmount];
    items->p10 = new unsigned int[itemsAmount];

    for (unsigned int i = 0; i < itemsAmount; i++)
    {
        items->p1[i] = 1;
    }

    time = clock();

    unsigned int count = 0;
    for (unsigned int i = 0; i < itemsAmount; i++)
    {
        count += items->p1[i];
    }

    cout << (clock() - time) << endl;
    cout << count << endl;

    system("pause");
}
    

Ответы

Ответ 1

Это классическая иллюстрация работы кэш-памяти.
В первом случае разность адресов двух соседних элементов p1 равна sizeof(Item), во
втором случае - sizeof(unsigned int), что в 10 раз меньше. Это означает, что во втором
случае при последовательном чтении элементов p1 загрузка в кэш очередного блока памяти
будет выполняться реже, что приведет к сокращению времени доступа к данным из этого
блока. В вашем случае это дало выигрыш в 10 раз.


Ответ 2

В первом случае выделяется один большой кусок памяти, размером в sizeof(Item), а
во второй раз - много маленьких кусков по sizeof(unsigned int). Проблема - накладные
расходы на кучу вызовов new несравнимо больше зависимости размера выделяемой области.


Ответ 3

я взял и специально посмотрел разницу в скомпилированном коде между
for (unsigned int i = 0; i < itemsAmount; i++)
{
    items[i].p1 = 1;
}

и
for (unsigned int i = 0; i < itemsAmount; i++)
{
    items->p1[i] = 1;
}

Разница только в константах. И сильно повлиять на скорость работы не может. А вот
выделить памяти на один гигабайт (около того) на большинстве современных машинах достаточно
накладно (потому что памяти на большинстве машин все таки 4 гигабайта, и 2 из них -
под ось). А память нужно одним большим куском.
Во втором случае выделям 10 кусков по 100М. И хотя это по размеру тоже, но найти
куски такого размера сильно проще.
Хочу дома на 16 гигах протестить. Думаю, там разница в скорости выполнения кода будет
в долях процентов.
Можете просто уменьшить кол-во запрашиваемой памяти и увидите, как скорость выполнения
выровняется.