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

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


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

+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 тысяч символов.
+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.

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) или более нелинейная? Корректность нормировки вызывает сомнения.
+1
кстати у вас в описании теста указан размер строки 20000, а в бенчах везде 15000. Это так задумано?

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


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


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

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

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

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


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

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

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

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

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


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

на


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

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

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

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

+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
Половина(если не больше) топ игор в appstore и google play написаных на Unity. Разные красивые AR демки от Google и Apple сразуже имеют поддержку Unity или вообще написаны на ей. Все это так, фигня.
+1
Конечно нет.
Просто, имхо, количестов C# кода в играх на unity(там логику можно писать не только на C#) мне кажется меньшим чем той же охапки бизнесс-логики написанных для ASP
Как минимум я считаю что он скорее приближаетсяпо сложности ASP.NET сейчас.
Да, возможно это просто моё субъективное восприятие, а реальное положение дел иное.
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
В тестах С# 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
+1

C# .NET Core 3.1


Это unsafe реализация, у меня она медленее на 0.11 с обычной реализации на строках на R7 2700X.


Unsafe с выводом вне блока unsafe - 0.667 с
using System;
using System.Diagnostics;

public class Program
{
    public static unsafe int LevDist(char* s1, int m, char* s2, int n)
    {
        // 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 < 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()
    {
        var s1 = new string('a', 15000);
        var s2 = s1;
        var s3 = new string('b', 15000);

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

        int res1, res2;

        unsafe
        {

            fixed (char* c1 = s1)
            fixed (char* c2 = s2)
            fixed (char* c3 = s3)
            {
                res1 = LevDist(c1, s1.Length, c2, s2.Length);
                res2 = LevDist(c1, s1.Length, c3, s3.Length);
            }
        }

        execTimer.Stop();

        Console.WriteLine(res1);
        Console.WriteLine(res2);

        var execTime = execTimer.ElapsedMilliseconds / 1000.0;

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

Однако, если в данной реализации вывод положить внутрь unsafe блока и убрать переменные, то результаты уравниваются с результатом стандартной реализации, но с отдельными переменными и отдельным выводом (с unsafe всё наоборот).


Unsafe с выводом внутри блока unsafe - 0.556 с
using System;
using System.Diagnostics;

public class Program
{
    public static unsafe int LevDist(char* s1, int m, char* s2, int n)
    {
        // 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 < 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()
    {
        var s1 = new string('a', 15000);
        var s2 = s1;
        var s3 = new string('b', 15000);

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

        unsafe
        {

            fixed (char* c1 = s1)
            fixed (char* c2 = s2)
            fixed (char* c3 = s3)
            {
                Console.WriteLine(LevDist(c1, s1.Length, c2, s2.Length));
                Console.WriteLine(LevDist(c1, s1.Length, c3, s3.Length));
            }
        }

        execTimer.Stop();

        var execTime = execTimer.ElapsedMilliseconds / 1000.0;

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

Стандартная safe реализация.


Safe с выводом вне блока замера времени - 0.556 с
using System;
using System.Diagnostics;

public class Program
{
    public static int LevDist(string s1, string 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 < 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()
    {
        var s1 = new string('a', 15000);
        var s2 = s1;
        var s3 = new string('b', 15000);

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

        var res1 = LevDist(s1, s2);
        var res2 = LevDist(s1, s3);

        execTimer.Stop();

        Console.WriteLine(res1);
        Console.WriteLine(res2);

        var execTime = execTimer.ElapsedMilliseconds / 1000.0;

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

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


Safe с выводом внутри блока замера времени - 0.667 c
using System;
using System.Diagnostics;

public class Program
{
    public static int LevDist(string s1, string 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 < 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()
    {
        var s1 = new string('a', 15000);
        var s2 = s1;
        var s3 = new string('b', 15000);

        var 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");
        return 0;
    }
}
0

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

+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# для этого. Это я скорее про расходы от копирования говорил (предположительно от копирования один раз в начале работы функции).

+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 должен разворачиваться в компилтайме, это таки не лист и не вектор. И да, в одном из заключений про это написано.


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

+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
Никакой особенной истории — просто если раньше 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.


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

+1

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


Ну или в коде.

0

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

+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* — с чего бы компилятору его опасаться?

+7
С того, что это, блин, 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
Дык в том месте, где про 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++, обсуждают, как же на этом языке сделать строки, и уже почти сутки не могут придти к консенсусу — это прикольно. Хороший язык.

0

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


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

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

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


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

0

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

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

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

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

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

Хороший язык.
Отличный просто. Никогда ни в чём нельзя быть уверенным.
0
Однако редкий трэш. Я про вот это:
mov byte ptr [rsp - 16], 0
......
mov rcx, qword ptr [rsp - 16]
mov qword ptr [rsp - 16], rcx
......
test cl, cl


Объяснение по ссылке выглядит убедительным (хотя для меня не очень понятным, ну да ладно), однако вообще это выглядит как, скажем так, некий приговор, если не языку, то использованным идиомам. Меньше кортежей, меньше…
0
Ну а какие альтернативы? Этот конкретный косяк разработчикам LLVM уже известен, фикс, как я сказал, на review…
0
Это понятно, но вопрос в том, что сложность и неочевидность ситуации порождается «богатыми возможностями языка». Сомнительный результат парадигмы «язык усложняем — программы упрощаем». Хотя конечно кортежи — вещь мощная, спору нет.
0

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

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

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


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

Но пока это происходит как и с initializer_list: встраивается-то оно встраивается, но ошмётки во все стороны торчат.
0
Ну, я не в курсе, что именно там за ошметки, но пространство для творчества там конечно есть. И, да, встроить простой генератор — еще можно, согласен.

Ситуация с initializer_list выглядит грустной еще и потому, что описание std::min с таким параметром не гласит о том, что при таком вызове раскручивается маховик репрессий чудес и аллокаций. Это все буквально выглядит просто как способ передачи параметров, использующий синтаксис initializer_list. И типа все должно быть потом прекрасно и быстро. А там вон чего творится…
0
А там вон чего творится…
Тут action item — однозначно «клевать мозг» разработчикам clang. Я попробую. Так быть не должно.
+8
А почему вы на Go работаете с массивами, а на Rust — со строками? Метод bytes() создает cloned итератор, который не бесплатный.
-1
И вы получите тоже время выполния с отклонением в пределах статистической погрешности. По крайней мере на .NET 4.7.2.
-1

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


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

0
snippet
    <…>
    let ca1: Vec<u8> = s1.bytes().collect();
    let ca2: Vec<u8> = s2.bytes().collect();

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

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

            for (j, c2) in ca2.iter().enumerate() {
    <…>

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

0

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

+1

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

+1

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

+3

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

0

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

0

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


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


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


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

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

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

Python
Косметические изменения в коде:
import sys
import time
import numpy as np
from numba import jit


@jit
def lev_dist(s1: bytes, s2: bytes) -> int:
    m = len(s1)
    n = len(s2)

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

    v0 = np.arange(0, n + 1)
    v1 = np.arange(0, n + 1)

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

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

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

        v0, v1 = v1, v0

    return v0[n]


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

На долю процентов C быстрее, но скорости практически сравнимы.
0

Умножьте на (4/3)² — для этих данных время квадратично зависит от длины, а везде строки в 20 тыщ символов.


Ну и, кстати, сколько тогда работы выполняется в питоне, а сколько — в C?

+2
Можно привести и к 20 тыщ, но в целом видно, что C и Python практически сравнимы по скорости.
Ну и, кстати, сколько тогда работы выполняется в питоне, а сколько — в C?
Ну Python же это язык. У него может быть реализация как у интепретируемого языка, а может быть и jit компиляция.

А по факту я взял приведенный исходник на Python, практически добавил всего одну аннотацию, запустил в стандартной реализации CPython и получил практически скорость языка С. С точки зрения разработчика я нигде не вышел из окружения Python.
0
Ну Python же это язык. У него может быть реализация как у интепретируемого языка, а может быть и jit компиляция.

Безусловно (поэтому там есть сравнение с pypy). Но FFI в C — это ИМХО как-то не очень честно при бенчмаркинге реализаций, так как вы тогда сравниваете не эффективность реализаций, а эффективность FFI.

0

Теперь-то обратил внимание на @jit. Прикольная штука, буду иметь в виду, если вдруг придётся столкнуться с питоном.

0
Она, к сожалению, меняет семантику (и довольно существенно).

То есть если вы сами пишите код — в общем не проблема.

А вот взять чужой код и налепить на него jit — можно поиметь проблем.

Но учитывая ускорение в несколько раз — иногда можно поиграться…
+1
Тут вопрос сложный. У нас есть Java Script с его V8, nim с его компиляцией в C, Julia с ее компиляцией через llvm. Да и тот же pypy в несколько раз медленнее numba, хотя оба пытаются компилировать код.

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

Да и чем, грубо говоря, декоратор "@jit" так уж сильно отличается от набора специальных флагов «gcc» с подсказками для оптимизаций?
+1

Я в том комментарии был неправ, так как неправильно прочитал код.


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

+1
Выше уже ответили, нужны только numpy и numba:
$ pip3 install numpy
$ pip3 install numba


На всякий случай, вот полный код:
#!/usr/bin/env python3
import sys
import time
import numpy as np
from numba import jit


@jit
def lev_dist(s1: bytes, s2: bytes) -> int:
    m = len(s1)
    n = len(s2)

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

    v0 = np.arange(0, n + 1)
    v1 = np.arange(0, n + 1)

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

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

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

        v0, v1 = v1, v0

    return v0[n]


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

    exec_time = -time.monotonic()

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

    exec_time += time.monotonic()
    print(f"Finished in {exec_time:.3f}s", file=sys.stderr)
0
Начал с практически того же варианта, что и Вы, потом упростил внутренний цикл без потери производительности до:

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


Не понимаю, чем не понравился автору статьи min()?
0

Подобные "упрощения" не очень то и упрощают чтение кода. :)

0
Было 7 строк кода (понятного лишь из-за закомментированного варианта), 4 одноразовых переменных (которым еще имена придумать надо), стала одна строка, которая понятно что делает.

P.S. В конце концов можно так сделать:
        for j, c2 in enumerate(s2):
            v1[j+1] = min(v0[j] if c1 == c2 else (v0[j]+1), 
                          v0[j+1]+1, 
                          v1[j]+1)
+2

Numba – это что-то невероятное…
У меня оно не получилось быстрее C, но оно справилось быстрее Julia.

+2

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


Например, если на код автора просто навесить декоратор @jit — программа отработает за 2.528 на моем железе.


Если убрать isinstance — уже будет 1.7.


Что не может не радовать. :)


Все-таки, если уже считаем в Питоне, то берем для этого инструменты, которые для него придумали.

+2
Уже прокомментировали про C++, добавлю то же самое про D. Достаточно добавить флажок boundscheck=off и получить удвоение скорости. Размен безопасности на скорость, которую вы сделали в хаскеле.
P.S. Забыл про главное, компилятор ldc2, а не референсный DMD.
+1

Не хочу комментировать, что 0xd34df00d намерял с C++, но ведь с D именно так оно и есть уже.
Можно было бы ещё LDC приложить, ведь он быстрее DMD справился с сей задачей.

0
Да, невнимательно посмотрел на флаги. Дописал в P.S.
Протестировал у себя, получил похожие цифры, а потом уже удвоился за счёт проверок границ. Даже не задумывался, что можно бенчмаркать DMD, на автомате взял ldc. Результаты у меня:
C gcc 8.3: Finished in 0.696s
D ldc2 1.10.0: Finished in 0.638s
Есть разброс, но в целом D версия чуть быстрее.
+2
Пожалуйста, перетестируйте js:
const levDist = (s1, s2) => {
  const m = s1.length;
  const n = s2.length;

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

  let v0 = new Uint16Array(n + 1);
  let v1 = new Uint16Array(n + 1);

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

    for (let j = 0; j < n; ++j) {
      v1[j + 1] = Math.min(
        v0[j] + (s1[i] === s2[j] ? 0 : 1),
        v0[j + 1] + 1,
        v1[j] + 1
      );
    }

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

  return v0[n];
};


const s1 = new Uint8Array(15000).fill('a'.charCodeAt(0));
const s2 = s1.slice();
const s3 = new Uint8Array(15000).fill('b'.charCodeAt(0));

console.time('Finished in');

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

console.timeEnd('Finished in');
0

Спасибо, вечером на той же машине проверю и обновлю результаты.

0

Для консистентности с хаскель-версией, там Int — знаковый и соответствующей машине битности. Впрочем, замена на uint64_t или на (u)int32_t вообще ничего не меняла на моей машине (что ожидаемо, работа с L2-кешем таки не оказывается боттлнеком, чтения/записи исключительно последовательные и хорошо предсказываются, векторизации здесь нет, а сравнения и сложения процессор выполняет, видимо, одинаково эффективно).

+2
Старому clang (6.0) очень помогло вынести в отдельную функцию внутренний цикл и написать __restrict. Что-то типа:
void calc_line(const char c1, const std::string &s2, const int64_t *__restrict v0, int64_t *__restrict v1, size_t n);

Сразу sse появляются и прочие удовольствия
+4
Если начинать хитрые трюки устраивать, то непонятно где останавливаться. Как автор и заметил — так можно и до ручной генерации кода дойти.

Так что самый быстрый вариант, в пределе, будет выглядеть как asm("<многа букав>") — на любом языке.
0
А что же вы в GO unsafe не заюзали — он там тоже есть и тоже «педалирует» решение значительно.
0

С указательной арифметикой? Ну жуть же!
Обрати внимание на -gcflags=-B.
Да, всё так, без отключения проверок границ (что в коде сделать нельзя, к сожалению) было бы сильно хуже.

0

интересно что у меня на clang++8 если ставить флаг -std=gun++2a вместо -std=gnu++17 есть прирост где-то на 8%.
К тому же еще странно как у вас шланг так сливает гцц, я вот захожу на годболт, и там шланг векторизирует а гцц нет, и у меня на машине шланг8 быстрее гцц9.1. Сейчас поставлю новые версии.
Еще расту тоже надо указывать -C "target-cpu=native для честности. Кстати хаскелю наверное тоже что то такое т.к. это флаг скорее всего для ллвм.

+1
интересно что у меня на clang++8 если ставить флаг -std=gun++2a вместо -std=gnu++17 есть прирост где-то на 8%.

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


К тому же еще странно как у вас шланг так сливает гцц, я вот захожу на годболт, и там шланг векторизирует а гцц нет, и у меня на машине шланг8 быстрее гцц9.1.

Я, кстати, не знаю, как тут так просто бы векторизовать, так как у каждого следующего элемента массива есть неприятная зависимость по данным от всех предыдущих. Если он там действительно векторизует, а не просто использует векторные регистры и векторные мувы, чтобы сразу 8-16-32 инта получать, то это очень круто.


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


Кстати хаскелю наверное тоже что то такое т.к. это флаг скорее всего для ллвм.

Если вкратце, то у меня не получилось, а жаль. Могло бы быть ещё чуточку быстрее.

0

У меня разница между шланг8 и шланг9 минимальна. 8-ой шланг действительно дает маленькую регрессию при с++17.

0

А я уже тестил с оптимизацией s1[i] за границей цикла. Иначе (на вашем оригинальном коде) в шланге9 дикая регрессия больше чем в два раза!

0
Похоже, что за неполные 4 часа, неопротестованными остались всего несколько тестов =)

Было бы неплохо обновить статью новой табличкой результатов. И новыми выводами.

И еще статья дает больше информации не столько о скорости ЯП, сколько об их читаемости.
+2

Как вечером доберусь до домашней машины — прогоню предложенные новые варианты и обновлю.


А выводы-то… Ну вот питон с numba приятно удивил, да. Другой вывод — похоже, я не умею передавать смысл того, что я делаю.

+1
Видимо да.

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

И можно не пренебрегать безопасностью в угоду производительности.

Но в любом случае надо хорошо знать свой инструмент.
0
У меня вывод простой (из аналогичных тестов) — если язык компилируемый, то в большинстве случаев производительности достаточно, кроме разве что, специализированных задач.

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


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

0
JIT стал хорош только по прошествии 20 лет, и то пока примеров единицы — JVM, NET, отчасти JS, и возможно Julia, остальные глотают пыль.

Проблема Хаскеля (ну и не только, например linq, sql), как я глупо думаю — что высокоуровневые абстракции скрывают реальные накладные расходы — и очень легко написать красивый код, получив ужасную практическую реализацию с квадратичными расходами.
0

А фиг его знает, в чём проблема.


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


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

UFO landed and left these words here
0

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

UFO landed and left these words here
+1

И так для каждой микроархитектуры.


А если серьёзно, я смотрел на асм (но больше на хаскелевский — интересно было, чего там компилятор наворотил). В общем, мне пока хватит.

0

Что, если в хаскелевском коде 0.8с уходит на инициализацию некого рантайма, а остальные 0.01с на что-то вроде


.LC0:
        .string "0"
main:
        movl    $.LC0, %edi
        jmp     puts

? Я бы добавил зависимость от входных данных, чтобы быть уверенным, что результат считается не в compile-time.

0

Ну тут две вещи дают уверенность:


  1. Я добавлял NOINLINE-прагму к определению функции (с очевидной семантикой) — ничего не изменилось вообще никак, а кроссмодульную оптимизацию в ghc не завезли.
  2. Библиотека criterion специально сделана так, чтобы данные не протекали в функцию до начала бенчмарка, и результаты от этой библиотеки согласуются с результатами из табличек.
0
Трудно удержаться от написания тестов на каком-нибудь другом языке. Автор знает толк!
Я написал по мотивам С реализацию на Ada для строк длиной 20000, получилось на 3.6 ГГц процессоре 0.86 секунды…
0

А вы с 15к или с 20к символами запускали?


Вот это моя, наверное, самая большая ошибка — надо было не лениться и переделать везде на 20к. А то теперь одна путаница и неразбериха.


И код-то покажите, интересно же!

+1
ну, вот так примерно (писалось в спешке :)
with Ada.Text_IO;

procedure Main is
   function Levenshtein_Distance (S1, S2 : String) return Long_Integer is
      M  : Integer := S1'Length;
      N  : Integer :=  S2'Length;
      R  : Long_Integer := 0;
      type q is array(1.. N+1) of Long_Integer;
      k0 : aliased q := (others => 0);
      k1 : aliased q := (others => 0);
      v0 : access q := k0'access;
      v1 : access q := k1'access;
      temp: access q := k1'access;
   begin
        for I in S1'Range loop
        v1(1) := Long_Integer(i) + 1;
        for J in S2'Range loop
            declare
             del_cost   : Long_Integer := v0(j + 1) + 1;
             ins_cost   : Long_Integer := v1(j) + 1;
            begin
              if s1(i) = s2(j) then
                  -- v0(j)
                  if v0(j) < del_cost then v1(j+1) := v0(j); else v1(j+1) := del_cost; end if;
              else
                  if v0(j)+1 < del_cost then v1(j+1) := v0(j)+1; else v1(j+1) := del_cost; end if
                  -- v0(j)+1
              end if;
            if ins_cost < v1(j + 1) then
                v1(j + 1) := ins_cost;
            end if;
            end;
        end loop;
        temp := v0;
        v0 := v1;
        v1 := temp;
      end loop;

      return v0(N);
   end Levenshtein_Distance;

  A : String(1..20000) := (others => 'a');
  A2: String(1..20000) := (others => 'a');
  B : String(1..20000) := (others => 'b');

begin
   Ada.Text_IO.Put_Line
     ("1:" &
      Long_Integer'Image (Levenshtein_Distance (A,A2)+Levenshtein_Distance (A,B)));
end Main;
+1
PHP можно попросить удалить ненужные строки и переменные `$ca1`, `$ca2`:

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


А соответствующие циклы заменить на:
    for($i = 0;  $i < $m; $i++) {
        $v1[0] = $i + 1;

        for($j = 0; $j < $n; $j++) {
            $subst_cost = ($s1[$i] === $s2[j]) ? $v0[$j] : ($v0[$j] + 1);
            $del_cost = $v0[$j + 1] + 1;
            $ins_cost = $v1[$j] + 1;

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

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


 Минус два цикла — должно дать существенный прирост производительности
+1
минус два цикла с вычислением ord()
плюс строгое равенство при сравнении одиночных символов.

Зуб даю мой код быстрее и читабельнее. Не говоря уже про UTF-8
0
минус два цикла с вычислением ord()

Вне цикла подобные манипуляции вообще ничего не значат на общем фоне. Так-то их можно вообще вынести наружу… только зачем?


плюс строгое равенство при сравнении одиночных символов

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


Не говоря уже про UTF-8

Все версии сделаны именно так, чтобы сравнивались именно индивидуальные байты для однородности и простоты (ну, в большинстве случаев).
Но вообще, как ни иронично, именно вариант с конвертацией в массив чисел более юникододружелюбный, потому что с ним для UTF-8 нужно просто заменить ord на mb_ord, а иначе нужно использовать mb_substr; а это, сам понимаешь, уже целый вызов функции внутри цикла.

0
минус два цикла с вычислением ord()

Вне цикла подобные манипуляции вообще ничего не значат на общем фоне. Так-то их можно вообще вынести наружу… только зачем?


Я не понял что именно вы предлагаете «вынести наружу»?

Что-то я не понял мысль. Или мне кажется вы не поняли про какие два цикла я говорю.
Я предложил тупо убрать два вспомогательных цикла перед двумя вложенными друг в друга — потому что они ничего не добавляют важного и нужного. И если их цель преобразовать строки в числа — то мне кажется это немного высокая цена ради того чтобы позже выиграть на сравнении чисел вместо строк.
+1

Но преобразование строк в числа — m + n операций (где это длины строк), а сравнений потом происходит в районе mn. 40 тысяч против 400 миллионов в этом случае.

+1
И если их цель преобразовать строки в числа

Как бы, ord
Неужели так сложно поверить, что числа сравнивать дешевле, чем целые строки, хоть и единичные %)?


это немного высокая цена

Два for на 40 000 циклов суммарно.


ради того чтобы позже выиграть на сравнении чисел вместо строк

А вот сравнение происходит 400 000 000 раз.

0

Кто-нибудь пробовал в итоге запустить и сравнить эти два PHP варианта между собой? Рассуждения интересные, но хотелось бы понять на практике.

0
Я таки попробовал. И мой предложенный вариант не выдал улучшения, а таки негативно сказался на производительности примерно на 10-15%.
0
Не говоря уже про UTF-8

Предложенная функция всё равно остаётся метрикой (в математическом смысле), пусть и считает немного не то.


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

0
считать всё корректно для уникода (и особенно для UTF-8) чуть менее просто.

Тут зависит от реализации. Для раста можно заменить итератор по bytes на итератор по chars и получить всё то же самое и без особой просадки производительности.
А на php с кем-то предложенным тут mb_substr это будет уже O(n⁴), потому что для взятия каждого следующего символа надо будет пробежать по всей строке.
-2
Добавлю свои 0.05 копеек.

В коде на С++ внутри одного цикла идет std::swap длинных векторов, в коде на С — меняются указатели. До кучи внутри swap идет вызов new/delete, которые на Це эквиваленты дерагнью malloc/free, что само по себе плохо сказывается на производительности и зависит от того, как там heap устроен, плюс есть эффект на забивание кешей процессора
+4

Там нет вызова new/delete. И быть его там не должно, если ваша реализация STL зачем-то там выделяет/освобождает память, то её лучше выкинуть.


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

-1
Там нет вызова new/delete.


Вот специально перед написанием посмотрел на например, вот это.
+1

Там первым ответом код с использованием std::move, который уже сам по себе убирает всякую потребность в delete.


А так как стандарт по большей части не специфицирует, как именно должна быть реализована та или иная функция, а лишь описывает поведение, то лучше проверять экспериментально. Никто не мешает std::vector'у, например, вообще иметь свою кастомную std::swap.

-1
Разве не так?
Foo()
{
T temp; // вызов new
} // вызов delete

А так как стандарт по большей части не специфицирует,

ну да, ну да. Однако вангую, что сделано в большинстве реализаций по простому, как написано на стекеоверфлоу.
+2
Разве не так?

Если вкратце, то нет.


Если вы специфицируете эту функцию для int, например, то никакого new там не будет заведомо.


Если теперь вы вернётесь к векторам и посмотрите на правую часть от присваивания, то там там std::move — это позволяет просто взять указатель и размер от вектора справа и переместить его в temp слева, без всяких копирований и выделений памяти, оставив вектор справа в полудохлом состоянии. Аналогично со следующими мувами.


Однако вангую, что сделано в большинстве реализаций по простому, как написано на стекеоверфлоу.

Это снова вопрос качества реализации. Но писать адекватные стандартные библиотеки чуточку проще, чем проходы оптимизации (хоть и чуть более муторно и чуть менее весело), поэтому поставщики основных библиотек (libstdc++ среди них) таки в это вкладываются. Удивительно, люди там далеко не всегда работают спустя рукава (и это не сарказм, учитывая всю опенсорсовость и бесплатность).


Плюс, упомянутая на SO реализация не будет nothrow для векторов, чьи элементы не имеют nothrow-move-конструктора, а std::swap ЕМНИП обязан быть nothrow (по крайней мере, в этом случае).

-3
Если вкратце, то нет.

если быть точным, то в общем — нет, по факту для для любого нетривиального класса — да.
там std::move — это позволяет просто взять указатель и размер от вектора справа и переместить его в temp слева, без всяких копирований и выделений памяти, оставив вектор справа в полудохлом состоянии


Поскольку я не пользуюсь систематически «этим безобразием» (темплейтами), то проверил это утверждение экспериментально. Как минимум в общем случае ;-) утверждение, что там нет копирования — ложно.
0
Поскольку я не пользуюсь систематически «этим безобразием» (темплейтами), то проверил это утверждение экспериментально. Как минимум в общем случае ;-) утверждение, что там нет копирования — ложно.

Покажете код?


В предыдущем комментарии я говорил о копировании storage вектора, но и в более общем смысле копирования для классов с поддержкой мув-операций быть не должно.

+2
если быть точным, то в общем — нет, по факту для для любого нетривиального класса — да.
Конкретно для std::vector C++17 гарантирует, что исключений не выбрасывается, а это возможно только если выделания памяти не происходит.

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

Может я отстал от жизни, но раньше было только два варианта выделения памяти для нестатических переменных — из стека или из кучи (для неембеднутых С/C++),

Ну вот попробовал погулять в отладчике MS VS2017 по коду С++ который выше приведен.
std::vector<int64_t> v0; прямо вызывает new(),

а вот swap для vector действительно хитровыделанный и совсем не похож для swap с стекореврфлоу. И сходу конечно непонятно, но в new вроде не попадает и копирования не вижу.
0
Прошу прощения. Не заметил, что вы там обсужджаете создание временного объекта, а не, собственно, swap.

Тут фишка как раз в том, что у std::swap обязана иметься специализацию для std::vector — и вот она уже не имеет права бросать исключения, а значит, должна как-то обходиться без выделения памяти на куче.

Будет она создавать временные объекты (которые не будут выделять памяти) или как-то без них обойдётся (тогда память не будет выделяться просто потому, что временных объектов нет) — действительно оставлено на усмотрение реализаторов…
0
ну да, ну да. Однако вангую, что сделано в большинстве реализаций по простому, как написано на стекеоверфлоу.

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


Да и собственно откройте код и узнайте, чем гадать.

-2
, стандартная библиотека делает все максимально быстро,

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

Преобразование вот этого неоптимального куска


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

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

в вот этот (тоже, наверное, не самый оптимальный)


            var v0j = v0[j];
            var substCost = s1[i] == s2[j] ? v0j : v0j + 1;
            var delCost = v0[j + 1] + 1;
            var insCost = v1[j] + 1;

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

ускорило C# версию на 26% на моей машине.

0

На моей машине такая замена код замедлила. Тоже её увидел, и тоже весьма удивился.

0

Вот этот вот минимум — об него все языки в том или ином виде спотыкаются.

0
Почему вы берёте самописное решение, а не какую-либо готовую библиотеку, в которой сделаны нужные оптимизации? Взял ваше решение на Go (0.78 сек. у меня минимально), библиотеку github.com/agnivade/levenshtein — получил 0.354 сек. минимально.
+1

Потому что имеющиеся решения меня не устраивали. В моём случае доступны две библиотеки:


  • text-metrics — она тратит время на обработку уникода (и оказывается в 3-4 раза медленнее моей реализации), а мне это не нужно.
  • edit-distance — она оказывает слишком большое давление на GC, и мне было интересно, не получится ли у меня эффективнее. Кроме того, я в первый раз читал её код ж… неправильно, и сделал неправильные выводы о том, как она внутри работает, что добавило мне уверенности, что я могу лучше (по памяти, впрочем, лучше и получилось). Плюс, если туда передавать свои собственные коэффициенты, то она просто взрывается по памяти, а мой вариант взрываться не должен.

Кроме того, в той библиотеке на Go есть не очень устраивающее меня ограничение «As a performance optimization, the library can handle strings only up to 65536 characters (runes).» (не говоря о том, что мой код не на Go).

+2

Если интересно можно побенчить такую более олдскульную версию на указателях, у меня она на 15% быстрее с gcc и на 6% с clang9 (сама по себе шланг версия ускоряется в два раза после того как вынести s1[i] — вангую что из-за алиасинга компилятор не может сделать эту оптимизацию). Естественно это уже не самая наивная версия. Далее надо уже применять думаю некую векторизацию. И в рамках сравнение языков инетересно бы узнать как это будет выглядеть в разных языках.


код
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <string>

size_t lev_dist(const std::string& s1, const std::string& s2)
{
    const auto m = s1.size();
    const auto n = s2.size();

    std::vector<int> v0;
    v0.resize(n + 1, 0);

    std::vector<int> v1;
    v1.resize(n + 1, 0);

    for (size_t i = 0; i < m; ++i) {
        v1[0] = i + 1;
        char c1 = s1[i];

        auto i0 = v0.cbegin();
        auto end = v0.cend() - 1;               
        auto i1 = v1.begin();
        const char *c2 = s2.data();
        while (i0 != end) {
            int delInsCost = std::min(*(i0+1), *i1) + 1;
            int substCost = *i0 + !(c1 == *c2);
            *(++i1) = std::min(delInsCost, substCost);
            ++i0; ++c2;
        }
        std::swap(v0, v1);
    }
    return v0[n];
}

int main()
{
    std::string s1(20000, 'a');
    std::string s2(20000, 'a');
    std::string s3(20000, 'b');

    std::cout << lev_dist(s1, s2) << std::endl;
    std::cout << lev_dist(s1, s3) << std::endl;
}
0

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


Но экспериментальная точка интересная, спасибо.

0
Ну так код на хаскеле у вас тоже хаскелеспецифичный (или как минимум ФП-специфичный).

Вы бы на всех языках код пооптимизировали, а не делали кликбэйт-заголовки.
+1

Я только на плюсах-то могу код оптимизировать (и с большим натягом на С). И там на оптимизацию я потратил примерно столько же времени, сколько в случае хаскеля.

0

закралась ошибка. исправил — стало быстрей.


Быстрый С++ Код
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <string>

size_t lev_dist(const std::string &s1, const std::string &s2) {
    const auto m = s1.size();
    const auto n = s2.size();

    std::vector<int> v0;
    v0.resize(n + 1);
        std::iota(v0.begin(), v0.end(), 0);
    auto v1 = v0;

    for (size_t i = 0; i < m; ++i) {
        v1[0] = i + 1;
        char c1 = s1[i];

        auto i0 = v0.cbegin();
        auto end = v0.cend() - 1;
        auto i1 = v1.begin();
        const char *c2 = s2.data();
        while (i0 != end) {
            int delInsCost = std::min(*(i0 + 1), *i1) + 1;
            int substCost = (c1 == *c2) ? *i0 : *i0 + 1;
            *(++i1) = std::min(delInsCost, substCost);
            ++i0;
            ++c2;
        }
        std::swap(v0, v1);
    }
    return v0[n];
}

int main()
{
    std::string s1(20000, 'a');
    std::string s2(20000, 'a');
    std::string s3(20000, 'b');

    std::cout << lev_dist(s1, s2) << std::endl;
    std::cout << lev_dist(s1, s3) << std::endl;
}
0

оптимизация-коварная штука. один раз пару часов оптимизировали большой кусок кода долго работающей программы. в итоге ускорили ее в 3 раза. с 1 секунды до 0.3. учитывая, что суммарно программа работает час.

+5
Это ещё хорошо, если так. Куда веселее, если окажется что ваша оптимизация замедляет программу.

Сейчас не могу найти письма от какого-то прыща, который объяснял, что разработчики Linux-ядра — идиоты, что они нифига не понимают в оптимизациях и прочее. Ну вот прям все. Они все — идиоты, я д’Артаньян.

Его попросили показать пример. Он показал. Развернул циклы, таблички какие-то развёл, ещё что-то… скорость подсчёта TCP чексуммы выросла в 10 раз. Победа в сухую!

После чего кто-то (Ingo Molnar, кажется) ему ответил. Что-то в духе «ну, бенчмарки ты запускать умеешь… а вот думать — кажется нет». Дальше — другие бенчмарки, уже с TUXом (самый быстрый тогдашний Web-сервер), который с этими «ускоренными» циклами тормозится (ибо все эти таблицы убивают L1 напрочь) и риторическим вопросом: «как ты думаешь — функция подсчёта чексуммы в ядре нужна, чтобы красивые цифирьки на тестах показывать или для того, чтобы Web-сервера могли работать?».

Это было эпично…
0

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

0
А кому и зачем может понадобиться убивающая кеш версия? Вы ж эту чексумму не «от нечего делать» считаете — после вычисления (если передача) или до (если приём) у вас данные в сеть отдаются… там задержки миллисекундами меряются (даже если в локалке).

То есть задача ядра (в данном случае, да и вообще почти всегда) — это «сделать что-то и убраться с дороги». Недаром ядро работает быстрее часто, если скопилировать его с опцией -Os, а не с -O2!

Этот режим не используется по умолчанию, потому что -Os GCC интерпретируется как мне нужен маленький размер, а на скорость мне наплевать (отключая, в частности, тщательно расставленные likely и unlikely), но сам результат показтелен.
0
А кому и зачем может понадобиться убивающая кеш версия?

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

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

А разработчики ядра очень не любят обсуждать гипотетические случаи.
0

Это правда, но не знаю как сейчас 3-4 года назад AFAIK один из быстрейших способов это работать без уровней ядра через dpdk не дёргая ядро для обработки пакетов вообще и многие в sdn юзали именно его

0
В этом случае толку от скоростной функции в ядре ведь всё равно нет…
+1
А в холиварах я постоянно встречал аргумент, что С++ быстрее Паскаля минимум в 3 раза :-)
0

Если сравнивать современный оптимизирующий компилятор С++ с древним компилятором паскаля/делфи — вполне реальная цифра, может быть даже больше.

0

А можете дописать в хаскель листинг как должен выглядеть main и как запускать чтобы сравнить по простому?

0

Никто не читает статьи Я выложил всё сюда, можете склонировать, а потом stack build && stack exec -- edit-distance-linear-bench-exe 6 +RTS -sstderr для наибыстрейшей реализации.

0

Cпасибо ссылку я нашёл но что с ней делать не знал.


Тогда откуда это строка в таблице? И не хотите ли вы ее как бы исправить?
C++ clang 9 323%
Это я так понимаю на Haswell цпу? На моем Skylake там где-то 200%. Далее путем минимального перемещения s1[i] за границу цикла, что есть в хаскель версии, все ожидаемо приходит в четкие 100%.
Более того хаскель у меня использовал дефалтный ллвм то беж llvm-8, т.е. на самом деле 100% у меня при clang-8, а 9ая версия может быстрее. В связи с этим вопрос какой ллвм используется у вас?

0

У меня clang 9 и llvm 9. Это всё на хазвеллах, да.


Сегодня вечером перепроверю (а то я уже из дома ушёл), как там вынос s1 повлияет на производительность, и обновлю статью, если что.

0

Если ваш код будет корректно работать на произвольных строках (т. е. выдавать те же ответы, что предложенный в статье код на плюсах), то нет.

0
Я честно пытался, но быстрее не получилось, ни по диагонали, ни блоками по диагонали. Может быть на размерах превышающих L2 или L3 мог бы быть выигрыш.
0
Проверьте пожалуйста эту реализацию на Rust в ваших условиях. Спасибо!
0

Это ж с одной строкой матрицы вместо двух, да?


0.823 секунды минимум. Впрочем, однострочные варианты что на плюсах, что на хаскеле тоже чуть быстрее (0.800-0.810 с для хаскеля).

0
Да. Но я заметил что Rust заметно проседает из-за начальной инициализации кеша:

(0..).take(n + 1).collect()

Попробуйте заменить на обычный цикл (как в моем решении), и результаты должны стать лучше.
0

Не, плюс-минус тоже (1.026 с вместо 1.028).


Интересно, что у вас оно влияет — оно ж делается один раз и вне цикла.

+1
0xd34df00d Я так понял что в коментах подкорректировали скорость для версий Python и C# / .net core, обновлять данные в таблицах будете?
0

Да, но я гентушник же, сейчас компиляю numba, которая тянет llvm 8, и (снова) ноду.


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

+1
Если у вас не выходит запустить неткор на своей генте, то запускайте его же в докере, используя оффициальный контейнер.
0

А почему для Raku указана бесконечность? Не дождались финиша бенчмарка?

+1
Интересная статья-дополнение вышла… я попробовал сделать, как рекомендовал автор и вот результат, если кратко — C++ проигрывает C, C проигрывает Ada. Причем код ассемблера у всех разный

Самое интересное — вот бы кто-нибудь сдалал тест на fortran с компилятором от Интела — думаю, что он бы порвал всех раза в два быстрее считал (по опыту, как ни извращайся, как не оптимизируй, фортран на счетных задачах ровно в 2 раза быстрее ..)
0

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

0

Это тоже не вошло в пост, спасибо, что напомнили, чуть позже сделаю апдейт.


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


У меня нет хорошей интуиции, почему код замедлялся.

0
MATLAB:
function main()
  s1 = char(repmat('a', 1, 15000));
  s2 = s1;
  s3 = char(repmat('b', 1, 15000));
  tic();
  fprintf('%d\n', lev_dist(s1, s2));
  fprintf('%d\n', lev_dist(s1, s3));
  exec_time = toc();
  fprintf('Finished in %.3fs\n', exec_time);
end

function d = lev_dist(s,t)
% Levenshtein distance between strings or char arrays.
% lev(s,t) is the number of deletions, insertions,
% or substitutions required to transform s to t.
% https://en.wikipedia.org/wiki/Levenshtein_distance

    m = length(s);
    n = length(t);
    x = 0:n;
    y = zeros(1,n+1);   
    for i = 1:m
        y(1) = i;
        for j = 1:n
            c = (s(i) ~= t(j)); % c = 0 if chars match, 1 if not.
            y(j+1) = min([y(j) + 1
                          x(j+1) + 1
                          x(j) + c]);
        end
        % swap
        [x,y] = deal(y,x);
    end
    d = x(n+1);
end


Finished in 10.801s

См. также: blogs.mathworks.com/cleve/2017/08/14/levenshtein-edit-distance-between-strings и en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance
+1

Очередной бессмысленный бенчмарк, после Encoding.UTF8.GetBytes для двухбайтовых строк в дотнете и аппроксимации результата по другим бенчам не стал даже читать. Особенно посмеялся с того, что во многих тестируемых языках (баунд)чеки выключены флагом.

+1
Особенно посмеялся с того, что во многих тестируемых языках (баунд)чеки выключены флагом.

Почему? Это полностью соответствует коду на плюсах и коду на хаскеле.

0

Почему не отключили в Моно? почему не использовали ллвм бэкенд? Вы просто так добавили без понимания платформы, кто-то посмотрит и сделает ошибочные выводы — за это я не люблю бестолковые бенчмарки. Я с отключенными баундчеками (вернее их даже не надо отключать, достаточно подсказать компилятору простым условием, а он дальше сам их вырежет) и ллвм бэком прогнал ваш цикл близко к перфомансу Си (что не мудрено раз Си в кланге использует тот же ллвм).

+2

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

0

Зачем включать то, в чём вы не потрудились хотя бы аргументы посмотреть? Бонус — не бонус, а в меня уже кинули ссылкой в стиле "смотри в 5 раз медленее азаза".

+1

Я их заведомо все не могу знать, и про это в статье тоже есть.


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


Да и это действительно размывает смысл статьи, лучше оставить для комментов.

0

Именно, вы даете юзеру красивую табличку и он делает свои выводы, никто из тех, кто пнул шарп даже не открывал ваш код. Им было не интересно что вы ваш бенчмарк меряет конвертацию больших двухбайтовых утф16 строк в два раза меньший утф8, баунд чеки и т.п.

+3

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

+1
В 90% случаев люди вообще не читают статьи. В принципе. У них есть в голове нечто, во что они искренне верят — и они сканируют статьи на предмет кусков, которые бы эту веру подтвердили.

Больше их ничего не волнует. Если у них есть вопрос — они не статью пойдут читать, а на StackOverflow вопрос зададут, зачем им статьи? Только чтобы почувствовать себя «крутыми».
0

Печаль в том что мы идем к тому, что 90% людей не могут прочитать текст длиннее одного твита в твиттере (простите за тавтологию)

0
Можете успокоиться — мы давно там.

Так всегда было и всегда будет.

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

А потом — туда перебрались все. Вы задумайтесь вот над чем: 10% жителей США (взрослых, старше 18 лет) — умеют читать и писать на уровне третьего класса… и не более того.

Думаете ситуация в России или других странах сильно лучше?
0
10% жителей любой страны с населением >100тыс. имеют IQ <80, фактически считаются умственно отсталыми и, обычно, не совсем справляются с начальной школой.
+1
Да, но это не значит, что оставшиеся 90% все прям поголовно профессора.
0

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

0

Дык тут на нем пишут пару интузиастов. Тут тригернул ты мало того что сишников так еще и шарпистов с жавистами которые заполонили все коменты :)

0

А вот чего джависты триггерятся, непонятно — джава там в топчике вообще. Я очень сильно удивился, когда ее запустил.

0
Ну с шарпом у тебя точно пока фейл. Моно говно во всех тестах, а НЕТ от МС не сильно хуже Явы, а местами и лучше (быстрее грузится, но хуже джит).
0

У меня, хуже того, пока не завелся .net core sdk, там что-то оверлей недоступен для моих линуксов, руками софт ставить не комильфо, а ебилды писать для этого я что-то не хочу. Сегодня вот ещё поковыряю, чего там с оверлеем.

+1
Где то пробегал совет прогнать тесты в докере или в снапе с НЕТом.

Но шутка про линуксоида «я не могу установить» выглядит смешно....=)
+2

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

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

Первый позитивный комментарий

0
Тем не менее все такие статьи кончаются одним и тем же: выясняется что идеоматичный код на C++ неизменно медленнее идеоматичного же кода на C.

То есть zero-cost abstractions — всё ещё нифига не zero-cost. Впрочему сейчас они уже в пределах 20-30%, похоже… но всё равно неприятно.
0
Закон сохранения энергии… она была потрачена на дополнительные уровни абстракции. Но опять же, пример из статьи для меня не показателен, нужно безопасней и читабельно — пишем С++, нужно быстро и оптимально — делаем вставки С кода или специально оптимизированного С++, избегая стандартной библиотеки и хип менеджера.
Все эти сравнения это чистой воды PR и войны за популярность с препрятанным роялем в кустах и еще до написания статьи известным результатом ибо цель это воздействие на сообщество и его управляемая реакция, а не инжиниринг и действительно объективное сравнение
+3
Ну почему же «заранее известный результат-то». Я вот для себя сделал аж три интересных октрытия:
1. initializer_list всё ещё не всегда изводится clangом
2. Numba крута (надо будет поиграться).
3. «Безопасный char» проще всего сделать через типизированный enum

Вполне приятный выхлоп с одной статьи…
0
Согласен, есть интересные моменты в статье и в целом это очень граммотный пример пропаганды — не просто в чем то пытаются убедить, а как бы делают вид, что не пытаются, показывают интересные трюки, а параллельно внедряя идею. В этом и отличие от тупой пропаганды «хаскель лучше Х, тчк!»
Статья начинается с «У меня тут случайно код на хаскеле получился быстрее аналогичного кода на C++. Иногда — на 40%.»
И дальше очень много работы для «случайного» результата, куча отпимизаций хаскеля, очень много учебных хинтов для новичков и разумеется, результат тот что нужен.
Это классика умной пропаганды через вброс, доверие и заинтересованность.
Помнится англичане еще во время мировой в пику немцам выдавали честные сводки с фронтов, настолько честные что немцы им доверяли больше чем своит… мастерски примешивая нужные им выводы в правильной пропорции.

Если цель статьи это инжинириг сравнение делается многофакторное, с участием специалистов из каждой области которые умеют готовить яву, С++, питон, хаскель и прочие. Замеры всех потребляемых ресурсов, времени разработки, сбоев, надежности, каждый старается выдать максимально оптимальный код из своей области.
Плюс правильная постановка задачи где не сравнивается несколько сотен ассеблерных инструкций которые у одного языка удачно ложаться на пайплайны процессора.
Что уж далеко ходить мы в свое время развлекались на С/С++ и один и тот же код у разных людей получался в 30 раз быстрее/медленнее, просто потому что кто-то знает как это утоптать, а кто-то еще нет. 30 раз это не погрешность :)
Поэтому для меня эта статья умелая провокация с хорошо установленной целью :) Автор молодец :)
+1
И дальше очень много работы для «случайного» результата, куча отпимизаций хаскеля

Которая заняла всего час.


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

Эм, да. И в этом смысл статьи — поделиться информацией о том, какие действия как влияют на код.


результат тот что нужен

Вернее, тот, что был анонсирован. Другое дело, что если бы результат был сильно другим, то статьи (или сравнения с C и C++, по крайней мере) не было бы. И про это в статье тоже есть :)


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

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

0
Которая заняла всего час.

Вы очень производительны, чтоб за час разработать тесты, сделать все замеры, написать статью и отвечать в комментах :)
Не поймите меня не правильно, я без претензии к статье, это хорошая работа и хорошая популяризация.
Как вот измерить то, что основной проект, где это будет использоваться, у меня на хаскеле, а с FFI в плюсы я нагеморроился куда больше, чем с этими всеми оптимизациями вместе взятыми?

Интрументы, языки просто инструменты и очень много субъективизма который искажает наши оценки и как видите сколько людей высказалось :) Потому что задеваются струнки которые не являются частью нашего неокортекса, а лежат в древних областях нашего мозга :)
+1
Вы очень производительны, чтоб за час разработать тесты, сделать все замеры, написать статью и отвечать в комментах :)

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


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


Интрументы, языки просто инструменты и очень много субъективизма который искажает наши оценки и как видите сколько людей высказалось :) Потому что задеваются струнки которые не являются частью нашего неокортекса, а лежат в древних областях нашего мозга :)

Отож!


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


Рациональность, в конце концов — это не про неверие в эльфов, а про неверие в эльфов в мире, где эльфов нет, и веру в эльфов в мире, где эльфы есть.

+1

Эх, вот не надо было мне добавлять остальные языки, а надо было оставить те два.


Рецепт холиварной статьи прост — берем один язык и тщательно оптимизируем пример на нем

Не тщательно, из хаскеля тоже можно еще несколько процентов выжать относительно легко.

+1

А добавьте пожалуйста для Rust опцию -C target-cpu=native для более честного сравнения с C(++). На моём Skylake она снижает время работы приведённого кода с 0.65 секунды до 0.55.
(update: вижу, выше уже предлагали, но поиск по Rust тот комментарий не нашёл ввиду русскоязычного написания)

+1
Мне почему-то не понравился тут swap массивов
просто заменив на работу с указателями получилось срезать ещё почти 20%
(запуски произвоизводил бесконечным циклом, результат воспроизводим)
13:24:02 dkorchagin@desktop:/tmp$ git diff test.cpp test2.cpp
diff --git a/test2.cpp b/test.cpp
index 286bd4a..f954792 100644
--- a/test2.cpp
+++ b/test.cpp
@@ -26,25 +26,28 @@ lev_dist(const std::string &s1,
 
     auto v1 = v0;
 
+    auto v0_ptr = &v0;
+    auto v1_ptr = &v1;
+
     for (size_t i = 0; i < m; ++i) {
-        v1[0] = i + 1;
+        v1_ptr->operator[](0) = i + 1;
 
         for (size_t j = 0; j < n; ++j) {
-            const auto subst_cost = (ca1[i] == ca2[j]) ? v0[j] : (v0[j] + 1);
-            const auto del_cost = v0[j + 1] + 1;
-            const auto ins_cost = v1[j] + 1;
+            const auto subst_cost = (ca1[i] == ca2[j]) ? v0_ptr->operator[](j) : (v0_ptr->operator[](j) + 1);
+            const auto del_cost = v0_ptr->operator[](j + 1) + 1;
+            const auto ins_cost = v1_ptr->operator[](j) + 1;
 
             // std::min({ subst_cost, del_cost, ins_cost }) is slow.
-            v1[j + 1] = std::min(subst_cost, del_cost);
-            if (ins_cost < v1[j + 1]) {
-                v1[j + 1] = ins_cost;
+            v1_ptr->operator[](j + 1) = std::min(subst_cost, del_cost);
+            if (ins_cost < v1_ptr->operator[](j + 1)) {
+                v1_ptr->operator[](j + 1) = ins_cost;
             }
         }
 
-        std::swap(v0, v1);
+        std::swap(v0_ptr, v1_ptr);
     }
 
-    return v0[n];
+    return v0_ptr->operator[](n);
 }
 
 int
13:21:29 dkorchagin@desktop:/tmp$ clang++ -std=c++17 -O3 test2.cpp 
13:20:37 dkorchagin@desktop:/tmp$ while true; do ./a.out; done
Finished in 0.492s

13:21:29 dkorchagin@desktop:/tmp$ clang++ -std=c++17 -O3 test1.cpp 
13:21:32 dkorchagin@desktop:/tmp$ while true; do ./a.out; done
Finished in 0.579s


0
Уточнение ради уточнения:
Для java прогнал для 20000 элементов изменив циклы на классический for со счетчиком внутри.
Без данной замены время приблизительно не отличалось от указанного в статье (около 50-70 мс)
macOS Mojave 10.14.6
java 12.0.2-zulu

Код:
Заголовок спойлера
public static long levDist(byte[] s1, byte[] s2)
    {
        int m = s1.length;
        int n = s2.length;

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

        long[] v0 = new long[n+1];
        long[] v1 = v0.clone();

        for (int i = 0; i < s1.length; i++) {
            v1[0] = i + 1;

            for (int j = 0; j < s2.length; j++) {
                long substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
                long delCost = v0[j + 1] + 1;
                long insCost = v1[j] + 1;

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

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

        return v0[n];
    }



Результаты выглядят заметно приятнее:
image
+1

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

0
Еще бы и железо одинаковое. А то я на работе на ноуте i5 сижу, а дома Xeon 24 ядра.
0

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

0

Но автор не разбирается в нюансах разных языков и их методиках тестирования :)

+1
Надо репу на gihub'e создать
Знатоки платформ будут контрибьютить :)
+1
заголовок «Быстрее, чем C++; медленнее, чем PHP»
а что значит вторая часть заголовка «медленнее, чем PHP»?
первая часть, как я понимаю, значит «хаскель Быстрее, чем C++»
тогда вторая — «хаскель медленнее, чем PHP»? или что?
0
Это такая завлекалочка. Raku (бывший Perl 6) у него медленнее PHP вышел.

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

Может лет через 20-30 мы и увидим вторую часть: как дерьмо превратить-таки в конфетку…
+1
да это я к тому, что
если «хаскель медленнее, чем PHP»,
то «PHP быстрее, чем хаскель»
но «хаскель Быстрее, чем C++»
и тогда «PHP быстрее, чем C++»
тогда как в статье наоборот!
-1

Вы как буд-то первый кликбэйтный заголовок на хабре увидели.

0
Вот код с лёгкими оптимизациями для Delphi, без ассемблера и арифметики указателей, который работает быстрее исходного кода, приведённого у вас для Pascal. У меня примерно на 30%. Для использования в боевой программе лучше конечно переписать часть или всё на ассемблере.
function LevenshteinDistance2(const S1, S2: RawByteString): UInt32;
var
  len1, len2, i1, i2: NativeUint;
  c1: AnsiChar;
  v0, v1: TArray<UInt32>;
begin
  len1 := Length(S1);
  len2 := Length(S2);
  if len1 = 0 then
    Exit(len2)
  else if len2 = 0 then
    Exit(len1);
  SetLength(v0, len2+1);
  for i1 := 0 to len2 do
    v0[i1] := i1;
  v1 := Copy(v0, 0, len2+1);
  for i1 := 1 to len1 do begin
    c1 := S1[i1];
    v1[0] := i1;
    for i2 := 1 to len2 do begin
      var cost1 := v0[i2-1] + UInt32(c1 <> S2[i2]); // Cost of substitution
      var cost2 := v0[i2] + 1; // Cost of deletion
      if cost1 > cost2 then
        cost1 := cost2;
      cost2 := v1[i2-1] + 1; // Cost of insertion
      if cost1 < cost2 then
        v1[i2] := cost1
      else
        v1[i2] := cost2
    end;
    var temp := v0;
    v0 := v1;
    v1 := temp;
  end;
  Result := v0[len2]
end;

0
И ещё вариант на Delphi, немного задействовал поинтеры. +17% к скорости предыдущей версии без поинтеров, +42% к исходной версии в статье. Но -кроссплатформенность.
function LevenshteinDistance3(const S1, S2: RawByteString): UInt32;

  procedure Swap(var P1, P2); inline;
  var
    temp: Pointer;
  begin
    temp := Pointer(P1);
    Pointer(P1) := Pointer(P2);
    Pointer(P2) := temp
  end;

var
  len1, len2, i1: NativeUint;
  c1: AnsiChar;
  v0, v1: TArray<UInt32>;
begin
  len1 := Length(S1);
  len2 := Length(S2);
  if len1 = 0 then
    Exit(len2);
  if len2 = 0 then
    Exit(len1);
  SetLength(v0, len2+1);
  for i1 := 0 to len2 do
    v0[i1] := i1;
  v1 := Copy(v0, 0, len2+1);
  for i1 := 1 to len1 do begin
    c1 := S1[i1];
    v1[0] := i1;
    var p0: PUInt32 := @v0[0];
    var p1: PUInt32 := @v1[0];
    var ps2: PAnsiChar := @S2[1];
    while ps2^ <> #0 do begin
      var cost1 := p0^ + UInt32(c1 <> ps2^); // Cost of substitution
      Inc(p0);
      var cost2 := p0^ + 1; // Cost of deletion
      if cost1 > cost2 then
        cost1 := cost2;
      cost2 := p1^ + 1; // Cost of insertion
      Inc(p1);
      if cost1 < cost2 then
        p1^ := cost1
      else
        p1^ := cost2;
      Inc(ps2)
    end;
    Swap(v0, v1);
  end;
  Result := v0[len2]
end;
0
Заодно уже, чтоб 2 раза не бегать по Гуглу: Calculation of the Damerau–Levenshtein distance, an optimized algorithm written in the pure Delphi language is here:
Spoiler header
function DamerauLevenshteinDistance(const S1, S2: RawByteString): UInt32;
var
  len1, len2, i1, i2: NativeUint;
  c1, c2, prevC1, prevC2: AnsiChar;
  v_1, v0, v1: TArray<UInt32>;
begin
  len1 := Length(S1);
  len2 := Length(S2);
  if len1 = 0 then
    Exit(len2);
  if len2 = 0 then
    Exit(len1);
  SetLength(v_1, len2+1);
  SetLength(v0, len2+1);
  for i1 := 0 to len2 do
    v0[i1] := i1;
  v1 := Copy(v0, 0, len2+1);
  prevC1 := #0;
  for i1 := 1 to len1 do begin
    c1 := S1[i1];
    v1[0] := i1;
    prevC2 := #0;
    for i2 := 1 to len2 do begin
      c2 := S2[i2];
      var cost := UInt32(c1 <> c2);
      var cost1 := v0[i2-1] + cost; // Cost of substitution
      var cost2 := v0[i2] + 1; // Cost of deletion
      if cost1 > cost2 then
        cost1 := cost2;
      cost2 := v1[i2-1] + 1; // Cost of insertion
      if cost1 > cost2 then
        cost1 := cost2;
      if (c1 = prevC2) and (prevC1 = c2) then begin
        cost2 := v_1[i2-2] + cost; // Cost of transposition
        if cost1 > cost2 then
          cost1 := cost2
      end;
      v1[i2] := cost1;
      prevC2 := c2
    end;
    var temp := v_1;
    v_1 := v0;
    v0 := v1;
    v1 := temp;
    prevC1 := c1
  end;
  Result := v0[len2]
end;

0
Паскаль прекрасный учебный язык.

Но на практике все спотыкается о то, что никто не хочет на нем писать.

Он может прекрасно оптимизироваться, но последние версии GPC от 2007 года, а FPC и Дельфи сложно назвать современными оптимизирующими компиляторами (

Ну и цена лицензии на Д-Архитект это просто гвоздь.

Я бы смотрел на миграцию в Го, там похожий то стилю язык.
0
Ну и цена лицензии на Д-Архитект это просто гвоздь.
А оно для всех экзотических языков примерно на одном уровне. Недавно только обнаружил, что Visual Age for Smalltalk во-первых ещё продаётся, а во-вторых — вот по такой вот цене.
0
Такой?
Call or Email for Pricing
Впрочем за Смаллток всегда просили от 5к$ и потому в том числе он и загнулся.

Ада чудом избежала такой судьбы получив GNUada
0

Вы в аде тут все шарите, что ли?


Если да, то я слышал, что в агду завезут завтипы в следующем релизе стандарта. Правда, ссылка вела на статью в Вики, а там я ничего не нашел. Это правда или какая-то ерунда?,

0
Я не совсем понимаю завтипы. Вот например в Аде есть (от начала) тип массив с «какой-то» длиной, это ведь зависимый тип? Он при указании переменной такого типа должен быть инстантиирован значением диапазона (тип диапазона как раз и задается при объявлении типа. Вот так, например:
 type QR is array (Natural range <>) of Character;
 P : QR(7..1001);


Вы такое имели в виду?
0

Это просто дженерик. Зависимый тип выглядит как-то так:


type QR is array (Natural range <>) of Character;
N : Natural;
P : QR(1..N);
0
Это то же самое. Но тогда еще зависимые типы — все generic (вот уж где зависимость, так зависимость), а также параметрические описания task…

Видимо, я все же не понимаю, что такое зависимые типы :(, ну или это наоборот, очень просто…
0

Если это то же самое, то скажите сколько получилось элементов в этом массиве P.

0
согласно правилам языка — 0 элементов, так как неинициализированных переменных нет, то N примет значение 1 (как минимальное для своего типа) и стало быть QR станет массивом от 1 до 1 — то есть 0 элементов
0

Но это и означает, что завтипов нет. Были бы завтипы — вы бы не смогли посчитать количество элементов как константу, оно бы зависело от N.

0
Интересно, что если в вашем примере N было бы Integer, то была бы ошибка времени исполнения, так как его значение по умолчанию 0
0
Для бизнес-приложений под Windows оптимизации достаточно (+ассемблер для узких мест). Библиотека VCL вылизана донельзя за долгие годы, FireMonkey тоже юзабельным стал. Так что если писать коммерческие программы под Windows, можно часто не обновлятся.

Ну а учиться и новые фичи можно трогать в бесплатном Delphi Community Edition. Вот ждём вскоре 10.4, с обещанными давно Custom Managed Records. Можно будет делать мощные вещи, не теряя в производительности. Ещё раньше были разговоры про LLVM-бэкэнд в компилятор под Windows, но пока это заглохло. Пока он задействован только в компиляторе для iOS, Android и Linux. А так — жизнь продолжается.
0
Лицензия на Community Edition не позволяет никакой коммерческой деятельности, если ты не Диоген конечно. Файрманки и платформы кроме вин настолько сырые, что без обновлений никак.

Впрочем, относительно этой статьи это оффтоп. А касательно — оптимизатор в Дельфи средненький. Но, кстати, можно нормировать тесты относительно С-Билдера — там хоть LLVM. Посмотрим.
0
Я ссылку выше кидал, есть и для Delphi LLVM-based compilers, кроме Windows. Программы, написанные на Community, можно продавать, но там ограничение по сумме за год. Поэтому коммерческая разработка на CE только для стартапов. (Иначе в CE не было бы смысла для Embarcadero, ведь по фичам эта редакция эквивалента Pro). Насчёт сырости спорить не буду, т.к. для меня Windows основная платформа, и здесь всё тип-топ.
0
Коммунити версия с ограничением дохода 5k$ в год. См.Диоген.

Pro теперь без клиент сервера, который всегда был киллер фичей.
LLVM-based compilers, кроме Windows… для меня Windows основная платформа
ну ОК, что сказать.

Ешьте сами
+1
Если за год заработать на продаже программ написанных на Delphi CE $5000, придётся отдать $1650 за новую лицензию Pro. Нет — значит нет. Мне кажется, для стартапов и некоммерческих организаций нормально. По сравнению с тем, что было раньше — небо и земля. Я помню Delphi XE2 Starter Edition: обрезанная версия, без исходников библиотек VCL и FireMonkey, продавалась за деньги. И то люди на ней писали клиент-серверные приложения, прикручивая сторонние библиотеки. А про проблемы, связанные с развитием и поддержкой Delphi я и сам знаю.

Что касается оптимизации, ну вот я, немного посидев, ускорил выложенную в статье реализацию на 40%. А есть более быстрые алгоритмы для решения этой задачи. Например, можно попробовать вот эту реализацию для алгоритма Дамерау-Левенштейна. Там хранится только одна строка матрицы расстояний, а не две, добавлены оптимизации для похожих строк.
0
А есть более быстрые алгоритмы для решения этой задачи.
Вы думаете на других языках невозможно реализовать «более быстрые алгоритмы»? Возможно, конечно. А ведь по сути Delphi — ближе к Ada, чем к C++… должно быть быстрее.

Впрочем всё это фигня: разница в скорости является проблемой, когда она 10x или там 100x. Разница в 10-15% ничего не решает вообще и даже 50% — это терпимо.

Мне кажется самая большая проблема Delphi — они «потеряли хайп». Было время, когда во всех в школах и институтах Pascal учили поголовно. Вот в те времена Delphi мог бы взлететь — достаточно легко.

А сегодня учат Python, С++ или Java. В этом беда. И непонятно что с этим можно сделать.

А цены и даже скорость — это как раз не так критично.
0
Можно много писать что было сделано не так, но надо исходить из того, что есть.

Возвращаясь к оптимизации (по теме) компилятору Delphi для Windows не хватает более широко использования регистров процессора. Практически не используется EBX. Большинство операций выглядят так: читаются данные из стека в EAX, обрабатываются, и тут же сбрасываются обратно в стек. Иногда бывает два подряд идущих
mov [ebp-$4c],eax
mov eax,[ebp-$4c]

Поэтому обработки на Delphi всегда чуть сзади хорошо оптимизированных C-модулей. С другой стороны, кэш L1 в современных процессорах, где обычно обитает стек текущей процедуры, очень быстрые. Вот здесь пишут про доступ в 4 такта. И размер его всё время растёт, в моём AMD Ryzen 5 3600 это 384КБ. + паралельное исполнение команд и предсказание ветвлений в процессоре. Поэтому где недоработал компилятор — выручает современный процессор, и в целом разница по скорости с C есть, но не критична.
0
Это где вы L1 кеш растущий увидели? Или это вы просуммировали размеры L1 кеша для всех ядер?

Наоборот — размер L1 кеша это [почти] константа. Вот как появились 16K кеша примерно четверть века назад — так и ходит индустрия между тремя размерами: 16K/32K/64K… причём в Zen2 как раз обратно на 32K вернулись.

Но и если бы там шла речь про L1 — то Delphi отставал бы от C++ на порядок (4 такта плюс 2-3 операции за такт). На самом деле в современных процессорах есть специальные схемы для ускорения подобного кода, так как он был весьма характерен для вообще всех старых компиляторов.

Возвращаясь к оптимизации (по теме) компилятору Delphi для Windows не хватает более широко использования регистров процессора.
Если то, о чём вы пишите, правда — то ему не хватает вообще хоть какого-то оптимизатора. Потому что подобные вещи уже даже в самых ранних версиях GCC, треть века назад, обрабатывались прилично — с очень редкими случаями такого ужаса, как вы описываете.

То есть это как раз тот случаяй, когда чинить бессмысленно — нужно выкидывать и переписывать. Ну или прикрутить LLVM…
-1
Конечно 384КБ L1 на процессор. Я и пишу, надежда насовременный процессор.

Когда-то была идея написать типа пост-компилятора конкретно под программы на Delphi 32-bit. Передаём утилите EXE, MAP файлы, и указываем процедуры в узких местах, которые требуется оптимизировать. А она находит все такие участки как выше пример, и забивает лишнее NOP или XOR или другой дешёвой операцией. Там ещё и другие паттерны можно выловить, которые прям в глаза бросаются. Вот как пример:
mov edx,[ebp-$18]
mov ecx,[ebp-$18]

Или вот, cost1 уже загружена в регистр eax, можно переиспользовать:
uLevenshtein.pas.199: cost1 := cost2
mov eax,[ebp-$40]
mov [ebp-$3c],eax
uLevenshtein.pas.201: v1[i2] := cost1;
mov eax,[ebp-$2c]
mov edx,[ebp-$1c]
mov ecx,[ebp-$3c]
mov [eax+edx*4],ecx

Интересно, насколько можно было бы ускорить обработку…
0
Конечно 384КБ L1 на процессор.

На процессор, не на ядро. Если у вас алгоритм однопоточный и живёт на одном ядре, то кеши на остальных ядрах вам никак не помогут, увы.

0
Попробовал ускорить код на C++: использовать vector и избавиться от std::min.

Исходный вариант: 100% (4733 мс)
Вариант с заменой string на vector: 85,6% (4051 мс)
Вариант с заменой на вектора и заменой std::min на два if-а: 50,6% (2394 мс).

Т.е. парой действий в рамках C++ можно ускорить код на 97,7%, почти в 2 раза.

0
Можно добавить прогрев JVM в тест по Java? Просто несколько прогонов теста подряд. У меня результаты такие:
0
15000
Finished in 0,705s
0
15000
Finished in 0,588s
0
15000
Finished in 0,425s
0
На самом деле при подсчёте расстояния Левенштейна необязательно заводить второй массив. Можно вполне справиться с одним массивом и ячейкой памяти на предыдущий диагональный. Выглядит это примерно следующим образом (здесь правда ещё идёт шаблонизация, чтобы можно было использовать не только для строк, но и для векторов):
#include <algorithm>
#include <vector>

template<typename T>
typename T::size_type LevenshteinDistance(const T &source,
                                          const T &target) {
    if (source.size() > target.size()) {
        return LevenshteinDistance(target, source);
    }

    using TSizeType = typename T::size_type;
    const TSizeType min_size = source.size(), max_size = target.size();
    std::vector<TSizeType> lev_dist(min_size + 1);
    std::iota(lev_dist.begin(), lev_dist.end(), 0);

    for (TSizeType j = 1; j <= max_size; ++j) {
        TSizeType previous_diagonal = lev_dist[0];
        TSizeType previous_diagonal_save;
        ++lev_dist[0];

        for (TSizeType i = 1; i <= min_size; ++i) {
            previous_diagonal_save = lev_dist[i];
            if (source[i - 1] == target[j - 1]) {
                lev_dist[i] = previous_diagonal;
            } else {
                lev_dist[i] = std::min(std::min(lev_dist[i - 1], lev_dist[i]), previous_diagonal) + 1;
            }
            previous_diagonal = previous_diagonal_save;
        }
    }

    return lev_dist[min_size];
}
0

Есть на самом деле ещё более эффективные алгоритмы, но это уже совсем другая история.

0
С Java получилось заметно быстрей если использовать обычные циклы, тестировал с помощью JMH
Benchmark Mode Cnt Score Error Units
JMH.test avgt 5 575.046 ± 26.305 ms/op
Против
Benchmark Mode Cnt Score Error Units
JMH.test avgt 5 982.166 ± 63.062 ms/op
Заголовок спойлера
public static long levDist(byte[] s1, byte[] s2) {
        int m = s1.length;
        int n = s2.length;

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

        long[] v0 = new long[n + 1];
        for (int i = 0; i < n + 1; i++) {
            v0[i] = i;
        }
        long[] v1 = v0.clone();

        for (int i = 0; i < s1.length; i++) {
            v1[0] = i + 1;
            for (int j = 0; j < s2.length; j++) {
                long substCost = (s1[i] == s2[j]) ? v0[j] : (v0[j] + 1);
                long delCost = v0[j + 1] + 1;
                long insCost = v1[j] + 1;
                v1[j + 1] = Math.min(substCost, delCost);
                if (insCost < v1[j + 1]) {
                    v1[j + 1] = insCost;
                }
            }
            long[] temp = v0;
            v0 = v1;
            v1 = temp;

        }
        return v0[n];
    }

+2

Не успел прочитать все комментарии, поэтому поправлю шарповый код (поправил баг с неправильным заполнением v0 и v1, за основу взял вариант из раста):


public static Int32 LevDist(byte[] s11, byte[] s22)
{
    var n = s22.Length;
    // Edge cases.
    if (s11.Length == 0)
    {
        return s22.Length;
    }

    if (s22.Length == 0)
    {
        return s11.Length;
    }

    var s1 = s11.Select(x => (int) x).ToArray();
    var s2 = s22.Select(x => (int) x).ToArray();

    var v0 = new Int32[n + 1];
    var v1 = new Int32[n + 1];

    for (int i = 0; i < v0.Length; i++)
    {
        v0[i] = i;
    }

    for (int i = 0; i < v1.Length; i++)
    {
        v1[i] = i;
    }

    for (var i = 0; i < s11.Length; i++)
    {
        v1[0] = i + 1;

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

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

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

    return v0[n];
}

Изначальная версия: 0.789 секунд
Версия с выравниванием: 0,635 секунд — видимо, джиту трудно работать с невыровненными данными. Поэтому копируем байтовый массив в интовый
Версия с инлайном длины массива: 0.53 секунд — сохраннение длины массива известная деоптимизация. Сишарп выкидывает проверки только если видит длину массива. Если Сохранить её в переменную — проверка вернется.


Ну и желательно включить галку x64 при сборке, потому что х86 почти в 1.5 раза медленнее.


Вариант на расте на моей машине прогняется за 0.456 секунд. Таким образом вариант на шарпе отрабатывает на 16% дольше раста, ну и следовательно равняется 144% от плюсового эталона.




Пока загорелся оптимизацией шарпа, забыл сказать — спасибо за материал! Отличный слог, и глубокая проработка. Бенчи на всех языках так вообще бесподобны.

0

Спасибо!


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


Обратите внимание, что для сравнения времени ваши результаты надо либо перенормировать на длину а 20 тыщ (учитывая, что алгоритм квадратичный), либо просто в коде поменять 15 на 20 везде.

0

Проблема в том что bash: dotnet: command not found, и поставить в 2 клика из пакетного менеджера на ОСи человека не представляется возможным.

0
mkdir /tmp/app
docker run -it --rm -v /tmp/app:/app mcr.microsoft.com/dotnet/core/sdk:3.1 bash
cd /app
dotnet new console
dotnet run -c release 
exit
0

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

+1
dotnet build -c release -r linux-x64

потом можно запустить готовое приложение без докера:


/tmp/app/bin/release/netcoreapp3.1/linux-x64/app
0

Он может внести погрешности в системные вызовы, но не в вычислительную задачу.

+1

Пожалуйста, следите кто и на что отвечает. Я отвечал на вот этот комментарий:


Если заведется, то как им пользоваться и что нажимать, чтобы собрать все как надо с оптимизацией?

Если заведется, то у него таки будет команда dotnet.

0

Кстати раст я ведь тоже гонял на 15 тыщах, так что пропорция сохраняется.

0
Если в коде на Julia сделать пару изменений, то на моей машине время выполнения падает раза в 2:
1. Убрать аннотации типов
2.
codeunits(...)
на
Int64.(codeunits(...))

3.
(i, ...) in enumerate(...)
на
i in 1:length(...)


Не знаю почему последний пункт влияет, компилятор почему то не до конца оптимизирует.
-1
Однажды в универе (2-ой курс) нам задали задачку — реализовать какой-то метод шифрования (уже не помню какой точно), где в частности использовалось побитовое сложение.
Я реализовал первый вариант на VB6. Работало очень медленно.
Тогда я решил, что можно написать библиотеку на С++ и вызвать ее из VB6. Этот вариант работал значительно быстрее, но в процессе написания я выяснил, что можно и на VB6 переписать так, чтобы работало быстро — и переписал, получив скорость, почти идентичную с С++ библиотекой.
Фишка была в том, что в первой версии на VB6 вместо операции побитового сложения я вручную переводил каждый символ в строку из нулей и единиц, вручную же складывал, а потом преобразовывал обратно. Естественно это работало очень медленно.

К чему это я? Прежде чем сравнивать скорость работы различных ЯП, стоит убедиться, что код на них одинакового качества.
0

Да уж. Получается, всё-таки, что на каждое применение нужен свой инструмент. А вот какой именно, понимаешь уже чисто на опыте: не всегда в сети найдёшь пример с решением, похожий именно на твою ситуацию. Опыт и знание нескольких языков рулят.

0

Позволил себе пооптимизировать ваш алгоритм на D.


Добавил функцию min, которая не использует ветвления:


auto min(N)(N a, N b)
{
    auto d = b - a;
    return a + (d & (d >> (N.sizeof * 8 - 1)));
}

Избавился от второго массива и лишних обращений к массивам по индексу:


long levDist(String)(in String str1, in String str2)
{
    if (str1.length == 0)
        return str2.length;
    if (str2.length == 0)
        return str1.length;

    long[] costs = str1.length.to!long.iota.array;

    foreach (i, char1; str1)
    {
        auto delCost = costs[0];
        auto insCost = i.to!long + 1;

        foreach (j, char2; str2)
        {
            auto substCost = delCost;
            if (char1 == char2)
                --substCost;

            delCost = costs[j];

            insCost = 1 + substCost.min(delCost).min(insCost);

            costs[j] = insCost;
        }
    }

    return costs[str1.length - 1];
}

Ну и код переписал более идиоматично. Возможно где-то накосячил, не до конца разобравшись в алгоритме.

0
Добавил функцию min, которая не использует ветвления

А это точно быстрее работает? Например, современные компиляторы С++ свои std::min через conditional move реализовывают.

Only those users with full accounts are able to leave comments.  , please.