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

Если хочешь, вот что я сравнивал (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с

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

А размеры…

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

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

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

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

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

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

Похоже, что V8 от Math.min, наоборот, получает выигрыш.

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

Э-хэм…

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

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

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

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

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

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

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

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() {
    <…>

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

Погружаемся в opensource-экосистему Android

SafetyNet "Basic Integrity" c Magisk и microG должен успешно проходиться, коли microG и DroidGuard Helper находятся в priv-app (например, через модуль Magisk systemize), и Magisk Hide использован на нужном приложении.
Но если стоит Xposed Framework, нужный для подмены подписи через FakeGapps, то тогда нет, basicIntegrity не пройдёт.