Это небольшое подведение итогов на пост “Быстрее, чем C++; медленнее, чем PHP”
Неблагодарное дело — «спорить» в комментариях, поэтому формулирую несколько мыслей в отдельный пост. Автор утверждал тут, тут, и еще много где, что у него большой стаж и богатый опыт в программировании на С++.
Итак, мы имеем десяток «примерно» эквивалентного кода на различных языках, рассматривать будем из них только два C и C++
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
static long
lev_dist (const char *s1,
const char *s2)
{
unsigned long m, n;
unsigned long i, j;
long *v0, *v1;
long ret, *temp;
m = strlen (s1);
n = strlen (s2);
/* Edge cases. */
if (m == 0) {
return n;
} 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 memoryn");
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] = '';
start_time = clock ();
printf ("%ldn", lev_dist (s1, s2));
printf ("%ldn", lev_dist (s1, s3));
exec_time = clock () - start_time;
fprintf (stderr,
"Finished in %.3fsn",
((double) exec_time) / CLOCKS_PER_SEC);
return 0;
}
#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 ("%ldn", 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%, эту задачку предлагаю решить вам, уважаемый читатель.
Автор: Boctopr
