Ох уж этот медленный C/C++

Это небольшое подведение итогов на пост “Быстрее, чем C++; медленнее, чем PHP”

Автор утверждал тут, тут, и еще много где, что у него большой стаж и богатый опыт в программировании на С++.
Итак, мы имеем десяток «примерно» эквивалентного кода на различных языках, рассматривать будем из них только два C и C++
Неблагодарное дело — «спорить» в комментариях, поэтому формулирую несколько мыслей в отдельный пост.

код C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h> static long
lev_dist (const char *s1, const char *s2)
else if (n == 0) { return m; } v0 = malloc (sizeof (long) * (n + 1)); v1 = malloc (sizeof (long) * (n + 1)); if (v0 == NULL || v1 == NULL) { fprintf (stderr, "failed to allocate memory\n"); exit (-1); } for (i = 0; i <= n; ++i) { v0[i] = i; } memcpy (v1, v0, n + 1); for (i = 0; i < m; ++i) { v1[0] = i + 1; for (j = 0; j < n; ++j) { const long subst_cost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1); const long del_cost = v0[j + 1] + 1; const long ins_cost = v1[j] + 1; #if !defined(__GNUC__) || defined(__llvm__) if (subst_cost < del_cost) { v1[j + 1] = subst_cost; } else { v1[j + 1] = del_cost; }
#else v1[j + 1] = (subst_cost < del_cost) ? subst_cost : del_cost;
#endif if (ins_cost < v1[j + 1]) { v1[j + 1] = ins_cost; } } temp = v0; v0 = v1; v1 = temp; } ret = v0[n]; free (v0); free (v1); return ret;
} int
main ()
{ const int len = 15000; int i; char s1[15001], *s2 = s1, s3[15001]; clock_t start_time, exec_time; for (i = 0; i < len; ++i) { s1[i] = 'a'; s3[i] = 'b'; } s1[len] = s3[len] = '\0'; start_time = clock (); printf ("%ld\n", lev_dist (s1, s2)); printf ("%ld\n", lev_dist (s1, s3)); exec_time = clock () - start_time; fprintf (stderr, "Finished in %.3fs\n", ((double) exec_time) / CLOCKS_PER_SEC); return 0;
}

Код C++

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <string> size_t lev_dist(const std::string& s1, const std::string& s2)
{ const auto m = s1.size(); const auto n = s2.size(); std::vector<int64_t> v0; v0.resize(n + 1); std::iota(v0.begin(), v0.end(), 0); auto v1 = v0; for (size_t i = 0; i < m; ++i) { v1[0] = i + 1; for (size_t j = 0; j < n; ++j) { auto delCost = v0[j + 1] + 1; auto insCost = v1[j] + 1; auto substCost = s1[i] == s2[j] ? v0[j] : (v0[j] + 1); v1[j + 1] = std::min({ delCost, insCost, substCost }); } std::swap(v0, v1); } return v0[n];
} int main()
{ std::string s1(20000, 'a'); std::string s2(20000, 'a'); std::string s3(20000, 'b'); std::cout << lev_dist(s1, s2) << std::endl; std::cout << lev_dist(s1, s3) << std::endl;
}

Три грубейшие ошибки:

• Методология замеров времени исполнения кода. В коде на С замер времени происходит в самом коде, а С++ такой код отсутствует, значит, если замерять вызов программы через time (*nix системах) имеются накладные расходы на создания стека и инициализацию переменных.
• Сравнивается не только алгоритм, но и вывод числа на консоль. В каждом языке, даже в таких, казалось бы, «родных» языках С/С++, вывод через printf и cout занимает очень разное время. Поэтому — правильно проверять алгоритм, а не скорость вывода на консоль.
• Бенчмарк проводился всего лишь на двух пограничных случаях, но не на случайных данных, а это значит, что CPU может предсказывать однотипные условные переходы с высокой точностью и за счет этого выполнять программу быстрее чем на реальных данных.

Небольшой разбор кода:

• В программе на С критическая ошибка в строке

  char s1[15001], *s2 = s1, s3[15001];

  это значит что строка s2 это эквивалент памяти строки s1. Из этого следует что в первом тесте

  printf ("%ld\n", lev_dist (s1, s2));

  процессор обращается в 2 раза реже к памяти чем следует.
  Исправляем на

  char s1[15001], s2[15001], s3[15001];

  а также не забываем инициализировать строку s2.
  Результат код на C работает на 20-30% медленнее чем заявлено.

• В программе на C++ критических ошибок несколько.
  Массив строк 20000 вместо сравниваемых 15000, хоть автор и указал что их нормализовал (разделил на коэффициент поправки) это лукавство, так как Кеш процессора и оптимизация переходов сильно от этого страдают, итого 1-5% быстрее чем заявлено.
• Нахождение минимального числа, строчкой

  v1[j + 1] = std::min({ delCost, insCost, substCost });

  каждый раз создает на стеке массив из трех значений, находит минимальное число, удаляет массив на стеке, в данном случае стек не статичный поскольку это анонимный массив. Решается заменой классической идиомой поиска минимального числа из трех

  v1[j + 1] = std::min(std::min(delCost, insCost), substCost);

  итог производительность 250-300% быстрее чем заявлено.

Возможные оптимизации кода:

• Присутствует два вложенных цикла где идет «плотная» обработка данных, в них присутствуют один прямой if и два косвенных через поиск минимального числа (std::min). Есть формула

  min = x ^ ((y ^ x) & -(x > y))

  которая с помощью бинарной арифметики возвращает минимальное число из двух значений x, y. Заменив строчку поиска минимального числа на

  auto z = substCost ^ ((insCost ^ substCost) & -(substCost > insCost));
v1[j + 1] = z ^ ((delCost ^ z) & -(z > delCost));

  получаем прирост скорости 1-10% (с учетом что бенчмарк теперь работает на более разнордных данных)

• Строка кода также подвергаеться оптимизации

  substCost = s1[i] == s2[j] ? v0[j] : (v0[j] + 1);

  которую также можно исправить на бинарную арифметику и избавиться от ветвления в коде, что тоже даст прирост на 1-4%, эту задачку предлагаю решить вам, уважаемый читатель.

Update

Уважаемые, теоретики, представляю вам, сжатый список ссылок и литературы, для того чтобы не считать команды вручную и писать в комментариях что раз количество больше то работать будет медленнее, или то что initialization_list не работает с памятью (команды взятия адреса в ассемблере, но уж точно не работа со списком регистров).

как работают процессоры, в частности, современные процессоры:

Суперскалярны — значит что большое количество элементарных команд он выполняет параллельно, и получившийся ассемблерный код в большее количество команд может работать быстрее, чем несколько сложных такие как ветвление или вызов функции, примерный подсчет можно сделать по этой таблице:
Современные процессоры также имеют несколько вычислительных конвейеров, что также дает большой прирост к скорости, а выполнение по ассемблерным коммандам предсказать становиться практически невозможным.

Процессоры и микропроцессоры(контроллеры) отличаются не только частотой, а также принципом работы скалярных вычислений и количеством конвейеров.

Информация данного поста основана на книгах:

Проверенные методы повышения производительности — методологии замеров, оптимизация аллокаций, и алгоритмов Оптимизация программ на C++.

Генри С. Алгоритмические трюки для программистов | Уоррен мл. — оптимизация на уровне скалярных процессоров, по средствам бинарной арифметики

Краткий курс | Страуструп Бьярне — современное программирование в частности как писать идиоматический код, а не лапшу старого C стиля с современным С++. Язык программирования C++.

Справочное руководство | Джосаттис Николаи М. Стандартная библиотека C++. — как устроен std::min и initialization_list и многое другое

Самое главное не путайте ваше ДОЛЖЕН, от рекомендаций к стандарту языка, компиляторов, и выполнению кода непосредственно самим процессором, делайте замеры на реальном железе использовав несколько разных операционных систем и последних версий разных компиляторов.