लेख [लिंक] ने कहा कि हास्केल कोड का प्रदर्शन C ++ कोड से बेहतर था। क्या तुरंत रुचि जगी, जैसा कि दोनों कंपाइलर द्वारा LLVM द्वारा उत्पन्न किए जा सकते हैं, जिसका अर्थ है कि या तो एस्सेल कंपाइलर को अधिक संकेत दे सकता है, या C ++ कार्यान्वयन के साथ कुछ गलत है। इसके बाद, हम विश्लेषण करेंगे कि लेखक के कार्यों में दुर्घटनाओं की एक श्रृंखला ने गलत निष्कर्ष कैसे निकाले, जो नीचे दी गई तालिका (कट के तहत) में वर्णित हैं।

प्रस्तावना

हाल ही में, एक और लेख से0xd34df00dहास्केल कोड अनुकूलन। इसकी तुलना ऐसे मामलों में स्वाभाविक रूप से प्रदर्शन में निर्विवाद नेता के साथ की जाती है - C / C ++। फिर इस लेख से एक परसिंग आईyleoक्या asm कोड वास्तव में बेहतर है, और विभिन्न भाषाओं पर कार्यान्वयन के बीच अंतर क्या है (मैं पढ़ने की सलाह देता हूं)। इससे पहले भी (लगभग डेढ़ महीने पहले), हास्केल बनाम सी / सी ++ सीरीज़ का पिछला लेख प्रकाशित हुआ था, और मैंने भी इसी तरह का विश्लेषण किया था, लेकिन इसे हाबरा - अलास को प्रकाशित करने के बजाय, मैंने इसे बैक बॉक्स में डाल दिया। इस सप्ताह टिप्पणियों में गर्म चर्चाओं ने मुझे पिछले विषय पर लौटने के लिए प्रेरित किया। आज मुझे अंत में दराज के बाहर उस मार्कडाउन दस्तावेज़ मिला, जो धूल से सना हुआ था,ख़त्म होना, और इसे अपनी समीक्षा के लिए प्रदान करें।

परिचय

, [], :

/++, .. , , " , ". "", . , , , 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.
• प्रोसेसर: इंटेल i5-8250U (हाँ, लैपटॉप)
• OS: उबंटू 19.04 / लिनक्स 5.0.0
• टर्बो बूस्ट में तेजी लाने के लिए पहला रन, फिर एक पंक्ति में न्यूनतम पांच। 1-2% के भीतर विचलन।
• विभिन्न 1s कार्यान्वयन के लॉन्च के बीच, हम शांत हो जाएंगे (हाँ, लैपटॉप)

जोड़ा गया: आलसी के लिए स्क्रिप्ट

आप अपने हार्डवेयर पर एक ही चीज़ चला सकते हैं और जनता को इसका परिणाम बता सकते हैं: गीथब का लिंक ।

जोड़ा गया: -march = देशी के बिना परिणाम

टिप्पणियों में अनुरोधों के अनुसार, मैंने इस ध्वज के प्रभाव की जांच करने का निर्णय लिया।