8

А давайте соберём здесь неалгоритмические методы оптимизации программ. Не алгоритмы «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++) 
  …
6
  • На мой взгляд и опыт, самый общий рецепт тут - использование параллелизма, особенно на GPU.
    – skegg
    1 ноя 2013 в 16:14
  • А я бы наоборот, если бы надо было выбрать один приём, назвал обеспечение последовательного доступа к данным 1 ноя 2013 в 16:42
  • 2
    Одно другому не мешает. И потом, эффективное программирование GPU - та еще забава. Там тоже нужно думать о правильном обращении к памяти, о пересылках данных, о кеше и пр. При этом можно получить ускорение на современных GPU в сотни раз.
    – skegg
    1 ноя 2013 в 17:02
  • 1
    По формату топик, скорее, напоминает исследование. Вопрос к модераторам: Может стоит преобразовать?
    – Risto
    2 ноя 2013 в 14:22
  • 1
    @Risto, в принципе Вы наверное правы, но IMHO как только тема попадает в "Исследования" интерес к ней (активность обсуждения) резко падает (остается 2-3 человека). Более того, здесь можно активно отвечать, а в формате исследований нет (а размер комментариев там тоже ограничен (как и здесь)). А тема в принципе интересная, может кто-то что дельное скажет. IMHO лучше оставить здесь. -- @Михаил М, не очень-то мне вериться в эффективность ручного перемешивания операций. Хороший компилятор с оптимизатором, скажем icc для процессоров Intel наверняка справится с этим лучше.
    – avp
    2 ноя 2013 в 19:32

4 ответа 4

6

Хорошая идея! Подождём ответов от специалистов по оптимизациям.

Внесу свои 5 копеек: битовые трюки. Многие операции имеют неожиданно простую и эффективную реализацию с учётом особенностей двоичной записи чисел. Вот популярный сборник.

Пример: для положительного числа v выражение

(v & (v - 1)) == 0

определяет, является ли v степенью двойки.

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

4
  • Врут ведь avp@avp-xub11:~/src/codegoogle/smhasher$ gcc -O3 t.c -lm avp@avp-xub11:~/src/codegoogle/smhasher$ time ./a.out sqrt() -lm : x = 65536.000000 real 0m9.956s user 0m9.057s sys 0m0.168s avp@avp-xub11:~/src/codegoogle/smhasher$ gcc -O3 -DQUAKE t.c -lm avp@avp-xub11:~/src/codegoogle/smhasher$ time ./a.out QUAKE: x = 65536.003900 real 0m13.387s user 0m12.201s sys 0m0.232s avp@avp-xub11:~/src/codegoogle/smhasher$ и вообще, эта 1/sqrt наверное для CPU без "аппаратного" sqrt.
    – avp
    1 ноя 2013 в 15:35
  • @avp: А исходник выложите? А вообще-то, все неалгоритмические трюки очень системно-, компиляторо-, оптимизаторо- и процессорозависимые, так что всегда надо пробовать перед использованием и не завязывать архитектуру на них.
    – VladD
    1 ноя 2013 в 15:41
  • Сейчас выложу. В комментарий не лезет.
    – avp
    1 ноя 2013 в 15:51
  • 1
    На SO пишут, что начиная с SSE есть такая инструкция, rsqrtss. И этот алгоритм был разработан, когда Pentium был топовым процессором. Она не эффективна на современных процессорах: чтение 8-ми байт сразу после записи их двумя 4-байтными порциями очень медленно (погуглите "store forwarding stalls") carmack's invsqrt in asm 1 ноя 2013 в 16:01
5

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

UPD: Наваял демонстрацию:

$ cat test.cc
#include <memory>
#include <thread>
#include <vector>

int main() {
  const int THREADS = 2;
  const int ITERATIONS = 50000000;
  std::vector<std::thread> threads;
  std::vector<int> 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<int> ptr1(new int(i));
        std::unique_ptr<double> 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 <stdio.h>
#include <stdlib.h>
#include <math.h>

//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);
}
5
  • 1
    Круто. Это прекрасно подтверждает тезис о том, что преждевременная оптимизация — источник всех бед.
    – VladD
    1 ноя 2013 в 15:58
  • @avp: Хм. Поменфл стартовую константу на 1.1 и уменьшил в 10 раз количество итераций: [Vlad@Kenga] [17:02:24] [~/c++] {0,514}$> gcc -O3 quakesqrt.cpp -o quakesqrt -lm && time ./quakesqrt sqrt() -lm : x = 65536.000000 real 0m3.205s user 0m3.125s sys 0m0.046s [Vlad@Kenga] [17:02:40] [~/c++] {0,515}$> gcc -O3 -DQUAKE quakesqrt.cpp -o quakesqrt -lm && time ./quakesqrt QUAKE: x = 282124.157738 real 0m1.188s user 0m1.140s sys 0m0.015s
    – VladD
    1 ноя 2013 в 16:04
  • Не, этот код слишком маленький и не запутанный :) (ядрёная формула не в счёт!). Он скорее подтверждает компиляторо- и процессорозависимость. Мда, опасно так (x += 1 / sqrt(x)) играть. Операция деления вон тоже довольно быстрая, если делитель оказывается степенью двойки 1 ноя 2013 в 16:11
  • Еще на одном компе посмотрел (также поменял начальное значение на 1.1) [avp@nas ~]$ gcc -O3 qt.c -lm [avp@nas ~]$ time ./a.out sqrt() -lm : x = 65536.000000 real 0m1.925s user 0m1.925s sys 0m0.000s [avp@nas ~]$ gcc -DQUAKE -O3 qt.c [avp@nas ~]$ time ./a.out QUAKE: x = 65536.000000 real 0m2.029s user 0m2.028s sys 0m0.001s [avp@nas ~]$ grep CPU /proc/cpuinfo | tail -1 model name : Intel(R) Xeon(R) CPU E5520 @ 2.27GHz [avp@nas ~]$ и опять родной sqrt быстрее
    – avp
    1 ноя 2013 в 18:58
  • @avp: у вас процессор круче. [Vlad@Kenga] [20:12:15] [~/t] {0,538}$> grep 'model name' /proc/cpuinfo model name : Dual Core AMD Opteron(tm) Processor 175 model name : Dual Core AMD Opteron(tm) Processor 175
    – VladD
    1 ноя 2013 в 19:12
3

К сожалению, у нас начинается флейм оптимизаторов-теоретиков и оптимизаторов-практиков (здесь и в вопросе-примере). Но т.к. я вспомнил практический пример в тему, я его всё-таки приведу :) . К вопросу о том, что всё, что не даёт лучшей оценки (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. Читается легко, всем рекомендую :)

3
  • Вообще-то, тысяча баксов — зарплата хорошего программиста за 2-3 дня. Поэтому возможно «купить сервер получше» является более выгодной стратегий в краткосрочной перспективе.
    – VladD
    3 ноя 2013 в 12:42
  • 1
    В среднестатистической России, 10000 баксов в месяц? И, к слову, я тогда был скорее junior'ом 3 ноя 2013 в 13:20
  • @Михаил М: в среднестатистической Германии. Учите язык и уезжайте.
    – VladD
    4 ноя 2013 в 10:07

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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