Методы оптимизации, основанные на эффективном использовании оборудования

#алгоритм #оптимизация

А давайте соберём здесь неалгоритмические методы оптимизации программ. Не алгоритмы
«N*log n вместо N^2», а приёмы позволяющие использовать имеющееся оборудование более
эффективно. Что приходит на ум мне:

Использование кэша процессора:


Обработка данных небольшими порциями, чтобы каждый раз все необходимые данные влезали
в кэш. 
Пример (для начала; можно придумать что-то более удачное): для quicksort эта рекомендация
выполняется, когда дело доходит до небольших блоков. Но на больших объёмах данных на
первых итерациях сортируемые и сливаемые половинки не помещаются в кэш. Следствие:
если, допустим, помимо сортировки надо с данными сделать что-то ещё, это выгодно делать
после сортировки каждого небольшого блока, пока данные ещё в кэше.


Обход латентности доступа к данным (применимо и к чтению/записи данных процессором
из памяти и к работе с диском):


Чтение/запись данных последовательно, а не в случайном порядке. Пример: внешняя сортировка
позволяет обойтись эффективными операциями чтения/записи больших последовательных блоков
данных. Если реализовать quicksort с хранением данных на диске, то при объёме данных
> объёма кэша потребуется O(n * log n) движений головки диска. 
Буферизация ввода/вывода. Пример: всё та же внешняя сортировка. Одна из операций
там – слияние данных из нескольких файлов с диска и запись результата на диск. Это
будет работать гораздо быстрее, если читать данные из каждого входного файла порциями,
скажем, по 10 МБ и писать результаты в буфер, который сбрасывать на диск тоже по мере
накопления.
Группировка нужных данных. Пример: параллельные массивы. Допустим, у нас есть большой
массив точек на плоскости и описание к каждой из них длиной 50 символов. Тогда, например,
выбор точек, попадающих в некоторый прямоугольник (допустим, нам невыгодно применять
что-то более сложное, чем простой проход по массиву) будет работать существенно быстрее,
если разбить информацию на два массива:

struct THeader {  int x, y;  };
struct TInfo {  char description[50];  };
THeader dotHeaders[10000000], dotInfos[10000000];

Другой похожий пример (вопрос Примеры оптимизации путём группировки данных в памяти).


Оптимальное использование имеющейся пропускной способности:


Сжатие данных «на лету». Пример: объёмная база данных с некоторыми  закономерностями
в данных (между полями записей или между соседними записями). Сжатие данных перед записью
на диск и расжатие при чтении может позволить достичь большей скорости записи/чтения
с диска.
Использование специальных команд процессора, содержащих дополнительные "подсказки"
по работе с памятью. Пример: intrinsic'и _mm_stream_ps и т.п. в примере http://pastebin.com/Xzq9dYww
@superhackkiller1997'a. _mm_stream_ps компилируется в команду MOVNTPS - аналог memset,
работающий в обход кэша.


Обход «неудобных» шаблонов доступа к данным:


Выравнивание данных по границам, кратным 4, 8 и более байт. Обычно делается компилятором
именно потому, что на многих процессорах доступ, например, к 4-байтному целому в памяти
по адресу, не кратному 4, намного медленнее.


Использование нескольких имеющихся устройств одновременно (несколько ядер процессора/несколько
вычислительных устройств в ядре процессора/процессор и диск):


Многопоточная обработка. Эта тема слишком обширная чтобы пытаться охватить её здесь.
Использование специальных наборов команд процессора (MMX, SSE, …).
Расчёты на графических картах.
Обработка данных в одном потоке, буферизация и сохранение в другом потоке.


Обход латентности конвейера процессора:


Уменьшение количества условных переходов в принципе.
В частности – путём разворачивания циклов. Пример: для несложной обработки большого
массива данных 


вместо

for (int i = 0; i < n; i++) 
  process(a[i]);


может быть выгодно написать

int i, stopI = n - 4;
for (i = 0; i <= stopI; i += 4) {
  process(a[i]);
  process(a[i + 1]);
  process(a[i + 2]);
  process(a[i + 3]);
}
for ( ; i < n; i++) 
  process(a[i]);


(естественно, очень желательно, чтобы функции process была inline или просто одним
оператором)


Переупорядочивание операций. Подходит и для уменьшения зависимостей по данным и для
загрузки большего количества вычислительных устройств.
Совмещение итераций цикла. Аналогично предыдущему пункту – подходит для разных случаев.
Пример (тут тоже можно придумать что-нибудь получше): для обработки большого массива
данных 


вместо

for (int i = 0; i < n; i++) {
  b[i].x += deltaX;
  if (b[i].x < 0)
    b[i].x += 100;
  b[i].y *= b[i].x * y2;
}


-

int i, stopI = n - 2;
for (i = 0; i <= stopI; i += 2) {
  b[i].x += deltaX;
  if (b[i].x < 0)
    b[i].x += 100;
  b[i + 1].x += deltaX;   // Пока  b[i].y *= b[i].x * y2; ждёт выполнения процессором
условия и, возможно, += 100, мы начинаем обрабатывать следующий элемент
  if (b[i + 1].x < 0)
    b[i + 1].x += 100;
  b[i].y *= b[i].x * y2;
  b[i + 1].y *= b[i + 1].x * y2;
}
for ( ; i < n; i++) 
  …

    

Ответы

Ответ 1

Хорошая идея! Подождём ответов от специалистов по оптимизациям.
Внесу свои 5 копеек: битовые трюки. Многие операции имеют неожиданно простую и эффективную
реализацию с учётом особенностей двоичной записи чисел. Вот популярный сборник.
Пример: для положительного числа v выражение
(v & (v - 1)) == 0

определяет, является ли v степенью двойки.
Ещё одним классическим трюком на грани между алгоритмическими и неалгоритмическими
является быстрое вычисление 1/sqrt(x) из Quake.


Ответ 2

Внесу свои пять копеек. В многопоточных программах могут возникнуть проблемы с производительностью,
когда потоки интенсивно выделяют/освобождают память. Это происходит из-за того, что
стандартный malloc не умеет работать параллельно и просто делает lock на каждое выделение.
С этим можно бороться по-разному, например выделяя большой кусок памяти для каждого
потока, и используя его как пул. Но самый простой способ, это применить библиотеку
tcmalloc, которая входит в gperttools. Самое приятное, что для ее использования ничего
не надо менять в исходниках, нужно просто добавить флаг -ltcmalloc при линковке. На
моей памяти простое добавление tcmalloc увеличивало производительность на 20-30% в
одном проекте, связанном с алгоритмами на графе.
UPD: Наваял демонстрацию:
$ cat test.cc
#include 
#include 
#include 

int main() {
  const int THREADS = 2;
  const int ITERATIONS = 50000000;
  std::vector threads;
  std::vector arr(THREADS, 0);
  for (int t = 0; t < THREADS; ++t) {
    threads.emplace_back([t, &arr]() {
      for (int i = 0; i < ITERATIONS; ++i) {
        std::unique_ptr ptr1(new int(i));
        std::unique_ptr ptr2(new double(i));
        arr[t] += *ptr1 + *ptr2;
        arr[t] %= ITERATIONS;
      }
    });
  }
  for (std::thread& thread: threads) {
    thread.join();
  }
  int sum = 0;
  for (int s: arr) {
    sum = (sum + s) % ITERATIONS;
  }
  return sum;
}
$ g++-4.7 --std=c++11 test.cc -O2 -pthread
$ time ./a.out

real    0m16.127s
user    0m30.602s
sys 0m0.172s
$ g++-4.7 --std=c++11 test.cc -O2 -pthread -ltcmalloc
$ time ./a.out

real    0m8.743s
user    0m16.417s
sys 0m0.056s

Как видно, даже на 2-х тредах tcmalloc ускорил программу почти в 2 раза.


Ответ 3

Вот такой примитвный. Просто транслирую с -DQUAKE и запускаю через time.
avp@avp-xub11:~/src/codegoogle/smhasher$ grep CPU /proc/cpuinfo 
model name  : Pentium(R) Dual-Core  CPU      E5400  @ 2.70GHz
avp@avp-xub11:~/src/codegoogle/smhasher$

#include 
#include 
#include 

//float InvSqrt (float x);
static inline float InvSqrt (float x){
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i>>1);
    x = *(float*)&i;
    x = x*(1.5f - xhalf*x*x);
    return x;
}

#if QUAKE
#define WHO "QUAKE"
#else
#define WHO "sqrt() -lm "
#endif

int main()
{
  int i;
  float x = 1.0;

  for (i = 0; i < 1000000000; i++)
#if QUAKE
    x += InvSqrt(x);
#else
  x += 1 / sqrt(x);
#endif

  printf ("%s: x = %f\n", WHO, x);
}


Ответ 4

К сожалению, у нас начинается флейм оптимизаторов-теоретиков и оптимизаторов-практиков
(здесь и в вопросе-примере). Но т.к. я вспомнил практический пример в тему, я его всё-таки
приведу :) . К вопросу о том, что всё, что не даёт лучшей оценки (O(n*log n) вместо
O(n^2) и т.п.)- это баловство.

Я тоже как-то, например, написал для каждой вставки в базу дополнительный select
max(id)+1 ... Авто-инкремент там нельзя было сделать т.к. несколько процессов заливали
данные в одну таблицу, но каждый - в своём диапазоне id, чтобы можно было по этим id
в каждом диапазоне находить новые данные. Но суть не в этом.

Суть в том, что когда код заработал, производительность была довольно грустной. Точно
не помню, приведу очень примерные цифры ради отображения соотношений величин. Допустим,
записывалось 50 элементов данных в секунду. При этом в процессе работы всех загрузчиков
новых данных поступает 10 в секунду. Но когда загрузчики перезапускаются, им в сумме
нужно загрузить 20000 элементов. Т.е. запас по прочности вроде как в 5 раз, но при
рестарте надо ждать 6 минут. А код надо ещё тестировать и отлаживать. 

Было понятно, что select max(id)+1 это хрень, но избавление от него обещало прирост
ну процентов 20 (что такого, быстренько в индексе пробежаться, тем более, он и так
в памяти). И я точно помню, что мне казалось, что смысла нет. Тем не менее, после того,
как мы немного подумали и я поправил эту и несколько подобных мелких проблем, производительность
возросла раза в 3. И просто работать стало намного приятней! Не говоря о том, что я
сэкономил себе много часов ожидания на имеющихся машинах (вполне нормальных по тем
временам). Т.е. можно было ходить и плакаться, что мне надо машину на 1000$ дороже
и сервер тоже, а можно было подумать-поработать пару дней.

Upd: нашёл в одном вопросе (Книги по теме Concurrency и Parallel Programming) замечательный
сборник статей. И в частности: приём переделки бинарных деревьев с тем, чтобы при спуске
по дереву приходилось читать из памяти менее разбросанные данные: 1024CORES / RAM -
не RAM, или Cache-Conscious Data Structures. Читается легко, всем рекомендую :)