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

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

#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%, эту задачку предлагаю решить вам, уважаемый читатель.