#алгоритм #оптимизация
А давайте соберём здесь неалгоритмические методы оптимизации программ. Не алгоритмы
«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. Читается легко, всем рекомендую :)
