Примеры оптимизации путём группировки данных в памяти

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

Не совсем вопрос, скорее статья-пример к вопросу Методы оптимизации, основанные на
эффективном использовании оборудования, пункт "Обход латентности доступа к данным",
пп. "Группировка нужных данных".

Вполне себе пример из жизни - система частиц. Первый вариант - массив структур (в
результатах - два левых столбца), второй - два массива со структурами, разбитыми по
назначению (основные данные - в одной структуре, вспомогательные - в другой).

Естественно, пример не содержит множества различных процедур обработки данных. Он
лишь демонстрирует изменение производительности на небольшом фрагменте реальной системы.
Т.е., допустим, у нас есть большая сложная программная система (допустим, Folding@Home),
в которой большой объём данных - массив записей. Одна из типичных вычислительных задач
на этих данных, со скоростью обсчёта которой возникла проблема - обработка подмножества
данных. Данным приёмом можно ускорить этот обсчёт. При этом возникнут некоторые проблемы
(менее красивый код, небольшое замедление некоторых других процедур обработки данных).
Вобщем, как обычно при оптимизации.

#include 
#include 
#include 
#include 

const int size = 1 << 24;
const int repeatCount = 10;

typedef float TVector[3];
struct TSparkle_Full
{
    TVector coords, speed;
    COLORREF color;
    float startSize;
    float startLuminTime, fadingTime;
    float lifeTime;
};

TSparkle_Full g_sparkles_Full[size];

struct TSparkle1
{
    TVector coords, speed;
};
struct TSparkle2
{
    COLORREF color;
    float startSize;
    float startLuminTime, fadingTime;
    float lifeTime;
};

TSparkle1 g_sparkles1[size];
TSparkle2 g_sparkles2[size];

void test1()
{
    LARGE_INTEGER start, end, freq;

    QueryPerformanceFrequency(&freq);

    int i;

    QueryPerformanceCounter(&start);
    memset(g_sparkles_Full, 0, sizeof(g_sparkles_Full));    
    for (i = 0; i < size; i++)
    {
        g_sparkles_Full[i].speed[0] = float(rand());
        g_sparkles_Full[i].speed[1] = float(rand());
        g_sparkles_Full[i].speed[2] = float(rand());
    }
    QueryPerformanceCounter(&end);
    printf("%16.6g", double(end.QuadPart - start.QuadPart) / freq.QuadPart);

    QueryPerformanceCounter(&start);
    for (int n = 0; n < repeatCount; n++)
        for (i = 0; i < size; i++)
        {
            g_sparkles_Full[i].coords[0] += g_sparkles_Full[i].speed[0]; 
            g_sparkles_Full[i].coords[1] += g_sparkles_Full[i].speed[1]; 
            g_sparkles_Full[i].coords[2] += g_sparkles_Full[i].speed[2]; 
        }
    QueryPerformanceCounter(&end);
    printf("%16.6g", double(end.QuadPart - start.QuadPart) / freq.QuadPart);
}

void test2()
{
    LARGE_INTEGER start, end, freq;

    QueryPerformanceFrequency(&freq);

    int i;

    QueryPerformanceCounter(&start);
    memset(g_sparkles1, 0, sizeof(g_sparkles1));    
    memset(g_sparkles2, 0, sizeof(g_sparkles2));    
    for (i = 0; i < size; i++)
    {
        g_sparkles1[i].speed[0] = float(rand());
        g_sparkles1[i].speed[1] = float(rand());
        g_sparkles1[i].speed[2] = float(rand());
    }
    QueryPerformanceCounter(&end);
    printf("%16.6g", double(end.QuadPart - start.QuadPart) / freq.QuadPart);

    QueryPerformanceCounter(&start);
    for (int n = 0; n < repeatCount; n++)
        for (i = 0; i < size; i++)
        {
            g_sparkles1[i].coords[0] += g_sparkles1[i].speed[0]; 
            g_sparkles1[i].coords[1] += g_sparkles1[i].speed[1]; 
            g_sparkles1[i].coords[2] += g_sparkles1[i].speed[2]; 
        }
    QueryPerformanceCounter(&end);
    printf("%16.6g\n", double(end.QuadPart - start.QuadPart) / freq.QuadPart);
}

int _tmain(int argc, wchar_t* argv[])
{   
    printf("%16s%16s%16s%16s\n", "Fill", "Add speed", "Fill 2", "Add speed 2");
    for (int i = 0; i < 5; i++)
    {
        test1();
        test2();
    }
    return 0;
}


MS Visual Studio 2010, процессор intel Сore i5 порядка 2.5 ГГц, память DDR3. Каждый
тест запускается несколько раз (каждому запуску соответствует строка в результатах.
На точность измерений не претендую - процессы на фоне, hyperthreading, ... Но всё видно
и так: скорость обработки координат и скоростей отличается в два раза (1-я и 3-я колонки):

       Fill       Add speed          Fill 2     Add speed 2
    2.20742         2.67801         1.66939         1.44776
    1.63304         2.62465         1.66015         1.45007
    1.65731         2.61806         1.63312         1.43443
     1.6489         2.64562         1.70421         1.48133
    1.65934         2.67894         1.63182         1.47675


А если ещё добавить std::string, то разница - в 3 раза :)
    

Ответы

Ответ 1

@superhackkiller1997, потестил(?) (в смысле все-таки откомпилировал и запустил) я
Ваш код с "pastebin-а":
avp@avp-ubu1:~/hashcode$ gcc hacker3.c  -fopenmp -O3 -std=gnu99
  ... Оооооооооо сколько warning-ов!!!
avp@avp-ubu1:~/hashcode$ ./a.out 
MEMSET: 0.061sec - 61.18GB/s
MEMSET: 0.064sec - 58.29GB/s
MEMADD: 0.188sec - 39.84GB/s
MEMRAND: 0.559sec - 6.71GB/s
avp@avp-ubu1:~/hashcode$ grep CPU /proc/cpuinfo | tail -1
model name  : Intel(R) Core(TM) i5-2500 CPU @ 3.30GHz
avp@avp-ubu1:~/hashcode$

Результат впечатляет (абсолютно серьезно). Только Вы бы все-таки писали с какими
ключами его собирать (не все ведь захотят разбираться, каких lib-ов не хватает -:)).
Ну и обилие warnings не украшет...
Программу @Михаил М, попробовал собрать, но из-за всех этих M$-х DWORD,  LONGLONG
и т.д. бросил.
Если честно, тщательно разбираться как сопоставить Ваш результат с результатом ТС
не стал. На первый взгляд его колонки 'Fill' это сумма Ваших 'MEMSET' / 2, его 'Add
speed' надо сравнивать с 'MEMADD' / 2.
Почему такая колоссальная разница во времени исполнения я толком объяснить (рассчитать)
не могу.
@superhackkiller1997, попробуйте проанализировать и толком рассказать всем (только
без дурацкого жаргона, pls).