Быстрее, чем C++; медленнее, чем PHP +82



Привет, Хабр.


У меня тут случайно код на хаскеле получился быстрее аналогичного кода на C++. Иногда — на 40%.



(время работы, меньше — лучше, C++ снизу)


Что самое смешное — я собирал хаскель-код через LLVM-бекенд, но при этом сравнивал с GCC. Если сравнивать с clang (что вроде как логичнее), то всё становится ещё хуже для плюсов: почему-то на этой задаче clang проигрывает GCC в пару раз, и разница становится не 40%, а этак раза три. Впрочем, одна маленькая модификация C++-кода это поменяет.


Началось всё с того, что для одного моего проекта (который, естественно, делается на хаскеле, и о котором я тоже скоро напишу) нужно было быстро и эффективно считать расстояние Левенштейна между двумя строками. Расстояние Левенштейна — это такая метрика, которая говорит, сколько символов нужно удалить, добавить или заменить в одной строке, чтобы она стала равна другой строке. Я считал расстояния между довольно большими строками (масштаба десятков тысяч символов), поэтому эффективность была действительно важна.


А потом мне стало интересно, насколько быстро я вообще могу это расстояние считать (потратив разумное время на оптимизацию, конечно), так что я набросал вариант на С++ и взял его время работы за этакий идеал, к которому стоит стремиться. Впрочем, как уже понятно, идеал оказался превзойдён.


Посмотрим, как этого можно достичь?



В качестве бонуса — сравнение с некоторыми другими языками. Спойлеры:


  • Nim медленнее компилятора C двадцатилетней давности.
  • C# в пять раз медленнее Java, которая оказывается вполне на уровне Rust.
  • Go вровень с C.
  • PHP быстрее питона (что оправдывает вторую часть заголовка).

Про расстояние Левенштейна

Нахождение расстояния Левенштейна — как раз одна из тех задач, что просто создана для динамического программирования. Классическое решение сводится к построению матрицы размера $m \times n$ (где $m$ и $n$ — длины строк) и построчному её заполнению сверху вниз. Увы, если строки имеют смешной размер порядка десятка килобайт, то такая матрица сожрёт 0.5-1 гигабайт, что не очень приятно. Однако, если присмотреться, то можно заметить, что мы в каждый момент времени используем только две строки (текущую заполняемую и предыдущую), поэтому можно хранить только их.


На самом деле можно обойтись одной строкой, но нам и с двумя хорошо будет.


Бенчмаркинг


Будем замерять производительность двумя способами.


Во-первых, есть замечательный пакет criterion, который помогает делать бенчмарки правильно, запуская код много раз, высчитывая всякие стандартные отклонения и прочие статистики.


Но запускать его долго, поэтому у нас будет ещё один наколенный бенчмарк. Возьмём три строки s1, s2, s3, первые две из которых состоят из 20000 символов 'a', а последняя — из 20000 символов 'b', и будем считать расстояния от s1 до s2 и от s1 до s3 (естественно, ожидая получить 0 и 20000).


Так как выделение полсотни килобайт и заполнение их одним и тем же символом — ничто по сравнению со временем работы алгоритма, мы просто будем замерять время работы всей программы (в случае хаскеля — согласно +RTS -sstderr). Чтобы не делать бенчмарк совсем уж наколенным, защитимся от выбросов: будем запускать код три раза и брать минимум из трёх. Минимум, а не среднее — так как случайная активность на машине может заставить код выполняться медленнее, чем он есть на самом деле, а вот быстрее выполнять не получится. Тем более, что никакой случайности во входных данных у нас нет, и выполнение строго детерминированно.


По ходу рассмотрения различных вариантов кода мы будем рассматривать лишь результаты этого наколенного бенчмарка, а аккуратные графики criterion'а будут в самом конце.


К чему стремиться?


Давайте начнём с ожиданий: насколько быстро мы можем решить нашу задачу в этих условиях? Это можно оценить двумя способами: очень грубо теоретически и чуть более аккуратно практически.


Теоретически

Предположим, что все наши данные помещаются в L2-кеш, но из L1 они таки вымываются. Обосновано ли это предположение? Посмотрим, что нам нужно хранить:


  • Две строки по 20000 байт: примерно 40 килобайт (это уже больше, чем L1 на моей машине!).
  • Два массива по 20000 8-байтных чисел, что даёт нам дважды по 160 — итого 320 килобайт (и даже если бы мы использовали 4-байтные инты, то это бы всё равно было 160 килобайт, что куда больше L1).

Сколько данных за время работы алгоритма мы должны передать в/из L2?


Мы сделаем в районе 20000 итераций, каждая из которых читает одну из строк целиком (20 КБ), весь построенный на прошлом шаге массив (160 КБ), и при этом пишет новую строку (ещё 160 КБ). Оптимистично предполагая, что запись ни на что не влияет (у нас же грубая оценка снизу) рассмотрим только чтение: суммарно нам нужно прочитать (20 + 160)?20000 КБ из L2, что равно 3.6 ГБ. Учитывая, что, судя по разным источникам, мой Haswell имеет устоявшуюся скорость чтения из L2 в районе 50 ГБ/с, это даст нам порядка 0.1 с на одну пару строк, или 0.2 с на весь тест. Быстрее мы никак не можем.


Ну, то есть, совсем теоретически могли бы, но решение этой задачи блочным образом, чтобы помещаться в L1, совсем не подняло производительность.


Практически

Набросаем вот эту программу на 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;
}

Минимум времени работы этой программы из трёх запусков — 1.356 секунд (Core i7 4770, никакого оверклокинга). При этом использовался gcc 9.2, опции — -O3 -march=native.


Как уже упоминалось во введении, clang (9.0.1, естественно, с теми же опциями) показывает себя хуже: время работы оказывается в районе 2.6-2.7 с.


Так что наша цель — 1.3 секунды.


Код


Наивная чистая реализация


Никакой явной мутабельности (кроме того, что внутри Data.Vector, но это не наша кухня), никакой явной хвостовой рекурсии. Просто строгая левая свёртка и немного костыльный Data.Vector.constructN:


import qualified Data.ByteString as BS
import qualified Data.Vector.Unboxed as V
import Data.List

levenshteinDistance :: BS.ByteString -> BS.ByteString -> Int
levenshteinDistance s1 s2 = foldl' outer (V.generate (n + 1) id) [0 .. m - 1] V.! n
  where
    m = BS.length s1
    n = BS.length s2

    outer v0 i = V.constructN (n + 1) ctr
      where
        s1char = s1 `BS.index` i
        ctr v1 | V.length v1 == 0 = i + 1
        ctr v1 = min (substCost + substCostBase) $ 1 + min delCost insCost
          where
            j = V.length v1
            delCost = v0 V.! j
            insCost = v1 V.! (j - 1)
            substCostBase = v0 V.! (j - 1)
            substCost = if s1char == s2 `BS.index` (j - 1) then 0 else 1

Это может показаться немного уродливым, но, на мой взгляд, это всё равно достаточно читабельный и идиоматичный код (насколько такие алгоритмы вообще могут быть идиоматично представимыми).


Время согласно наколенному бенчмарку? 5.5 секунд. Как-то не оч.


Можно ли лучше?


Тривиальные улучшения


К счастью, есть пара способов улучшить производительность, вообще не трогая код.


Во-первых, вряд ли компилятор правильно вывел все характеристики строгости. Давайте ему поможем и добавим {-# LANGUAGE Strict #-} в самое начало файла. Конечно, мы могли бы быть более дотошными и начать аккуратно расставлять bang patterns, но и так сойдёт.


В любом случае, это уменьшает время работы до 3.4 секунд. Куда лучше, но всё ещё так себе.


Во-вторых, давайте вдобавок попробуем использовать не штатный кодогенератор GHC (NCG — Native CodeGen), а LLVM? Для этого добавим {-# OPTIONS_GHC -fllvm #-} в начало файла. Результат? 2.1 секунд. Это уже что-то! И, кстати, уже даже этот вариант быстрее того, что сгенерировал clang.


Чистая реализация с небезопасными операциями


Теперь попробуем чуть более значимые улучшения: заменим операции доступа по индексу их небезопасными версиями (которые, впрочем, эквивалентны по безопасности плюсовым operator[]). Так V.! заменяется на V.unsafeIndex, а BS.index на BS.unsafeIndex.


Полный код
import qualified Data.ByteString as BS
import qualified Data.ByteString.Unsafe as BS
import qualified Data.Vector.Unboxed as V
import Data.List

levenshteinDistance :: BS.ByteString -> BS.ByteString -> Int
levenshteinDistance s1 s2 = foldl' outer (V.generate (n + 1) id) [0 .. m - 1] V.! n
  where
    m = BS.length s1
    n = BS.length s2

    outer v0 i = V.constructN (n + 1) ctr
      where
        s1char = s1 `BS.unsafeIndex` i
        ctr v1 | V.length v1 == 0 = i + 1
        ctr v1 = min (substCost + substCostBase) $ 1 + min delCost insCost
          where
            j = V.length v1
            delCost = v0 `V.unsafeIndex` j
            insCost = v1 `V.unsafeIndex` (j - 1)
            substCostBase = v0 `V.unsafeIndex` (j - 1)
            substCost = if s1char == s2 `BS.unsafeIndex` (j - 1) then 0 else 1

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


В любом случае, время выполнения (без всех тривиальных улучшений) составляет 4.2 секунды (против 5.5 секунд «безопасной» версии).


А что с улучшениями?


Добавление {-# LANGUAGE Strict #-} сокращает время до 2.5 секунд (против 3.4 секунд «безопасной» версии).


Компиляция через LLVM улучшает результат аж до 1.6 секунд (против 2.1 секунд ранее). Это уже быстрее clang!


И вообще, это интересный результат по ряду причин:


  1. Мы уже получили почти-C++-производительность, в то же время по-прежнему имея достаточно идиоматичный код.
  2. Мы получаем такие результаты несмотря на то, что мы аллоцируем новый массив на каждой итерации (то есть, в 20000 раз больше, чем это делает C++-версия). К счастью, каждый такой массив не очень долгоживущий, так что он умирает и собирается GC ещё в роддоме нулевом поколении. Сборщики мусора с поколениями рулят и педалят!
  3. «Штраф за безопасность» что строгой, что нестрогой версии составляет примерно 20% при использовании NCG. Лично я бы ожидал существенно меньшее влияние проверок на производительность — они никогда не срабатывают, так что предсказатель ветвлений должен достаточно быстро понять соответствующий паттерн.
  4. Использование LLVM-бекенда уменьшает этот штраф до примерно 0.5 секунд. Почему? LLVM способен избавиться от некоторых проверок, или же сами проверки становятся более дружественными к предсказателю ветвлений? Или оба фактора сразу?

Реализация с мутабельностью


Давайте начнём с прямого переписывания алгоритма с использованием мутабельного Data.Array.ST:


import qualified Data.Array.Base as A(unsafeRead, unsafeWrite)
import qualified Data.Array.ST as A
import qualified Data.ByteString.Char8 as BS
import Control.Monad
import Control.Monad.ST

levenshteinDistance :: BS.ByteString -> BS.ByteString -> Int
levenshteinDistance s1 s2 = runST $ do
  v0Init <- A.newListArray (0, n) [0..]
  v1Init <- A.newArray_ (0, n)
  forM_ [0 .. m - 1] $ \i -> do
    let (v0, v1) | even i = (v0Init, v1Init)
                 | otherwise = (v1Init, v0Init)
    loop i v0 v1
  A.unsafeRead (if even m then v0Init else v1Init) n

  where
    m = BS.length s1
    n = BS.length s2

    loop :: Int -> A.STUArray s Int Int -> A.STUArray s Int Int -> ST s ()
    loop i v0 v1 = do
      A.unsafeWrite v1 0 (i + 1)
      let s1char = s1 `BS.index` i
      forM_ [0..n - 1] $ \j -> do
        delCost <- v0 `A.unsafeRead` (j + 1)
        insCost <- v1 `A.unsafeRead` j
        substCostBase <- v0 `A.unsafeRead` j
        let substCost = if s1char == s2 `BS.index` j then 0 else 1
        A.unsafeWrite v1 (j + 1) $ min (substCost + substCostBase) $ 1 + min delCost insCost

По моему опыту массивы (в смысле Data.Array.ST) оказываются быстрее векторов (Data.Vector.Mutable и их unboxed-версия) при некоторых дополнительных условиях, которые здесь выполняются. Поэтому (а также в целях удержания размера поста в рамках разумного) рассматривать версию на векторах мы не будем. Ровно по тем же причинам мы не будем рассматривать «безопасные» функции для индексации и сразу обратимся к unsafeRead/unsafeWrite.


Насколько быстро работает этот вариант?


5.9 секунд. Чёрт. Куда хуже, чем безопасная и чистая реализация! И даже если мы отпрофилируем этот код, то окажется, что… В общем, ничего интересного из этого профиля не выйдет.


С другой стороны, эта реализация по крайней мере почти не требует GC: 2-3 минорных сборки мусора и 2-3 мажорных (согласно +RTS -sstderr) против тысяч минорных в случае чистого Data.Vector. Впрочем, как мы видим, даже это не особо помогает производительности — GC с поколениями рулят, живи быстро, умри молодым.


Как насчёт наших старых добрых друзей?
Строгость уменьшает время работы до 4.1 секунды. Сборка через LLVM выигрывает ещё 0.4 секунды, позволяя достичь суммарного времени в 3.7 секунд.


Нет, спасибо, я лучше останусь с чистой версией.


Но давайте продолжим.


Явная хвостовая рекурсия


Есть множество свидетельств того, что GHC очень любит хвостовую рекурсию, так что давайте перепишем наш код так, чтобы она была явной. Для этого придётся убрать комбинатор forM_ и получить примерно следующий код:


import qualified Data.Array.Base as A(unsafeRead, unsafeWrite)
import qualified Data.Array.ST as A
import qualified Data.ByteString.Char8 as BS
import Control.Monad.ST

levenshteinDistance :: BS.ByteString -> BS.ByteString -> Int
levenshteinDistance s1 s2 = runST $ do
  v0Init <- A.newListArray (0, n) [0..]
  v1Init <- A.newArray_ (0, n)
  loop 0 v0Init v1Init
  A.unsafeRead (if even m then v0Init else v1Init) n

  where
    m = BS.length s1
    n = BS.length s2

    loop :: Int -> A.STUArray s Int Int -> A.STUArray s Int Int -> ST s ()
    loop i v0 v1 | i == m = pure ()
                 | otherwise = do
      A.unsafeWrite v1 0 (i + 1)
      let s1char = s1 `BS.index` i
      let go j | j == n = pure ()
               | otherwise = do
            delCost <- v0 `A.unsafeRead` (j + 1)
            insCost <- v1 `A.unsafeRead` j
            substCostBase <- v0 `A.unsafeRead` j
            let substCost = if s1char == s2 `BS.index` j then 0 else 1
            A.unsafeWrite v1 (j + 1) $ min (substCost + substCostBase) $ 1 + min delCost insCost
            go (j + 1)
      go 0
      loop (i + 1) v1 v0

Время работы этого варианта — 4.3 секунды. Строгость снижает время работы до 1.7 секунд — прямо как с векторами с небезопасной индексацией. Если честно, я удивлён и обескуражен тем, что GHC не смог оптимизировать forM_ так же хорошо, как он смог это сделать с хвостовой рекурсией.


Но теперь давайте попробуем собрать с LLVM.


0.96 секунд. Шта? Быстрее чем C++? Я где-то сделал ошибку?



0.96 секунд.


Но можно лучше.


Всякая мелочь


Мы всё ещё безопасно читаем строки (на самом деле я просто забыл это поправить при написании начальной мутабельной версии, а потом было лень переделывать бенчмарки).


Замена BS.index на BS.unsafeIndex срезает ещё 0.04 секунды, давая время работы в 0.92 секунды.


Кроме того, есть ещё одна оптимизация, которую можно попробовать. Заметим, что мы пишем в v1[j+1] на j-ой итерации и читаем из того же элемента на следующей итерации. Что будет, если мы будем явно передавать соответствующее значение в рекурсивный вызов?


Соответствующий код
{-# LANGUAGE Strict #-}
{-# OPTIONS_GHC -fllvm #-}

import qualified Data.Array.Base as A(unsafeRead, unsafeWrite)
import qualified Data.Array.ST as A
import qualified Data.ByteString as BS
import qualified Data.ByteString.Unsafe as BS
import Control.Monad.ST

levenshteinDistance :: BS.ByteString -> BS.ByteString -> Int
levenshteinDistance s1 s2 = runST $ do
  v0Init <- A.newListArray (0, n) [0..]
  v1Init <- A.newArray_ (0, n)
  loop 0 v0Init v1Init
  A.unsafeRead (if even m then v0Init else v1Init) n

  where
    m = BS.length s1
    n = BS.length s2

    loop :: Int -> A.STUArray s Int Int -> A.STUArray s Int Int -> ST s ()
    loop i v0 v1 | i == m = pure ()
                 | otherwise = do
      A.unsafeWrite v1 0 (i + 1)
      let s1char = s1 `BS.unsafeIndex` i
      let go j prev | j == n = pure ()
                    | otherwise = do
            delCost <- v0 `A.unsafeRead` (j + 1)
            substCostBase <- v0 `A.unsafeRead` j
            let substCost = if s1char == s2 `BS.unsafeIndex` j then 0 else 1
            let res = min (substCost + substCostBase) $ 1 + min delCost prev
            A.unsafeWrite v1 (j + 1) res
            go (j + 1) res
      go 0 (i + 1)
      loop (i + 1) v1 v0

Эта микрооптимизация даёт нам примрено 0.09 секунд, уменьшая время работы до 0.83 секунд. Это победа.


Интересно, что аналог этой микрооптимизации для C++ ни на что не влияет.


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


Результаты


Наколенные бенчмарки


Сначала сведем результаты всех наколенных бенчмарков в одну таблицу. Базовое время для C++-версии — 1.36 секунд, все остальные времена отнормированы относительно него (так что оно составляет 100%).


Версия Базовое время + строгость + LLVM
Чистая 406% 250% 154%
Чистая (unsafe-индексация) 309% 181% 121%
Мутабельный массив 435% 298% 274%
Массив + хвостовая рекурсия 318% 129% 70%
Массив + хвостовая рекурсия + микрооптимизации 61%

У меня также была возможность прогнать некоторые из тестов на машине с i7-6700, и две наиболее важные точки таковы:


  • 178% для чистой версии с небезопасной индексацией,
  • 84% для наиболее эффективной версии.

Похоже, что Haskell ближе к Haswell, чем к Skylake. Хотя, конечно, даже на последнем наибыстрейшая Haskell-версия быстрее C++.


Результаты criterion


Приведём скриншоты графиков criterion (увы, JavaScript тут вставлять нельзя, так что они неживые).


На Haswell (i7 4770):



На Skylake (i7 6700):



Здесь использовалась C++-версия, которая вызывается через FFI. Однако время работы получилось плюс-минус равным времени «чистой» C++-версии без всякого FFI, что позволяет считать, что расходами на FFI можно пренебречь (да и этого следовало бы ожидать исходя из того, как в памяти представляются ByteString).


Заключение


  • На чистом, достаточно идиоматичном хаскеле вполне возможно достичь не настолько уж далеко отстоящей от C++ производительности.
  • Строгость (вернее, её корректное использование) важна.
  • Хвостовая рекурсия важна. GHC, увы, не способен заметить, что некоторые вещи могут быть выражены через хвостовую рекурсию, и приходится объяснять ему это вручную. Так что при написании вычислительно тяжёлых алгоритмов точно стоит уделить этому внимание.
  • LLVM важен. Я нечасто видел, чтобы использование LLVM давало такой профит даже в некоторых числодробильных алгоритмах, так что приятно видеть задачу, где от этого есть прок.
  • Оптимизация кода — строго нелинейный процесс. Нельзя ожидать, что одно и то же изменение (даже очень «техническое» вроде строгости или изменения бекенда) даст одинаковый прирост производительности для различных формулировок даже одного и того же алгоритма.
    В частности, был соблазн даже не рассматривать Data.Array.ST после того, как мы увидели, как плохо он себя показывает по сравнению с чистой версией, но именно он оказался победителем.

Всякое разное


О чём я умолчал в посте?


  • В первую очередь, на некотором мета-уровне рассуждений, это история успеха. Этот пост не означает, что хаскель всегда может быть оптимизирован так, чтобы соответствовать C++-версии. Мне просто в известном смысле повезло натолкнуться на задачу, где это действительно так. Окажись это не совсем так, этот пост не был бы таким радостным (или вообще не был бы).
  • Импорт правильных строк важен. Data.ByteString.Char8 ненамного, но статистически значимо медленнее, чем Data.ByteString.
  • Версия GHC важна. Исследование этого, впрочем, составляет ещё одно измерение в пространстве этого бенчмарка.
    Код в этом посте компилировался при помощи GHC 8.6 (Stackage LTS 14.16). GHC 8.8 (с одним из nightly-снапшотов Stackage), похоже, генерирует более эффективный код при компиляции с NCG, но в среднем проигрывает при использовании LLVM. Однако это не влияет на наиболее быстрый из представленных вариантов.
  • Зависимые типы, блин, важны. На самом деле в посте я это уже упомянул, но не могу не подчеркнуть это ещё раз. Необходимость писать unsafe там, где в более выразительном языке вполне всё можно доказать статически и избавиться от рантайм-проверок, не потеряв в безопасности — это ужасно, это как лопата дворника по асфальту зимой.
  • Ещё один аспект, который было бы интересно исследовать — поведение на более широком наборе входов. Несмотря на то, что количество итераций алгоритма не зависит от входных данных, вряд ли сравнение двух одинаковых (или двух полностью разных) строк представляет репрезентативный бенчмарк.
  • Микроархитектура важна. Необходимо отметить, что, помимо упомянутой разницы между Haswell и Skylake, я также получил репорт о том, что C++-код и хаскель-код идут вровень на некоторых машинах. У меня это воспроизвести не получилось, и тот репорт был от обладателя Ryzen, так что я виню AMD.
    Ну и даже одинаковая производительность — это всё равно круто.
  • Наверняка наша базовая C++-версия может быть ещё более оптимизирована, но я не хочу тратить на это больше времени, чем я потратил на оптимизацию хаскель-версии (иначе теряется всякий смысл — и на хаскеле можно генерировать LLVM IR, например).
  • Кроме того, я получил репорт о том, что замена std::min на вручную написанное сравнение улучшает производительность. Мне это удалось воспроизвести, но с двоякими результатами: gcc замедляется ещё больше, до 1.4-1.5 секунд, а clang резко ускоряется — до примерно 0.84 с, что вполне на уровне GHC.
    Впрочем, разворачивание std::min ускоряет и хаскель-версию, и это не та оптимизация, которая имеет смысл в контексте поста.
  • И, наконец, входные строки важны. Я сделал пару ещё более наколенных тестов на случайных строках, и что хаскель-, что C++-версия немного замедлились. Но аккуратно бенчмаркать со случайными данными, да ещё между двумя разными языками, да с прицелом на портирование на ещё пару дюжин языков (см. ниже) сложно, да и смысл поста не в этом.

Так что воспринимайте этот пост с долей скептицизма.


Ссылки



Бонус


А теперь начнём специальную олимпиаду и посмотрим, как другие языки справятся с этой задачей. Методика сравнения та же — запускаем трижды, берём минимальное значение.


Скажу сразу — я ни на одном из них писать не умею (кроме C++), так что ничего про них сказать не могу. С этими всеми реализациями мне помог XRevan86 — чувак настоящий полиглот и фанат своего дела, так что подписывайтесь, ставьте лайк.


Код для всех примеров сравнивает строки длиной 15 тысяч символов, а не 20, однако числа перенормированы для длины в 20 тысяч символов.


Мы отдельно рассмотрим компилируемые языки (куда мы также для простоты и холивара включим Java и C#) и отдельно — интерпретируемые.


Компилируемые языки


C++-вариант приведен для сравнения. Его можно оптимизировать ещё немного (например, развернув руками std::min или заменив std::vector/std::string на сырые данные), но тогда это получится C с плюсовым main'ом, что не так интересно. Если бы я писал научную работу, я бы написал «out of scope of this work».


С-вариант с технологиями 2000-ого года (BCC 5.5) приведен для лулзов. Другие варианты приведены для демонстрации зависимости от компилятора и его опций.


Язык Реализация Отн. время Абс. время, с Опции тулчейна
С clang 9 103% 0.860 -O3 -march=native
Go go 1.13 106% 0.876 -compiler gc -gcflags=-B -ldflags '-w -s'
D ldc 1.19 117% 0.972 -boundscheck=off -O3 -relocation-model=pic -release -L=-s
Rust rustc 1.38 124% 1.028 -C debuginfo=0 -C opt-level=3
Zig zig 0.5 125% 1.040 --release-fast -fPIC --strip -target x86_64-linux-gnu build-exe
Java openjdk 1.8.0 125% 1.040 -g:none
С gcc 9.2 125% 1.046 -Ofast -fPIC -fPIE -static -flto
С clang 9 132% 1.096 -Ofast -fPIC -fPIE -static -flto
Crystal crystal 0.32 152% 1.262 --release
C++ gcc 9.2 163% 1.356 -O3 -march=native
D dmd 2.087 182% 1.515 -fPIC -boundscheck=safeonly -O -release
Pascal fpc 3.0 183% 1.520 -Mfpc -O3 -Cg XX -Xg -Xs -k-flto
С bcc 5.5 190% 1.581
Nim nim 1.0.2 223% 1.851 -d:release --opt:speed --checks:off --passc:-flto --passc:-s
C++ clang 9 323% 2.684 -O3 -march=native
C# Mono 6.6.0 356% 2.967 mcs -o+
C# .NET core 3.1 721% 5.984 ?\_(?)_/?

Наблюдения:


  • nim'у пока не удалось победить Borland C++ Compiler, выпущенный в 2000-м году. Увы.
  • Разница между Java и C# какая-то огромная, и Java оказывается подозрительно близко к вершине, хотя я просто сделал javac -g:none LevDist.java && java LevDist. Наверное, тут что-то совсем не так. Хотя, с другой стороны, это очень JIT-friendly-задача, так что, может, здесь JIT творит чудеса.
  • Ещё любопытно, что clang умудряется подчистую сливать на C++-коде, но при этом вырываться вперёд на С-коде.
  • C# с .NET Core у меня не получилось запустить, и я взял результаты XRevan86, отнормировав их на разницу производительностей наших машин согласно остальным результатам. Научность зашкаливает, понимаю.
  • Везде куча ансейфа. Интересно, насколько он влияет в разных языках?
  • В некоторых реализациях (по крайней мере, в С++) время работы зависит от порядка сравнений. Оптимизировать этот порядок — имхо скорее читерство и снова out of scope.
  • При некоторых из этих порядков мне таки удалось воспроизвести ускорение в случае C++. Так, если вместо std::min({ delCost, insCost, substCost }) написать std::min(substCost, std::min(delCost, insCost)), то время работы под gcc увеличивается до 1.440 секунд, а под clang — уменьшается до 0.840 секунд (ура, быстрее всех остальных вариантов и почти хаскель). Похоже, clang не любит initializer lists и не может их заинлайнить, а gcc шедулит операции и регистры так, что, по крайней мере, на этих конкретных данных результат проигрывает.
    Но ещё раз отмечу, что оптимизацией порядка в случае хаскеля я не занимался, и заниматься этим в рамках этого бенчмарка не рекомендую в любом языке.
    Кроме того, это значит, что нельзя рассчитывать на компилятор даже в таком языке, как C++, где в компиляторы влиты десятки тысяч человеколет.

Собственно код выглядит так:


C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

static long
lev_dist (const char *s1, unsigned long m
          const char *s2, unsigned long n)
{
    unsigned long m, n;
    unsigned long i, j;
    long *v0, *v1;
    long ret, *temp;

    /* 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, sizeof(long) * (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[15001], s3[15001];
    clock_t start_time, exec_time;

    for (i = 0; i < len; ++i) {
        s1[i] = 'a';
        s2[i] = 'a';
        s3[i] = 'b';
    }
    s1[len] = s2[len] = s3[len] = '\0';

    start_time = clock ();

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

    exec_time = clock () - start_time;
    fprintf (stderr,
             "Finished in %.3fs\n",
             ((double) exec_time) / CLOCKS_PER_SEC);
    return 0;
}

Crystal
def lev_dist(s1 : String, s2 : String) : Int
  m = s1.bytesize
  n = s2.bytesize

  # Edge cases.
  return n if m == 0
  return m if n == 0

  v0 = (Slice.new(n + 1) { |i| i }).to_unsafe
  v1 = (Slice.new(n + 1) { |i| i }).to_unsafe

  ca1, ca2 = s1.bytes, s2.bytes

  ca1.each_with_index do |c1, i|
    v1[0] = i + 1

    ca2.each_with_index do |c2, j|
      subst_cost = (c1 == c2) ? v0[j] : (v0[j] + 1)
      del_cost = v0[j + 1] + 1
      ins_cost = v1[j] + 1

      # [del_cost, ins_cost, subst_cost].min is slow.
      min_cost = (subst_cost < del_cost) ? subst_cost : del_cost
      if ins_cost < min_cost
        min_cost = ins_cost
      end
      v1[j + 1] = min_cost
    end

    v0, v1 = v1, v0
  end

  return v0[n]
end

s1 = "a" * 15_000
s2 = s1
s3 = "b" * 15_000

exec_time = -Time.monotonic.to_f

puts lev_dist(s1, s2)
puts lev_dist(s1, s3)

exec_time += Time.monotonic.to_f
STDERR.puts "Finished in #{"%.3f" % exec_time}s"

C#
using System;
using System.Diagnostics;
using System.Linq;
using System.Text;

public class Program
{
    public static Int32 LevDist(string s1, string s2)
    {
        var ca1 = Encoding.UTF8.GetBytes(s1);
        var ca2 = Encoding.UTF8.GetBytes(s2);
        return LevDist(ca1, ca2);
    }

    public static Int32 LevDist(byte[] s1, byte[] s2)
    {
        var m = s1.Length;
        var n = s2.Length;

        // Edge cases.
        if (m == 0)
        {
            return n;
        }
        else if (n == 0)
        {
            return m;
        }

        Int32[] v0 = Enumerable.Range(0, n + 1).ToArray();
        var v1 = new Int32[n + 1];

        v0.CopyTo(v1, 0);

        for (var i = 0; i < m; ++i)
        {
            v1[0] = i + 1;

            for (var j = 0; j < n; ++j)
            {
                var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
                var delCost = v0[j + 1] + 1;
                var insCost = v1[j] + 1;

                v1[j + 1] = Math.Min(substCost, delCost);
                if (insCost < v1[j + 1])
                {
                    v1[j + 1] = insCost;
                }
            }

            var temp = v0;
            v0 = v1;
            v1 = temp;
        }

        return v0[n];
    }

    public static int Main()
    {
        string s1 = new String('a', 15000);
        string s2 = s1;
        string s3 = new String('b', 15000);

        Stopwatch execTimer = new Stopwatch();
        execTimer.Start();

        Console.WriteLine(LevDist(s1, s2));
        Console.WriteLine(LevDist(s1, s3));

        execTimer.Stop();
        double execTime = execTimer.ElapsedMilliseconds / 1000.0;

        Console.WriteLine($"Finished in {execTime:0.000}s");
        return 0;
    }
}

D
module main;
import core.time;
import std.stdio;
import std.algorithm : swap;
import std.array : array;
import std.range : iota, replicate;

long levDist(ref const string s1,
             ref const string s2) pure nothrow @trusted
{
    const auto m = s1.length;
    const auto n = s2.length;

    if (m == 0)
    {
        return n;
    }
    else if (n == 0)
    {
        return m;
    }

    long[] v0 = iota(0, long(n) + 1).array;
    long[] v1 = v0.dup;

    size_t i = 0;
    foreach (ref c1; s1)
    {
        v1[0] = i + 1;

        size_t j = 0;
        foreach (ref c2; s2)
        {
            const auto substCost = (c1 == c2) ? v0[j] : (v0[j] + 1);
            const auto delCost = v0[j + 1] + 1;
            const auto insCost = v1[j] + 1;

            // min(substCost, delCost, insCost) is slow.
            v1[j + 1] = (substCost < delCost) ? substCost : delCost;
            if (insCost < v1[j + 1])
            {
                v1[j + 1] = insCost;
            }

            ++j;
        }

        swap(v0, v1);
        ++i;
    }

    return v0[n];
}

void main(string[] args)
{
    string s1 = "a".replicate(15000);
    string s2 = s1;
    string s3 = "b".replicate(15000);

    auto startTime = MonoTime.currTime;

    writeln(levDist(s1, s2));
    writeln(levDist(s1, s3));

    auto endTime = MonoTime.currTime;
    auto execTime = (endTime - startTime).total!"msecs" / 1000.0;

    stderr.writefln("Finished in %.3fs", execTime);
}

Go
package main

import (
    "bytes"
    "fmt"
    "os"
    "time"
)

func levDist(s1, s2 []byte) int {

    m := len(s1)
    n := len(s2)

    // Edge cases.
    if m == 0 {
        return n
    } else if n == 0 {
        return m
    }

    root := make([]int, (n+1)*2)

    v0 := root[:n+1]
    v1 := root[n+1:]
    for i, _ := range v0 {
        v0[i] = i
    }
    copy(v1, v0)

    for i, c1 := range s1 {
        v1[0] = i + 1

        for j, c2 := range s2 {
            substCost := v0[j]
            if c1 != c2 {
                substCost++
            }
            delCost := v0[j+1] + 1
            insCost := v1[j] + 1

            if substCost < delCost {
                v1[j+1] = substCost
            } else {
                v1[j+1] = delCost
            }
            if insCost < v1[j+1] {
                v1[j+1] = insCost
            }
        }

        v0, v1 = v1, v0
    }

    return v0[n]
}

func main() {

    s1 := bytes.Repeat([]byte("a"), 15000)
    s2 := s1
    s3 := bytes.Repeat([]byte("b"), 15000)

    startTime := time.Now()

    fmt.Println(levDist(s1, s2))
    fmt.Println(levDist(s1, s3))

        execTime := time.Now().Sub(startTime).Seconds()
    fmt.Fprintf(os.Stderr, "Finished in %.3fs\n", execTime)
}

Rust
use std::cmp::min;
use std::time::Instant;

fn lev_dist(s1: &str, s2: &str) -> i32 {
    let m = s1.len();
    let n = s2.len();

    // Edge cases.
    if m == 0 {
        return n as i32;
    } else if n == 0 {
        return m as i32;
    }

    let mut v0: Vec<i32> = (0..).take(n + 1).collect();
    let mut v1 = v0.to_vec();

    for (i, c1) in s1.bytes().enumerate() {
        unsafe {
            *v1.get_unchecked_mut(0) = i as i32 + 1;

            for (j, c2) in s2.bytes().enumerate() {
                let mut subst_cost = *v0.get_unchecked(j);
                if c1 != c2 {
                    subst_cost += 1;
                }
                let del_cost = *v0.get_unchecked(j + 1) + 1;
                let ins_cost = *v1.get_unchecked(j) + 1;

                let mut min_cost = min(subst_cost, del_cost);
                if ins_cost < min_cost {
                    min_cost = ins_cost;
                }
                *v1.get_unchecked_mut(j + 1) = min_cost;
            }
        }

        std::mem::swap(&mut v0, &mut v1);
    }

    return v0[n];
}

fn main() {
    let s1 = "a".repeat(15000);
    let s2 = &s1;
    let s3 = "b".repeat(15000);

    let start_time = Instant::now();

    println!("{}", lev_dist(&s1, &s2));
    println!("{}", lev_dist(&s1, &s3));

    let exec_time = start_time.elapsed().as_millis() as f64 / 1000.0;
    eprintln!("Finished in {:.3}s", exec_time);
}

Zig
const std = @import("std");
const time = std.time;
const Allocator = std.mem.Allocator;

pub fn lev_dist(allocator: *Allocator, s1: []const u8, s2: []const u8) !i32 {
    @setRuntimeSafety(false);
    const m = s1.len;
    const n = s2.len;

    // Edge cases.
    if (m == 0) {
        return @intCast(i32, n);
    } else if (n == 0) {
        return @intCast(i32, m);
    }

    var root = try allocator.alloc(i32, (n + 1) * 2);
    defer allocator.free(root);

    var v0 = root[0..(n + 1)];
    var v1 = root[(n + 1)..];

    for (v0) |*it, i| {
        it.* = @intCast(i32, i);
    }
    std.mem.copy(i32, v1, v0);

    for (s1) |c1, i| {
        v1[0] = @intCast(i32, i) + 1;

        for (s2) |c2, j| {
            const subst_cost = if (c1 == c2) v0[j] else (v0[j] + 1);
            const del_cost = v0[j + 1] + 1;
            const ins_cost = v1[j] + 1;

            // std.mem.min(i32, [_]i32{subst_cost, del_cost, ins_cost}) is slow.
            v1[j + 1] = if (subst_cost < del_cost) subst_cost else del_cost;
            if (ins_cost < v1[j + 1]) {
                v1[j + 1] = ins_cost;
            }
        }

        std.mem.swap([]i32, &v0, &v1);
    }

    return v0[n];
}

pub fn main() !void {
    const allocator = std.heap.page_allocator;
    const stdout = &(try std.io.getStdOut()).outStream().stream;

    const s1 = [_]u8{'a'} ** 15000;
    const s2 = s1;
    const s3 = [_]u8{'b'} ** 15000;

    var exec_timer = try time.Timer.start();

    try stdout.print("{}\n", try lev_dist(allocator, s1, s2));
    try stdout.print("{}\n", try lev_dist(allocator, s1, s3));

    const exec_time = @intToFloat(f64, exec_timer.read()) / time.ns_per_s;
    std.debug.warn("Finished in {d:.3}s\n", exec_time);
}

Pascal
program main(output);
uses
  sysutils, dateutils;

function levDist(const s1: AnsiString; const s2: AnsiString): longint;
  var
    m, n: NativeUint;
    i, j: NativeUint;
    c1, c2: AnsiChar;
    v0, v1, temp: array of longint;
    substCost, delCost, insCost: longint;
  begin
    m := length(s1);
    n := length(s2);

    // Edge cases.
    if m = 0 then
      exit(n)
    else if n = 0 then
      exit(m);

    setLength(v0, n+1);
    for i := 0 to n do
      v0[i] := i;
    v1 := copy(v0, 0, n+1);

    i := 0;
    for c1 in s1 do
      begin
        j := 0;
        v1[0] := i + 1;

        for c2 in s2 do
          begin
            substCost := v0[j];
            if c1 <> c2 then
              inc(substCost);
            delCost := v0[j+1] + 1;
            insCost := v1[j] + 1;

            if substCost < delCost then
              v1[j+1] := substCost
            else
              v1[j+1] := delCost;
            if insCost < v1[j+1] then
              v1[j+1] := insCost;

            inc(j);
          end;

        temp := v0;
        v0 := v1;
        v1 := temp;

        inc(i);
      end;

    exit(v0[n]);
  end;

var
  i: integer;
  s1, s2, s3: AnsiString;
  startTime, execTime: TDateTime;
begin
  s1 := '';
  s3 := '';
  for i := 1 to 15000 do
    begin
      s1 := s1 + 'a';
      s3 := s3 + 'b';
    end;
  s2 := s1;

  startTime := now;

  writeln(levDist(s1, s2));
  writeln(levDist(s1, s3));

  execTime := secondSpan(startTime, now);
  writeln(stderr, format('Finished in %.3fs', [execTime]));
end.

Nim
import strformat, strutils, times

{.push checks: off.}
func levDist(s1, s2: string): int32 =
  let m = s1.len
  let n = s2.len

  # Edge cases.
  if m == 0: return int32(n)
  elif n == 0: return int32(m)

  var v0 = newSeq[int32](n + 1)
  for i, _ in v0:
    v0[i] = int32(i)

  var v1 = v0

  for i, c1 in s1:
    v1[0] = int32(i) + 1

    for j, c2 in s2:
      let delCost = v0[j + 1] + 1
      let insCost = v1[j] + 1
      var substCost = v0[j]
      if c1 != c2:
        inc(substCost)

      # min([substCost, delCost, insCost]) is slow.
      v1[j + 1] = min(substCost, delCost)
      if insCost < v1[j + 1]:
        v1[j + 1] = insCost

    swap(v0, v1)

  result = v0[n]
{.pop.}

let s1 = repeat("a", 15000)
let s2 = s1
let s3 = repeat("b", 15000)

let startTime = cpuTime()

echo levDist(s1, s2)
echo levDist(s1, s3)

let execTime = cpuTime() - startTime;
stderr.write &"Finished in {execTime:.3f}s\n";

Java
import java.util.Arrays;
import java.util.stream.LongStream;
import java.lang.Math;

public class LevDist
{
    public static long levDist(String s1, String s2)
    {
        return levDist(s1.getBytes(), s2.getBytes());
    }

    public static long levDist(byte[] s1, byte[] s2)
    {
        int m = s1.length;
        int n = s2.length;

        // Edge cases.
        if (m == 0) {
            return n;
        } else if (n == 0) {
            return m;
        }

        long[] v0 = LongStream.range(0, n + 1).toArray();
        long[] v1 = v0.clone();

        int i = 0, j;
        for (byte c1 : s1) {
            v1[0] = i + 1;

            j = 0;
            for (byte c2 : s2) {
                long substCost = (c1 == c2) ? v0[j] : (v0[j] + 1);
                long delCost = v0[j + 1] + 1;
                long insCost = v1[j] + 1;

                v1[j + 1] = Math.min(substCost, delCost);
                if (insCost < v1[j + 1]) {
                    v1[j + 1] = insCost;
                }

                ++j;
            }

            long[] temp = v0;
            v0 = v1;
            v1 = temp;

            ++i;
        }

        return v0[n];
    }

    public static void main(String[] args)
    {
        byte[] s1 = new byte[15000];
        byte[] s2 = s1;
        byte[] s3 = new byte[15000];

        Arrays.fill(s1, (byte) 'a');
        Arrays.fill(s3, (byte) 'b');

        long execTime = -System.nanoTime();

        System.out.println(levDist(s1, s2));
        System.out.println(levDist(s1, s3));

        execTime += System.nanoTime();

        System.err.printf("Finished in %.3fs%n", execTime / 1000000000.0);
    }
}

Интерпретируемые языки


Язык Реализация Отн. время Абс.время, с
Julia julia 1.3.0 241% 2.00
JavaScript spidermonkey 60.5.2 308% 2.56
JavaScript v8 (node.js 13.3.0) 414% 3.43
Python pypy 7.2.0 978% 8.12
Lua luajit 2.0.5 ?2890% 24
PHP php 7.4 ?4670% 39
Hack HHVM 4.39 ?5100% 43
Lua lua 5.1 ?8900% 74
Perl 6 NQP nqp 2019.07 ?11100% 92
Ruby ruby 2.6 ?12200% 101
Perl perl 5.30 ?19100% 158
Python python 3.6 ?27400% 227
Python python 3.8 ?30000% 249
Perl 6 Raku rakudo 2019.11 ?% ?
Octave octave 5.1 ?% ?

Снова наблюдения:


  • Привычно думать, что V8 — более эффективный JS-движок. Не в этой задаче.
  • Кое-где мы не дождались результатов вычислений (там, где значок ?).
  • Python для вычислений так себе. Pypy уже можно, но лучше всё-таки Julia.
  • Octave хорошо работает с матрицами, а тут задача имеет совершенно нематричную форму, так что увы.
  • Про Raku хочется пошутить, но не буду. Мне же не 12 лет, в конце концов.

Julia
#!/usr/bin/env julia
using Base: @pure, stderr
using Printf

@pure function lev_dist(s1::AbstractString, s2::AbstractString)::Int32
    m, n = sizeof(s1), sizeof(s2)

    m == 0 && return n
    n == 0 && return m

    ca1, ca2 = codeunits(s1), codeunits(s2)

    v0::Vector{Int32} = collect(0:n)
    v1 = copy(v0)

    @inbounds begin
        for (i, c1) in enumerate(ca1)
            v1[1] = i

            for (j, c2) in enumerate(ca2)
                subst_cost = v0[j] + ((c1 === c2) ? 0 : 1)
                del_cost = v0[j + 1] + 1
                ins_cost = v1[j] + 1

                v1[j + 1] = min(subst_cost, del_cost, ins_cost)
            end
            v0, v1 = v1, v0
        end
    end

    return v0[n + 1]
end

let
    s1 = 'a'^15000
    s2 = s1
    s3 = 'b'^15000

    exec_time = @elapsed begin
        println(lev_dist(s1, s2))
        println(lev_dist(s1, s3))
    end
    @printf(stderr, "Finished in %.3fs\n", exec_time)
end

JS
function stringToByteArray(s) {
  let a = [];
  for (let c of s) {
    c = c.charCodeAt(0);
    do {
      a.unshift(c & 0xFF);
      c >>= 8;
    } while (c !== 0);
  }
  return a;
}

function levDist(s1, s2) {
  if (typeof s1 === "string" || s1 instanceof String) {
    s1 = stringToByteArray(s1);
  }
  if (typeof s2 === "string" || s2 instanceof String) {
    s2 = stringToByteArray(s2);
  }

  const m = s1.length;
  const n = s2.length;

  // Edge cases.
  if (m == 0) {
    return n;
  } else if (n == 0) {
    return m;
  }

  let v0 = [];
  for (let i = 0; i <= n; ++i) {
    v0[i] = i;
  }
  let v1 = v0.slice();

  for (let i = 0; i < m; ++i) {
    v1[0] = i + 1;

    for (let j = 0; j < n; ++j) {
      const substCost = v0[j] + ((s1[i] === s2[j]) ? 0 : 1);
      const delCost = v0[j + 1] + 1;
      const insCost = v1[j] + 1;

      // Math.min(substCost, delCost, insCost) is slow.
      v1[j + 1] = (substCost < delCost) ? substCost : delCost;
      if (insCost < v1[j + 1]) {
        v1[j + 1] = insCost;
      }
    }

    [v0, v1] = [v1, v0];
  }

  return v0[n];
}

var s1 = new Uint8Array(15000);
var s2 = s1;
var s3 = new Uint8Array(s1.length);

for (let i = 0; i < s1.length; ++i) {
    s1[i] = "a".charCodeAt(0);
    s3[i] = "b".charCodeAt(0);
}

var execTime = -Date.now();

console.log(levDist(s1, s2));
console.log(levDist(s1, s3));

execTime += Date.now();
console.log(`Finished in ${(execTime / 1000).toFixed(3)}s`);

Python
#!/usr/bin/env python3
import sys
import time
from typing import AnyStr

def lev_dist(s1: AnyStr, s2: AnyStr) -> int:
    if isinstance(s1, str): s1 = s1.encode()
    if isinstance(s2, str): s2 = s2.encode()

    m = len(s1)
    n = len(s2)

    # Edge cases.
    if m == 0: return n
    elif n == 0: return m

    v0 = list(range(0, n + 1))
    v1 = v0[:]

    for i, c1 in enumerate(s1):
        v1[0] = i + 1

        for j, c2 in enumerate(s2):
            subst_cost = v0[j] if c1 == c2 else (v0[j] + 1)
            del_cost = v0[j + 1] + 1
            ins_cost = v1[j] + 1

            # min(subst_cost, del_cost, ins_cost) is slow.
            min_cost = subst_cost if subst_cost < del_cost else del_cost
            if ins_cost < min_cost:
                min_cost = ins_cost
            v1[j + 1] = min_cost

        v0, v1 = v1, v0

    return v0[n]

if __name__ == "__main__":
    s1 = b"a" * 15_000
    s2 = s1
    s3 = b"b" * 15_000

    exec_time = -time.monotonic()

    print(lev_dist(s1, s2))
    print(lev_dist(s1, s3))

    exec_time += time.monotonic()
    print(f"Finished in {exec_time:.3f}s", file=sys.stderr)

Lua
#!/usr/bin/env lua

function levDist (s1, s2)
  local m = s1:len()
  local n = s2:len()

  -- Edge cases
  if m == 0 then return n end
  if n == 0 then return m end

  local ct1, ct2 = {}, {}
  for i = 1, #s1 do
      ct1[i] = s1:sub(i, i)
  end
  for i = 1, #s2 do
      ct2[i] = s2:sub(i, i)
  end

  local v0, v1 = {}, {}
  for i = 1, n + 1 do
    v0[i] = i - 1
    v1[i] = i - 1
  end

  local minCost, substCost, delCost, insCost
  for i, c1 in pairs(ct1) do
    v1[1] = i

    for j, c2 in pairs(ct2) do
      substCost = (c1 == c2) and v0[j] or (v0[j] + 1)
      delCost = v0[j + 1] + 1
      insCost = v1[j] + 1

      -- math.min(substCost, delCost, insCost) is slow.
      minCost = (substCost < delCost) and substCost or delCost
      if insCost < minCost then
        minCost = insCost
      end
      v1[j + 1] = minCost
    end

    v0, v1 = v1, v0
  end

  return v0[n + 1]
end

s1 = string.rep("a", 15000)
s2 = s1
s3 = string.rep("b", 15000)

execTime = -os.clock()

print(levDist(s1, s2))
print(levDist(s1, s3))

execTime = execTime + os.clock()
io.stderr:write(string.format("Finished in %.3fs\n", execTime))

PHP
#!/usr/bin/env php
<?php

function lev_dist(string $s1, string $s2): int
{
    $m = strlen($s1);
    $n = strlen($s2);

    // Edge cases.
    if ($m == 0) {
        return $n;
    } elseif ($n == 0) {
        return $m;
    }

    $ca1 = $ca2 = [];
    for ($i = 0; $i < $m; ++$i) {
        $ca1[] = ord($s1[$i]);
    }
    for ($i = 0; $i < $n; ++$i) {
        $ca2[] = ord($s2[$i]);
    }

    $v0 = range(0, $n + 1);
    $v1 = $v0;

    foreach ($ca1 as $i => $c1) {
        $v1[0] = $i + 1;

        foreach ($ca2 as $j => $c2) {
            $subst_cost = ($c1 == $c2) ? $v0[$j] : ($v0[$j] + 1);
            $del_cost = $v0[$j + 1] + 1;
            $ins_cost = $v1[$j] + 1;

            // min($subst_cost, $del_cost, $ins_cost) is slow.
            $min_cost = ($subst_cost < $del_cost) ? $subst_cost : $del_cost;
            if ($ins_cost < $min_cost) {
                $min_cost = $ins_cost;
            }
            $v1[$j + 1] = $min_cost;
        }

        [$v0, $v1] = [$v1, $v0];
    }

    return $v0[$n];
}

$s1 = str_repeat('a', 15000);
$s2 = $s1;
$s3 = str_repeat('b', 15000);

$exec_time = -hrtime(true);

echo lev_dist($s1, $s2), "\n";
echo lev_dist($s1, $s3), "\n";

$exec_time += hrtime(true);
fprintf(STDERR, "Finished in %.3fs\n", $exec_time / 1000000000);

HHVM
#!/usr/bin/env hhvm

function lev_dist(string $s1, string $s2): int {
  $m = \strlen($s1);
  $n = \strlen($s2);

  // Edge cases.
  if ($m == 0) {
    return $n;
  } else if ($n == 0) {
    return $m;
  }

  $ca1 = $ca2 = vec[];
  for ($i = 0; $i < $m; ++$i) {
    $ca1[] = \ord($s1[$i]);
  }
  for ($i = 0; $i < $n; ++$i) {
    $ca2[] = \ord($s2[$i]);
  }

  $v0 = vec(\range(0, $n + 1));
  $v1 = $v0;

  foreach ($ca1 as $i => $c1) {
    $v1[0] = $i + 1;

    foreach ($ca2 as $j => $c2) {
      $subst_cost = ($c1 == $c2) ? $v0[$j] : ($v0[$j] + 1);
      $del_cost = $v0[$j + 1] + 1;
      $ins_cost = $v1[$j] + 1;

      // \min($subst_cost, $del_cost, $ins_cost) is slow.
      $min_cost = ($subst_cost < $del_cost) ? $subst_cost : $del_cost;
      if ($ins_cost < $min_cost) {
        $min_cost = $ins_cost;
      }
      $v1[$j + 1] = $min_cost;
    }

    list($v0, $v1) = vec[$v1, $v0];
  }

  return $v0[$n];
}

<<__EntryPoint>>
function main(): void {
  $s1 = \str_repeat('a', 15000);
  $s2 = $s1;
  $s3 = \str_repeat('b', 15000);

  $exec_time = -\clock_gettime_ns(\CLOCK_MONOTONIC);

  echo lev_dist($s1, $s2), "\n";
  echo lev_dist($s1, $s3), "\n";

  $exec_time += \clock_gettime_ns(\CLOCK_MONOTONIC);
  \fprintf(\STDERR, "Finished in %.3fs\n", $exec_time / 1000000000);
}

NQP
#!/usr/bin/env nqp
use nqp;

sub str-to-byte-array(str $s) {
    my @a;
    for nqp::split('', $s) -> $c {
        $c := nqp::ord($c);
        repeat {
            my uint8 $b := $c +& 0xFF;
            @a.unshift($b);
            $c := nqp::bitshiftr_i($c, 8);
        } while $c != 0;
    }
    return @a;
}

sub lev-dist(str $s1, str $s2) {
    my @ca1 := str-to-byte-array($s1);
    my @ca2 := str-to-byte-array($s2);

    my $m := nqp::elems(@ca1);
    my $n := nqp::elems(@ca2);

    # Edge cases.
    return $n if $m == 0;
    return $m if $n == 0;

    my @v0[$n + 1];
    my @v1[$n + 1];

    my int $i := 0;
    while $i <= $n {
        @v0[$i] := $i;
        @v1[$i] := $i;
        ++$i;
    }

    $i := 0;
    for @ca1 -> $c1 {
        @v1[0] := $i + 1;

        my int $j := 0;
        for @ca2 -> $c2 {
            my int $subst-cost := @v0[$j] + (($c1 == $c2) ?? 0 !! 1);
            my int $del-cost := @v0[$j + 1] + 1;
            my int $ins-cost := @v1[$j] + 1;

            my int $min-cost := ($subst-cost < $del-cost) ?? $subst-cost !! $del-cost;
            if $ins-cost < $min-cost {
                $min-cost := $ins-cost;
            }
            @v1[$j + 1] := $min-cost;

            ++$j;
        }

        my @temp := @v0;
        @v0 := @v1;
        @v1 := @temp;

        ++$i;
    }

    return @v0[$n];
}

sub MAIN(*@ARGS) {
    my str $s1 := nqp::x('a', 15_000);
    my str $s2 := $s1;
    my str $s3 := nqp::x('b', 15_000);

    my num $start-time := nqp::time_n();

    say(lev-dist($s1, $s2));
    say(lev-dist($s1, $s3));

    my num $exec-time := nqp::sub_n(nqp::time_n(), $start-time);
    stderr().print(nqp::sprintf("Finished in %.3fs\n", [$exec-time]));
}

Ruby
#!/usr/bin/env ruby
# encoding: utf-8

def lev_dist(s1, s2)
  m = s1.bytesize
  n = s2.bytesize

  # Edge cases.
  return n if m == 0
  return m if n == 0

  v0 = (0..n).to_a
  v1 = v0.dup

  ca1, ca2 = s1.bytes, s2.bytes

  ca1.each_with_index do |c1, i|
    v1[0] = i + 1

    ca2.each_with_index do |c2, j|
      subst_cost = (c1 == c2) ? v0[j] : (v0[j] + 1)
      del_cost = v0[j + 1] + 1
      ins_cost = v1[j] + 1

      # [del_cost, ins_cost, subst_cost].min is slow.
      min_cost = (subst_cost < del_cost) ? subst_cost : del_cost
      if ins_cost < min_cost
        min_cost = ins_cost
      end
      v1[j + 1] = min_cost
    end

    v0, v1 = v1, v0
  end

  return v0[n]
end

s1 = "a" * 15_000
s2 = s1
s3 = "b" * 15_000

exec_time = -Process.clock_gettime(Process::CLOCK_MONOTONIC)

puts lev_dist(s1, s2)
puts lev_dist(s1, s3)

exec_time += Process.clock_gettime(Process::CLOCK_MONOTONIC)
STDERR.puts "Finished in #{"%.3f" % exec_time}s"

Raku
#!/usr/bin/env raku
=encoding utf8;
use v6;

multi lev-dist(Str:D $s1, Str:D $s2 --> Int:D) {
    my $ca1 := buf8.new($s1.encode);
    my $ca2 := buf8.new($s2.encode);

    return lev-dist($ca1, $ca2);
}

multi lev-dist(buf8:D $s1, buf8:D $s2 --> Int:D) {
    my $m := $s1.bytes;
    my $n := $s2.bytes;

    # Edge cases.
    return $n if $m == 0;
    return $m if $n == 0;

    my @ca1 = $s1.list;
    my @ca2 = $s2.list;

    my @v0[$n + 1] = 0..$n;
    my @v1[$n + 1] = 0..$n;

    for @ca1.kv -> $i, $c1 {
        @v1[0] = $i + 1;

        for @ca2.kv -> $j, $c2 {
            my $subst-cost := @v0[$j] + (($c1 == $c2) ?? 0 !! 1);
            my $del-cost := @v0[$j + 1] + 1;
            my $ins-cost := @v1[$j] + 1;

            # min($subst-cost, $del-cost, $ins-cost) is slow.
            my $min-cost := ($subst-cost < $del-cost) ?? $subst-cost !! $del-cost;
            if $ins-cost < $min-cost {
                $min-cost = $ins-cost;
            }
            @v1[$j + 1] = $min-cost;
        }

        my @temp := @v0;
        @v0 := @v1;
        @v1 := @temp;
    }

    return @v0[$n];
}

sub MAIN() {
    my $s1 := 'a' x 15_000;
    my $s2 := $s1;
    my $s3 := 'b' x 15_000;

    my $start-time := now;

    say(lev-dist($s1, $s2));
    say(lev-dist($s1, $s3));

    my $exec-time := now - $start-time;
    note(sprintf("Finished in %.3fs", $exec-time));
}

Octave
#!/usr/bin/env octave
1;

function retval = lev_dist (s1, s2)
  if (!isvector (s1) || iscell (s1) || !isvector (s2) || iscell (s2))
    error ("lev_dist: Incompatible types in assignment");
  endif

  m = length (s1);
  n = length (s2);

  if (m == 0)
    retval = n;
  elseif (n == 0)
    retval = m;
  else
    v0 = [0:n];
    v1 = v0;

    for i = 1:m
      v1(1) = i;

      for j = 1:n
        subst_cost = v0(j) + (s1(i) != s2(j));
        del_cost = v0(j + 1) + 1;
        ins_cost = v1(j) + 1;

        # min ([subst_cost, del_cost, ins_cost]) is slow.
        if (subst_cost < del_cost)
          min_cost = subst_cost;
        else
          min_cost = del_cost;
        endif
        if (ins_cost < min_cost)
          min_cost = ins_cost;
        endif
        v1(j + 1) = min_cost;
      endfor

      [v0, v1] = deal (v1, v0);
    endfor

    retval = v0(n + 1);
  endif
endfunction

function main ()
  s1 = repmat (["a"], 15_000, 1);
  s2 = s1;
  s3 = repmat (["b"], 15_000, 1);
  tic ();
  printf ("%d\n", lev_dist (s1, s2));
  printf ("%d\n", lev_dist (s1, s3));
  exec_time = toc ();
  fprintf (stderr, "Finished in %.3fs\n", exec_time);
endfunction

main ();

Помощь зала


Язык Реализация Отн. время Абс.время, с Авторство
Python/Numba python 3.6, numba 0.39 120% 0.998 alec_kalinin / код
JavaScript spidermonkey 60.5.2 251% 2.09 ZoNT / код
JavaScript v8 (nodejs 13.3.0) 313% 2.60 ZoNT / код

Python c JIT-компиляцией через Numba просто рвёт все остальные скриптовые языки.


Заключение (окончательное)


Естественно, всё это не значит, что хаскель рулит и педалит и вообще новый король производительности. Я в своей практике часто сталкиваюсь со случаями, когда код на плюсах существенно быстрее. Однако, если мне не нужно перемножать матрицы (для чего всё равно используется сишно-фортранный MKL), и если я пишу приложение на хаскеле, то можно смело брать этот самый хаскель и не думать о том, что придётся делать реализацию вычислительного ядра на С и париться с FFI.


Ну и рассчитывать на компилятор нигде нельзя.


Чего действительно не хватает?


  • Окамля и SML с реализацией MLton (говорят, она компилирует полчаса, но творит чудеса).
  • Idris 2 с uniqueness types. Это тут тоже может сотворить чудеса, безо всякой явной мутабельности (ну и без unsafe, само собой).

Такие дела.


UPD: в комментариях возникли вопросы о роли std::min, включая довольно серьёзные утверждения о том, что при этом в рантайме каждый раз выделяется вектор, и это ответственно за малую скорость работы версии на C++. Увы, но нет, это скорее говорит о плохом качестве одной из реализации (clang).


UPD2: добавил таблицу с предложениями людей из комментариев. Кроме того, добавил в исходные результаты данные для ldc2 и починил код на C, в результате чего вариант с gcc незначительно (в рамках погрешности) замедлился, а вариант с clang чуть более значительно ускорился (с 0.877 с до 0.855 с).




Комментарии (398):

  1. Siemargl
    /#21131316 / +1

    Главное — правильно померять! =)

    • AgentRX
      /#21135950

      Ага, компилятором Intel)
      На самом деле, вопрос «какой код быстрее?» имеет больше прикладной вопрос, чем реальный. В реальности начинают с вопроса «какой разработчик дешевле?» )

  2. hc4
    /#21131634

    Включение галки Optimize Code в Net Core 3.1 ускоряет выполнение в 4 раза на моём i7-4790 (0,9с против 3.6с)
    Кроме того C# используют безопасное обращение к массиву.

    • 0xd34df00d
      /#21131638 / +1

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


      Я C# не знаю, так что если вы дадите вариант с ансейф-доступом, то я с радостью его прогоню на той же машине под Mono. Ну и да, в Java-то обращения тоже безопасные, насколько я могу судить.

      • byme
        /#21131668

        Доберусь домой сравню у себя на машине с растом.

      • hc4
        /#21132020 / +3

        Сделал условие циклов по s1.Length и s2.Length
        Убрал преобразование строки в массив байт.

        Эта версия работает 0.63 сек
        using System;
        using System.Diagnostics;
        using System.Linq;
        
        public class Program
        {
            public static Int32 LevDist(string s1, string s2)
            {
                var m = s1.Length;
                var n = s2.Length;
        
                // Edge cases.
                if (m == 0)
                {
                    return n;
                }
                if (n == 0)
                {
                    return m;
                }
        
                var v0 = Enumerable.Range(0, n + 1).ToArray();
                var v1 = new int[n + 1];
                v0.CopyTo(v1, 0);
        
                for (var i = 0; i < s1.Length; ++i)
                {
                    v1[0] = i + 1;
        
                    for (var j = 0; j < s2.Length; ++j)
                    {
                        var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
                        var delCost = v0[j + 1] + 1;
                        var insCost = v1[j] + 1;
        
                        v1[j + 1] = Math.Min(substCost, delCost);
                        if (insCost < v1[j + 1])
                        {
                            v1[j + 1] = insCost;
                        }
                    }
        
                    var temp = v0;
                    v0 = v1;
                    v1 = temp;
                }
        
                return v0[n];
            }
        
            public static void Main()
            {
                var s1 = new String('a', 15000);
                var s2 = new String('a', 15000);
                var s3 = new String('b', 15000);
        
                for (var i = 0; i < 5; i++)
                {
                    Stopwatch execTimer = new Stopwatch();
                    execTimer.Start();
        
                    Console.WriteLine(LevDist(s1, s2));
                    Console.WriteLine(LevDist(s1, s3));
        
                    execTimer.Stop();
                    var execTime = execTimer.ElapsedMilliseconds / 1000.0;
        
                    Console.WriteLine($"Finished in {execTime:0.000}s");
                }
            }
        }

        • Boctopr
          /#21132250

          Не только, в коде С++ там тоже 20000, а во всех остальных языках 15000 даже в С, что как бы намекает.

          • 0xd34df00d
            /#21132286 / +3

            что как бы намекает.

            На то, что мне надо было сделать в тексте пожирнее соответствующее замечание:


            Код для всех примеров сравнивает строки длиной 15 тысяч символов, а не 20, однако числа перенормированы для длины в 20 тысяч символов.

            • Boctopr
              /#21132434 / -3

              Может народ дурить не будешь, в коде С++ ты 4 раза выделил память на 20000 символов

                  std::string s1(20000, 'a');
                  std::string s2(20000, 'a');
                  std::string s3(20000, 'b');
              
                std::vector<int64_t> v0;
                v0.resize(n + 1);
                std::iota(v0.begin(), v0.end(), 0);
              


              а в коде С ты выдялешь 15000
                 const int len = 15000;
                  int i;
                  char s1[15001], *s2 = s1, s3[15001];

              причем создаешь как ты говоришь на СТЕК, а не на динамической памяти как в С++.

              • XRevan86
                /#21132460 / +3

                Это вообще буквально до замера всё делается.
                Не влияет ну совсем.

                • Boctopr
                  /#21132488 / +2

                  Еще один, он потом пробегает это в двух вложенных циклах, именно размер созданого массива.

                  • 0xd34df00d
                    /#21132500 / -1

                    Да. У C голый результат с 15 тыщами символов получится в районе 0.5-0.6 секунд (на память). После нормировки на разные длины получится то, что приведено в таблице.


                    Собственно, сишная реализация была одной из тех, корректность переномировки которых я проверил отдельно.

                  • XRevan86
                    /#21132534

                    А размеры…


                    Код для всех примеров сравнивает строки длиной 15 тысяч символов, а не 20, однако числа перенормированы для длины в 20 тысяч символов.

                  • technic93
                    /#21132564

                    ну запусти сам и проверь разницу 15 и 20 тыс.

                  • XRevan86
                    /#21132586 / +3

                    Если хочешь, вот что я сравнивал (15?000):


                    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;
                    }

                • zuko3d
                  /#21138982

                  Не влияет ну совсем.

                  Так-то стек лежит надёжно в L1-кэше процессора, а динамическая память — далеко-далеко и её кучу раз придётся доставать.

                  • 0xd34df00d
                    /#21139020

                    Как это стек лежит в L1-кеше, если там минимум 60 килобайт на три строки, а кеш весь целиком в два раза меньше?

                    • zuko3d
                      /#21139102

                      Оу, да, погорячился. В L1 будет только верхушка, остальное в L2.

              • 0xd34df00d
                /#21132492 / +2

                20000 символов

                Про это я уже написал. Это написано в тексте поста, это написано в комментариях теперь уже раза три, так что я не понимаю, что вам тут не нравится.


                4 раза

                Технически — пять раз, там ещё копия этого v0 есть.


                причем создаешь как ты говоришь на СТЕК, а не на динамической памяти как в С++.

                Это происходит один раз за время жизни программы, которая работает порядка одной секунды. Вы действительно думаете, что выделение пары сотен килобайт пятью кусками займёт какое-то время, хотя бы даже сравнимое с погрешностью измерений, на этом фоне?


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

                • Boctopr
                  /#21132568 / +7

                  1. 20000 и 15000 это разный обьем памяти и циклов.
                  2. Количество памяти влияет на кеш, а он как известно очень мал
                  3 ????
                  4 выдляем 100500 нормируем и говорим что С++ медленный.

                  • 0xd34df00d
                    /#21132624 / +3

                    В обоих случаях данные не помещаются в L1. В обоих случаях данные целиком помещаются в L2.


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


                    Код прямо из поста, 15 тыщ символов, минимальное время из пяти запусков — 0.578 секунд, стандартное отклонение — 0.0026 секунды.
                    Поменял везде 15 тыщ на 20 тыщ, минимальное время — 1.031 секунд, стандартное отклонение — 0.0021 секунды.
                    Нормировка: 0.578 * (4 / 3) ** 2 даёт 1.028 секунд.


                    1.028 достаточно близко к 1.031? Особенно учитывая, что разница между ними примерно равна стандартному отклонению каждого из них?

                    • Smog1on1the1water
                      /#21132834 / +3

                      В чистом С коде «нечестно» вызывать strlen, поскольку там вместо немедленноо return m_stringLength происходит поиск в массиве из 20001 char элементов значения, равного нулю. Поэтому unsigned long m, n нужно передавать как параметры lev_dist — на моей стороне это съедает лишние 2% или около того.

                      • 0xd34df00d
                        /#21132854 / -2

                        Не могу воспроизвести, скорость ровно такой же получается.


                        Что, в принципе, ожидаемо, так как на цикл приходится, считайте, всё время работы программы, а strlen дёргается вне цикла.

                        • Smog1on1the1water
                          /#21132888 / +1

                          Возможно, на вашей стороне разница просто перекрывается обычным разбросом значений между запусками. Я пробую на ноутбучном i7-4710HQ, и у меня разница заметна.

                          В любом случае, strlen привносит излишнюю непредусмотренную тестом логику и работу в алгоритм. Ни один из других языков не выполняет подобного поиска среди элементов массива, поэтому правильнее было бы добавить параметры в вызов lev_dist

                          • mayorovp
                            /#21133140

                            Разница перекрывается не "обычным разбросом значений", а двумя вложенными циклами.


                            Когда время выполнения имеет вид a N2 + b N + c, то для достаточно большого N на коэффициенты b и c просто пофигу.


                            Да, при особо неудачном раскладе вы можете из-за strlen получить время 101%. Но если там вышло 190% — дело точно не в strlen.

                        • Smog1on1the1water
                          /#21132988 / +2

                          Еще в чистом С коде ошибка
                          Должно быть

                          memcpy(v1, v0, sizeof (long) * (n + 1));

                          • Deosis
                            /#21134682 / +1

                            Разницы никакой, так как эти данные никто не читает.

                            • avdx
                              /#21135478

                              Более того, массив v1, по хорошему, вообще не нужен.

                        • Ketovdk
                          /#21135174

                          ну просто понятно, что код на хаскеле, который вы оптимайзили 2 часа будет работать возможно лучше, чем нативный на цпп, но его же тоже можно прооптимайзить? Массивы, быстрый вывод и уже должен полететь сильно быстрее

                          • 0xd34df00d
                            /#21137070 / +1

                            но его же тоже можно прооптимайзить?

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


                            Массивы

                            Так там и так массив.


                            быстрый вывод

                            Он делается один раз за время жизни программы, в самом конце.

                            • Ketovdk
                              /#21137930

                              в ++ах стринги а не массив (ну если я правильно смотрел), логика вычисления минимума сильно избыточная и лишние +1-ы, которые можно не делать 2 раза, а просто выбрать минимум и бахнуть ++. Ну просто на хаскеле вы за 0.06 секунд сражались, а тут как-то нативненько, я бы сказал

                              • 0xd34df00d
                                /#21138034

                                логика вычисления минимума сильно избыточная и лишние +1-ы, которые можно не делать 2 раза, а просто выбрать минимум и бахнуть ++

                                Про +1 хорошее замечание. Я переместил его внутрь, как в хаскеле — ничего не изменилось. Кроме того, я даже сделал GVN руками, сохраняя предыдущее значение на стеке для следующей переменной (как последняя оптимизация в хаскеле) — плюсам от нее ни холодно, ни жарко, видать, gcc 9.2 и clang 9 оба умеют ее делать (что не расходится с моими ожиданиями, я не так давно про нее где-то читал, в частности, что в них она реализована).


                                А дальше можно было бы выжать ещё производительности из обоих вариантов, в правильном порядке сравнивая значения… Но это как-то уже немножко другой сорт оптимизаций.

                            • khim
                              /#21137976

                              Массивы
                              Так там и так массив.
                              Строки — это не массивы. Это странная штука, которая заточена под быстрое-быстрое копирование всякого-разного из одного места в другое и редкие операции, собственно, с их элементами.

                              Ассимтотика там такая же как в массивах, но константа — заметно выше по скорости и заметно ниже по памяти.

                              • 0xd34df00d
                                /#21138020

                                Строки — это не массивы. Это странная штука, которая заточена под быстрое-быстрое копирование всякого-разного из одного места в другое и редкие операции, собственно, с их элементами.

                                Это в плюсах? На длинах порядка тысяч, когда SSO не играет?

                                • khim
                                  /#21138222

                                  К сожалению это лишний код на любых размерах. Ну потому что нужно же понять, что строка всё ещё длинная. Каждый раз при обращении к каждому элементу.

                                  Да, теоретически компилятор может эту проверку вытащить наружу и сделать 4 версии — но не факт, что он это делает. Проверять нужно.

                                  А процессор, конечно, справится без вопросов — но всё давно ему эти инструкции нужно декодировать, как минимум…

                                  • 0xd34df00d
                                    /#21138250

                                    Ну что ж, std::string не подходит для строк. Неприятное открытие для меня.


                                    Надо мне уже завязывать с плюсами, что-то это все как-то...

                                    • khim
                                      /#21138446

                                      Ну что ж, std::string не подходит для строк. Неприятное открытие для меня.
                                      Просто строки, в большинстве программ, это не то, что вы думаете. В Java отличие вообще явное: есть java.lang.String (где строка обычно воспринимается «как единое целое»), есть java.lang.StringBuilder.

                                      А в C++ всё можно сделать и прямо в std::string, а можно — перебросив их в std::vector… но это имеет смысл делать только если строки большие.

                                      Если маленькие, в среднем меньше 20-30 символов — то затраты на переброску не окупят ускорение. А они, в реальных программах, как правило такие и есть.

                                      Надо мне уже завязывать с плюсами, что-то это все как-то...
                                      Ну дык. Где вы ещё столько ногострелов найдёте в одном месте? Разве что в PHP и то не факт…

                                      • 0xd34df00d
                                        /#21138510

                                        Просто строки, в большинстве программ, это не то, что вы думаете.

                                        Ну так там уникод какой или ещё какая ерунда, что не даёт относиться к ним как к массиву байт. А тут, казалось бы...


                                        Где вы ещё столько ногострелов найдёте в одном месте?

                                        В моем личном зачёте после плюсов пока лидирует Coq. Но оно там несколько другого рода.

                                        • khim
                                          /#21138570

                                          Ну так там уникод какой или ещё какая ерунда, что не даёт относиться к ним как к массиву байт.
                                          Именно.

                                          А тут, казалось бы...
                                          Структура, разработанная для работы с объектами, которые почти никогда не обрабатываются как массив байт плохо справляется с этим?

                                          Чего вас удивляет?

                                          Ну это всё равно как если бы вы использовали для замера скорости движения автомобиля автокран, экскаватор или вообще шасси для запуска ракет С-400 и удивлялись — а чё они так медленно ездят-то?

                                          А потому что они не для этого. Да, они, конечно, и автомобили тоже… но это — не их основное предназначение!

                                          В моем личном зачёте после плюсов пока лидирует Coq.
                                          Ну вот… и тут C++ не лидер.

                                          • 0xd34df00d
                                            /#21138654

                                            Структура, разработанная для работы с объектами, которые почти никогда не обрабатываются как массив байт плохо справляется с этим?

                                            Ну, может, это я такой, но строки как массивы байт нужно довольно часто обрабатывать.


                                            Другое дело, что нечасто это строки хотя бы в несколько килобайт.


                                            Ну вот… и тут C++ не лидер.

                                            Лидер-лидер, все остальное как раз следует за ним.

                                            • khim
                                              /#21138728

                                              Другое дело, что нечасто это строки хотя бы в несколько килобайт.
                                              Ну вот тут и порылась собака: строки, в современном C++, заточены под выигрыш за счёт отказа (довольно частого) от new/delete. Когда строк много, они, в среднем, короткие, копируют их часто (а внутрь смотрят мало) — получается очень хороший результат.

                                              А вот когда все строки длинные, копируют их мало, внутрь смотрят часто… тогда выигрыша от отказа от new/delete — нет… а плата за него (хоть и небольшая) — есть…

                                              Так-то tradeoff неплохой: проигрыш — всегда не слишком большой (почти никогда не больше чем вдвое, обычно процентов 20-30, даже если специально делать плохие условия для них), а вот выигрыш — может быть очень и очень приличным… но вот как раз конкретно в вашем тесте проигрыш есть, выигрыша — нету.

                                            • mayorovp
                                              /#21139676

                                              Ну, может, это я такой, но строки как массивы байт нужно довольно часто обрабатывать.

                                              Это вы такой. Прикладному программисту строки надо считывать, выводить, парсить, формировать через форматирование-интерполяцию или конкатенацию, в крайних случаях менять в них регистр или искать подстроки.


                                              Для всего этого придумываются свои структуры данных, не являющиеся просто массивами байт (и std::string в текущих реализациях — далеко не самая сложная из них).

                                      • Akon32
                                        /#21140830

                                        А в C++ всё можно сделать и прямо в std::string, а можно — перебросив их в std::vector… но это имеет смысл делать только если строки большие.

                                        А в чём смысл перебрасывания, когда в std::string есть метод reserve(size_type)? Вполне аналог функций StringBuilder-а.

                                        • khim
                                          /#21141458

                                          Вы дискуссию-то читали? У std::string дорогой operator[]. Примерно вдвое дороже, чем у std::vector.

                                          Да, это 3-4 операции вместо 1-2, но это всё равно разница вдвое.

                                          Однако поскольку она мала в абсолютных величинах это не имеет смысла если вы применяете к строке «однопроходные» алгоритмы: времени на копирование туда и обратно будет потрачено столько, что операции сразу с std::string будут быстрее.

                                          А вот если у вас алгоритм O(N?)… или даже если вы просто делаете 10 проходов при обработке вашей строки… это может иметь смысл.

                                          • technic93
                                            /#21141660

                                            Это из за small-string-optimization лишние операции?
                                            Ну а если string_view. тогда должен быть просто char* + size_t, и не надо делать проверку где лежат данные.

                                    • PyerK
                                      /#21142804

                                      Ну что ж, std::string не подходит для строк.

                                      недавно ктото заявил что std::stream не подходит для юникода.
                                      Вообще за 5 лет универа и 10 лет работы, всё еще понимаю что ничего не понимаю про строки (а ещё про даты и плавающую запятую, а ещё и про файловые системы) и чем дальше, тем больше накапливается разного непонимания.
                                      Особенно те, где! американские_символы. Нам раньше каждую неделю присылали какой то иероглиф в тикет, который был должен отрисовываться как то не так. Например не справаналево, а снизувверх например.

                                      Зато приятно общаться с учениками, горит огонь в глазах, и думают что уже всё знают :)

                                      • 0xd34df00d
                                        /#21142832

                                        Особенно те, где! американские_символы. Нам раньше каждую неделю присылали какой то иероглиф в тикет, который был должен отрисовываться как то не так.

                                        Не, ну я в своё время писал строки, которые адекватно поддерживают UTF-8 и умеют работать в терминах уникодовых символов (не глифов, нет, просто единичных символов, забыл, как они там на юникодовом называются) с O(1)-доступом к символу по индексу, и там как раз было предельно понятно, что std::string не подходит, но тут-то… массив байт...

                    • remzalp
                      /#21134492 / +1

                      У Вас сложность O(n) или более нелинейная? Корректность нормировки вызывает сомнения.

        • 0xd34df00d
          /#21132282 / +1

          кстати у вас в описании теста указан размер строки 20000, а в бенчах везде 15000. Это так задумано?

          Да. C++-код и хаскель-код из первой «части» писался мной, и так как я работал над всего двумя языками, мне было не лень гонять их на чуть больших данных. Для остальных языков это куда больнее, особенно когда они работают в 100-300 раз дольше этих двух версий.


          Так как сложность алгоритма — O(mn), т. е. квадратичная для строк одинаковой длины, можно просто умножить ваш результат на соотношение длин строк (т. е. на (4/3)?).


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

          • batyrmastyr
            /#21140106

            Простите, но на кой чёрт вообще сдалась эта нормировка? Почему во всех языках не запускать тест на одинаковом числе символов?

            • khim
              /#21141618 / +3

              Официальный ответ тут… но как по мне — это очень хороший способо отловить «разоблачителей», которых не волнует ничего, кроме обсирания «неправильной», как им кажется, точки зрения.

              Очень хорошо получилось и прекрасно показало что публика на Хабре вовсе не так продвинута, как она сама о себе думает…

              • 0xd34df00d
                /#21142610 / +1

                Очень хорошо получилось и прекрасно показало что публика на Хабре вовсе не так продвинута, как она сама о себе думает…

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


                Надо как-нибудь при случае проверить, что чем громче и с большим количеством обвинений вбрасывать какой-то тезис, при этом минимизируя конкретику и проверяемые цифры/эксперименты, тем лучше он будет воспринят.

                • khim
                  /#21142744

                  Пресловутый «король» это уже проверил — не воспринимают.

                  Ну то есть после громких криков даже его редкие разумные комментарии минусуют.

                  Наверное нужно что-то ещё.

        • dimaaan
          /#21132766 / +1

          Ну и для красоты, замените


          var temp = v0;
          v0 = v1;
          v1 = temp;

          на


          (v0, v1) = (v1, v0);

          Чем мы хуже гошников, в конце-то концов? :)

          • XRevan86
            /#21132778 / -1

            Чем мы хуже гошников, в конце-то концов? :)

            Таки тем, что это C#7 без особой на то причины (а там замер с Mono 5).

            • dimaaan
              /#21132798

              Но таблице указано Mono 6.6.0 и кортежи есть в 7ой версии

              • XRevan86
                /#21132838

                Но таблице указано Mono 6.6.0

                А, и правда.

        • byme
          /#21133108 / +2

          Эта верия работает еще быстрее
          using System;
          using System.Diagnostics;
          using System.Linq;
          using System.Text;
          
          public class Program
          {
              public static Int32 LevDist(string s1, string s2)
              {
                  if (s1.Length == 0)
                  {
                      return s2.Length;
                  }
                  else if (s2.Length == 0)
                  {
                      return s1.Length;
                  }
          
                  var v0 = new int[s2.Length + 1];
                  var v1 = new int[s2.Length + 1];
                  for (int i = 0; i < v0.Length; i++)
                  {
                      v0[i] = v1[0] = i;
                  }
          
                  for (var i = 0; i < s1.Length; i++)
                  {
                      v1[0] = i + 1;
          
                      for (var j = 0; j < s2.Length; j++)
                      {
                          var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
                          var delCost = v0[j + 1] + 1;
                          var insCost = v1[j] + 1;
          
                          v1[j + 1] = Math.Min(substCost, delCost);
                          if (insCost < v1[j + 1])
                          {
                              v1[j + 1] = insCost;
                          }
                      }
          
                      (v0, v1) = (v1, v0);
                  }
          
                  return v0[s2.Length];
              }
          
              public static void Main()
              {
                  string s1 = new String('a', 15000);
                  string s2 = s1;
                  string s3 = new String('b', 15000);
          
                  for (var i = 0; i < 5; i++)
                  {
                      Stopwatch execTimer = new Stopwatch();
                      execTimer.Start();
          
                      Console.WriteLine(LevDist(s1, s2));
                      Console.WriteLine(LevDist(s1, s3));
          
                      execTimer.Stop();
                      double execTime = execTimer.ElapsedMilliseconds / 1000.0;
          
                      Console.WriteLine($"Finished in {execTime.ToString():0.000}s");
                  }
              }
          }
          

          • 0xd34df00d
            /#21134496

            Что-то все эти изменения к mono (на которой я могу проверить) не очень дружественны. Эта версия выполняется ещё медленнее — 3.189 с минимальное время.

            • hc4
              /#21134542 / +10

              Честно говоря не очень ясно, кому сегодня нужен чистый Mono, когда есть .Net Core. Учитывая что MS купили Xamarin вместе с Mono и частично используют его в Core.

              • khim
                /#21136028 / -3

                А кому вообще нужен чистый C# без Windows? В каком-нибудь Unity уже .Net Core или всё ещё Mono?

                Пока там Mono — сказать, что Mono никому не нужен таки нельзя…

                • hc4
                  /#21136050 / +1

                  .Net Core вполне себе кросс-платформенный.
                  И есть даже возможность компиляции нативных бинарников (например CoreRT).
                  Mono разве что в Unitiy, и то со временем думаю перейдут на Core.

                  • khim
                    /#21136670

                    Ну вот когда перейдут — тогда, я думаю, и автор про Mono забудет…

                    • Kobalt_x
                      /#21136900

                      Unity скажем так далеко не самый flagship проект в мире .Net

                      • byme
                        /#21137008

                        Половина(если не больше) топ игор в appstore и google play написаных на Unity. Разные красивые AR демки от Google и Apple сразуже имеют поддержку Unity или вообще написаны на ей. Все это так, фигня.

                        • Kobalt_x
                          /#21137414 / +1

                          Конечно нет.
                          Просто, имхо, количестов C# кода в играх на unity(там логику можно писать не только на C#) мне кажется меньшим чем той же охапки бизнесс-логики написанных для ASP
                          Как минимум я считаю что он скорее приближаетсяпо сложности ASP.NET сейчас.
                          Да, возможно это просто моё субъективное восприятие, а реальное положение дел иное.

                          • Aldrog
                            /#21137754

                            Разве ASP ещё не перенесли на .NET Core?

                            • byme
                              /#21137934

                              Есть AspNet Core, но он не совместим с обычным AspNet. Много старого легаси осталось фреймворке. Все новое уже на core.

            • byme
              /#21135142

              Ну не вижу ничего особенного. Цель моно была быть максимально совместимым с .Net framework. Там даже некоторые баги пришлось копировать, чтобы ничего не сломать. .Net Core же сделан с «нуля» без груза обратной совместимости.

              Еще немного оптимизаций. Вынес вывод в консоль из замеров. Стало работать за 0.54-0.53. ТОже самое для rust стало 0.47-0.48
              using System;
              using System.Diagnostics;
              using System.Linq;
              using System.Text;
              
              public class Program
              {
                  public static Int32 LevDist(string s1, string s2)
                  {
                      if (s1.Length == 0)
                      {
                          return s2.Length;
                      }
                      else if (s2.Length == 0)
                      {
                          return s1.Length;
                      }
              
                      var v0 = new int[s2.Length + 1];
                      var v1 = new int[s2.Length + 1];
                      for (int i = 0; i < v0.Length; i++)
                      {
                          v0[i] = v1[0] = i;
                      }
              
                      for (var i = 0; i < s1.Length; i++)
                      {
                          v1[0] = i + 1;
              
                          for (var j = 0; j < s2.Length; j++)
                          {
                              var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
                              var delCost = v0[j + 1] + 1;
                              var insCost = v1[j] + 1;
              
                              v1[j + 1] = Math.Min(Math.Min(substCost, delCost), insCost);
                          }
              
                          (v0, v1) = (v1, v0);
                      }
              
                      return v0[s2.Length];
                  }
              
                  public static void Main()
                  {
                      string s1 = new String('a', 15000);
                      string s2 = s1;
                      string s3 = new String('b', 15000);
              
                      for (var i = 0; i < 5; i++)
                      {
                          Stopwatch execTimer = new Stopwatch();
                          execTimer.Start();
              
                          var levDist1 = LevDist(s1, s2);
                          var levDist2 = LevDist(s1, s3);
              
                          execTimer.Stop();
                          
                          Console.WriteLine(levDist1);
                          Console.WriteLine(levDist2);
                          double execTime = execTimer.ElapsedMilliseconds / 1000.0;
              
                          Console.WriteLine($"Finished in {execTime.ToString():0.000}s");
                      }
                  }
              }
              

        • 0xd34df00d
          /#21134490

          У меня на mono 6.6.0 стало чуть медленнее: 3.052 с против предыдущих 2.967 с.

      • fixer_m
        /#21133508 / +1

        C# версия из статьи на Core 3.1 у меня отрабатывает за 760 ms (Core i7 7700k).
        С небольшими оптимизациями — 560 ms: image

        Код для BenchmarkDotNet
        public class LevensteinDistance
        {
            [Params(15_000, 20_000)]
            public int Size;
        
            private string _s1;
            private string _s2;
            private string _s3;
        
            [GlobalSetup]
            public void Setup()
            {
                _s1 = new string('a', Size);
                _s2 = new string('a', Size);
                _s3 = new string('b', Size);
            }
        
            [Benchmark(Baseline = true)]
            public int Levenstein_Orig()
            {
                return LevDist_Orig(_s1, _s2) + LevDist_Orig(_s1, _s3);
            }
        
            public int LevDist_Orig(string s1, string s2)
            {
                var ca1 = Encoding.UTF8.GetBytes(s1);
                var ca2 = Encoding.UTF8.GetBytes(s2);
        
                return LevDist_Orig(ca1, ca2);
            }
        
            public int LevDist_Orig(byte[] s1, byte[] s2)
            {
                var m = s1.Length;
                var n = s2.Length;
        
                // Edge cases.
                if (m == 0)
                {
                    return n;
                }
                else if (n == 0)
                {
                    return m;
                }
        
                Int32[] v0 = Enumerable.Range(0, n + 1).ToArray();
                var v1 = new Int32[n + 1];
        
                v0.CopyTo(v1, 0);
        
                for (var i = 0; i < m; ++i)
                {
                    v1[0] = i + 1;
        
                    for (var j = 0; j < n; ++j)
                    {
                        var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
                        var delCost = v0[j + 1] + 1;
                        var insCost = v1[j] + 1;
        
                        v1[j + 1] = Math.Min(substCost, delCost);
                        if (insCost < v1[j + 1])
                        {
                            v1[j + 1] = insCost;
                        }
                    }
        
                    var temp = v0;
                    v0 = v1;
                    v1 = temp;
                }
        
                return v0[n];
            }
        
            [Benchmark]
            public int Levenstein_Opt()
            {
                return LevDist_Opt(_s1, _s2) + LevDist_Opt(_s1, _s3);
            }
        
            public int LevDist_Opt(string s1, string s2)
            {
                if (s1.Length == 0)
                {
                    return s2.Length;
                }
                else if (s2.Length == 0)
                {
                    return s1.Length;
                }
        
                var v0 = Enumerable.Range(0, Size + 1).ToArray();
                var v1 = new int[Size + 1];
                v0.CopyTo(v1, 0);
        
                for (var i = 0; i < s1.Length; i++)
                {
                    v1[0] = i + 1;
        
                    for (var j = 0; j < s2.Length; j++)
                    {
                        var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
                        var delCost = v0[j + 1] + 1;
                        var insCost = v1[j] + 1;
        
                        v1[j + 1] = Math.Min(Math.Min(substCost, delCost), insCost);
                    }
        
                    (v0, v1) = (v1, v0);
                }
        
                return v0[s2.Length];
            }
        }
        

        • KvanTTT
          /#21134042 / +2

          Только не используйте Range в высокопроизводительном коде:


          var v0 = Enumerable.Range(0, Size + 1).ToArray();

          Попробуем сравнить версию с Range и обычным циклом с спомощью SharpLab. Вызов Range никак не инлайнится в релизе, поэтому лезем за ним в документацию на referencesource, копируем код, избавляемся от мусора и получаем такое. Как видим, метод крайне не оптимален: используется yield внутри, который генерирует кучу лишнего кода для такой простой операции, как инициализация массива последовательными значениями.

          • fixer_m
            /#21136058 / +2

            Вы смотрите на исходники .NET Framework. Исходники .NET Core вот тут: source.dot.net.
            Дело в том, что метод в Enumerable.Range в Core оптимизирован так, что работает в ~10 раз быстрее, чем в Framework и по времени выполнения почти не отличается от ручного заполнения массива через цикл.

            Мои тесты:
            image

            Код
            [Params(15_000)]
            public int Size;
            
            [Benchmark]
            public int Range()
            {
                int[] arr = Enumerable.Range(0, Size + 1).ToArray();
                return arr[0];
            }
            
            [Benchmark]
            public int Loop()
            {
                var arr = new int[Size + 1];
            
                for (var i = 0; i < Size; i++)
                    arr[i] = i;
            
                return arr[0];
            }

            • KvanTTT
              /#21136124

              Хм, действительно, я залез не в особо актуальную версию) Все равно взял себе за правило не использовать yield в высокопроизводительном коде, т.к. встречал как минимум одно место, где из-за него проседала производительность.

              • hc4
                /#21136274 / +2

                yield можно использовать в любом коде, главное учитывать его оверхед.
                Если вычислительная сложность задачи между yield'ами высокая, то влияние самого yield'а будет ничтожным.

      • eduard_matveev
        /#21137072

        В тестах С# string, в java и других byte[], не справедливо

        C# unsafe
        using System;
        using System.Diagnostics;
        using System.Runtime.CompilerServices;
        using System.Runtime.InteropServices;
        
        public class Program
        {
            [MethodImpl(MethodImplOptions.AggressiveOptimization)]
            public static unsafe Int32 LevDist(char[] s1, char[] s2)
            {
                var m = s1.Length;
                var n = s2.Length;
        
                // Edge cases.
                if (m == 0)
                    return n;
                if (n == 0)
                    return m;
                var n1 = n + 1;
                var v0Ptr = Marshal.AllocHGlobal(n1 * sizeof(int));
                var v1Ptr = Marshal.AllocHGlobal(n1 * sizeof(int));
                var v0 = (int*) v0Ptr;
                var v1 = (int*) v1Ptr;
                for (var i = 0; i < n1; i++)
                {
                    v0[i] = i;
                    v1[i] = i;
                }
        
                for (var i = 0; i < m; ++i)
                {
                    v1[0] = i + 1;
                    for (var j = 0; j < n; ++j)
                    {
                        var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
                        var delCost = v0[j + 1] + 1;
                        var insCost = v1[j] + 1;
        
                        v1[j + 1] = Math.Min(Math.Min(substCost, delCost), insCost);
                    }
        
                    var temp = v0;
                    v0 = v1;
                    v1 = temp;
                }
        
                var result = v0[n];
                Marshal.FreeHGlobal(v0Ptr);
                Marshal.FreeHGlobal(v1Ptr);
                return result;
            }
        
            public static void Main()
            {
                var s1 = new char[15000];
                for (var i = 0; i < s1.Length; i++)
                    s1[i] = 'a';
                var s2 = s1;
                var s3 = new char[15000];
                for (var i = 0; i < s3.Length; i++)
                    s3[i] = 'b';
                for (var i = 0; i < 5; ++i)
                {
                    var execTimer = new Stopwatch();
                    execTimer.Start();
        
                    Console.WriteLine(LevDist(s1, s2));
                    Console.WriteLine(LevDist(s1, s3));
        
                    execTimer.Stop();
                    Console.WriteLine($"Finished 2 in {(execTimer.ElapsedMilliseconds / 1000.0):0.000}s");
                }
            }
        }

    • byme
      /#21131660

      Кроме того C# используют безопасное обращение к массиву.

      Его можно обойти, если использовать контрукцию вида:
      for (var i = 0; i < array.Length; i++)
      {
          var item = array[i];
      }
      

      Копиляров в состоянии понять что i ограничено по array.Length и переполнения быть не может.

      • hc4
        /#21131712 / +1

        Реально работает.
        В моём случае оригинальная версия работает 0,84с, версия с a.Length работает 0,68с, а unsafe версия работает 0.63с.
        Я и не думал об этом, хотя всегда использую именно a.Length, но не для скорости, а чтоб не накосячить.

      • DistortNeo
        /#21138088

        Самое удивительное, что раньше, когда компьютеры были большими, наоборот, учили сохранять длину во временную переменную перед циклом.

    • impwx
      /#21132184 / +4

      Немного улучшенная версия на C#
      public static Int32 LevDist(string s1, string s2)
      {
      	return LevDist(s1.ToCharArray(), s2.ToCharArray());
      }
      
      public static Int32 LevDist(char[] s1, char[] s2)
      {
      	var m = s1.Length;
      	var n = s2.Length;
      
      	// Edge cases.
      	if (m == 0)
      	{
      		return n;
      	}
      	else if (n == 0)
      	{
      		return m;
      	}
      
      	var v0 = new int[n+1];
      	var v1 = new int[n+1];
      	for(var i = 0; i < n; i++)
      		v0[i] = v1[i] = i;
      
      	for (var i = 0; i < m; i++)
      	{
      		v1[0] = i + 1;
      
      		for (var j = 0; j < n; j++)
      		{
      			var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
      			var delCost = v0[j + 1] + 1;
      			var insCost = v1[j] + 1;
      
      			v1[j + 1] = Math.Min(Math.Min(substCost, delCost), insCost);
      		}
      
      		var temp = v0;
      		v0 = v1;
      		v1 = temp;
      	}
      
      	return v0[n];
      }
      
      public static void Main()
      {
      	string s1 = new String('a', 15000);
      	string s2 = s1;
      	string s3 = new String('b', 15000);
      
      	Stopwatch execTimer = new Stopwatch();
      	execTimer.Start();
      
      	Console.WriteLine(LevDist(s1, s2));
      	Console.WriteLine(LevDist(s1, s3));
      
      	execTimer.Stop();
      	double execTime = execTimer.ElapsedMilliseconds / 1000.0;
      
      	Console.WriteLine($"Finished in {execTime:0.000}s");
      }
      

      • ac-93
        /#21134046

        На удивление, использование ReadOnlySpan дает худшие результаты по сравнению с копированием массива в char[].


        Не могли бы показать вариант с ReadOnlySpan? Интересно посмотреть почему так происходит, какая версия .Net Core?

        • impwx
          /#21135000

          Да все то же самое, только вместо .ToCharArray() используется .AsSpan(). Использую последний LINQPad 6, в нем .NET Core 3.1.

      • Politura
        /#21134976

        А зачем вообще строки в массив копировать? Судя по коду, никакие изменения в s1 и s2 не делаются, а читать символы по индексу можно прямо у строки.

        Просто засунуть тело функции LevDist(char[] s1, char[] s2) в LevDist(string s1, string s2) и все будет работать еще быстрее.

        • impwx
          /#21135004

          Так тоже можно, но никакого прироста скорости не дает. Полагаю, дело в том, что индексация массива оптимизирована лучше, чем индексация строки.

          • Politura
            /#21135148

            Посмотрел внимательнее: там в бенчмарке всего два раза вызывается LevDist так что это копирование просто копейки на фоне остальной работы. Наверное во время реальной работы, когда вызовов LevDist будут тысячи, влияние будет уже другое.

            • 0xd34df00d
              /#21137078 / +1

              Относительное влияние останется тем же самым, так как тело-то тоже будет выполняться тысячи раз.

              • Politura
                /#21138248

                Часто приходится встречать строчки длинной в тысячи символов?

                • 0xd34df00d
                  /#21138254 / +1

                  Нет, чаще — в десятки тысяч символов. Я эту ерунду на исходный код натравливаю.

                  • Politura
                    /#21139086 / -1

                    Исходный код в десятки тысяч символов? Это обфусцированный какой-то?
                    Знаю про древний стандарт в 80 символов, у редакторов даже подсветка раньше была, когда выходишь дальше.
                    Интересно было-бы найти статистику гитхаба, сколько там средняя длинна строки в исходниках.

                    Впрочем, не особо важно. Если подумать, копирование в массивы в данном случае будет не дольше чем заполнение двух массивов int дальше по коду и уж явно сильно быстрее, чем вложенный цикл m*n. Так что на производительность слабо влияет. Просто в нем нет никакого смысла, почему-бы и не убрать.

                    • 0xd34df00d
                      /#21139090 / +1

                      Там строка — это весь файл целиком, без разбития по привычным человеку строкам по \n.

                      • Politura
                        /#21139140

                        Все, понял. Интересно, что за задачка. Может проще было-бы делать какой-нибудь обычный diff, а это расстояние считать только для тех строк, которые различаются по диффу.
                        А то квадратичная сложность от длинны файла как-то совсем не очень, как-бы сильно не было все соптимизированно.

                        • 0xd34df00d
                          /#21139166 / +1

                          Пытаюсь по имеющейся кодовой базе подобрать стиль для автоформаттера. Я про это тоже скоро напишу (сегодня вот начал писать статью).


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

              • PsyHaSTe
                /#21138406

                Ну не знаю, лично у меня замена в сишарпе Enumerable.Range на ручной цикл дала порядка 10% прироста производительности.

                • 0xd34df00d
                  /#21138514

                  Ну, код я не проверял, слишком уж не знаю C# для этого. Это я скорее про расходы от копирования говорил (предположительно от копирования один раз в начале работы функции).

      • unsafePtr
        /#21135794

        impwx Span это же всеже больше про память. Здесь есть небольшие бенчмарки, где спаны немного уступают по скорости массивам
        adamsitnik.com/Span/#span-vs-array

      • euroUK
        /#21136090 / +1

        Еще раз убеждаемся, что люди, не работающие с языками не должны даже пытаться проводить какие-либо бенчмарки.

        А когда взял кто-то, кто видит C# не в первый раз, то и вуаля — Java уже медленее.

        • PsyHaSTe
          /#21138418

          А что в том коде на сишарпе не так? Ну да, пара моментов неоптимально написана (типа кэширования m и n), но в остльном нормальный такой код.


          Как челоек получил 5.6с для меня — загадка. У меня код выше отрабатывает примерно за 0.63 секунды, чуть-чуть быстрее чем оригинальный.

          • 0xd34df00d
            /#21138518

            Запустите код со строками в 20 тыщ символов.


            Ну и, может, там прогревать надо или ещё что как-то особо. numba питоновая вон в первый запуск тоже раза в полтора-два медленнее у меня.

            • PsyHaSTe
              /#21138578

              Сори, тупанул.


              С 20к символов у меня сишарп выдает 1.18с. Раст — 0.8с.
              На .net 472 — 0.935c. Это объясняется тем, что в неткоре джит делает ставку на быстрый запуск и хуже оптимизирует. Недавно ввели tieredJIT которы до старого уровня иногда догоняет во время работы, когда какой-то код горячим получается, но очевидно на задачке выполняемой секунду он не успевает ничего сделать.

              • 0xd34df00d
                /#21138616

                В статье код для 15 тыщ, но результаты как для 20 (путаница, да, сорян).

    • DistortNeo
      /#21133588 / +2

      У меня получилось так:
      NET Core 3.1 — 0.9 s
      NET Framework 4.7.2 — 1.2 s
      Mono 6.6.0 — 1.8 s

  3. Boctopr
    /#21131714 / +1

    Просто кто-то программировать не умеет, меняем:

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

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

    и о чудо, не нужно список(вектор) из трех переменных инициализировать (выделять память) и удалять ее. На моей машине ускорение в 3 раза.
    P. S. Ох уж эти истории про медленный C и C++

    • 0xd34df00d
      /#21131724 / -4

      А там и не выделяется ничего — initializer_list должен разворачиваться в компилтайме, это таки не лист и не вектор. И да, в одном из заключений про это написано.


      А ещё производительность зависит от того, в каком порядке вы выполняете сравнения.

      • Boctopr
        /#21131734 / +1

        Так ты не болаболь а проверь, теоретик

        • 0xd34df00d
          /#21131750 / -2

          И про это в заключении тоже написано. Вот, процитирую себя же на всякий:


          При некоторых из этих порядков мне таки удалось воспроизвести ускорение в случае C++. Так, если вместо std::min({ delCost, insCost, substCost }) написать std::min(substCost, std::min(delCost, insCost)), то время работы под gcc увеличивается до 1.440 секунд, а под clang — уменьшается до 0.840 секунд (ура, быстрее всех остальных вариантов и почти хаскель). Похоже, clang не любит initializer lists и не может их заинлайнить, а gcc шедулит операции и регистры так, что, по крайней мере, на этих конкретных данных результат проигрывает.
          Но ещё раз отмечу, что оптимизацией порядка в случае хаскеля я не занимался, и заниматься этим в рамках этого бенчмарка не рекомендую в любом языке.
          Кроме того, это значит, что нельзя рассчитывать на компилятор даже в таком языке, как C++, где в компиляторы влиты десятки тысяч человеколет.

          • khim
            /#21131802

            Вы тут пришите про порядок, а проблема вот нифига не в нём — проблема в обращения в использовании initializer_list и, соотвественно, «недооптимизированных» обращениях в память.

            • 0xd34df00d
              /#21131856

              Это проблема QoI.


              И gcc тому же с ручной развёрткой становится хуже, а не лучше.

              • khim
                /#21131916

                И gcc тому же с ручной развёрткой становится хуже, а не лучше.
                Пожимает плечами. Это уже совсем другая история.

                GCC, в последнее время, очень сильно сдал. Google оттуда всех разработчиков снял и куча народу из «академиев» тоже на Clang переключились.

                Кое-где, иногда, он ещё может «показть класс» (всё-таки в него много тысяч человеко-лет вбухано тоже), но объективно — он таки от Clang отстаёт.

                • DaylightIsBurning
                  /#21138132

                  А что за история с гуглом и GCC?

                  • khim
                    /#21138244

                    Никакой особенной истории — просто если раньше Google компилировал все свои сервера GCC, то сейчас произошла консолидация и используется Clang/LLVM везде, где возможно.

                    Как несложно догадаться раньше Google содержал сколько-то контрибуторов в GCC, сейчас — часть переключилась на Clang, часть уволилась…

      • khim
        /#21131788

        А там и не выделяется ничего — initializer_list должен разворачиваться в компилтайме, это таки не лист и не вектор.
        initializer_list — это, увы, именно-таки массив. И обрабатывается как массив и косяки у него, как при работе с массивом.

        И да — из-за проблем с алиасингом подобные вещи компилятору «тяжело» обрабатывать. Я внизу приводил вообще патологический пример.

        Это одно из мест, где разработчики языка придумали очередную подлянку, которую должны уметь «изводить» разработчики компиляторов — а они, увы, не всегда справляются.

        • 0xd34df00d
          /#21131842

          initializer_list — это, увы, именно-таки массив

          Но не вектор. Динамических аллокаций там нет (то есть, компилятор, наверное, имеет право реализовывать их с аллокациями, но зачем ненавидеть своих пользователей?).


          Кроме того, предельный случай без всех этих листов и шаблонных minов тоже приведен — это вариант на С. И он не оказывается существенно быстрее.

          • khim
            /#21131894

            Динамических аллокаций там нет (то есть, компилятор, наверное, имеет право реализовывать их с аллокациями, но зачем ненавидеть своих пользователей?).
            Динамических аллокаций нет, а проблемы алиасинга — есть.

            Для оптимизации C++ они — вообще больное место.

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

            Автовекторизация в C++ сейчас — это скорее игрушки (типа inline в прошлом веке) — мы вообще пока не в курсе чего там можно автоматически сделать. Обрабатываются только кой-какие самые очевидные циклы.

            • 0xd34df00d
              /#21131942

              Динамических аллокаций нет, а проблемы алиасинга — есть.

              Именно! Значит, по крайней мере, писать идиоматичный код надо с оглядкой на ассемблер. Ну, как вы и говорите.


              И, значит, идиоматичный код почти наверное не будет в топе производительности, хотя казалось бы — zero-overhead abstractions и прочие красивые слова.


              Впрочем, ваши ссылки ниже я ещё не смотрел внимательно — с мобильника по пути на работу это не очень, чуть позже гляну.


              А что-нибудь вообще — оказывается «существенно быстрее»? Не так, что вы, в версии на C (и исправленной версии на C++) уже добрались до пределов того, что можно сделать без векторизации?

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

              • khim
                /#21132394

                И, значит, идиоматичный код почти наверное не будет в топе производительности, хотя казалось бы — zero-overhead abstractions и прочие красивые слова.
                Ну — слова-то красивые, а на практике — надо в ассемблер смотреть. Когда я в школе учился я вообще был большим скептиком по отношению к C++: что толку от абстракций, которые «могли бы быть zero-overhead», если на практике — там «overhead» нифига даже не «zero»?

                Сейчас компиляторы умеют уже убирать 99% этих абстракций, но иногда… вот это вот что такое? Какая абстракция и куда протекла, что компилятор вдруг решил в оптимизированном «до упора» коде оставить test cl, cl — притом, что в cl, в этот момент, будет нуль!

                Но это именно алгоритмические улучшения.
                На это вроде C++ компиляторы не пытаются замахиваться, всё-таки. Да и никакие другие промышленные (не зная что нам «на переднем крае науки, впрочем).

                • 0xd34df00d
                  /#21132454 / +2

                  Я бы удивился, если бы они хотя бы заметили, что там можно обойтись одной строкой, а не двумя.


                  Собственно, если вдруг интересно, вот этот папир с более эффективной реализацией.


                  tl;dr там два улучшения — можно сравнивать не посимвольно, а сразу 8 (или сколько байт в вашем слове) символов через хитрые наблюдения и немного препроцессинга (что теоретически даёт улучшение константы в 8 раз), плюс не обязательно смотреть на всю матрицу, а можно идти вдоль диагонали, отступая не сильно далеко от неё, особенно если вы удовлетворитесь ответом вида «расстояние больше N» для некоторого наперёд заданного N.


                  Увы, я в своей задаче понял, что расстояние Левенштейна — не лучшая метрика, и мне резко стало лень реализовывать более эффективные варианты.

                  • DaylightIsBurning
                    /#21138150

                    А какая метрика лучше в Вашей задаче?

                    • 0xd34df00d
                      /#21138190 / +1

                      Я сравниваю расстояние между исходными кодами, отформатированными согласно разным стилям. Соответственно, лучше рассматривать пару из (d1, d2), где d1 — модуль разности гистограмм непробельных символов, d2 — сколько пробельных символов надо удалить или добавить, чтобы выровнять две строки. Соответственно, сравнение тогда лексикографическое.


                      Ну или в коде.

      • Boctopr
        /#21131846 / +1

        случайно продублировал

        • 0xd34df00d
          /#21131886

          Нет, конечно. Вектор выделяет память в рантайме, массив на стеке с известным размером (какой там правильный standardese для него) — нет.

    • khim
      /#21131748

      Ну всё-таки «уважающий себя компилятор» должен такое убивать.

      P. S. Ох уж эти истории про медленный C и C++
      А они всегда про это: компилятор, вроде бы, должен лишнее удалять… но не всегда ему это удаётся. И это — после тысяч человеко-лет, в это вбуханных.

      • Boctopr
        /#21131810

        Компилятор комнды символьных строк переводить в бинарный машинный код, а то что ты говоришь должен, делать программист. Например можно с помощью бинарных операций найти минимальное число, без использования if, источник как это сделать Алгоритмические трюки для программистов [Генри С. Уоррен мл.] Hacker's Delight

        • khim
          /#21131852

          Не должен. std::initializer_list был разработан как раз для таких случаев. И его использование у 0xd34df00d — как раз вполне идеоматично.

          А что у компилятора при этом ролики за шарики заезжают — так это как раз вечная беда C++: теоретически на нём можно писать не глядя в ассемблерный выхлоп, практически — регулярно вот подобные косяки и вылезают.

          Про ваши трюки компилятор в курсе и вполне способен их применять — тут не в них дело.

        • nikbond
          /#21132026 / +7

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

    • vics001
      /#21131936

      Эх, а кто умеет?!
      Сам пишу на Java и вижу, что неправильно написать гораздо сложнее, чем упомнить и внимательно прочитать все детали конструкторов, const* указателей, ссылок и shared_ptr, а разница между ними иногда кратная. Еще и новые стандарты добавляют и добавляют синтаксического мусора…

    • technic93
      /#21133710 / +2

      Разницы нету, смотри тут https://godbolt.org/z/E5WRNT
      В более общем случае может быть разница из-за порядка сравнений когда переменные приходят из разных мест но к "выделять память" отношения не имеет.

  4. khim
    /#21131722

    Проблема с clang очень похожа вот на это. Тут вообще какой-то бардак происходит.

    Разработчики про это знают, так что, похоже, вы очень вовремя написали статью…

    • XRevan86
      /#21131948

      Clang++ даёт хорошие результаты, если использовать range-based for или если вместо std::string сравнивать прямо элементы C-массива (.c_str()).
      Не знаю, насколько это близко к описанной проблеме, но что-то явно очень медленно при использовании оператора [] у std::string.

      • khim
        /#21131988

        Не знаю, насколько это близко к описанной проблеме, но что-то явно очень медленно при использовании оператора [] у std::string.
        У std::string очень сложный operator[]. Теоретически «общую» часть компилятор должен бы вынести… но, похоже, в данном случае — не выходит.

        Может быть тоже проблемы aliasing'а легко…

        • 0xd34df00d
          /#21132056

          Про алиасинг таки интересно. Там же нигде нет записи по char* или unsigned char* — с чего бы компилятору его опасаться?

          • khim
            /#21132312 / +6

            С того, что это, блин, C/C++. Потому значение по указателю char* или unsigned char* может меняться (с точки зрения указателя) при записи в любую переменную адрес которой мог утечь куда-то.

            В результате некоторые алгоритмы могут резко усколяться если вместо char использовать что-то типа:

              struct __attribute__((packed)) FastChar {
                long long value:8;
            };

            • 0xd34df00d
              /#21132326 / +1

              Об этом я не подумал, да. Вы правы. Правда, здесь-то я пишу в локальные для функции вектора, на которые даже адрес или ссылка ни разу не берётся (если не считать локальный же std::swap), и компилятору должно бы хватить мозгов это увидеть.


              С другой стороны, LICM-вынос чтения символа из строки s1 на уровень внешнего цикла производительность (для gcc, по крайней мере) не меняет вообще никак.

              • khim
                /#21132378 / +3

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

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

                • 0xd34df00d
                  /#21132398 / +1

                  У меня в соседнем коде был шанс алиасинга, и я уже подумывал заменить std::string на std::vector<CharWrapper>, где struct CharWrapper { char ch; }; — по идее этого достаточно, чтобы алиасинга не было, потому что больше нет указателей на char. У вас там, однако, обёртка выглядит по-другому. Что я теряю от такого, более простого варианта?

                  • khim
                    /#21132824 / +2

                    Непонятно что вы вообще от такого варианта получаете. Доступ к элементу структуры может же алиаситься с доступом ко всем, с чем алиасится соответствующий тип поля структуры.

                    То есть мне было бы, в принципе, интересно увидеть пример кода, где ваш CharWrapper может хоть на что нибудь повлиять…

                    • mayorovp
                      /#21133174 / +2

                      Доступ к элементу структуры может же алиаситься с доступом ко всем, с чем алиасится соответствующий тип поля структуры.

                      ЕМНИП, в случае с char там алиасинг может быть только однонаправленный — char* может указывать на кусок int, а вот int* на char указывать не может никогда. Ну, это если я правильно понял что означает термин glvalue (придумали, блин, терминологию, и всё лишь бы не рассуждать о языке в терминах самого языка!)

                      • khim
                        /#21133404

                        ЕМНИП, в случае с char там алиасинг может быть только однонаправленный — char* может указывать на кусок int, а вот int* на char указывать не может никогда.
                        Да, но для создания проблем этого же достаточно. Если вы имеете строку — то вы работает с её содержимым через указатели, а раз так, что алиасинг, с точки зрения компилятора, возможен.

                        Тут фишка в том, что да, вы, формально, не имеете права взять указатель на CharWrapper, прератить в указатель на int — и использовать. Всё так.

                        Но если указатель на CharWrapper приходит откуда-то снаружи, то у компилятора нет никой возможности узнать — это таки настоящий CharWrapper или кусок int (см. пример ниже)… и, соответственно, ему приходится «закладываться на подставу».

                      • Antervis
                        /#21135260 / -1

                        ЕМНИП, в случае с char там алиасинг может быть только однонаправленный — char* может указывать на кусок int, а вот int* на char указывать не может никогда.
                        Либо диапазоны могут пересекаться, и тогда int* и char* потенциально указывают на одну память (алиасятся), либо не пересекаются (и мы, возможно, исходим из этого предположения). Никакой однонаправленности в алиасинге нет

                        • mayorovp
                          /#21136500

                          Но у нас нет int* и char*. У нас есть int* и char.

                          • khim
                            /#21136692

                            Дык в том месте, где про aliasing пишется речь идёт о glvalue и именно-таки о char, а не char*...

                            • mayorovp
                              /#21136698

                              Ну да, там так и написано — алиасинг разрешен, если glvalue типа char. А если объект типа char, а glvalue какого-то другого типа — то алиасинг не разрешен.

                    • 0xd34df00d
                      /#21133258

                      Я получаю отсутствие объектов типа char*. Соответственно, я не пишу по таким указателям и не читаю, а это значит, что про алиасинг, по идее, можно не думать.

                      • khim
                        /#21133470

                        Ну вот рассмотрите такой код:

                        void foo(int);
                        
                        int bar(CharWrapper* x, CharWrapper* y, int *z) {
                          foo(*z);
                          *x = {1};
                          *y = {32};
                          return *z;
                        }
                        

                        Здесь ведь никаких UB нету с вашим подходом — и компилятору придётся это учитывать. А с моим — есть… и он может немного своевольничать.

                        Можете запустить и убедиться что ваша версия выдаёт 8234, а моя — 298…

                        Потому что в вашем случае всё равно доступ к данным идёт через glvalue типа char, а моём случае — через long long. Да, это небольшой такой long long, размером в один байт… но это всё равно long long!

                        • 0xd34df00d
                          /#21133568

                          А у вас там слева разве нет UB? Ну, где вы пишете в один член юниона, а потом читаете из другого?


                          Как иначе сделать так, чтобы ссылка на char внутри структуры указывала куда-то ещё, я не знаю.

                          • khim
                            /#21133626

                            Ну, где вы пишете в один член юниона, а потом читаете из другого?
                            Нет. Ну во всяком случае так считают разработчики компиляторов. Тут всё упирается в то, что все эти автогенерённые CharWrapper() и operator= автогенерируются компилятором — но остаются законными даже если указатель на CharWrapper() был порождён из указателя на другой тип…

                            If a program attempts to access the stored value of an object through a glvalue of other than one of the following types the behavior is undefined:

                            —(11.8) a char, unsigned char, or std::byte type
                            То есть в C++ вообще никого не волнует указатель какого типа вы используете… только к объекту какого типа вы пытаетесь «достучаться».

                            Как иначе сделать так, чтобы ссылка на char внутри структуры указывала куда-то ещё, я не знаю.
                            Через reinterpret_cast самое простое.

                            • 0xd34df00d
                              /#21133666

                              Нет.

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


                              Ну и тут явно 6.7.3.1/5.


                              То есть в C++ вообще никого не волнует указатель какого типа вы используете… только к объекту какого типа вы пытаетесь «достучаться».

                              Я бы ожидал, что компилятор увидит, что я пытаюсь обратиться к char.


                              Через reinterpret_cast самое простое.

                              Но кастить вы будете к типу структуры, а он ничего не алиасит.

                              • khim
                                /#21134028

                                Ну и тут явно 6.7.3.1/5.
                                С какого перепугу? У нас по-прежнему всё время всё тот же int, с которого мы начинали… только доступ к нему — через объект типа charчто явно разрешено

                                Я бы ожидал, что компилятор увидит, что я пытаюсь обратиться к char.
                                Как он это увидит, извините? Если ему явно разрешено обращаться к объекту типа int через glvalue типа char?

                                Но кастить вы будете к типу структуры, а он ничего не алиасит.
                                Алиасит-алиасит! В том-то и дело, что алиасит. В этом-то и беда. C (а за ним и C++) так устроен.

                                То есть если вы имеете что-нибудь типа
                                struct Point {
                                  int lattitude;
                                  int longitude;
                                };
                                struct 3DPoint {
                                  int x,y,z;
                                };
                                
                                то Point и 3DPoint можно безболезненно кастить друг к другу (обращаться к z у чего-то, что было рождено как Point, конечно, нельзя). Это очень активно применяется программистами на C, потому и появляются все эти чудесные pointer interconvertible типы.

                                И, соотвественно, можно заворачивать char в «обёртки» из struct, union или std::array сколько угодно — он всё равно останется charом и ему будет разрешего алиаситься с чем угодно.

                                Это вам, извините, не Rust и не Haskell. Ушки-то от C всё равно торчат…

                                • 0xd34df00d
                                  /#21134034

                                  С какого перепугу?

                                  Потому что я зареюзил сторедж, записав в член-массив. Все, инт, как тривиальный объект тривиального типа без деструктора, сдох в этот момент, лайфтайм у него кончился.


                                  Как он это увидит, извините? Если ему явно разрешено обращаться к объекту типа int через glvalue типа char?

                                  Потому что все способы сделать так, чтобы этот char указывал не на char, нелегальны, насколько я понимаю. Ну а что компиляторы по рукам вас не бьют за игры с юнионами — вопросы к компиляторам.


                                  Алиасит-алиасит!

                                  Не согласен:


                                  то Point и 3DPoint можно безболезненно кастить друг к другу (обращаться к z у чего-то, что было рождено как Point, конечно, нельзя)

                                  На эту тему я сходу так не уверен, но к nested object, сиречь к char, можно кастить, да. Но это именно что голый чар, он не был получен как указатель на что-то, и компилятор вполне имеет право считать, что он не алиасит.


                                  Либо алиасит настолько же, насколько любой другой тип, могущий быть common subobject или как оно там называется. То есть, почти любой тип.

                                  • khim
                                    /#21134088

                                    Потому что я зареюзил сторедж, записав в член-массив.
                                    С чего вдруг? Вы модицицировали имеющееся там значение типа int используя данный вам char. Там по прежнему остался int.

                                    Вы не туда смотрите — тут мой union вообще непричём, я мог бы и reinterpret_cast сделать.

                                    Потому что все способы сделать так, чтобы этот char указывал не на char, нелегальны, насколько я понимаю.
                                    Наоборот! Почти что любой способ будет корректным! Проблемы тут в том, что структура pointer-interconvertible со своим первым членом, а указатель на char должен алиасится с любым типом (иначе вообще никак нельзя написать memcpy или memmove).

                                    Но это именно что голый чар, он не был получен как указатель на что-то, и компилятор вполне имеет право считать, что он не алиасит.
                                    Почитайте ещё раз про pointer interconvertible типы внимательно. Обратите внимание на последний случай — мы имеем возможность придумать себе объект, которого не существует, но который поможет нам перейти от одного объекта к другому через воображаемые структуры и объединения!

                                    А иначе как бы непонятно вы вообще могли использовать штуки типа offsetof.

                                    Либо алиасит настолько же, насколько любой другой тип, могущий быть common subobject или как оно там называется. То есть, почти любой тип.
                                    Вы тут мешаете в кучу два процесса:
                                    1. Возможность преобразования типов указателей на объекты.
                                    2. Возможность модификации самих объектов, на которые эти указатели указывают.

                                    Так вот первое — можно делать почти всегда. Вы можете преобразовать указатель на int в указатель на float, char, CharWrapper или вообще почти что угодно (с функциями и, особенно, указателями на члены класса есть ограничения).

                                    Однако это не значит, что вы можете, используя этот указатель, безопасно обращаться к значениям, которые там находятся!

                                    Ментальная модель такая: разные типы обрабатываются разными устройствами. Неважно — у вас там 8087 (почитайте о том, как 8087 обращается в память — это весьма нетривиально) или Weitek — в любом случае «главный» CPU может обратиться за результами тогда, когда они ещё не готовы. Синхронизация, в общем, небесплатна — и осущствляется тогда, когда вы используете указатели на char.

                                    Вот это — ментальная модель, описанная в документации на C++: возможность преобразовать один указатель в другой — не даёт вам, автоматически, права этот указатель использовать!

                                    У вас же, похоже, ментальная модель какая-то совсем другая, потому что я даже следов её не вижу! Законно ли, скажем, преобразовать указатель на int в указатель на short, а потом сдвинуть его на пару элементов? Да не вопрос! А вот можно ли потом обращаться к этому shortу? Ну… если у вас там изначально была структура из intа и shortа… то да — законно и беспроблемно. А вот если там был, изначально, массив intов… тогда нет.

                                    А вот char — он особое исключение. Он всегда может использоваться — независимо от того, с какого типа вы изначально начали и, что важно, тип результата тоже может быть каким угодно. Через него можно прямо добраться до байтов из которых состоит объект — без ограничений (и да, в стандарте есть места, где он говорит о «байтах из которых состоит объект»).

                                    Да, во многих других языках типы — куда более «серьёзная» конструкция (не только Haskell, но даже и Pascal какой-нибудь). А в C++ — это тооооненькая-тооооненькая прослоечка над байтами.

                                    А ограничения алиасинга, которые используют компиляторщики — они изначально для совсем-совсем другого был придуманы… Условно — для связки 8086+8087 (и других подобных).

                                    Такие дела…

                                    • 0xd34df00d
                                      /#21134150

                                      С чего вдруг? Вы модицицировали имеющееся там значение типа int используя данный вам char. Там по прежнему остался int.

                                      Записав в другой объект с тем же стореджем.


                                      Вы не туда смотрите — тут мой union вообще непричём, я мог бы и reinterpret_cast сделать.

                                      К чему, к char*?


                                      Почитайте ещё раз про pointer interconvertible типы внимательно. Обратите внимание на последний случай — мы имеем возможность придумать себе объект, которого не существует, но который поможет нам перейти от одного объекта к другому через воображаемые структуры и объединения!

                                      Да, это значит, что вы можете привести указатель на CharWrapper к указателю на char.


                                      Но это не значит, что glvalue, соответствующая CharWrapper'овскому char, может указывать на произвольный объект. Вы же её можете получить только от этого CharWrapper!


                                      А иначе как бы непонятно вы вообще могли использовать штуки типа offsetof.

                                      А я их не использую Что там компилятор делает и какую магию в своей нутрянке он предоставляет — не моё дело. Это его магия, семантика которой ему известна.


                                      Ментальная модель такая: разные типы обрабатываются разными устройствами.

                                      Моя ментальная модель предельно проста — для работы с объектом я могу использовать только указатель на него либо указатель на char/uchar/std::byte. Всё.


                                      Законно ли, скажем, преобразовать указатель на int в указатель на short, а потом сдвинуть его на пару элементов?

                                      Да, конечно.


                                      Ну… если у вас там изначально была структура из intа и shortа… то да — законно и беспроблемно.

                                      Не уверен. А вдруг у вас там компилятор паддинг вставит?


                                      Более того, не уверен даже в случаях отсутствия паддинга (и с кем-то про это несколько лет назад даже спорил, но лень и на эту тему по стандарту бегать).


                                      Но в любом случае это всё неважно. Да, если у вас есть указатель на CharWrapper, то вы можете из него сделать указатель на char. Но что это ломает? Вы, в конце концов, из любого объекта можете сделать указатель на char.


                                      Вопрос в другом: можете ли вы сделать указатель на CharWrapper из указателя на char, который изначально не указывал на CharWrapper или на char? Я утверждаю, что нет, поэтому алиасинга быть не может.


                                      Есть дыра, связанная с тем, что CharWrapper является pointer-interconvertible c любым другим типом, имеющим char первым членом, но это выполняется и для предложенного вами типа.

                                      • khim
                                        /#21134212

                                        Записав в другой объект с тем же стореджем.
                                        Ну уж нет. Читаем:
                                        In simple assignment (=), the object referred to by the left operand is modified ([defns.access]) by replacing its value with the result of the right operand.

                                        Простое присваивание не создаёт нового объекта — оно модифицирует существующий.

                                        Отсюда, собственно, вся разница между конструктором и оператором присваивания.

                                        Вы не туда смотрите — тут мой union вообще непричём, я мог бы и reinterpret_cast сделать.
                                        К чему, к char*?
                                        К char*, double*, CharWrapper*… да вообще указатель на один тип можно в указатель на почти любой другой тип в C++ безопасно кастить через reinterepret_cast. Вот использовать полученный указатель — да, можно только с ограничениями…

                                        Да, это значит, что вы можете привести указатель на CharWrapper к указателю на char.

                                        Но это не значит, что glvalue, соответствующая CharWrapper'овскому char, может указывать на произвольный объект. Вы же её можете получить только от этого CharWrapper!
                                        Почему это? Я могу стартовать с указтеля на целое число, пробразовать его в указатель на char (нет ограничений), могу его потом и подвигать (кто запретит?), потом преобразовать в CharWrapper*.

                                        Нигде на этом пути никаких запретов нет…

                                        А я их не использую Что там компилятор делает и какую магию в своей нутрянке он предоставляет — не моё дело. Это его магия, семантика которой ему известна.
                                        Причём тут «нутрянка»? Если у вас standard-layout-тип то вы имеете в вашей программе всеми этими удобствами пользоваться безусловно… а начиная с C++17 — разработчики компилятора могуть разрешить вам пользоваться всеми этими чудесами и в других случаях (но не обязаны).

                                        Впрочем вам CharWrapper — он, конечно, standard-layout… что сразу закрывает тему.

                                        Для того, чтобы написать offsetof — нужна магия, выходящая за рамки стандарта, да… но чтобы использовать — магии не нужно… а с вашим подходом она таки была бы нужна.

                                        Моя ментальная модель предельно проста — для работы с объектом я могу использовать только указатель на него либо указатель на char/uchar/std::byte. Всё.
                                        Это отличная ментальная модель, но разрабочики компилятров должны поддерживать не только такие вещи, а всё, что разрешает стандарт… а разрешает он весьма много чего…

                                        Не уверен. А вдруг у вас там компилятор паддинг вставит?
                                        Дык и размером int может оказаться не в два shortа. Для проверки подобных вещей как раз offsetof и sizeof и нужны.

                                        Вопрос в другом: можете ли вы сделать указатель на CharWrapper из указателя на char, который изначально не указывал на CharWrapper или на char? Я утверждаю, что нет, поэтому алиасинга быть не может.
                                        На основании чего вы это утверждаете? Кто вам это запретит? В каком именно месте возникнет UB? Pointer-interconvertible типы потому так и называются, что их можно конвертировать в любом направлении…

                                        Есть дыра, связанная с тем, что CharWrapper является pointer-interconvertible c любым другим типом, имеющим char первым членом, но это выполняется и для предложенного вами типа.
                                        Разумеется! Разница-то не в этом! Разница в том, что в моём типе никаких charов нету. Там long long. Небольшой такой, однобайтовый. Он не может ни с чем алиаситься.

                                        Кстати я тут подумал и понял, что перемудрил. Ибо никакого «небольшого» long long, конечно не нужно. Достаточно небольшого однобайтового char… потому что у битовых полей же нельзя взять адрес — то есть тип битового поля не совпадает с объявленным типом этого поля… это отдельный тип… хотя выглядит, конечно, как «масло масляное»… но работает… но сносит крышу ICC… прекрасно, просто прекрасно…

                                        Люблю C++: где ещё можно выстрелить себе в ногу столькими разными способами?

                                        • 0xd34df00d
                                          /#21134228

                                          Простое присваивание не создаёт нового объекта — оно модифицирует существующий.

                                          У юнионов создаёт. То есть, там написано не совсем это, и вы теоретически могли бы взять указатель на этот член (как вы и делаете), скастануть в char и что-то туда присвоить, но я, опять же, не уверен, что это легально. Получается какой-то уж больно очевидный хак и дыра.


                                          Вот использовать полученный указатель — да, можно только с ограничениями…

                                          Естественно, и мы же обсуждаем вопрос использования.


                                          Я могу стартовать с указтеля на целое число, пробразовать его в указатель на char (нет ограничений), могут его потом подвигать (кто запретит?), потом преобразовать в CharWrapper*.

                                          Прекрасно. И где у вас здесь возник алиасинг? Откуда у вас возможность через указатель на CharWrapper писать куда-то ещё?


                                          На основании чего вы это утверждаете? Кто вам это запретит?

                                          Если быть совсем формальным (один фиг не агду ковыряю), то сделать указатель можете. Разыменовать вы его потом не можете.


                                          В каком именно месте возникнет UB?

                                          В том, где вы попытаетесь работать с объектом с типом, отличающимся от CharWrapper, через указатель на CharWrapper.


                                          То есть, конечно, вы его можете преобразовать обратно в char* и творить стандартную вакханалию, но вы её будете творить через указатель на char*. Нет указателя на char* — нет проблем, а я в сухости и безопасности.


                                          Кстати я тут подумал и понял, что я перемудрил. Ибо никакого «небольшого» long long, конечно не нужно. Достаточно небольшого однобайтового char… потому что у битовых полей же нельзя взять адрес — то есть тип битового поля не совпадает с объявленным типом этого поля… это отдельный тип…

                                          Я битовые поля не люблю, enum class meh : char в рамках вашего подхода хватит? Или даже signed char?

                                          • khim
                                            /#21134268

                                            То есть, там написано не совсем это, и вы теоретически могли бы взять указатель на этот член (как вы и делаете), скастануть в char и что-то туда присвоить, но я, опять же, не уверен, что это легально.
                                            Легально-легально. Вы вообще подумайте: кому и зачем могла бы быть нужно разрешение на получение доступа к объектам произвольного типа через glvalue типа char, unsigned char или std::byte, если бы на самом деле ограничения касались бы именно указателей?

                                            Получается какой-то уж больно очевидный хак и дыра.
                                            Никаких хаков и никакой дыры: вы можете записывать в char независимо откуда вы его взяли и через какие тернии этот char при этом прошёл. По крайней мере если мы не выходим за рамки standard-layout типов…

                                            Естественно, и мы же обсуждаем вопрос использования.
                                            А тут тоже всё просто: если это указатель на char и он указывает на какой-то объект… то обращаться к нему легально. Мы могли его лаже в чиселко превратить и куда-нибудь в SQL базу положить, а потом забрать… без разницы (впрочем это возможно только если в реализации существует intptr_t).

                                            Откуда у вас возможность через указатель на CharWrapper писать куда-то ещё?
                                            Ну тут-то как раз всё просто: если вы явно преобразуете этот указать обратно указатель на char — то всё будет точно законно. А вот должен ли автоматически сгенерированный оператор присваивания допускать то, что изначально указатель мог быть рождён из указателя на другой тип… хороший вопрос — не знаю, следует ли это откуда-нибудь.

                                            То есть может быть с точки зрения стандарта вы, может быть, и правы. А вот с точки зрения GCC — точно нет. А поскольку ошибка консервативная (код корректный, хотя возможно не оптимальный) то вряд ли её кто-то будет править, пока не появятся реальные программы, где это важно…

                                            Нет указателя на char* — нет проблем, а я в сухости и безопасности.
                                            Этого недостаточно: тут же как раз всё наоборот — вы же хотите убедить компилятор, что ему разрешено чуть больше, чем с указателями на char*. Если компилятор вообще все указатели будет трактовать как указатели на char — всё же корректно будет (собственно для этого даже опция есть -fno-strict-aliasing).

                                            Или даже signed char?
                                            Signed char ничем не отличается… а вот enum — да, работает… похоже это самый лучший и переносимый вариант. Он и ICC не пугает

                                            • 0xd34df00d
                                              /#21134450

                                              Вы вообще подумайте: кому и зачем могла бы быть нужно разрешение на получение доступа к объектам произвольного типа через glvalue типа char, unsigned char или std::byte, если бы на самом деле ограничения касались бы именно указателей?

                                              Я уже давно перестал думать о «зачем» в контексте стандарта. По крайней мере, в таких местах, где куча разных разделов играет друг с другом в каких-то нетривиальных комбинациях.


                                              Никаких хаков и никакой дыры: вы можете записывать в char независимо откуда вы его взяли и через какие тернии этот char при этом прошёл. По крайней мере если мы не выходим за рамки standard-layout типов…

                                              Я о другом.


                                              Пусть у вас


                                              union
                                              {
                                                  int a;
                                                  float b;
                                              };

                                              Тогда если вы сделаете


                                              auto ptr = &b;
                                              *ptr = 20;
                                              a = 10;
                                              return *ptr;

                                              то это просто обязано быть невалидным.


                                              А тут тоже всё просто: если это указатель на char и он указывает на какой-то объект… то обращаться к нему легально.

                                              Но наличие отдельного типа CharWrapper именно что позволяет избегать наличия указателя на char в коде в явном виде!


                                              Ну тут-то как раз всё просто: если вы явно преобразуете этот указать обратно указатель на char — то всё будет точно законно.

                                              Полностью согласен. Но для этого мне надо получить указатель на char. И это работает для абсолютно любого типа: вы можете указатель на него превратить в указатель на char и писать куда угодно.


                                              То есть может быть с точки зрения стандарта вы, может быть, и правы. А вот с точки зрения GCC — точно нет.

                                              Вы меня уже убедили, что мой исходный вариант, вероятно, работает не очень, и надёжнее делать по-другому. Но я всё ещё не могу понять, где моя брешь в понимании алиасинга.


                                              А поскольку ошибка консервативная (код корректный, хотя возможно не оптимальный) то вряд ли её кто-то будет править, пока не появятся реальные программы, где это важно…

                                              Когда-то и сравнение this с нулём не выбрасывалось, а LLVM вроде как в 9-й версии это стал оптимизировать.


                                              Этого недостаточно: тут же как раз всё наоборот — вы же хотите убедить компилятор, что ему разрешено чуть больше, чем с указателями на char*.

                                              Именно! Поэтому у меня нет указателей на char.

                                              • khim
                                                /#21136118

                                                Тогда если вы сделаете
                                                auto ptr = &b;
                                                *ptr = 20;
                                                a = 10;
                                                return *ptr;
                                                

                                                то это просто обязано быть невалидным.
                                                Ну тут у вас никаких chat нету и типы не similar, так что да — тут это невалидно.

                                                Я уже давно перестал думать о «зачем» в контексте стандарта.
                                                Тем не менее разработчики стандартна об этом думают (работа у них такая). В частности есть прекрасный пример, который разработчики компиляторов считают невалидным, хотя стандарт, вроде бы, его допускает.

                                                  union DeathToHumans {
                                                    float f;
                                                    int i;
                                                  };
                                                  void foo(int* pi,
                                                           float* pf,
                                                           DeathToHumans* switcher) {
                                                     switcher.f = 1.0;
                                                     *pf = 2.0;
                                                     switcher.i = 42;
                                                     *pi = 57;
                                                  }
                                                  ...
                                                  DeathToHumans x;
                                                  foo(&x.i, &x.f, &x);
                                                  ...
                                                
                                                Причём даже разработчики стандарта, в принципе, признали, что то, что стандарт это допускает — «не есть хорошо»… потому что если такое признать допустимым, то получится что указатели на что угодно могут алиаситься, если между ними вызывается функция, кода которой мы не видим…

                                                Однако пока никто не предложил хорошего решения (в смысле: изменения текста стандарта).

                                                Но наличие отдельного типа CharWrapper именно что позволяет избегать наличия указателя на char в коде в явном виде!
                                                Но речь же идёт не об указателе типа char, а о glvalue типа char!

                                                Этого недостаточно: тут же как раз всё наоборот — вы же хотите убедить компилятор, что ему разрешено чуть больше, чем с указателями на char*.
                                                Именно! Поэтому у меня нет указателей на char.
                                                У вас-то нет… а вот в автоматически сгенерированной функции CharWrapper::operator=(const CharWrapper&) — они есть (вернее там есть glvalue типа char — но в нужном месте стандарта речь как раз о glvalue, не об указателях). И компилятор считает, что они могут обращаться к другому типу… хотя следует ли это из стандарта — я сказать и не могу…

                                                • 0xd34df00d
                                                  /#21137106 / +1

                                                  Ну тут у вас никаких chat нету и типы не similar, так что да — тут это невалидно.

                                                  Так там у вас тоже char нету, есть только CharWrapper. Вы можете получить указатель на char, но для этого придётся сделать явный каст, и у вас будет указатель на char.


                                                  Причём даже разработчики стандарта, в принципе, признали, что то, что стандарт это допускает — «не есть хорошо»… потому что если такое признать допустимым, то получится что указатели на что угодно могут алиаситься, если между ними вызывается функция, кода которой мы не видим…

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


                                                  Но речь же идёт не об указателе типа char, а о glvalue типа char!

                                                  Мой поинт в том, что код заш… может, начинает алиасить тогда и только тогда, когда у вас в том или ином виде вылезает явный указатель на char. Скастуете CharWrapper к нему — будет боль и алиасинг. Нет каста — нет проблем.


                                                  И компилятор считает, что они могут обращаться к другому типу…

                                                  Вот мое впечатление — что компилятору здесь силёнок не хватает.


                                                  Впрочем, если сделать шаг назад, ситуация, когда два вроде как неглупых разработчика, более-менее знающих C++, обсуждают, как же на этом языке сделать строки, и уже почти сутки не могут придти к консенсусу — это прикольно. Хороший язык.

                                                  • technic93
                                                    /#21137294

                                                    оставлю тут https://lkml.org/lkml/2018/6/5/769. тоже пытался понять после вашей дискуссии с "царём" в соседнем топике но ни**а не понял.

                                                    • 0xd34df00d
                                                      /#21137742

                                                      Увидел, от кого письмо — сразу понял, что в письме будет «в гцц работает, значит, всё в порядке».


                                                      Прям синдром Линуса в поле from.

                                                      • DaylightIsBurning
                                                        /#21138376

                                                        Но линус не это написал. Он написал, что решение, которое принял комитет по стандартизации по поводу алиасинга — говно, хорошо, что в gcc есть инструменты его обхода. На сколько я могу судить, создатели Haskell и Rust согласны с Линусом по сути, потому в более новых языках эти проблемы тоже учтены иначе, чем в стандарте C.

                                                        • 0xd34df00d
                                                          /#21138522 / +1

                                                          Так наоборот, gcc позволяет программисту больше, давая себе меньше простора для оптимизаций.


                                                          А в других языках просто нет таких юнионов (или вообще указателей).

                                                          • mayorovp
                                                            /#21139696

                                                            Ну, в Rust указатели очень даже есть. Но там отслеживание времени жизни даёт намного больше информации о том, что с чем способно алиаситься (если коротко — то в safe коде алиаситься не может ничего и ни с чем), чем в принципе возможно получить из информации о базовых типах.

                                                            • khim
                                                              /#21141676 / +1

                                                              Rust вообще мне жутко нравится идеологически и также жутко не нравится синтаксически… но то такое — мне и C++ в этом смысле нравится меньше, чем какой-нибудь Pascal.

                                                              • PsyHaSTe
                                                                /#21141830 / +1

                                                                А что бы вы в нем изменили? Ну, чтобы был хороший синтаксис?

                                                  • khim
                                                    /#21137488 / +1

                                                    Впрочем, если сделать шаг назад, ситуация, когда два вроде как неглупых разработчика, более-менее знающих C++, обсуждают, как же на этом языке сделать строки, и уже почти сутки не могут придти к консенсусу — это прикольно.
                                                    Почему не могут? Могут. Уже пришли к консенсусу: "enum FastChar : char {};" — это точно рабочий вариант.

                                                    А дальнейшее — это уже попытка придумать можно ли обойтись структурой…

                                                    Хороший язык.
                                                    Отличный просто. Никогда ни в чём нельзя быть уверенным.

    • hhba
      /#21133442

      Однако редкий трэш. Я про вот это:
      mov byte ptr [rsp - 16], 0
      ......
      mov rcx, qword ptr [rsp - 16]
      mov qword ptr [rsp - 16], rcx
      ......
      test cl, cl


      Объяснение по ссылке выглядит убедительным (хотя для меня не очень понятным, ну да ладно), однако вообще это выглядит как, скажем так, некий приговор, если не языку, то использованным идиомам. Меньше кортежей, меньше…

      • khim
        /#21133494

        Ну а какие альтернативы? Этот конкретный косяк разработчикам LLVM уже известен, фикс, как я сказал, на review…

        • hhba
          /#21134680

          Это понятно, но вопрос в том, что сложность и неочевидность ситуации порождается «богатыми возможностями языка». Сомнительный результат парадигмы «язык усложняем — программы упрощаем». Хотя конечно кортежи — вещь мощная, спору нет.

      • 0xd34df00d
        /#21133574

        Просто не только у ФП-шников компиляторы ещё не достаточно умные.

        • hhba
          /#21134688 / +3

          Ну да, человечество заметно отстало от возможностей С++ )))

          • khim
            /#21136154

            Оооо! Это вы ещё не смотрели на корутины! Там тоже идея в том, что «достаточно умные» компиляторы могут сделать вот всё то, что наворотили в C++20 «zero-cost» за счёт встраивания короутины в объемлющую процедуру.

            Там до обещанного «zero-cost» ещё копать и копать — компиляторы ломаются в самых простейших случаях…

            • hhba
              /#21136226

              за счёт встраивания короутины в объемлющую процедуру


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

              • khim
                /#21136758

                Зависит о того, что это за корутина. Если это генератор и используется он для ranges — то как раз хочется, чтобы встраивалось.

                Но пока это происходит как и с initializer_list: встраивается-то оно встраивается, но ошмётки во все стороны торчат.

                • hhba
                  /#21136802

                  Ну, я не в курсе, что именно там за ошметки, но пространство для творчества там конечно есть. И, да, встроить простой генератор — еще можно, согласен.

                  Ситуация с initializer_list выглядит грустной еще и потому, что описание std::min с таким параметром не гласит о том, что при таком вызове раскручивается маховик репрессий чудес и аллокаций. Это все буквально выглядит просто как способ передачи параметров, использующий синтаксис initializer_list. И типа все должно быть потом прекрасно и быстро. А там вон чего творится…

                  • khim
                    /#21136812

                    А там вон чего творится…
                    Тут action item — однозначно «клевать мозг» разработчикам clang. Я попробую. Так быть не должно.

  5. dakuan
    /#21131736 / +1

    А почему вы на Go работаете с массивами, а на Rust — со строками? Метод bytes() создает cloned итератор, который не бесплатный.

    • 0xd34df00d
      /#21131760

      Я их оба не знаю :)


      Если кинете более эффективный вариант, то я его с радостью проверю сегодня вечером.

    • XRevan86
      /#21131896

          <…>
          let ca1: Vec<u8> = s1.bytes().collect();
          let ca2: Vec<u8> = s2.bytes().collect();
      
          let mut v0: Vec<i32> = (0..).take(n + 1).collect();
          let mut v1 = v0.to_vec();
      
          for (i, c1) in ca1.iter().enumerate() {
              unsafe {
                  *v1.get_unchecked_mut(0) = i as i32 + 1;
      
                  for (j, c2) in ca2.iter().enumerate() {
          <…>

      Действительно, так быстрее.

      • 0xd34df00d
        /#21134418

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

  6. JC_IIB
    /#21131824

    Отличная статья. Но я, признаться, недоумеваю, где же Idris с его завтипами? Интересно же.

    • 0xd34df00d
      /#21131876

      Там с массивами так себе, а на списках я это делать не буду, он не сможет их соптимизировать. Надо брать Idris 2, собирать его из гита… Тема для отдельной статьи, в общем.

      • Inobelar
        /#21133540 / +2

        С удовольствием бы почитал. Прогаю на плюсах, с интересом перенимаю ФП практики, но не достиг просветления для перехода на Haskell. Бегло читал, что Idris ещё круче, потому буду ждать (предвкушая детальный разбор, анализ оптимизаций и ассемблерные листинги) :)

        • PsyHaSTe
          /#21138478

          Круче означает помимо всего прочего — сложнее. Поэтому прежде чем прыгать в самую гущу лучше с чего попроще начать. Новичкам на плюсах наверное самую темную темплейт магию сразу не показывают, сначала простенько, на массивчиках, в рантайме, и потом уже понемногу-понемногу дальше.

          • 0xd34df00d
            /#21138538

            Как посмотреть.


            ФП учить — ИМХО без разницы, базовая семантика что в хаскеле, что в идрисе одна и та же (с точностью до ленивость). Идрис даже, может, чуть лучше, там из коробки можно делать дырки и смотреть на типы.


            Учиться писать продакшн-код — хаскель на голову выше, за счёт тулинга и библиотек в основном.


            Учить всякую наркоманию в типах — идрис лучше, там все это адекватно, органично и из коробки. Как работают завтипы там, я плюс-минус понимаю. Как работает комбинация из полутора десятков расширений языка в случае хаскеля, которые пытаются это эмулировать — хорошей интуиции у меня нет, и проще в голове держать некий образец на идрисе, который потом транслировать в хаскель.

  7. alec_kalinin
    /#21131862

    Про то, что Python не готов для вычислений, вы не правы. И PyPy не нужен, нужны только Numpy, Numba и самый обычный Python. Вот результаты

    C
    Windows 10, gcc version 8.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project)
    $ gcc ld.c -Ofast -fPIC -fPIE -static -flto -o ld.exe
    $ ld.exe
    0
    15000
    Finished in 0.934s

    Python
    Косметические изменения в коде:

    import sys
    import time
    import numpy as np
    from numba import jit
    
    
    @jit
    def lev_dist(s1: bytes, s2: bytes) -> int:
        m = len(s1)
        n = len(s2)
    
        # Edge cases.
        if m == 0:
            return n
        elif n == 0:
            return m
    
        v0 = np.arange(0, n + 1)
        v1 = np.arange(0, n + 1)
    
        for i, c1 in enumerate(s1):
            v1[0] = i + 1
    
            for j, c2 in enumerate(s2):
                subst_cost = v0[j] if c1 == c2 else (v0[j] + 1)
                del_cost = v0[j + 1] + 1
                ins_cost = v1[j] + 1
    
                # min(subst_cost, del_cost, ins_cost) is slow.
                min_cost = subst_cost if subst_cost < del_cost else del_cost
                if ins_cost < min_cost:
                    min_cost = ins_cost
                v1[j + 1] = min_cost
    
            v0, v1 = v1, v0
    
        return v0[n]
    


    Результаты на Windows 10, Python 3.7.5
    $ python ld.py
    0
    15000
    Finished in 0.968s

    На долю процентов C быстрее, но скорости практически сравнимы.

    • 0xd34df00d
      /#21131958

      Умножьте на (4/3)? — для этих данных время квадратично зависит от длины, а везде строки в 20 тыщ символов.


      Ну и, кстати, сколько тогда работы выполняется в питоне, а сколько — в C?

      • alec_kalinin
        /#21132038 / +2

        Можно привести и к 20 тыщ, но в целом видно, что C и Python практически сравнимы по скорости.

        Ну и, кстати, сколько тогда работы выполняется в питоне, а сколько — в C?
        Ну Python же это язык. У него может быть реализация как у интепретируемого языка, а может быть и jit компиляция.

        А по факту я взял приведенный исходник на Python, практически добавил всего одну аннотацию, запустил в стандартной реализации CPython и получил практически скорость языка С. С точки зрения разработчика я нигде не вышел из окружения Python.

        • 0xd34df00d
          /#21132098

          Ну Python же это язык. У него может быть реализация как у интепретируемого языка, а может быть и jit компиляция.

          Безусловно (поэтому там есть сравнение с pypy). Но FFI в C — это ИМХО как-то не очень честно при бенчмаркинге реализаций, так как вы тогда сравниваете не эффективность реализаций, а эффективность FFI.

          • technic93
            /#21132128

            так numba это не ffi

            • 0xd34df00d
              /#21132168

              Теперь-то обратил внимание на @jit. Прикольная штука, буду иметь в виду, если вдруг придётся столкнуться с питоном.

              • khim
                /#21132332

                Она, к сожалению, меняет семантику (и довольно существенно).

                То есть если вы сами пишите код — в общем не проблема.

                А вот взять чужой код и налепить на него jit — можно поиметь проблем.

                Но учитывая ускорение в несколько раз — иногда можно поиграться…

          • alec_kalinin
            /#21132174 / +1

            Тут вопрос сложный. У нас есть Java Script с его V8, nim с его компиляцией в C, Julia с ее компиляцией через llvm. Да и тот же pypy в несколько раз медленнее numba, хотя оба пытаются компилировать код.

            На мой взгляд вполне честно все сравнивать с точки зрения разработчика. Есть код, есть плафторма, есть результат.

            Да и чем, грубо говоря, декоратор "@jit" так уж сильно отличается от набора специальных флагов «gcc» с подсказками для оптимизаций?

            • 0xd34df00d
              /#21132190 / +1

              Я в том комментарии был неправ, так как неправильно прочитал код.


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

              • chupasaurus
                /#21132208 / +1

                pip3 и через него модули numpy и numba.

              • alec_kalinin
                /#21132226 / +1

                Выше уже ответили, нужны только numpy и numba:
                $ pip3 install numpy
                $ pip3 install numba


                На всякий случай, вот полный код:

                #!/usr/bin/env python3
                import sys
                import time
                import numpy as np
                from numba import jit
                
                
                @jit
                def lev_dist(s1: bytes, s2: bytes) -> int:
                    m = len(s1)
                    n = len(s2)
                
                    # Edge cases.
                    if m == 0:
                        return n
                    elif n == 0:
                        return m
                
                    v0 = np.arange(0, n + 1)
                    v1 = np.arange(0, n + 1)
                
                    for i, c1 in enumerate(s1):
                        v1[0] = i + 1
                
                        for j, c2 in enumerate(s2):
                            subst_cost = v0[j] if c1 == c2 else (v0[j] + 1)
                            del_cost = v0[j + 1] + 1
                            ins_cost = v1[j] + 1
                
                            # min(subst_cost, del_cost, ins_cost) is slow.
                            min_cost = subst_cost if subst_cost < del_cost else del_cost
                            if ins_cost < min_cost:
                                min_cost = ins_cost
                            v1[j + 1] = min_cost
                
                        v0, v1 = v1, v0
                
                    return v0[n]
                
                
                if __name__ == "__main__":
                    s1 = b"a" * 15_000
                    s2 = s1
                    s3 = b"b" * 15_000
                
                    exec_time = -time.monotonic()
                
                    print(lev_dist(s1, s2))
                    print(lev_dist(s1, s3))
                
                    exec_time += time.monotonic()
                    print(f"Finished in {exec_time:.3f}s", file=sys.stderr)
                

                • Andy_U
                  /#21132884

                  Начал с практически того же варианта, что и Вы, потом упростил внутренний цикл без потери производительности до:

                          for j, c2 in enumerate(s2):
                              v1[j+1] = min(v0[j] if c1 == c2 else (v0[j]+1), v0[j+1]+1, v1[j]+1)
                  


                  Не понимаю, чем не понравился автору статьи min()?

                  • Senpos
                    /#21133362

                    Подобные "упрощения" не очень то и упрощают чтение кода. :)

                    • Andy_U
                      /#21134066

                      Было 7 строк кода (понятного лишь из-за закомментированного варианта), 4 одноразовых переменных (которым еще имена придумать надо), стала одна строка, которая понятно что делает.

                      P.S. В конце концов можно так сделать:

                              for j, c2 in enumerate(s2):
                                  v1[j+1] = min(v0[j] if c1 == c2 else (v0[j]+1), 
                                                v0[j+1]+1, 
                                                v1[j]+1)
                      

    • technic93
      /#21131978 / +9

      на любом языке можно писать на фортране

    • XRevan86
      /#21132010 / +2

      Numba – это что-то невероятное…
      У меня оно не получилось быстрее C, но оно справилось быстрее Julia.

    • Senpos
      /#21132042 / +2

      Круто, что даже без использования numpy при помощи numba можно прилично ускорить работу программы.


      Например, если на код автора просто навесить декоратор @jit — программа отработает за 2.528 на моем железе.


      Если убрать isinstance — уже будет 1.7.


      Что не может не радовать. :)


      Все-таки, если уже считаем в Питоне, то берем для этого инструменты, которые для него придумали.

  8. bfDeveloper
    /#21131874

    Уже прокомментировали про C++, добавлю то же самое про D. Достаточно добавить флажок boundscheck=off и получить удвоение скорости. Размен безопасности на скорость, которую вы сделали в хаскеле.

    • XRevan86
      /#21131930 / +1

      Не хочу комментировать, что 0xd34df00d намерял с C++, но ведь с D именно так оно и есть уже.
      Можно было бы ещё LDC приложить, ведь он быстрее DMD справился с сей задачей.

      • bfDeveloper
        /#21132066

        Да, невнимательно посмотрел на флаги. Дописал в P.S.
        Протестировал у себя, получил похожие цифры, а потом уже удвоился за счёт проверок границ. Даже не задумывался, что можно бенчмаркать DMD, на автомате взял ldc. Результаты у меня:
        C gcc 8.3: Finished in 0.696s
        D ldc2 1.10.0: Finished in 0.638s
        Есть разброс, но в целом D версия чуть быстрее.

  9. ZoNT
    /#21131984 / +2

    Пожалуйста, перетестируйте js:

    const levDist = (s1, s2) => {
      const m = s1.length;
      const n = s2.length;
    
      // Edge cases.
      if (m === 0) {
        return n;
      } else if (n === 0) {
        return m;
      }
    
      let v0 = new Uint16Array(n + 1);
      let v1 = new Uint16Array(n + 1);
    
      for (let i = 0; i < m; ++i) {
        v1[0] = i + 1;
    
        for (let j = 0; j < n; ++j) {
          v1[j + 1] = Math.min(
            v0[j] + (s1[i] === s2[j] ? 0 : 1),
            v0[j + 1] + 1,
            v1[j] + 1
          );
        }
    
        [v0, v1] = [v1, v0];
      }
    
      return v0[n];
    };
    
    
    const s1 = new Uint8Array(15000).fill('a'.charCodeAt(0));
    const s2 = s1.slice();
    const s3 = new Uint8Array(15000).fill('b'.charCodeAt(0));
    
    console.time('Finished in');
    
    console.log(levDist(s1, s2));
    console.log(levDist(s1, s3));
    
    console.timeEnd('Finished in');

    • 0xd34df00d
      /#21132090

      Спасибо, вечером на той же машине проверю и обновлю результаты.

    • XRevan86
      /#21132354

      Похоже, что V8 от Math.min, наоборот, получает выигрыш.

      • 0xd34df00d
        /#21134400

        Хм, а у меня они оба (вместе со spidermonkey) получают выигрыш.

  10. technic93
    /#21132108

    а зачем на с++ используется int64?

    • 0xd34df00d
      /#21132136

      Для консистентности с хаскель-версией, там Int — знаковый и соответствующей машине битности. Впрочем, замена на uint64_t или на (u)int32_t вообще ничего не меняла на моей машине (что ожидаемо, работа с L2-кешем таки не оказывается боттлнеком, чтения/записи исключительно последовательные и хорошо предсказываются, векторизации здесь нет, а сравнения и сложения процессор выполняет, видимо, одинаково эффективно).

      • technic93
        /#21132162

        Если по кэшу нет разницы то логично.

  11. wslc
    /#21132252 / +2

    Старому clang (6.0) очень помогло вынести в отдельную функцию внутренний цикл и написать __restrict. Что-то типа:

    void calc_line(const char c1, const std::string &s2, const int64_t *__restrict v0, int64_t *__restrict v1, size_t n);
    

    Сразу sse появляются и прочие удовольствия

    • khim
      /#21132362 / +4

      Если начинать хитрые трюки устраивать, то непонятно где останавливаться. Как автор и заметил — так можно и до ручной генерации кода дойти.

      Так что самый быстрый вариант, в пределе, будет выглядеть как asm("<многа букав>") — на любом языке.

  12. Sly_tom_cat
    /#21132466

    А что же вы в GO unsafe не заюзали — он там тоже есть и тоже «педалирует» решение значительно.

    • XRevan86
      /#21132486

      С указательной арифметикой? Ну жуть же!
      Обрати внимание на -gcflags=-B.
      Да, всё так, без отключения проверок границ (что в коде сделать нельзя, к сожалению) было бы сильно хуже.

  13. technic93
    /#21132750

    интересно что у меня на clang++8 если ставить флаг -std=gun++2a вместо -std=gnu++17 есть прирост где-то на 8%.
    К тому же еще странно как у вас шланг так сливает гцц, я вот захожу на годболт, и там шланг векторизирует а гцц нет, и у меня на машине шланг8 быстрее гцц9.1. Сейчас поставлю новые версии.
    Еще расту тоже надо указывать -C "target-cpu=native для честности. Кстати хаскелю наверное тоже что то такое т.к. это флаг скорее всего для ллвм.

    • 0xd34df00d
      /#21132818 / +1

      интересно что у меня на clang++8 если ставить флаг -std=gun++2a вместо -std=gnu++17 есть прирост где-то на 8%.

      Вот это вот действительно интересно. Я сходу не могу придумать, за счёт чего оно бы так могло быть.


      К тому же еще странно как у вас шланг так сливает гцц, я вот захожу на годболт, и там шланг векторизирует а гцц нет, и у меня на машине шланг8 быстрее гцц9.1.

      Я, кстати, не знаю, как тут так просто бы векторизовать, так как у каждого следующего элемента массива есть неприятная зависимость по данным от всех предыдущих. Если он там действительно векторизует, а не просто использует векторные регистры и векторные мувы, чтобы сразу 8-16-32 инта получать, то это очень круто.


      Ну и да, на одной из машин у меня был clang 8, и там он был быстрее gcc, так что, вероятно, это регрессия. Но полный набор тестов на той машине я провести не мог, а ставить clang 8 на ту, где мог, просто потому, что он тут быстрее — это какое-то читерство.


      Кстати хаскелю наверное тоже что то такое т.к. это флаг скорее всего для ллвм.

      Если вкратце, то у меня не получилось, а жаль. Могло бы быть ещё чуточку быстрее.

      • technic93
        /#21132900

        наверное про векторизацию я нагнал и это был код iota

      • technic93
        /#21133122

        У меня разница между шланг8 и шланг9 минимальна. 8-ой шланг действительно дает маленькую регрессию при с++17.

      • technic93
        /#21133190

        А я уже тестил с оптимизацией s1[i] за границей цикла. Иначе (на вашем оригинальном коде) в шланге9 дикая регрессия больше чем в два раза!

  14. Siemargl
    /#21132802

    Похоже, что за неполные 4 часа, неопротестованными остались всего несколько тестов =)

    Было бы неплохо обновить статью новой табличкой результатов. И новыми выводами.

    И еще статья дает больше информации не столько о скорости ЯП, сколько об их читаемости.

    • 0xd34df00d
      /#21132832 / +2

      Как вечером доберусь до домашней машины — прогоню предложенные новые варианты и обновлю.


      А выводы-то… Ну вот питон с numba приятно удивил, да. Другой вывод — похоже, я не умею передавать смысл того, что я делаю.

      • Siemargl
        /#21132984 / +1

        Видимо да.

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

        И можно не пренебрегать безопасностью в угоду производительности.

        Но в любом случае надо хорошо знать свой инструмент.

        • 0xd34df00d
          /#21133112

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

          С одной стороны — не только. Смотрите, как хорошо себя JS показывает на V8/SM.


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

          • Siemargl
            /#21133776

            JIT стал хорош только по прошествии 20 лет, и то пока примеров единицы — JVM, NET, отчасти JS, и возможно Julia, остальные глотают пыль.

            Проблема Хаскеля (ну и не только, например linq, sql), как я глупо думаю — что высокоуровневые абстракции скрывают реальные накладные расходы — и очень легко написать красивый код, получив ужасную практическую реализацию с квадратичными расходами.

            • 0xd34df00d
              /#21133816

              А фиг его знает, в чём проблема.


              Я на самом деле очень разочарован, что forM_ пришлось выкинуть и написать хвостовую рекурсию руками. Это плохо. Этого быть не должно. Я ожидаю, что компилятор это свернёт и сделает за меня.


              А ведь это, ну, очень базовая во всех смыслах вещь. И функция в базовой библиотеке, и используется часто, и от этой мелкой оптимизации можно выиграть разы (как показывает данный пост).

  15. crackedmind
    /#21132980

    Не хватает тестов clang -stdlibc :)

  16. somebody4
    /#21133222

    Осталось сделать версию на ассемблере и в конце концов решить вопрос умнее ли компилятор человека.

    • 0xd34df00d
      /#21133262

      Боюсь, её написание займёт больше виртуального лимита в час, который я себе отвёл, так что её время работы не определено.

      • somebody4
        /#21133300

        Откомпилировать С версию, дизассемблировать, добавить ручные оптимизации, протестировать.

        По идее должно достаточно быстро получиться.

        • 0xd34df00d
          /#21133330 / +1

          И так для каждой микроархитектуры.


          А если серьёзно, я смотрел на асм (но больше на хаскелевский — интересно было, чего там компилятор наворотил). В общем, мне пока хватит.

          • Akon32
            /#21135904

            Что, если в хаскелевском коде 0.8с уходит на инициализацию некого рантайма, а остальные 0.01с на что-то вроде


            .LC0:
                    .string "0"
            main:
                    movl    $.LC0, %edi
                    jmp     puts

            ? Я бы добавил зависимость от входных данных, чтобы быть уверенным, что результат считается не в compile-time.

            • 0xd34df00d
              /#21137126

              Ну тут две вещи дают уверенность:


              1. Я добавлял NOINLINE-прагму к определению функции (с очевидной семантикой) — ничего не изменилось вообще никак, а кроссмодульную оптимизацию в ghc не завезли.
              2. Библиотека criterion специально сделана так, чтобы данные не протекали в функцию до начала бенчмарка, и результаты от этой библиотеки согласуются с результатами из табличек.

    • Siemargl
      /#21133756 / -1

      вперде!

      у меня уже есть ответ, впрочем

  17. oam2oam
    /#21133224

    Трудно удержаться от написания тестов на каком-нибудь другом языке. Автор знает толк!
    Я написал по мотивам С реализацию на Ada для строк длиной 20000, получилось на 3.6 ГГц процессоре 0.86 секунды…

    • 0xd34df00d
      /#21133268

      А вы с 15к или с 20к символами запускали?


      Вот это моя, наверное, самая большая ошибка — надо было не лениться и переделать везде на 20к. А то теперь одна путаница и неразбериха.


      И код-то покажите, интересно же!

      • oam2oam
        /#21133338 / +1

        ну, вот так примерно (писалось в спешке :)

        with Ada.Text_IO;
        
        procedure Main is
           function Levenshtein_Distance (S1, S2 : String) return Long_Integer is
              M  : Integer := S1'Length;
              N  : Integer :=  S2'Length;
              R  : Long_Integer := 0;
              type q is array(1.. N+1) of Long_Integer;
              k0 : aliased q := (others => 0);
              k1 : aliased q := (others => 0);
              v0 : access q := k0'access;
              v1 : access q := k1'access;
              temp: access q := k1'access;
           begin
                for I in S1'Range loop
                v1(1) := Long_Integer(i) + 1;
                for J in S2'Range loop
                    declare
                     del_cost   : Long_Integer := v0(j + 1) + 1;
                     ins_cost   : Long_Integer := v1(j) + 1;
                    begin
                      if s1(i) = s2(j) then
                          -- v0(j)
                          if v0(j) < del_cost then v1(j+1) := v0(j); else v1(j+1) := del_cost; end if;
                      else
                          if v0(j)+1 < del_cost then v1(j+1) := v0(j)+1; else v1(j+1) := del_cost; end if
                          -- v0(j)+1
                      end if;
                    if ins_cost < v1(j + 1) then
                        v1(j + 1) := ins_cost;
                    end if;
                    end;
                end loop;
                temp := v0;
                v0 := v1;
                v1 := temp;
              end loop;
        
              return v0(N);
           end Levenshtein_Distance;
        
          A : String(1..20000) := (others => 'a');
          A2: String(1..20000) := (others => 'a');
          B : String(1..20000) := (others => 'b');
        
        begin
           Ada.Text_IO.Put_Line
             ("1:" &
              Long_Integer'Image (Levenshtein_Distance (A,A2)+Levenshtein_Distance (A,B)));
        end Main;
        

      • hhba
        /#21133426

        Однако поддержу просьбу показать код…

  18. dzsysop
    /#21133304 / +1

    PHP можно попросить удалить ненужные строки и переменные `$ca1`, `$ca2`:

        //$ca1 = $ca2 = [];
        //for ($i = 0; $i < $m; ++$i) {
        //    $ca1[] = ord($s1[$i]);
        //}
        //for ($i = 0; $i < $n; ++$i) {
        //    $ca2[] = ord($s2[$i]);
        //}
    


    А соответствующие циклы заменить на:
        for($i = 0;  $i < $m; $i++) {
            $v1[0] = $i + 1;
    
            for($j = 0; $j < $n; $j++) {
                $subst_cost = ($s1[$i] === $s2[j]) ? $v0[$j] : ($v0[$j] + 1);
                $del_cost = $v0[$j + 1] + 1;
                $ins_cost = $v1[$j] + 1;
    
                // min($subst_cost, $del_cost, $ins_cost) is slow.
                $min_cost = ($subst_cost < $del_cost) ? $subst_cost : $del_cost;
                if ($ins_cost < $min_cost) {
                    $min_cost = $ins_cost;
                }
                $v1[$j + 1] = $min_cost;
            }
    
            [$v0, $v1] = [$v1, $v0];
        }
    


     Минус два цикла — должно дать существенный прирост производительности

    • XRevan86
      /#21133344

      Сравнение чисел просто немножко дешевле.

      • dzsysop
        /#21133416 / +1

        минус два цикла с вычислением ord()
        плюс строгое равенство при сравнении одиночных символов.

        Зуб даю мой код быстрее и читабельнее. Не говоря уже про UTF-8

        • XRevan86
          /#21133480

          минус два цикла с вычислением ord()

          Вне цикла подобные манипуляции вообще ничего не значат на общем фоне. Так-то их можно вообще вынести наружу… только зачем?


          плюс строгое равенство при сравнении одиночных символов

          При сравнении строк иначе и нельзя. А вот при сравнении (гарантированных) чисел никакой разницы тут не будет.


          Не говоря уже про UTF-8

          Все версии сделаны именно так, чтобы сравнивались именно индивидуальные байты для однородности и простоты (ну, в большинстве случаев).
          Но вообще, как ни иронично, именно вариант с конвертацией в массив чисел более юникододружелюбный, потому что с ним для UTF-8 нужно просто заменить ord на mb_ord, а иначе нужно использовать mb_substr; а это, сам понимаешь, уже целый вызов функции внутри цикла.

          • dzsysop
            /#21133616

            минус два цикла с вычислением ord()

            Вне цикла подобные манипуляции вообще ничего не значат на общем фоне. Так-то их можно вообще вынести наружу… только зачем?


            Я не понял что именно вы предлагаете «вынести наружу»?

            Что-то я не понял мысль. Или мне кажется вы не поняли про какие два цикла я говорю.
            Я предложил тупо убрать два вспомогательных цикла перед двумя вложенными друг в друга — потому что они ничего не добавляют важного и нужного. И если их цель преобразовать строки в числа — то мне кажется это немного высокая цена ради того чтобы позже выиграть на сравнении чисел вместо строк.

            • 0xd34df00d
              /#21133628 / +1

              Но преобразование строк в числа — m + n операций (где это длины строк), а сравнений потом происходит в районе mn. 40 тысяч против 400 миллионов в этом случае.

            • XRevan86
              /#21133634 / +1

              И если их цель преобразовать строки в числа

              Как бы, ord
              Неужели так сложно поверить, что числа сравнивать дешевле, чем целые строки, хоть и единичные %)?


              это немного высокая цена

              Два for на 40?000 циклов суммарно.


              ради того чтобы позже выиграть на сравнении чисел вместо строк

              А вот сравнение происходит 400?000?000 раз.

              • PQR
                /#21134816

                Кто-нибудь пробовал в итоге запустить и сравнить эти два PHP варианта между собой? Рассуждения интересные, но хотелось бы понять на практике.

                • dzsysop
                  /#21137062

                  Я таки попробовал. И мой предложенный вариант не выдал улучшения, а таки негативно сказался на производительности примерно на 10-15%.

        • 0xd34df00d
          /#21133524

          Не говоря уже про UTF-8

          Предложенная функция всё равно остаётся метрикой (в математическом смысле), пусть и считает немного не то.


          Но игнорирование уникода было одним из моих допустимых предположений, считать всё корректно для уникода (и особенно для UTF-8) чуть менее просто.

          • torkve
            /#21136608

            считать всё корректно для уникода (и особенно для UTF-8) чуть менее просто.

            Тут зависит от реализации. Для раста можно заменить итератор по bytes на итератор по chars и получить всё то же самое и без особой просадки производительности.
            А на php с кем-то предложенным тут mb_substr это будет уже O(n?), потому что для взятия каждого следующего символа надо будет пробежать по всей строке.

  19. buratino
    /#21133748 / -2

    Добавлю свои 0.05 копеек.

    В коде на С++ внутри одного цикла идет std::swap длинных векторов, в коде на С — меняются указатели. До кучи внутри swap идет вызов new/delete, которые на Це эквиваленты дерагнью malloc/free, что само по себе плохо сказывается на производительности и зависит от того, как там heap устроен, плюс есть эффект на забивание кешей процессора

    • 0xd34df00d
      /#21133768 / +4

      Там нет вызова new/delete. И быть его там не должно, если ваша реализация STL зачем-то там выделяет/освобождает память, то её лучше выкинуть.


      В этом случае std::swap действительно делает чуть больше работы, чем обмен указателями (так как он обменивает ещё и длины, а они одинаковые), но я не думаю, что это принципиально что-то меняет.

      • buratino
        /#21133792 / -1

        Там нет вызова new/delete.


        Вот специально перед написанием посмотрел на например, вот это.

        • 0xd34df00d
          /#21133808 / +1

          Там первым ответом код с использованием std::move, который уже сам по себе убирает всякую потребность в delete.


          А так как стандарт по большей части не специфицирует, как именно должна быть реализована та или иная функция, а лишь описывает поведение, то лучше проверять экспериментально. Никто не мешает std::vector'у, например, вообще иметь свою кастомную std::swap.

          • buratino
            /#21133826 / -1

            Разве не так?
            Foo()
            {
            T temp; // вызов new
            } // вызов delete

            А так как стандарт по большей части не специфицирует,

            ну да, ну да. Однако вангую, что сделано в большинстве реализаций по простому, как написано на стекеоверфлоу.

            • 0xd34df00d
              /#21133846 / +2

              Разве не так?

              Если вкратце, то нет.


              Если вы специфицируете эту функцию для int, например, то никакого new там не будет заведомо.


              Если теперь вы вернётесь к векторам и посмотрите на правую часть от присваивания, то там там std::move — это позволяет просто взять указатель и размер от вектора справа и переместить его в temp слева, без всяких копирований и выделений памяти, оставив вектор справа в полудохлом состоянии. Аналогично со следующими мувами.


              Однако вангую, что сделано в большинстве реализаций по простому, как написано на стекеоверфлоу.

              Это снова вопрос качества реализации. Но писать адекватные стандартные библиотеки чуточку проще, чем проходы оптимизации (хоть и чуть более муторно и чуть менее весело), поэтому поставщики основных библиотек (libstdc++ среди них) таки в это вкладываются. Удивительно, люди там далеко не всегда работают спустя рукава (и это не сарказм, учитывая всю опенсорсовость и бесплатность).


              Плюс, упомянутая на SO реализация не будет nothrow для векторов, чьи элементы не имеют nothrow-move-конструктора, а std::swap ЕМНИП обязан быть nothrow (по крайней мере, в этом случае).

              • buratino
                /#21134016 / -3

                Если вкратце, то нет.

                если быть точным, то в общем — нет, по факту для для любого нетривиального класса — да.
                там std::move — это позволяет просто взять указатель и размер от вектора справа и переместить его в temp слева, без всяких копирований и выделений памяти, оставив вектор справа в полудохлом состоянии


                Поскольку я не пользуюсь систематически «этим безобразием» (темплейтами), то проверил это утверждение экспериментально. Как минимум в общем случае ;-) утверждение, что там нет копирования — ложно.

                • 0xd34df00d
                  /#21134030

                  Поскольку я не пользуюсь систематически «этим безобразием» (темплейтами), то проверил это утверждение экспериментально. Как минимум в общем случае ;-) утверждение, что там нет копирования — ложно.

                  Покажете код?


                  В предыдущем комментарии я говорил о копировании storage вектора, но и в более общем смысле копирования для классов с поддержкой мув-операций быть не должно.

                • khim
                  /#21134032 / +2

                  если быть точным, то в общем — нет, по факту для для любого нетривиального класса — да.
                  Конкретно для std::vector C++17 гарантирует, что исключений не выбрасывается, а это возможно только если выделания памяти не происходит.

                  Все нормальные реализации были так устроены, впрочем, всегда.

                  • buratino
                    /#21134122

                    , а это возможно только если выделания памяти не происходит.

                    Может я отстал от жизни, но раньше было только два варианта выделения памяти для нестатических переменных — из стека или из кучи (для неембеднутых С/C++),

                    Ну вот попробовал погулять в отладчике MS VS2017 по коду С++ который выше приведен.
                    std::vector<int64_t> v0; прямо вызывает new(),

                    а вот swap для vector действительно хитровыделанный и совсем не похож для swap с стекореврфлоу. И сходу конечно непонятно, но в new вроде не попадает и копирования не вижу.

                    • khim
                      /#21134226

                      Прошу прощения. Не заметил, что вы там обсужджаете создание временного объекта, а не, собственно, swap.

                      Тут фишка как раз в том, что у std::swap обязана иметься специализацию для std::vector — и вот она уже не имеет права бросать исключения, а значит, должна как-то обходиться без выделения памяти на куче.

                      Будет она создавать временные объекты (которые не будут выделять памяти) или как-то без них обойдётся (тогда память не будет выделяться просто потому, что временных объектов нет) — действительно оставлено на усмотрение реализаторов…

            • technic93
              /#21133854

              ну да, ну да. Однако вангую, что сделано в большинстве реализаций по простому, как написано на стекеоверфлоу.

              Абсолютно наоборот, стандартная библиотека делает все максимально быстро, насколько это позволяет ее обобщенность.


              Да и собственно откройте код и узнайте, чем гадать.

              • buratino
                /#21133980 / -2

                , стандартная библиотека делает все максимально быстро,

                стандартная библиотека делает в первую очередь максимально стандартно и безглючно, а уж потом быстро.

  20. m0n5ter
    /#21133758

    Преобразование вот этого неоптимального куска


                var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
                var delCost = v0[j + 1] + 1;
                var insCost = v1[j] + 1;
    
                v1[j + 1] = Math.Min(substCost, delCost);
                if (insCost < v1[j + 1])
                {
                    v1[j + 1] = insCost;
                }

    в вот этот (тоже, наверное, не самый оптимальный)


                var v0j = v0[j];
                var substCost = s1[i] == s2[j] ? v0j : v0j + 1;
                var delCost = v0[j + 1] + 1;
                var insCost = v1[j] + 1;
    
                v1[j + 1] = Math.Min(substCost, Math.Min(delCost, insCost));

    ускорило C# версию на 26% на моей машине.

    • PsyHaSTe
      /#21138542

      На моей машине такая замена код замедлила. Тоже её увидел, и тоже весьма удивился.

      • 0xd34df00d
        /#21138554

        Вот этот вот минимум — об него все языки в том или ином виде спотыкаются.

  21. neenik
    /#21133772

    Почему вы берёте самописное решение, а не какую-либо готовую библиотеку, в которой сделаны нужные оптимизации? Взял ваше решение на Go (0.78 сек. у меня минимально), библиотеку github.com/agnivade/levenshtein — получил 0.354 сек. минимально.

    • 0xd34df00d
      /#21133804 / +1

      Потому что имеющиеся решения меня не устраивали. В моём случае доступны две библиотеки:


      • text-metrics — она тратит время на обработку уникода (и оказывается в 3-4 раза медленнее моей реализации), а мне это не нужно.
      • edit-distance — она оказывает слишком большое давление на GC, и мне было интересно, не получится ли у меня эффективнее. Кроме того, я в первый раз читал её код ж… неправильно, и сделал неправильные выводы о том, как она внутри работает, что добавило мне уверенности, что я могу лучше (по памяти, впрочем, лучше и получилось). Плюс, если туда передавать свои собственные коэффициенты, то она просто взрывается по памяти, а мой вариант взрываться не должен.

      Кроме того, в той библиотеке на Go есть не очень устраивающее меня ограничение «As a performance optimization, the library can handle strings only up to 65536 characters (runes).» (не говоря о том, что мой код не на Go).

  22. technic93
    /#21133896 / +2

    Если интересно можно побенчить такую более олдскульную версию на указателях, у меня она на 15% быстрее с gcc и на 6% с clang9 (сама по себе шланг версия ускоряется в два раза после того как вынести s1[i] — вангую что из-за алиасинга компилятор не может сделать эту оптимизацию). Естественно это уже не самая наивная версия. Далее надо уже применять думаю некую векторизацию. И в рамках сравнение языков инетересно бы узнать как это будет выглядеть в разных языках.


    код
    #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<int> v0;
        v0.resize(n + 1, 0);
    
        std::vector<int> v1;
        v1.resize(n + 1, 0);
    
        for (size_t i = 0; i < m; ++i) {
            v1[0] = i + 1;
            char c1 = s1[i];
    
            auto i0 = v0.cbegin();
            auto end = v0.cend() - 1;               
            auto i1 = v1.begin();
            const char *c2 = s2.data();
            while (i0 != end) {
                int delInsCost = std::min(*(i0+1), *i1) + 1;
                int substCost = *i0 + !(c1 == *c2);
                *(++i1) = std::min(delInsCost, substCost);
                ++i0; ++c2;
            }
            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;
    }

    • 0xd34df00d
      /#21133936

      Это очень плюсоспецифичные оптимизации. Не уверен, что их можно портировать на другие языки, особенно где с указателями так вот не поиграешься.


      Но экспериментальная точка интересная, спасибо.

      • siziyman
        /#21136666

        Ну так код на хаскеле у вас тоже хаскелеспецифичный (или как минимум ФП-специфичный).

        Вы бы на всех языках код пооптимизировали, а не делали кликбэйт-заголовки.

        • 0xd34df00d
          /#21137138 / +1

          Я только на плюсах-то могу код оптимизировать (и с большим натягом на С). И там на оптимизацию я потратил примерно столько же времени, сколько в случае хаскеля.

    • technic93
      /#21140122

      закралась ошибка. исправил — стало быстрей.


      Быстрый С++ Код
      #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<int> 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;
              char c1 = s1[i];
      
              auto i0 = v0.cbegin();
              auto end = v0.cend() - 1;
              auto i1 = v1.begin();
              const char *c2 = s2.data();
              while (i0 != end) {
                  int delInsCost = std::min(*(i0 + 1), *i1) + 1;
                  int substCost = (c1 == *c2) ? *i0 : *i0 + 1;
                  *(++i1) = std::min(delInsCost, substCost);
                  ++i0;
                  ++c2;
              }
              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;
      }

  23. v1000
    /#21133994

    оптимизация-коварная штука. один раз пару часов оптимизировали большой кусок кода долго работающей программы. в итоге ускорили ее в 3 раза. с 1 секунды до 0.3. учитывая, что суммарно программа работает час.

    • khim
      /#21134056 / +5

      Это ещё хорошо, если так. Куда веселее, если окажется что ваша оптимизация замедляет программу.

      Сейчас не могу найти письма от какого-то прыща, который объяснял, что разработчики Linux-ядра — идиоты, что они нифига не понимают в оптимизациях и прочее. Ну вот прям все. Они все — идиоты, я д’Артаньян.

      Его попросили показать пример. Он показал. Развернул циклы, таблички какие-то развёл, ещё что-то… скорость подсчёта TCP чексуммы выросла в 10 раз. Победа в сухую!

      После чего кто-то (Ingo Molnar, кажется) ему ответил. Что-то в духе «ну, бенчмарки ты запускать умеешь… а вот думать — кажется нет». Дальше — другие бенчмарки, уже с TUXом (самый быстрый тогдашний Web-сервер), который с этими «ускоренными» циклами тормозится (ибо все эти таблицы убивают L1 напрочь) и риторическим вопросом: «как ты думаешь — функция подсчёта чексуммы в ядре нужна, чтобы красивые цифирьки на тестах показывать или для того, чтобы Web-сервера могли работать?».

      Это было эпично…

      • Akon32
        /#21136000

        Может, выбор "убивать кэш или не убивать кэш" нужно делать опцией ядра? Какая-то страшная ситуация, когда оптимизации делают наоборот, если их не к месту использовать.

        • khim
          /#21136266

          А кому и зачем может понадобиться убивающая кеш версия? Вы ж эту чексумму не «от нечего делать» считаете — после вычисления (если передача) или до (если приём) у вас данные в сеть отдаются… там задержки миллисекундами меряются (даже если в локалке).

          То есть задача ядра (в данном случае, да и вообще почти всегда) — это «сделать что-то и убраться с дороги». Недаром ядро работает быстрее часто, если скопилировать его с опцией -Os, а не с -O2!

          Этот режим не используется по умолчанию, потому что -Os GCC интерпретируется как мне нужен маленький размер, а на скорость мне наплевать (отключая, в частности, тщательно расставленные likely и unlikely), но сам результат показтелен.

          • Akon32
            /#21137056

            А кому и зачем может понадобиться убивающая кеш версия?

            Да мало ли, вдруг у кого-то процессор с чуть большим кэшем, а сеть — какой-нибудь infiniband, где счет идет на микросекунды… Это гипотетические случаи, естественно.

            • khim
              /#21137598

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

              А разработчики ядра очень не любят обсуждать гипотетические случаи.

              • Kobalt_x
                /#21138562

                Это правда, но не знаю как сейчас 3-4 года назад AFAIK один из быстрейших способов это работать без уровней ядра через dpdk не дёргая ядро для обработки пакетов вообще и многие в sdn юзали именно его

                • khim
                  /#21138596

                  В этом случае толку от скоростной функции в ядре ведь всё равно нет…

  24. nmrulin
    /#21134078 / +1

    А в холиварах я постоянно встречал аргумент, что С++ быстрее Паскаля минимум в 3 раза :-)

    • Akon32
      /#21136016

      Если сравнивать современный оптимизирующий компилятор С++ с древним компилятором паскаля/делфи — вполне реальная цифра, может быть даже больше.

  25. technic93
    /#21134080

    А можете дописать в хаскель листинг как должен выглядеть main и как запускать чтобы сравнить по простому?

    • 0xd34df00d
      /#21134156

      Никто не читает статьи Я выложил всё сюда, можете склонировать, а потом stack build && stack exec -- edit-distance-linear-bench-exe 6 +RTS -sstderr для наибыстрейшей реализации.

      • technic93
        /#21137018

        Cпасибо ссылку я нашёл но что с ней делать не знал.


        Тогда откуда это строка в таблице? И не хотите ли вы ее как бы исправить?
        C++ clang 9 323%
        Это я так понимаю на Haswell цпу? На моем Skylake там где-то 200%. Далее путем минимального перемещения s1[i] за границу цикла, что есть в хаскель версии, все ожидаемо приходит в четкие 100%.
        Более того хаскель у меня использовал дефалтный ллвм то беж llvm-8, т.е. на самом деле 100% у меня при clang-8, а 9ая версия может быстрее. В связи с этим вопрос какой ллвм используется у вас?

        • 0xd34df00d
          /#21137154

          У меня clang 9 и llvm 9. Это всё на хазвеллах, да.


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

  26. AlB80
    /#21134152

    Если в матрице по диагонали идти, то это чит?

    • 0xd34df00d
      /#21134154

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

  27. defuz
    /#21134166

    Проверьте пожалуйста эту реализацию на Rust в ваших условиях. Спасибо!

    • 0xd34df00d
      /#21134170

      Это ж с одной строкой матрицы вместо двух, да?


      0.823 секунды минимум. Впрочем, однострочные варианты что на плюсах, что на хаскеле тоже чуть быстрее (0.800-0.810 с для хаскеля).

      • defuz
        /#21134180

        Да. Но я заметил что Rust заметно проседает из-за начальной инициализации кеша:

        (0..).take(n + 1).collect()
        

        Попробуйте заменить на обычный цикл (как в моем решении), и результаты должны стать лучше.

        • 0xd34df00d
          /#21134188

          Не, плюс-минус тоже (1.026 с вместо 1.028).


          Интересно, что у вас оно влияет — оно ж делается один раз и вне цикла.

  28. Varim
    /#21134220 / +1

    0xd34df00d Я так понял что в коментах подкорректировали скорость для версий Python и C# / .net core, обновлять данные в таблицах будете?

    • 0xd34df00d
      /#21134232

      Да, но я гентушник же, сейчас компиляю numba, которая тянет llvm 8, и (снова) ноду.


      Для .NET Core не смогу обновить, правда — у меня он не работает :( Если вы скажете результаты для него и, скажем, результаты для оригинальной сишной версии (чтобы отмасштабировать), то я с радостью их добавлю.

      • Solexid
        /#21134860 / +1

        Если у вас не выходит запустить неткор на своей генте, то запускайте его же в докере, используя оффициальный контейнер.

  29. unclechu
    /#21134288

    Реквестирую вариант с Tcl.

  30. unclechu
    /#21134290

    А почему для Raku указана бесконечность? Не дождались финиша бенчмарка?

  31. oam2oam
    /#21134654 / +1

    Интересная статья-дополнение вышла… я попробовал сделать, как рекомендовал автор и вот результат, если кратко — C++ проигрывает C, C проигрывает Ada. Причем код ассемблера у всех разный

    Самое интересное — вот бы кто-нибудь сдалал тест на fortran с компилятором от Интела — думаю, что он бы порвал всех раза в два быстрее считал (по опыту, как ни извращайся, как не оптимизируй, фортран на счетных задачах ровно в 2 раза быстрее ..)

  32. Deosis
    /#21134732

    Интересное наблюдение: Автор подбирает данные, которые не влезают в кеш, но при этом не рассматривает ни одной оптимизации, чтобы сделать алгоритм кеш-френдли.
    Раньше была статья про перемножение матриц, в которой добились ускорения на порядки, учитывая размеры кешей процессора.

    • 0xd34df00d
      /#21134748

      Это тоже не вошло в пост, спасибо, что напомнили, чуть позже сделаю апдейт.


      Я пытался обрабатывать влезающими в L1 блоками (можно матрицу заполнять последовательно узкими вертикальными кусочками-ленточками, запоминая значение в последней ячейке кусочка). При малой ширине куска это даже замедлило код (а при большой скорость стремилась к представленной в посте, как и ожидается).


      У меня нет хорошей интуиции, почему код замедлялся.

  33. kyak
    /#21135422

    MATLAB:

    function main()
      s1 = char(repmat('a', 1, 15000));
      s2 = s1;
      s3 = char(repmat('b', 1, 15000));
      tic();
      fprintf('%d\n', lev_dist(s1, s2));
      fprintf('%d\n', lev_dist(s1, s3));
      exec_time = toc();
      fprintf('Finished in %.3fs\n', exec_time);
    end
    
    function d = lev_dist(s,t)
    % Levenshtein distance between strings or char arrays.
    % lev(s,t) is the number of deletions, insertions,
    % or substitutions required to transform s to t.
    % https://en.wikipedia.org/wiki/Levenshtein_distance
    
        m = length(s);
        n = length(t);
        x = 0:n;
        y = zeros(1,n+1);   
        for i = 1:m
            y(1) = i;
            for j = 1:n
                c = (s(i) ~= t(j)); % c = 0 if chars match, 1 if not.
                y(j+1) = min([y(j) + 1
                              x(j+1) + 1
                              x(j) + c]);
            end
            % swap
            [x,y] = deal(y,x);
        end
        d = x(n+1);
    end
    


    Finished in 10.801s

    См. также: blogs.mathworks.com/cleve/2017/08/14/levenshtein-edit-distance-between-strings и en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance

  34. Nagg
    /#21135530 / +1

    Очередной бессмысленный бенчмарк, после Encoding.UTF8.GetBytes для двухбайтовых строк в дотнете и аппроксимации результата по другим бенчам не стал даже читать. Особенно посмеялся с того, что во многих тестируемых языках (баунд)чеки выключены флагом.

    • 0xd34df00d
      /#21137190 / +1

      Особенно посмеялся с того, что во многих тестируемых языках (баунд)чеки выключены флагом.

      Почему? Это полностью соответствует коду на плюсах и коду на хаскеле.

      • Nagg
        /#21138094

        Почему не отключили в Моно? почему не использовали ллвм бэкенд? Вы просто так добавили без понимания платформы, кто-то посмотрит и сделает ошибочные выводы — за это я не люблю бестолковые бенчмарки. Я с отключенными баундчеками (вернее их даже не надо отключать, достаточно подсказать компилятору простым условием, а он дальше сам их вырежет) и ллвм бэком прогнал ваш цикл близко к перфомансу Си (что не мудрено раз Си в кланге использует тот же ллвм).

        • 0xd34df00d
          /#21138198 / +2

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

          • Nagg
            /#21138230

            Зачем включать то, в чём вы не потрудились хотя бы аргументы посмотреть? Бонус — не бонус, а в меня уже кинули ссылкой в стиле "смотри в 5 раз медленее азаза".

            • 0xd34df00d
              /#21138266 / +1

              Я их заведомо все не могу знать, и про это в статье тоже есть.


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


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

              • Nagg
                /#21138282

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

                • 0xd34df00d
                  /#21138316 / +3

                  Это другой вопрос. Опыт показывает, что люди как-то не всегда читают даже то, что прямо и явно написано, причем не где-то в середине текста, а в заключении.

                  • khim
                    /#21138460 / +1

                    В 90% случаев люди вообще не читают статьи. В принципе. У них есть в голове нечто, во что они искренне верят — и они сканируют статьи на предмет кусков, которые бы эту веру подтвердили.

                    Больше их ничего не волнует. Если у них есть вопрос — они не статью пойдут читать, а на StackOverflow вопрос зададут, зачем им статьи? Только чтобы почувствовать себя «крутыми».

                    • technic93
                      /#21138494

                      Печаль в том что мы идем к тому, что 90% людей не могут прочитать текст длиннее одного твита в твиттере (простите за тавтологию)

                      • khim
                        /#21138638

                        Можете успокоиться — мы давно там.

                        Так всегда было и всегда будет.

                        Просто одно время казалось, что мир устроен по-другому, потому что Интернетом пользовались только «яйцеголовые»…

                        А потом — туда перебрались все. Вы задумайтесь вот над чем: 10% жителей США (взрослых, старше 18 лет) — умеют читать и писать на уровне третьего класса… и не более того.

                        Думаете ситуация в России или других странах сильно лучше?

                        • DaylightIsBurning
                          /#21140852

                          10% жителей любой страны с населением >100тыс. имеют IQ <80, фактически считаются умственно отсталыми и, обычно, не совсем справляются с начальной школой.

                          • khim
                            /#21141692 / +1

                            Да, но это не значит, что оставшиеся 90% все прям поголовно профессора.

              • technic93
                /#21138444

                Ошибки нету, просто теперь вам надо сидеть и в течении следующего месяца прогонять все коды которые предоставлены тут в комментариях и обновлять табличку (шутка). Ну вообще да идея с пулл реквестами и скриптами которые это все будут собирать и выдавать репорты на любом железе годная.

          • Siemargl
            /#21138954

            Заметь, сколько % тут обсуждают Хаскель? LOL

            • 0xd34df00d
              /#21138972

              Вот это одна из двух вещей, от которых мне тут бомбит слегка.

              • technic93
                /#21138992

                Дык тут на нем пишут пару интузиастов. Тут тригернул ты мало того что сишников так еще и шарпистов с жавистами которые заполонили все коменты :)

                • 0xd34df00d
                  /#21139028

                  А вот чего джависты триггерятся, непонятно — джава там в топчике вообще. Я очень сильно удивился, когда ее запустил.

                  • Siemargl
                    /#21139098

                    Ну с шарпом у тебя точно пока фейл. Моно говно во всех тестах, а НЕТ от МС не сильно хуже Явы, а местами и лучше (быстрее грузится, но хуже джит).

                    • 0xd34df00d
                      /#21139134

                      У меня, хуже того, пока не завелся .net core sdk, там что-то оверлей недоступен для моих линуксов, руками софт ставить не комильфо, а ебилды писать для этого я что-то не хочу. Сегодня вот ещё поковыряю, чего там с оверлеем.

                      • Siemargl
                        /#21139168 / +1

                        Где то пробегал совет прогнать тесты в докере или в снапе с НЕТом.

                        Но шутка про линуксоида «я не могу установить» выглядит смешно....=)

                        • 0xd34df00d
                          /#21139312 / +2

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

  35. Lau
    /#21135604 / +10

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

    • technic93
      /#21136008

      потом берем другие языки и пишем код одной рукой иногда надолго закрывая глаза

      Первый позитивный комментарий

    • khim
      /#21136576

      Тем не менее все такие статьи кончаются одним и тем же: выясняется что идеоматичный код на C++ неизменно медленнее идеоматичного же кода на C.

      То есть zero-cost abstractions — всё ещё нифига не zero-cost. Впрочему сейчас они уже в пределах 20-30%, похоже… но всё равно неприятно.

      • Lau
        /#21136764

        Закон сохранения энергии… она была потрачена на дополнительные уровни абстракции. Но опять же, пример из статьи для меня не показателен, нужно безопасней и читабельно — пишем С++, нужно быстро и оптимально — делаем вставки С кода или специально оптимизированного С++, избегая стандартной библиотеки и хип менеджера.
        Все эти сравнения это чистой воды PR и войны за популярность с препрятанным роялем в кустах и еще до написания статьи известным результатом ибо цель это воздействие на сообщество и его управляемая реакция, а не инжиниринг и действительно объективное сравнение

        • khim
          /#21136806 / +3

          Ну почему же «заранее известный результат-то». Я вот для себя сделал аж три интересных октрытия:
          1. initializer_list всё ещё не всегда изводится clangом
          2. Numba крута (надо будет поиграться).
          3. «Безопасный char» проще всего сделать через типизированный enum

          Вполне приятный выхлоп с одной статьи…

          • Lau
            /#21136964

            Согласен, есть интересные моменты в статье и в целом это очень граммотный пример пропаганды — не просто в чем то пытаются убедить, а как бы делают вид, что не пытаются, показывают интересные трюки, а параллельно внедряя идею. В этом и отличие от тупой пропаганды «хаскель лучше Х, тчк!»
            Статья начинается с «У меня тут случайно код на хаскеле получился быстрее аналогичного кода на C++. Иногда — на 40%.»
            И дальше очень много работы для «случайного» результата, куча отпимизаций хаскеля, очень много учебных хинтов для новичков и разумеется, результат тот что нужен.
            Это классика умной пропаганды через вброс, доверие и заинтересованность.
            Помнится англичане еще во время мировой в пику немцам выдавали честные сводки с фронтов, настолько честные что немцы им доверяли больше чем своит… мастерски примешивая нужные им выводы в правильной пропорции.

            Если цель статьи это инжинириг сравнение делается многофакторное, с участием специалистов из каждой области которые умеют готовить яву, С++, питон, хаскель и прочие. Замеры всех потребляемых ресурсов, времени разработки, сбоев, надежности, каждый старается выдать максимально оптимальный код из своей области.
            Плюс правильная постановка задачи где не сравнивается несколько сотен ассеблерных инструкций которые у одного языка удачно ложаться на пайплайны процессора.
            Что уж далеко ходить мы в свое время развлекались на С/С++ и один и тот же код у разных людей получался в 30 раз быстрее/медленнее, просто потому что кто-то знает как это утоптать, а кто-то еще нет. 30 раз это не погрешность :)
            Поэтому для меня эта статья умелая провокация с хорошо установленной целью :) Автор молодец :)

            • 0xd34df00d
              /#21137214 / +1

              И дальше очень много работы для «случайного» результата, куча отпимизаций хаскеля

              Которая заняла всего час.


              очень много учебных хинтов для новичков и разумеется

              Эм, да. И в этом смысл статьи — поделиться информацией о том, какие действия как влияют на код.


              результат тот что нужен

              Вернее, тот, что был анонсирован. Другое дело, что если бы результат был сильно другим, то статьи (или сравнения с C и C++, по крайней мере) не было бы. И про это в статье тоже есть :)


              Замеры всех потребляемых ресурсов, времени разработки, сбоев, надежности, каждый старается выдать максимально оптимальный код из своей области.

              Как вот измерить то, что основной проект, где это будет использоваться, у меня на хаскеле, а с FFI в плюсы я нагеморроился куда больше, чем с этими всеми оптимизациями вместе взятыми?

              • Lau
                /#21137264

                Которая заняла всего час.

                Вы очень производительны, чтоб за час разработать тесты, сделать все замеры, написать статью и отвечать в комментах :)
                Не поймите меня не правильно, я без претензии к статье, это хорошая работа и хорошая популяризация.
                Как вот измерить то, что основной проект, где это будет использоваться, у меня на хаскеле, а с FFI в плюсы я нагеморроился куда больше, чем с этими всеми оптимизациями вместе взятыми?

                Интрументы, языки просто инструменты и очень много субъективизма который искажает наши оценки и как видите сколько людей высказалось :) Потому что задеваются струнки которые не являются частью нашего неокортекса, а лежат в древних областях нашего мозга :)

                • 0xd34df00d
                  /#21137782 / +1

                  Вы очень производительны, чтоб за час разработать тесты, сделать все замеры, написать статью и отвечать в комментах :)

                  Ну, если серьёзно, тут по коммитам всё видно, основная работа вся 30-го ноября была сделана.


                  Впрочем, там же видно, что я немного соврал — первые два варианта из этого поста я даже и не делал, так как было понятно, что они проиграют (а зря — чистая реализация без мутабельности в ST оказалась на удивление хороша).


                  Интрументы, языки просто инструменты и очень много субъективизма который искажает наши оценки и как видите сколько людей высказалось :) Потому что задеваются струнки которые не являются частью нашего неокортекса, а лежат в древних областях нашего мозга :)

                  Отож!


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


                  Рациональность, в конце концов — это не про неверие в эльфов, а про неверие в эльфов в мире, где эльфов нет, и веру в эльфов в мире, где эльфы есть.

    • 0xd34df00d
      /#21137184 / +1

      Эх, вот не надо было мне добавлять остальные языки, а надо было оставить те два.


      Рецепт холиварной статьи прост — берем один язык и тщательно оптимизируем пример на нем

      Не тщательно, из хаскеля тоже можно еще несколько процентов выжать относительно легко.

  36. Tanriol
    /#21135718 / +1

    А добавьте пожалуйста для Rust опцию -C target-cpu=native для более честного сравнения с C(++). На моём Skylake она снижает время работы приведённого кода с 0.65 секунды до 0.55.
    (update: вижу, выше уже предлагали, но поиск по Rust тот комментарий не нашёл ввиду русскоязычного написания)

    • 0xd34df00d
      /#21137220

      Окей, сегодня вечером перепроверю, спасибо.

  37. Sild
    /#21135766 / +1

    Мне почему-то не понравился тут swap массивов
    просто заменив на работу с указателями получилось срезать ещё почти 20%
    (запуски произвоизводил бесконечным циклом, результат воспроизводим)

    13:24:02 dkorchagin@desktop:/tmp$ git diff test.cpp test2.cpp
    diff --git a/test2.cpp b/test.cpp
    index 286bd4a..f954792 100644
    --- a/test2.cpp
    +++ b/test.cpp
    @@ -26,25 +26,28 @@ lev_dist(const std::string &s1,
     
         auto v1 = v0;
     
    +    auto v0_ptr = &v0;
    +    auto v1_ptr = &v1;
    +
         for (size_t i = 0; i < m; ++i) {
    -        v1[0] = i + 1;
    +        v1_ptr->operator[](0) = i + 1;
     
             for (size_t j = 0; j < n; ++j) {
    -            const auto subst_cost = (ca1[i] == ca2[j]) ? v0[j] : (v0[j] + 1);
    -            const auto del_cost = v0[j + 1] + 1;
    -            const auto ins_cost = v1[j] + 1;
    +            const auto subst_cost = (ca1[i] == ca2[j]) ? v0_ptr->operator[](j) : (v0_ptr->operator[](j) + 1);
    +            const auto del_cost = v0_ptr->operator[](j + 1) + 1;
    +            const auto ins_cost = v1_ptr->operator[](j) + 1;
     
                 // std::min({ subst_cost, del_cost, ins_cost }) is slow.
    -            v1[j + 1] = std::min(subst_cost, del_cost);
    -            if (ins_cost < v1[j + 1]) {
    -                v1[j + 1] = ins_cost;
    +            v1_ptr->operator[](j + 1) = std::min(subst_cost, del_cost);
    +            if (ins_cost < v1_ptr->operator[](j + 1)) {
    +                v1_ptr->operator[](j + 1) = ins_cost;
                 }
             }
     
    -        std::swap(v0, v1);
    +        std::swap(v0_ptr, v1_ptr);
         }
     
    -    return v0[n];
    +    return v0_ptr->operator[](n);
     }
     
     int
    13:21:29 dkorchagin@desktop:/tmp$ clang++ -std=c++17 -O3 test2.cpp 
    13:20:37 dkorchagin@desktop:/tmp$ while true; do ./a.out; done
    Finished in 0.492s
    
    13:21:29 dkorchagin@desktop:/tmp$ clang++ -std=c++17 -O3 test1.cpp 
    13:21:32 dkorchagin@desktop:/tmp$ while true; do ./a.out; done
    Finished in 0.579s
    


  38. glockbender
    /#21135828

    Уточнение ради уточнения:
    Для java прогнал для 20000 элементов изменив циклы на классический for со счетчиком внутри.
    Без данной замены время приблизительно не отличалось от указанного в статье (около 50-70 мс)
    macOS Mojave 10.14.6
    java 12.0.2-zulu

    Код:

    Заголовок спойлера
    public static long levDist(byte[] s1, byte[] s2)
        {
            int m = s1.length;
            int n = s2.length;
    
            // Edge cases.
            if (m == 0) {
                return n;
            } else if (n == 0) {
                return m;
            }
    
            long[] v0 = new long[n+1];
            long[] v1 = v0.clone();
    
            for (int i = 0; i < s1.length; i++) {
                v1[0] = i + 1;
    
                for (int j = 0; j < s2.length; j++) {
                    long substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
                    long delCost = v0[j + 1] + 1;
                    long insCost = v1[j] + 1;
    
                    v1[j + 1] = Math.min(substCost, delCost);
                    if (insCost < v1[j + 1]) {
                        v1[j + 1] = insCost;
                    }
                }
    
                long[] temp = v0;
                v0 = v1;
                v1 = temp;
            }
    
            return v0[n];
        }

  39. KvanTTT
    /#21136138 / +1

    А давайте теперь возьмем оптимальные коды и методики замеров от тех, кто разбирается в языках, объединим результаты и посмотрим кто кого быстрее?

    • euroUK
      /#21136164

      Еще бы и железо одинаковое. А то я на работе на ноуте i5 сижу, а дома Xeon 24 ядра.

      • KvanTTT
        /#21136234

        Так я и говорю, нужно чтобы кто-то собрал все и потестил на одном и том же железе. А то результаты у разных участников невозможно сравнивать.

        • technic93
          /#21136242

          Ну так насколько я понимаю автор тестит на одном железе.

          • KvanTTT
            /#21137006

            Но автор не разбирается в нюансах разных языков и их методиках тестирования :)

            • Navi91
              /#21142636 / +1

              Надо репу на gihub'e создать
              Знатоки платформ будут контрибьютить :)

  40. RekGRpth
    /#21136228 / +1

    заголовок «Быстрее, чем C++; медленнее, чем PHP»
    а что значит вторая часть заголовка «медленнее, чем PHP»?
    первая часть, как я понимаю, значит «хаскель Быстрее, чем C++»
    тогда вторая — «хаскель медленнее, чем PHP»? или что?

    • khim
      /#21136652

      Это такая завлекалочка. Raku (бывший Perl 6) у него медленнее PHP вышел.

      Но это вообще такой специальный язык для демонстрации того, как можно получить полное дерьмо, руководствуясь исключительно благими намерениями при разработке языка.

      Может лет через 20-30 мы и увидим вторую часть: как дерьмо превратить-таки в конфетку…

      • RekGRpth
        /#21141058

        да это я к тому, что
        если «хаскель медленнее, чем PHP»,
        то «PHP быстрее, чем хаскель»
        но «хаскель Быстрее, чем C++»
        и тогда «PHP быстрее, чем C++»
        тогда как в статье наоборот!

        • technic93
          /#21141140

          Вы как буд-то первый кликбэйтный заголовок на хабре увидели.

  41. kryvichh
    /#21137098

    Вот код с лёгкими оптимизациями для Delphi, без ассемблера и арифметики указателей, который работает быстрее исходного кода, приведённого у вас для Pascal. У меня примерно на 30%. Для использования в боевой программе лучше конечно переписать часть или всё на ассемблере.

    function LevenshteinDistance2(const S1, S2: RawByteString): UInt32;
    var
      len1, len2, i1, i2: NativeUint;
      c1: AnsiChar;
      v0, v1: TArray<UInt32>;
    begin
      len1 := Length(S1);
      len2 := Length(S2);
      if len1 = 0 then
        Exit(len2)
      else if len2 = 0 then
        Exit(len1);
      SetLength(v0, len2+1);
      for i1 := 0 to len2 do
        v0[i1] := i1;
      v1 := Copy(v0, 0, len2+1);
      for i1 := 1 to len1 do begin
        c1 := S1[i1];
        v1[0] := i1;
        for i2 := 1 to len2 do begin
          var cost1 := v0[i2-1] + UInt32(c1 <> S2[i2]); // Cost of substitution
          var cost2 := v0[i2] + 1; // Cost of deletion
          if cost1 > cost2 then
            cost1 := cost2;
          cost2 := v1[i2-1] + 1; // Cost of insertion
          if cost1 < cost2 then
            v1[i2] := cost1
          else
            v1[i2] := cost2
        end;
        var temp := v0;
        v0 := v1;
        v1 := temp;
      end;
      Result := v0[len2]
    end;
    

    • kryvichh
      /#21137474

      И ещё вариант на Delphi, немного задействовал поинтеры. +17% к скорости предыдущей версии без поинтеров, +42% к исходной версии в статье. Но -кроссплатформенность.

      function LevenshteinDistance3(const S1, S2: RawByteString): UInt32;
      
        procedure Swap(var P1, P2); inline;
        var
          temp: Pointer;
        begin
          temp := Pointer(P1);
          Pointer(P1) := Pointer(P2);
          Pointer(P2) := temp
        end;
      
      var
        len1, len2, i1: NativeUint;
        c1: AnsiChar;
        v0, v1: TArray<UInt32>;
      begin
        len1 := Length(S1);
        len2 := Length(S2);
        if len1 = 0 then
          Exit(len2);
        if len2 = 0 then
          Exit(len1);
        SetLength(v0, len2+1);
        for i1 := 0 to len2 do
          v0[i1] := i1;
        v1 := Copy(v0, 0, len2+1);
        for i1 := 1 to len1 do begin
          c1 := S1[i1];
          v1[0] := i1;
          var p0: PUInt32 := @v0[0];
          var p1: PUInt32 := @v1[0];
          var ps2: PAnsiChar := @S2[1];
          while ps2^ <> #0 do begin
            var cost1 := p0^ + UInt32(c1 <> ps2^); // Cost of substitution
            Inc(p0);
            var cost2 := p0^ + 1; // Cost of deletion
            if cost1 > cost2 then
              cost1 := cost2;
            cost2 := p1^ + 1; // Cost of insertion
            Inc(p1);
            if cost1 < cost2 then
              p1^ := cost1
            else
              p1^ := cost2;
            Inc(ps2)
          end;
          Swap(v0, v1);
        end;
        Result := v0[len2]
      end;
      

    • kryvichh
      /#21138858

      Заодно уже, чтоб 2 раза не бегать по Гуглу: Calculation of the Damerau–Levenshtein distance, an optimized algorithm written in the pure Delphi language is here:

      Spoiler header
      function DamerauLevenshteinDistance(const S1, S2: RawByteString): UInt32;
      var
        len1, len2, i1, i2: NativeUint;
        c1, c2, prevC1, prevC2: AnsiChar;
        v_1, v0, v1: TArray<UInt32>;
      begin
        len1 := Length(S1);
        len2 := Length(S2);
        if len1 = 0 then
          Exit(len2);
        if len2 = 0 then
          Exit(len1);
        SetLength(v_1, len2+1);
        SetLength(v0, len2+1);
        for i1 := 0 to len2 do
          v0[i1] := i1;
        v1 := Copy(v0, 0, len2+1);
        prevC1 := #0;
        for i1 := 1 to len1 do begin
          c1 := S1[i1];
          v1[0] := i1;
          prevC2 := #0;
          for i2 := 1 to len2 do begin
            c2 := S2[i2];
            var cost := UInt32(c1 <> c2);
            var cost1 := v0[i2-1] + cost; // Cost of substitution
            var cost2 := v0[i2] + 1; // Cost of deletion
            if cost1 > cost2 then
              cost1 := cost2;
            cost2 := v1[i2-1] + 1; // Cost of insertion
            if cost1 > cost2 then
              cost1 := cost2;
            if (c1 = prevC2) and (prevC1 = c2) then begin
              cost2 := v_1[i2-2] + cost; // Cost of transposition
              if cost1 > cost2 then
                cost1 := cost2
            end;
            v1[i2] := cost1;
            prevC2 := c2
          end;
          var temp := v_1;
          v_1 := v0;
          v0 := v1;
          v1 := temp;
          prevC1 := c1
        end;
        Result := v0[len2]
      end;
      

      • Siemargl
        /#21138986

        Паскаль прекрасный учебный язык.

        Но на практике все спотыкается о то, что никто не хочет на нем писать.

        Он может прекрасно оптимизироваться, но последние версии GPC от 2007 года, а FPC и Дельфи сложно назвать современными оптимизирующими компиляторами (

        Ну и цена лицензии на Д-Архитект это просто гвоздь.

        Я бы смотрел на миграцию в Го, там похожий то стилю язык.

        • khim
          /#21139040

          Ну и цена лицензии на Д-Архитект это просто гвоздь.
          А оно для всех экзотических языков примерно на одном уровне. Недавно только обнаружил, что Visual Age for Smalltalk во-первых ещё продаётся, а во-вторых — вот по такой вот цене.

          • Siemargl
            /#21139060

            Такой?

            Call or Email for Pricing
            Впрочем за Смаллток всегда просили от 5к$ и потому в том числе он и загнулся.

            Ада чудом избежала такой судьбы получив GNUada

            • 0xd34df00d
              /#21139094

              Вы в аде тут все шарите, что ли?


              Если да, то я слышал, что в агду завезут завтипы в следующем релизе стандарта. Правда, ссылка вела на статью в Вики, а там я ничего не нашел. Это правда или какая-то ерунда?,

        • kryvichh
          /#21139106

          Для бизнес-приложений под Windows оптимизации достаточно (+ассемблер для узких мест). Библиотека VCL вылизана донельзя за долгие годы, FireMonkey тоже юзабельным стал. Так что если писать коммерческие программы под Windows, можно часто не обновлятся.

          Ну а учиться и новые фичи можно трогать в бесплатном Delphi Community Edition. Вот ждём вскоре 10.4, с обещанными давно Custom Managed Records. Можно будет делать мощные вещи, не теряя в производительности. Ещё раньше были разговоры про LLVM-бэкэнд в компилятор под Windows, но пока это заглохло. Пока он задействован только в компиляторе для iOS, Android и Linux. А так — жизнь продолжается.

          • Siemargl
            /#21139124

            Лицензия на Community Edition не позволяет никакой коммерческой деятельности, если ты не Диоген конечно. Файрманки и платформы кроме вин настолько сырые, что без обновлений никак.

            Впрочем, относительно этой статьи это оффтоп. А касательно — оптимизатор в Дельфи средненький. Но, кстати, можно нормировать тесты относительно С-Билдера — там хоть LLVM. Посмотрим.

            • kryvichh
              /#21139136

              Я ссылку выше кидал, есть и для Delphi LLVM-based compilers, кроме Windows. Программы, написанные на Community, можно продавать, но там ограничение по сумме за год. Поэтому коммерческая разработка на CE только для стартапов. (Иначе в CE не было бы смысла для Embarcadero, ведь по фичам эта редакция эквивалента Pro). Насчёт сырости спорить не буду, т.к. для меня Windows основная платформа, и здесь всё тип-топ.

              • Siemargl
                /#21139158

                Коммунити версия с ограничением дохода 5k$ в год. См.Диоген.

                Pro теперь без клиент сервера, который всегда был киллер фичей.

                LLVM-based compilers, кроме Windows… для меня Windows основная платформа
                ну ОК, что сказать.

                Ешьте сами

                • kryvichh
                  /#21139248 / +1

                  Если за год заработать на продаже программ написанных на Delphi CE $5000, придётся отдать $1650 за новую лицензию Pro. Нет — значит нет. Мне кажется, для стартапов и некоммерческих организаций нормально. По сравнению с тем, что было раньше — небо и земля. Я помню Delphi XE2 Starter Edition: обрезанная версия, без исходников библиотек VCL и FireMonkey, продавалась за деньги. И то люди на ней писали клиент-серверные приложения, прикручивая сторонние библиотеки. А про проблемы, связанные с развитием и поддержкой Delphi я и сам знаю.

                  Что касается оптимизации, ну вот я, немного посидев, ускорил выложенную в статье реализацию на 40%. А есть более быстрые алгоритмы для решения этой задачи. Например, можно попробовать вот эту реализацию для алгоритма Дамерау-Левенштейна. Там хранится только одна строка матрицы расстояний, а не две, добавлены оптимизации для похожих строк.

                  • khim
                    /#21139318

                    А есть более быстрые алгоритмы для решения этой задачи.
                    Вы думаете на других языках невозможно реализовать «более быстрые алгоритмы»? Возможно, конечно. А ведь по сути Delphi — ближе к Ada, чем к C++… должно быть быстрее.

                    Впрочем всё это фигня: разница в скорости является проблемой, когда она 10x или там 100x. Разница в 10-15% ничего не решает вообще и даже 50% — это терпимо.

                    Мне кажется самая большая проблема Delphi — они «потеряли хайп». Было время, когда во всех в школах и институтах Pascal учили поголовно. Вот в те времена Delphi мог бы взлететь — достаточно легко.

                    А сегодня учат Python, С++ или Java. В этом беда. И непонятно что с этим можно сделать.

                    А цены и даже скорость — это как раз не так критично.

                    • kryvichh
                      /#21141152

                      Можно много писать что было сделано не так, но надо исходить из того, что есть.

                      Возвращаясь к оптимизации (по теме) компилятору Delphi для Windows не хватает более широко использования регистров процессора. Практически не используется EBX. Большинство операций выглядят так: читаются данные из стека в EAX, обрабатываются, и тут же сбрасываются обратно в стек. Иногда бывает два подряд идущих
                      mov [ebp-$4c],eax
                      mov eax,[ebp-$4c]

                      Поэтому обработки на Delphi всегда чуть сзади хорошо оптимизированных C-модулей. С другой стороны, кэш L1 в современных процессорах, где обычно обитает стек текущей процедуры, очень быстрые. Вот здесь пишут про доступ в 4 такта. И размер его всё время растёт, в моём AMD Ryzen 5 3600 это 384КБ. + паралельное исполнение команд и предсказание ветвлений в процессоре. Поэтому где недоработал компилятор — выручает современный процессор, и в целом разница по скорости с C есть, но не критична.

                      • khim
                        /#21141746

                        Это где вы L1 кеш растущий увидели? Или это вы просуммировали размеры L1 кеша для всех ядер?

                        Наоборот — размер L1 кеша это [почти] константа. Вот как появились 16K кеша примерно четверть века назад — так и ходит индустрия между тремя размерами: 16K/32K/64K… причём в Zen2 как раз обратно на 32K вернулись.

                        Но и если бы там шла речь про L1 — то Delphi отставал бы от C++ на порядок (4 такта плюс 2-3 операции за такт). На самом деле в современных процессорах есть специальные схемы для ускорения подобного кода, так как он был весьма характерен для вообще всех старых компиляторов.

                        Возвращаясь к оптимизации (по теме) компилятору Delphi для Windows не хватает более широко использования регистров процессора.
                        Если то, о чём вы пишите, правда — то ему не хватает вообще хоть какого-то оптимизатора. Потому что подобные вещи уже даже в самых ранних версиях GCC, треть века назад, обрабатывались прилично — с очень редкими случаями такого ужаса, как вы описываете.

                        То есть это как раз тот случаяй, когда чинить бессмысленно — нужно выкидывать и переписывать. Ну или прикрутить LLVM…

                        • kryvichh
                          /#21141806 / -1

                          Конечно 384КБ L1 на процессор. Я и пишу, надежда насовременный процессор.

                          Когда-то была идея написать типа пост-компилятора конкретно под программы на Delphi 32-bit. Передаём утилите EXE, MAP файлы, и указываем процедуры в узких местах, которые требуется оптимизировать. А она находит все такие участки как выше пример, и забивает лишнее NOP или XOR или другой дешёвой операцией. Там ещё и другие паттерны можно выловить, которые прям в глаза бросаются. Вот как пример:
                          mov edx,[ebp-$18]
                          mov ecx,[ebp-$18]

                          Или вот, cost1 уже загружена в регистр eax, можно переиспользовать:
                          uLevenshtein.pas.199: cost1 := cost2
                          mov eax,[ebp-$40]
                          mov [ebp-$3c],eax
                          uLevenshtein.pas.201: v1[i2] := cost1;
                          mov eax,[ebp-$2c]
                          mov edx,[ebp-$1c]
                          mov ecx,[ebp-$3c]
                          mov [eax+edx*4],ecx

                          Интересно, насколько можно было бы ускорить обработку…

                          • 0xd34df00d
                            /#21142618

                            Конечно 384КБ L1 на процессор.

                            На процессор, не на ядро. Если у вас алгоритм однопоточный и живёт на одном ядре, то кеши на остальных ядрах вам никак не помогут, увы.

                            • kryvichh
                              /#21142892

                              Это как бы само собой разумеется.

  42. Apoheliy
    /#21137168

    Попробовал ускорить код на C++: использовать vector и избавиться от std::min.

    Исходный вариант: 100% (4733 мс)
    Вариант с заменой string на vector: 85,6% (4051 мс)
    Вариант с заменой на вектора и заменой std::min на два if-а: 50,6% (2394 мс).

    Т.е. парой действий в рамках C++ можно ускорить код на 97,7%, почти в 2 раза.

  43. St_one
    /#21137228

    Можно добавить прогрев JVM в тест по Java? Просто несколько прогонов теста подряд. У меня результаты такие:
    0
    15000
    Finished in 0,705s
    0
    15000
    Finished in 0,588s
    0
    15000
    Finished in 0,425s

  44. CrafterKolyan
    /#21137232

    На самом деле при подсчёте расстояния Левенштейна необязательно заводить второй массив. Можно вполне справиться с одним массивом и ячейкой памяти на предыдущий диагональный. Выглядит это примерно следующим образом (здесь правда ещё идёт шаблонизация, чтобы можно было использовать не только для строк, но и для векторов):

    #include <algorithm>
    #include <vector>
    
    template<typename T>
    typename T::size_type LevenshteinDistance(const T &source,
                                              const T &target) {
        if (source.size() > target.size()) {
            return LevenshteinDistance(target, source);
        }
    
        using TSizeType = typename T::size_type;
        const TSizeType min_size = source.size(), max_size = target.size();
        std::vector<TSizeType> lev_dist(min_size + 1);
        std::iota(lev_dist.begin(), lev_dist.end(), 0);
    
        for (TSizeType j = 1; j <= max_size; ++j) {
            TSizeType previous_diagonal = lev_dist[0];
            TSizeType previous_diagonal_save;
            ++lev_dist[0];
    
            for (TSizeType i = 1; i <= min_size; ++i) {
                previous_diagonal_save = lev_dist[i];
                if (source[i - 1] == target[j - 1]) {
                    lev_dist[i] = previous_diagonal;
                } else {
                    lev_dist[i] = std::min(std::min(lev_dist[i - 1], lev_dist[i]), previous_diagonal) + 1;
                }
                previous_diagonal = previous_diagonal_save;
            }
        }
    
        return lev_dist[min_size];
    }

    • 0xd34df00d
      /#21137240

      Есть на самом деле ещё более эффективные алгоритмы, но это уже совсем другая история.

  45. ComatoZZZ
    /#21137844

    С Java получилось заметно быстрей если использовать обычные циклы, тестировал с помощью JMH
    Benchmark Mode Cnt Score Error Units
    JMH.test avgt 5 575.046 ± 26.305 ms/op
    Против
    Benchmark Mode Cnt Score Error Units
    JMH.test avgt 5 982.166 ± 63.062 ms/op

    Заголовок спойлера
    public static long levDist(byte[] s1, byte[] s2) {
            int m = s1.length;
            int n = s2.length;
    
            // Edge cases.
            if (m == 0) {
                return n;
            } else if (n == 0) {
                return m;
            }
    
            long[] v0 = new long[n + 1];
            for (int i = 0; i < n + 1; i++) {
                v0[i] = i;
            }
            long[] v1 = v0.clone();
    
            for (int i = 0; i < s1.length; i++) {
                v1[0] = i + 1;
                for (int j = 0; j < s2.length; j++) {
                    long substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
                    long delCost = v0[j + 1] + 1;
                    long insCost = v1[j] + 1;
                    v1[j + 1] = Math.min(substCost, delCost);
                    if (insCost < v1[j + 1]) {
                        v1[j + 1] = insCost;
                    }
                }
                long[] temp = v0;
                v0 = v1;
                v1 = temp;
    
            }
            return v0[n];
        }

  46. PsyHaSTe
    /#21138330 / +2

    Не успел прочитать все комментарии, поэтому поправлю шарповый код (поправил баг с неправильным заполнением v0 и v1, за основу взял вариант из раста):


    public static Int32 LevDist(byte[] s11, byte[] s22)
    {
        var n = s22.Length;
        // Edge cases.
        if (s11.Length == 0)
        {
            return s22.Length;
        }
    
        if (s22.Length == 0)
        {
            return s11.Length;
        }
    
        var s1 = s11.Select(x => (int) x).ToArray();
        var s2 = s22.Select(x => (int) x).ToArray();
    
        var v0 = new Int32[n + 1];
        var v1 = new Int32[n + 1];
    
        for (int i = 0; i < v0.Length; i++)
        {
            v0[i] = i;
        }
    
        for (int i = 0; i < v1.Length; i++)
        {
            v1[i] = i;
        }
    
        for (var i = 0; i < s11.Length; i++)
        {
            v1[0] = i + 1;
    
            for (var j = 0; j < s22.Length; j++)
            {
                var substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
                var delCost = v0[j + 1] + 1;
                var insCost = v1[j] + 1;
    
                v1[j + 1] = Math.Min(substCost, delCost);
                if (insCost < v1[j + 1])
                {
                    v1[j + 1] = insCost;
                }
            }
    
            (v0, v1) = (v1, v0);
        }
    
        return v0[n];
    }

    Изначальная версия: 0.789 секунд
    Версия с выравниванием: 0,635 секунд — видимо, джиту трудно работать с невыровненными данными. Поэтому копируем байтовый массив в интовый
    Версия с инлайном длины массива: 0.53 секунд — сохраннение длины массива известная деоптимизация. Сишарп выкидывает проверки только если видит длину массива. Если Сохранить её в переменную — проверка вернется.


    Ну и желательно включить галку x64 при сборке, потому что х86 почти в 1.5 раза медленнее.


    Вариант на расте на моей машине прогняется за 0.456 секунд. Таким образом вариант на шарпе отрабатывает на 16% дольше раста, ну и следовательно равняется 144% от плюсового эталона.




    Пока загорелся оптимизацией шарпа, забыл сказать — спасибо за материал! Отличный слог, и глубокая проработка. Бенчи на всех языках так вообще бесподобны.

    • 0xd34df00d
      /#21138544

      Спасибо!


      Вечером попробую ваш вариант, плюс попробую таки адекватно завести .NET Core на моей машине. Если заведется, то как им пользоваться и что нажимать, чтобы собрать все как надо с оптимизацией?


      Обратите внимание, что для сравнения времени ваши результаты надо либо перенормировать на длину а 20 тыщ (учитывая, что алгоритм квадратичный), либо просто в коде поменять 15 на 20 везде.

      • mayorovp
        /#21139728

        Тут в комментариях уже писали же: dotnet run -c release

        • PsyHaSTe
          /#21140912

          Проблема в том что bash: dotnet: command not found, и поставить в 2 клика из пакетного менеджера на ОСи человека не представляется возможным.

          • medvedevia
            /#21141786

            mkdir /tmp/app
            docker run -it --rm -v /tmp/app:/app mcr.microsoft.com/dotnet/core/sdk:3.1 bash
            cd /app
            dotnet new console
            dotnet run -c release 
            exit

            • PsyHaSTe
              /#21141822

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

              • medvedevia
                /#21141856 / +1

                dotnet build -c release -r linux-x64

                потом можно запустить готовое приложение без докера:


                /tmp/app/bin/release/netcoreapp3.1/linux-x64/app

              • mayorovp
                /#21141934

                Он может внести погрешности в системные вызовы, но не в вычислительную задачу.

          • mayorovp
            /#21141920 / +1

            Пожалуйста, следите кто и на что отвечает. Я отвечал на вот этот комментарий:


            Если заведется, то как им пользоваться и что нажимать, чтобы собрать все как надо с оптимизацией?

            Если заведется, то у него таки будет команда dotnet.

            • PsyHaSTe
              /#21142126

              Да. пропустил этот момент. Спасибо.

      • PsyHaSTe
        /#21140906

        Кстати раст я ведь тоже гонял на 15 тыщах, так что пропорция сохраняется.

  47. arthy
    /#21142630

    Если в коде на Julia сделать пару изменений, то на моей машине время выполнения падает раза в 2:
    1. Убрать аннотации типов
    2.

    codeunits(...)
    на
    Int64.(codeunits(...))

    3.
    (i, ...) in enumerate(...)
    на
    i in 1:length(...)


    Не знаю почему последний пункт влияет, компилятор почему то не до конца оптимизирует.

  48. GreenBee
    /#21143232

    Однажды в универе (2-ой курс) нам задали задачку — реализовать какой-то метод шифрования (уже не помню какой точно), где в частности использовалось побитовое сложение.
    Я реализовал первый вариант на VB6. Работало очень медленно.
    Тогда я решил, что можно написать библиотеку на С++ и вызвать ее из VB6. Этот вариант работал значительно быстрее, но в процессе написания я выяснил, что можно и на VB6 переписать так, чтобы работало быстро — и переписал, получив скорость, почти идентичную с С++ библиотекой.
    Фишка была в том, что в первой версии на VB6 вместо операции побитового сложения я вручную переводил каждый символ в строку из нулей и единиц, вручную же складывал, а потом преобразовывал обратно. Естественно это работало очень медленно.

    К чему это я? Прежде чем сравнивать скорость работы различных ЯП, стоит убедиться, что код на них одинакового качества.