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

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

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

Итак, мы имеем десяток «примерно» эквивалентного кода на различных языках, рассматривать будем из них только два 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

Источник ^[5]