L'article [lien] a déclaré que les performances du code Haskell étaient supérieures au code C ++. Ce qui a immédiatement suscité l'intérêt, les deux peuvent être générés par LLVM par le compilateur, ce qui signifie que Eskell peut donner plus d'indications au compilateur, ou que quelque chose ne va pas avec l'implémentation C ++. Ensuite, nous analyserons comment une série d'accidents dans les actions de l'auteur a conduit à des conclusions incorrectes, qui sont décrites dans le tableau ci-dessous (sous la coupe).
Préface
Récemment, un autre article de0xd34df00dOptimisation du code Haskell. Dans de tels cas, il est naturellement comparé au leader incontestable de la performance - C / C ++. Puis est venue une analyse de cet article deyleoquel code asm est vraiment meilleur et quelle est la différence entre les implémentations dans différents langages (je recommande la lecture). Encore plus tôt (il y a environ un mois et demi), l'article précédent de la série Haskell vs C / C ++ a été publié, et j'ai fait une analyse similaire, mais au lieu de le publier sur Habr - hélas, je l'ai mis dans la boîte arrière. Les discussions animées dans les commentaires cette semaine m'ont incité à revenir au sujet précédent. Aujourd'hui, j'ai finalement sorti ce document de démarque du tiroir, dépoussiéré,finiet fournissez-le pour examen.
introduction
, [], :
/++, .. , , " , ". "", . , , , 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. - Processeur: Intel i5-8250U (oui, ordinateur portable)
- Système d'exploitation: Ubuntu 19.04 / Linux 5.0.0
- La première manche pour accélérer le turbo boost, puis en prendre au minimum cinq d'affilée. Écarts de 1 à 2%.
- Entre les lancements de différentes implémentations de 1, nous allons refroidir (oui, un ordinateur portable)
Ajouté: scripts pour les paresseux
Vous pouvez exécuter la même chose sur votre matériel et informer le public du résultat: un lien vers le github .
Ajouté: Résultats sans -march = native
Selon les demandes dans les commentaires, j'ai décidé de vérifier l'influence de ce drapeau.