El artículo [enlace] declaró que el rendimiento del código Haskell fue superior al código C ++. Lo que inmediatamente despertó interés, como LLVM puede generar ambos por el compilador, lo que significa que Eskell puede dar más pistas al compilador o algo está mal con la implementación de C ++. A continuación, analizaremos cómo una serie de accidentes en las acciones del autor llevaron a conclusiones incorrectas, que se describen en la tabla a continuación (debajo del corte).

Prefacio

Recientemente, otro artículo de0xd34df00dHaskell optimización de código. En tales casos, se compara naturalmente con el líder indiscutible en rendimiento: C / C ++. Luego vino un análisis de este artículo deyleosobre qué código asm es realmente mejor y cuál es la diferencia entre las implementaciones en diferentes idiomas (recomiendo leer). Incluso antes (hace aproximadamente un mes y medio), se publicó el artículo anterior de la serie Haskell vs C / C ++, e hice un análisis similar, pero en lugar de publicarlo en Habr, por desgracia, lo puse en la caja posterior. Las acaloradas discusiones en los comentarios de esta semana me llevaron a volver al tema anterior. Hoy finalmente saqué ese documento de descuento del cajón, desempolvé el polvo,terminadoy proporcionarlo para su revisión.

Introducción

, [], :

/++, .. , , " , ". "", . , , , 10- .

-, , ++ , , , . , zero-cost, , , , - ++, . , clang 3 (!) , +, , .. lang llvm — .

, : gcc clang. , . ( ), gcc . , , , , , .

std::min({...})

, , std::min.

C++.
, std::min({delCost, insCost, substCost})
std::min(substCost, std::min(delCost, insCost)),
clang — 0.840
, .
( — 0xd34df00d)

:

A.unsafeWrite v1 (j + 1) $ min (substCost + substCostBase) $ 1 + min delCost insCost

, min ! (, ). , , C++ , , llvm llvm. , . , , "skell " . , " ++; , PHP" , , . :

stdlib gcc - std::min , ++. std::min_element. , , , :

f(int, int, int):
        cmp     esi, edi
        mov     eax, edx
        cmovg   esi, edi
        cmp     esi, edx
        cmovle  eax, esi
        ret

: cmov* = conditional move (: g — greater, le — less equal, ..).

, , , , clang, gcc, - ( rsp ):

fptr(int*, int*, int*):
        mov     eax, dword ptr [rdi]
        mov     dword ptr [rsp - 12], eax
        mov     ecx, dword ptr [rsi]
        mov     dword ptr [rsp - 8], ecx
        cmp     ecx, eax
        cmovle  eax, ecx
        mov     ecx, dword ptr [rdx]
        cmp     ecx, eax
        cmovle  eax, ecx
        ret

, clang . initializer_list asm -O1, (-O2), asm . , std::min(std::initializer_list) -, -, , .

s1[i]

, — , ++.

s1[i] ! ()

, , , - , , . , s1[i] ,

  let s1char = s1 `BS.index` i
  let go j | j == n = pure ()
    --  

++, , clang. .. + llvm - , -march=native. , , std::min , , ! , - , " " , .

C++ .
,
C main', .
( )

, , , - , :

  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];
      for (size_t j = 0; j < n; ++j) {
        auto substCost = c1 == s2[j] ? v0[j] : (v0[j] + 1);
        v1[j + 1] = std::min(substCost, std::min(v0[j + 1], v1[j]) + 1);
      }
      std::swap(v0, v1);
    }
    return v0[n];
  }

32- int — , ( ).

, GCC . j , GCC. clang .

LLVM == LLVM

-, , ++ Haskell , clang-9. , Skylake C++ . , , , Haswell, .

, , , GCC LLVM.

, , llvm, ffi, .

GCC vs CLANG

-, , gcc . , clang- .

, , , , (#if !defined(__GNUC__) || defined(__llvm__)), ++ , , ++ .

clang ( ) . ( )

, GCC LLVM. , asm. gcc - : , cmov* min ( , ). (3), , , ++ :

      for (size_t j = 0; j < n; ++j) {
        auto delCost = v0[j + 1] + 1;
        auto insCost = v1[j] + 1;
        auto substCost = c1 == s2[j] ? v0[j] : (v0[j] + 1);
        v1[j + 1] = std::min(substCost, std::min(delCost, insCost));
      }

, , :

.L42:
        inc     rcx  // j++
        mov     rdi, QWORD PTR [r12+rcx*8]  //  v0[j+1]
        xor     edx, edx  //  %edx
        cmp     r10b, BYTE PTR [r11-1+rcx]  // c1 == s2[j]
        setne   dl  //     %rdx
        lea     r9, [rdi+1]  //  v0[j+1] + 1
        add     rdx, QWORD PTR [r12-8+rcx*8]  //  v0[j]
        lea     rsi, [rax+1]  // %rax  v1[j]
        cmp     rdi, rax  //  v0[j+1]  v1[j]  += 1
        mov     rax, r9
        cmovg   rax, rsi  //       += 1
        cmp     rax, rdx  //  %rax, %rdx
        cmovg   rax, rdx
        mov     QWORD PTR [r8+rcx*8], rax  // v1[j+1] = ...
        cmp     rbx, rcx  // loop
        jne     .L42

, — v1[j] %rax.

LLVM, - , . , , :

.LBB1_40:                               #   in Loop: Header=BB1_36 Depth=2
        mov     qword ptr [r14 + 8*rsi + 8], rax
        mov     rdx, qword ptr [rbx + 8*rsi + 16]
        inc     rdx
        inc     rax
        xor     ebp, ebp
        cmp     cl, byte ptr [r13 + rsi + 1]
        setne   bpl
        add     rbp, qword ptr [rbx + 8*rsi + 8]
        cmp     rax, rdx
        jg      .LBB1_41
        lea     rdi, [rsi + 2]
        cmp     rax, rbp
        jle     .LBB1_44
        jmp     .LBB1_43

: jmp, j* = jump (: jg — greater, jle — less equal, ..).

v0[j+1], v0[j], cmp s1[i], cmp + jump . , , ( , ) , , . — .

, GCC , LLVM 2 (!) , .

, . : (jump), — (cmov).
, — .

, , . , , PGO (, JIT ). , GCC PGO clang. — , . , , // , , , .

• , —
• , LLVM
• , GCC LLVM ,
• ffi. , .. , , ,

, , .

: , , "" , , . Rust (, ).

P.S.

— , -
( )

, — , .. , , , s1 s2. . -, O(n*m) ( for). , . , k. , . , .

LinearLeopard .

• : -O3 -march=native -std=gnu++17.
• Procesador: Intel i5-8250U (sí, computadora portátil)
• SO: Ubuntu 19.04 / Linux 5.0.0
• La primera carrera para acelerar el turbo boost, luego toma un mínimo de cinco seguidos. Desviaciones dentro del 1-2%.
• Entre los lanzamientos de diferentes implementaciones de 1s, nos enfriaremos (sí, laptop)

Añadido: guiones para los perezosos

Puede ejecutar lo mismo en su hardware y decirle al público el resultado: un enlace al github .

Agregado: Resultados sin -march = native

De acuerdo con las solicitudes en los comentarios, decidí verificar la influencia de esta bandera.