In dem Artikel [Link] wurde angegeben, dass die Leistung von Haskell-Code C ++ - Code überlegen war. Was sofort Interesse weckte, als Beide können vom Compiler von LLVM generiert werden. Dies bedeutet, dass entweder Eskell dem Compiler weitere Hinweise geben kann oder dass etwas mit der C ++ - Implementierung nicht stimmt. Als nächstes werden wir analysieren, wie eine Reihe von Unfällen in den Handlungen des Autors zu falschen Schlussfolgerungen führte, die in der folgenden Tabelle (unter dem Schnitt) beschrieben sind.
Vorwort
Kürzlich ein weiterer Artikel aus0xd34df00dHaskell-Code-Optimierung. In solchen Fällen wird es natürlich mit dem unbestreitbaren Leistungsführer C / C ++ verglichen. Dann kam eine Analyse dieses Artikels ausyleodarüber, welcher asm-Code wirklich besser ist und was der Unterschied zwischen den Implementierungen in verschiedenen Sprachen ist (ich empfehle das Lesen). Noch früher (vor ungefähr anderthalb Monaten) wurde der vorherige Artikel aus der Reihe Haskell vs C / C ++ veröffentlicht, und ich habe eine ähnliche Analyse durchgeführt, aber anstatt ihn leider bei Habr zu veröffentlichen, habe ich ihn in die Backbox gelegt. Die hitzigen Diskussionen in den Kommentaren dieser Woche veranlassten mich, zum vorherigen Thema zurückzukehren. Heute habe ich endlich das Abschriften-Dokument aus der Schublade geholt, den Staub abgestaubt,fertigund geben Sie es für Ihre Überprüfung.
Einführung
, [], :
/++, .. , , " , ". "", . , , , 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. - Prozessor: Intel i5-8250U (ja, Laptop)
- Betriebssystem: Ubuntu 19.04 / Linux 5.0.0
- Der erste Lauf, um den Turbo-Boost zu beschleunigen, dann mindestens fünf in Folge. Abweichungen innerhalb von 1-2%.
- Zwischen den Starts verschiedener Implementierungen von 1s werden wir uns abkühlen (ja, Laptop).
Hinzugefügt: Skripte für die Faulen
Sie können dasselbe auf Ihrer Hardware ausführen und der Öffentlichkeit das Ergebnis mitteilen: einen Link zum Github .
Hinzugefügt: Ergebnisse ohne -march = native
Gemäß den Anfragen in den Kommentaren habe ich beschlossen, den Einfluss dieser Flagge zu überprüfen.