ذكرت المقالة [link] أن أداء كود Haskell كان أفضل من كود C ++. ما أثار على الفور الاهتمام ، كما يمكن إنشاء كلاهما بواسطة LLVM من قبل المترجم ، مما يعني إما أن Eskell يمكن أن يعطي المزيد من التلميحات للمترجم ، أو أن هناك خطأ في تنفيذ C ++. بعد ذلك ، سنحلل كيف أدت سلسلة من الحوادث في تصرفات المؤلف إلى استنتاجات غير صحيحة ، موصوفة في الجدول أدناه (تحت القطع).

مقدمة

في الآونة الأخيرة ، مقال آخر من0xd34df00dتحسين كود هاسكل. يقارن في مثل هذه الحالات بشكل طبيعي مع الزعيم الذي لا يمكن إنكاره في الأداء - C / C ++. ثم جاء تحليل هذا المقاليليوحول ما هو رمز asm الأفضل حقًا ، وما الفرق بين عمليات التنفيذ على لغات مختلفة (أوصي بالقراءة). حتى قبل ذلك (قبل شهر ونصف تقريبًا) ، تم نشر المقالة السابقة من سلسلة Haskell vs C / C ++ ، وقمت بتحليل مماثل ، ولكن بدلاً من نشرها إلى Habr - alas ، قمت بوضعها في الصندوق الخلفي. لقد دفعتني المناقشات الساخنة في التعليقات هذا الأسبوع بالعودة إلى الموضوع السابق. اليوم أخيرًا حصلت على وثيقة تخفيض السعر من الدرج ، وأتلفت الغبار ،تم الانتهاء من، وقدمها لمراجعتك.

المقدمة

, [], :

/++, .. , , " , ". "", . , , , 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.
• المعالج: Intel i5-8250U (نعم ، لابتوب)
• نظام التشغيل: Ubuntu 19.04 / Linux 5.0.0
• الجولة الأولى لتسريع تعزيز التوربو ، ثم تأخذ ما لا يقل عن خمسة على التوالي. الانحرافات في حدود 1-2٪.
• بين إطلاق تطبيقات مختلفة من 1s ، سنهدأ (نعم ، كمبيوتر محمول)

أضيفت: مخطوطات للكسل

يمكنك تشغيل نفس الشيء على جهازك وإخبار الجمهور بالنتيجة: رابط إلى جيثب .

تمت إضافة: النتائج بدون -march = أصلية

وفقًا للطلبات الواردة في التعليقات ، قررت التحقق من تأثير هذا العلم.