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

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


    У меня тут случайно код на хаскеле получился быстрее аналогичного кода на 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 с).

    Поделиться публикацией

    Похожие публикации

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 410

      +7
      Главное — правильно померять! =)
        0
        Ага, компилятором Intel)
        На самом деле, вопрос «какой код быстрее?» имеет больше прикладной вопрос, чем реальный. В реальности начинают с вопроса «какой разработчик дешевле?» )
        +8
        Включение галки Optimize Code в Net Core 3.1 ускоряет выполнение в 4 раза на моём i7-4790 (0,9с против 3.6с)
        Кроме того C# используют безопасное обращение к массиву.
          0

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


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

            0
            Доберусь домой сравню у себя на машине с растом.
              +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");
                      }
                  }
              }


              Unsafe версию не выкладываю — она работает примерно так же. Видимо из-за необходимости пинить указатель, или ещё какие-то накладные расходы вылазят.

              пс. кстати у вас в описании теста указан размер строки 20000, а в бенчах везде 15000. Это так задумано?
                0
                Не только, в коде С++ там тоже 20000, а во всех остальных языках 15000 даже в С, что как бы намекает.
                  +3
                  что как бы намекает.

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


                  Код для всех примеров сравнивает строки длиной 15 тысяч символов, а не 20, однако числа перенормированы для длины в 20 тысяч символов.
                    –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];

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

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

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

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


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

                            0

                            А размеры…


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

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

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

                                C++
                                #include <chrono>
                                #include <cstdio>
                                #include <numeric>
                                #include <string>
                                #include <vector>
                                
                                static long
                                lev_dist(const std::string &s1,
                                         const std::string &s2) noexcept
                                {
                                    const auto m = s1.size();
                                    const auto n = s2.size();
                                
                                    // Edge cases.
                                    if (m == 0) {
                                        return n;
                                    } else if (n == 0) {
                                        return m;
                                    }
                                
                                    const auto ca1 = s1.c_str();
                                    const auto ca2 = s2.c_str();
                                
                                    std::vector<long> v0(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) {
                                            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;
                                
                                            // 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;
                                            }
                                        }
                                
                                        std::swap(v0, v1);
                                    }
                                
                                    return v0[n];
                                }
                                
                                int
                                main()
                                {
                                    const auto s1 = std::string(15000, 'a');
                                    const auto &s2 = s1;
                                    const auto s3 = std::string(15000, 'b');
                                
                                    const auto start_time = std::chrono::steady_clock::now();
                                
                                    printf("%ld\n", lev_dist(s1, s2));
                                    printf("%ld\n", lev_dist(s1, s3));
                                
                                    const auto end_time = std::chrono::steady_clock::now();
                                    fprintf(stderr,
                                            "Finished in %.3lfs\n",
                                            std::chrono::duration<double>(end_time - start_time).count());
                                    return 0;
                                }

                                Получив:


                                • gcc 9.2: ~0.727с
                                • clang 9: ~0.775с
                                • g++ 9.2: ~0.869с
                                • clang++ 9: ~0.791с
                                0
                                Не влияет ну совсем.

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

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

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

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


                                4 раза

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


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

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


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

                                  +7
                                  1. 20000 и 15000 это разный обьем памяти и циклов.
                                  2. Количество памяти влияет на кеш, а он как известно очень мал
                                  3 ????
                                  4 выдляем 100500 нормируем и говорим что С++ медленный.
                                    +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? Особенно учитывая, что разница между ними примерно равна стандартному отклонению каждого из них?

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

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


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

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

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

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


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


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

                                            +2
                                            Еще в чистом С коде ошибка
                                            Должно быть
                                            memcpy(v1, v0, sizeof (long) * (n + 1));
                                              0

                                              Поправил, спасибо.

                                                +1

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

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

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


                                                  Массивы

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


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

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

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

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


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

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

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

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

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

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

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

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


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

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

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

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

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

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


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

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

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

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

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

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

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

                                                                  В моем личном зачёте после плюсов пока лидирует Coq.
                                                                  Ну вот… и тут C++ не лидер.
                                                                    0
                                                                    Структура, разработанная для работы с объектами, которые почти никогда не обрабатываются как массив байт плохо справляется с этим?

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


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


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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

                                                        O(n²) в данном случае.

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

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


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


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

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

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

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


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

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

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

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

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


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

                                              на


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

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

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

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

                                                  0

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

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

                                                    А, и правда.

                                                +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");
                                                        }
                                                    }
                                                }
                                                


                                                Тут Enumerable.Range(...) заменен на обычный масив и для красоты сделал (v0, v1) = (v1, v0). Выполняться стало за 0.55 вместо 0.65. Запускал на .NET Core SDK (3.1.100), следующим образом dotnet run -c release

                                                На той же машине раст отрабатывает за 0.490. Запускался через cargo run --release
                                                  0

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

                                                    +10
                                                    Честно говоря не очень ясно, кому сегодня нужен чистый Mono, когда есть .Net Core. Учитывая что MS купили Xamarin вместе с Mono и частично используют его в Core.
                                                      –3
                                                      А кому вообще нужен чистый C# без Windows? В каком-нибудь Unity уже .Net Core или всё ещё Mono?

                                                      Пока там Mono — сказать, что Mono никому не нужен таки нельзя…
                                                        +1
                                                        .Net Core вполне себе кросс-платформенный.
                                                        И есть даже возможность компиляции нативных бинарников (например CoreRT).
                                                        Mono разве что в Unitiy, и то со временем думаю перейдут на Core.
                                                          0
                                                          Ну вот когда перейдут — тогда, я думаю, и автор про Mono забудет…
                                                            0
                                                            Unity скажем так далеко не самый flagship проект в мире .Net
                                                              0
                                                              Половина(если не больше) топ игор в appstore и google play написаных на Unity. Разные красивые AR демки от Google и Apple сразуже имеют поддержку Unity или вообще написаны на ей. Все это так, фигня.
                                                                +1
                                                                Конечно нет.
                                                                Просто, имхо, количестов C# кода в играх на unity(там логику можно писать не только на C#) мне кажется меньшим чем той же охапки бизнесс-логики написанных для ASP
                                                                Как минимум я считаю что он скорее приближаетсяпо сложности ASP.NET сейчас.
                                                                Да, возможно это просто моё субъективное восприятие, а реальное положение дел иное.
                                                                  0

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

                                                                    0
                                                                    Есть AspNet Core, но он не совместим с обычным AspNet. Много старого легаси осталось фреймворке. Все новое уже на core.
                                                      0
                                                      Ну не вижу ничего особенного. Цель моно была быть максимально совместимым с .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");
                                                              }
                                                          }
                                                      }
                                                      

                                                    0

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

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

                                                    Убрал вывод через консоль, преобразование строк в массив байтов, в условиях циклов заменил переменные на s.Length, вычисление минимального из трех через два метода Math.Min.
                                                      +2

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


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

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

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

                                                        Плюс Enumerable.Range выполняется всего один раз в коде автора, так что его влияние на общий результат минимально.
                                                        Но в целом вы правы: если бы, скажем, этот метод выполнялся в цикле или размер массива был побольше (500к+) или мы бы взяли Framework вместо Core, тогда да — лучше было бы использовать ручное заполнение.
                                                          0

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

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

                                                            del

                                                        0
                                                        В тестах С# 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");
                                                                }
                                                            }
                                                        }


                                                        go: 0.491s
                                                        .net: 0.699s
                                                        +4
                                                        Кроме того C# используют безопасное обращение к массиву.

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

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

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

                                                            +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");
                                                            }
                                                            

                                                            Со включенной оптимизацией на моей машине дает 0.77с против 5.6c в оригинальной версии.

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


                                                              Не могли бы показать вариант с ReadOnlySpan? Интересно посмотреть почему так происходит, какая версия .Net Core?
                                                                0
                                                                Да все то же самое, только вместо .ToCharArray() используется .AsSpan(). Использую последний LINQPad 6, в нем .NET Core 3.1.
                                                                0
                                                                А зачем вообще строки в массив копировать? Судя по коду, никакие изменения в s1 и s2 не делаются, а читать символы по индексу можно прямо у строки.

                                                                Просто засунуть тело функции LevDist(char[] s1, char[] s2) в LevDist(string s1, string s2) и все будет работать еще быстрее.
                                                                  0
                                                                  Так тоже можно, но никакого прироста скорости не дает. Полагаю, дело в том, что индексация массива оптимизирована лучше, чем индексация строки.
                                                                    0
                                                                    Посмотрел внимательнее: там в бенчмарке всего два раза вызывается LevDist так что это копирование просто копейки на фоне остальной работы. Наверное во время реальной работы, когда вызовов LevDist будут тысячи, влияние будет уже другое.
                                                                      +1

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

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

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

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

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

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

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

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


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

                                                                          0

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

                                                                            0

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

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

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

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


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

                                                                          0

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


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

                                                                            0

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


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

                                                                              0

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

                                                                      +2

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

                                                                      +27
                                                                      Просто кто-то программировать не умеет, меняем:
                                                                       v1[j + 1] = std::min({delCost, insCost, substCost});

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

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

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


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

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

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


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

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


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

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

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

                                                                                  Кое-где, иногда, он ещё может «показть класс» (всё-таки в него много тысяч человеко-лет вбухано тоже), но объективно — он таки от Clang отстаёт.
                                                                                    0
                                                                                    А что за история с гуглом и GCC?
                                                                                      0
                                                                                      Никакой особенной истории — просто если раньше Google компилировал все свои сервера GCC, то сейчас произошла консолидация и используется Clang/LLVM везде, где возможно.

                                                                                      Как несложно догадаться раньше Google содержал сколько-то контрибуторов в GCC, сейчас — часть переключилась на Clang, часть уволилась…
                                                                            +1
                                                                            А там и не выделяется ничего — initializer_list должен разворачиваться в компилтайме, это таки не лист и не вектор.
                                                                            initializer_list — это, увы, именно-таки массив. И обрабатывается как массив и косяки у него, как при работе с массивом.

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

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

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


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

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

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

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

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

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


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


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


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

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

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

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

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

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


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


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


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

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

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


                                                                                          Ну или в коде.

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

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

                                                                                –4
                                                                                https://en.cppreference.com/w/cpp/utility/initializer_list
                                                                                ты слово Array видишь, а метод size? и что это не вектор по твоему?
                                                                                +1
                                                                                Ну всё-таки «уважающий себя компилятор» должен такое убивать.

                                                                                P. S. Ох уж эти истории про медленный C и C++
                                                                                А они всегда про это: компилятор, вроде бы, должен лишнее удалять… но не всегда ему это удаётся. И это — после тысяч человеко-лет, в это вбуханных.
                                                                                  –3
                                                                                  Компилятор, команды символьных строк, переводить в бинарный машинный код, а то что ты говоришь должен, делать программист. Например можно с помощью бинарных операций найти минимальное число, без использования if, источник как это сделать Алгоритмические трюки для программистов [Генри С. Уоррен мл.] Hacker's Delight
                                                                                    +11
                                                                                    Не должен. std::initializer_list был разработан как раз для таких случаев. И его использование у 0xd34df00d — как раз вполне идеоматично.

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

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

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

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

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

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

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

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

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

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

                                                                                              В результате некоторые алгоритмы могут резко усколяться если вместо char использовать что-то типа:
                                                                                                struct __attribute__((packed)) FastChar {
                                                                                                  long long value:8;
                                                                                              };
                                                                                                +1

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


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

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

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

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

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

                                                                                                      То есть мне было бы, в принципе, интересно увидеть пример кода, где ваш CharWrapper может хоть на что нибудь повлиять…
                                                                                                        +2
                                                                                                        Доступ к элементу структуры может же алиаситься с доступом ко всем, с чем алиасится соответствующий тип поля структуры.

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

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

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

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

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

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

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

                                                                                                            0

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

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

                                                                                                              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!
                                                                                                                0

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


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

                                                                                                                  0
                                                                                                                  Ну, где вы пишете в один член юниона, а потом читаете из другого?
                                                                                                                  Нет. Ну во всяком случае так считают разработчики компиляторов. Тут всё упирается в то, что все эти автогенерённые 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 самое простое.
                                                                                                                    0
                                                                                                                    Нет.

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


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


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

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


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

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

                                                                                                                      0
                                                                                                                      Ну и тут явно 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 всё равно торчат…
                                                                                                                        0
                                                                                                                        С какого перепугу?

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


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

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


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

                                                                                                                        Не согласен:


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

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


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

                                                                                                                          0
                                                                                                                          Потому что я зареюзил сторедж, записав в член-массив.
                                                                                                                          С чего вдруг? Вы модицицировали имеющееся там значение типа 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 (и других подобных).

                                                                                                                          Такие дела…
                                                                                                                            0
                                                                                                                            С чего вдруг? Вы модицицировали имеющееся там значение типа 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 первым членом, но это выполняется и для предложенного вами типа.

                                                                                                                              0
                                                                                                                              Записав в другой объект с тем же стореджем.
                                                                                                                              Ну уж нет. Читаем:
                                                                                                                              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++: где ещё можно выстрелить себе в ногу столькими разными способами?
                                                                                                                                0
                                                                                                                                Простое присваивание не создаёт нового объекта — оно модифицирует существующий.

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


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

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


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

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


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

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


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

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


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


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

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

                                                                                                                                  0
                                                                                                                                  То есть, там написано не совсем это, и вы теоретически могли бы взять указатель на этот член (как вы и делаете), скастануть в 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 не пугает
                                                                                                                                    0
                                                                                                                                    Вы вообще подумайте: кому и зачем могла бы быть нужно разрешение на получение доступа к объектам произвольного типа через 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.

                                                                                                                                      0
                                                                                                                                      Тогда если вы сделаете
                                                                                                                                      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, не об указателях). И компилятор считает, что они могут обращаться к другому типу… хотя следует ли это из стандарта — я сказать и не могу…
                                                                                                                                        +1
                                                                                                                                        Ну тут у вас никаких chat нету и типы не similar, так что да — тут это невалидно.

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


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

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


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

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


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

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


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