5

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

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

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

#include <stdafx.h>
#include <conio.h>
#include <math.h>
#include <Windows.h>

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 раза :)

4
  • Ну про любую оптимизацию можно сказать "просто стал делать меньше работы" или "просто стал делать работу эффективней". Это один из приёмов. Далеко не всегда это легко сделать, поэтому и выигрыш, если он есть, нельзя считать бесплатным 2 ноя 2013 в 18:20
  • 1
    @Михаил М, IMHO Вы тестируете здесь не latency, а "effective" throughput. По сути Вы демонстрируете, что обмен RAM/L3 Cache осуществляется порциями данных (у Вас я думаю по 64 байта) (их называют Cache line) фиксированного размера. Естественно, чем больше доля нужных для вычислений данных в Cache line, тем выше производительность. Но, не расстраивайтесь, для практических выводов это на самом деле значения не имеет.
    – avp
    2 ноя 2013 в 19:16
  • 1
    @Yura Ivanov, ну, Вы слишком строги в оценке оптимизации. O(n^2) => O(n log n) хотя бы это точно из области изменения алгоритма, а ТС все же говорит об оптимизации использования железа. По мне, так 20% в этой области -- уже неплохо.
    – avp
    2 ноя 2013 в 22:09
  • @avp, у меня и в мыслях не было тестировать latency (в нс). Я лишь хотел привести пример, демонстрирующий её проявление и как простые на вид изменения приводят к росту производительности в разы. @Yura Ivanov, приведите своё определение того, что такое оптимизация. >давайте на каждое поле просто заведем по массиву Во-первых, это будет иногда медленнее, во-вторых, я и не утверждаю, что оптимальный код всегда красивый и удобный в поддержке. И не призываю оптимизировать до последнего бита. Я призываю собрать приёмы и примеры, чтобы люди могли хотя бы задумываться об архитектуре и оптимизации 3 ноя 2013 в 6:56

1 ответ 1

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).

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.