Я профилировал небольшой фрагмент кода, который является частью большей симуляции, и, к моему удивлению, функция равенства STL (std :: equal) намного медленнее, чем простой цикл for, сравнивая два элемента массива элемент за элементом. Я написал небольшой тестовый пример, который, по моему мнению, представляет собой справедливое сравнение между ними, и разница с использованием g ++ 6.1.1 из архивов Debian не является незначительной. Я сравниваю два четырехэлементных массива целых чисел со знаком. Я протестировал std :: equal, operator == и маленький цикл for. Я не использовал std :: chrono для точного определения времени, но разницу можно увидеть со временем ./a.out.
Мой вопрос, учитывая приведенный ниже пример кода, почему оператор == и перегруженная функция std :: equal (которая, как я полагаю, вызывает оператор ==) требуют около 40 секунд, а рукописный цикл занимает всего 8 секунд? Я использую новейший ноутбук на базе Intel. Цикл for работает быстрее на всех уровнях оптимизации: -O1, -O2, -O3 и -Ofast. Я скомпилировал код с
g++ -std=c++14 -Ofast -march=native -mtune=native
Цикл проходит огромное количество раз, просто чтобы сделать разницу понятной невооруженным глазом. Операторы по модулю представляют собой дешевую операцию над одним из элементов массива и служат для предотвращения оптимизации компилятора вне цикла.
#include<iostream>
#include<algorithm>
#include<array>
using namespace std;
using T = array<int32_t, 4>;
bool
are_equal_manual(const T& L, const T& R)
noexcept {
bool test{ true };
for(uint32_t i{0}; i < 4; ++i) { test = test && (L[i] == R[i]); }
return test;
}
bool
are_equal_alg(const T& L, const T& R)
noexcept {
bool test{ equal(cbegin(L),cend(L),cbegin(R)) };
return test;
}
int main(int argc, char** argv) {
T left{ {0,1,2,3} };
T right{ {0,1,2,3} };
cout << boolalpha << are_equal_manual(left,right) << endl;
cout << boolalpha << are_equal_alg(left,right) << endl;
cout << boolalpha << (left == right) << endl;
bool t{};
const size_t N{ 5000000000 };
for(size_t i{}; i < N; ++i) {
//t = left == right; // SLOW
//t = are_equal_manual(left,right); // FAST
t = are_equal_alg(left,right); // SLOW
left[0] = i % 10;
right[2] = i % 8;
}
cout<< boolalpha << t << endl;
return(EXIT_SUCCESS);
}
Вот сгенерированная сборка for
зациклиться main()
когда are_equal_manual(left,right)
функция используется:
.L21:
xor esi, esi
test eax, eax
jne .L20
cmp edx, 2
sete sil
.L20:
mov rax, rcx
movzx esi, sil
mul r8
shr rdx, 3
lea rax, [rdx+rdx*4]
mov edx, ecx
add rax, rax
sub edx, eax
mov eax, edx
mov edx, ecx
add rcx, 1
and edx, 7
cmp rcx, rdi
И вот что генерируется, когда are_equal_alg(left,right)
функция используется:
.L20:
lea rsi, [rsp+16]
mov edx, 16
mov rdi, rsp
call memcmp
mov ecx, eax
mov rax, rbx
mov rdi, rbx
mul r12
shr rdx, 3
lea rax, [rdx+rdx*4]
add rax, rax
sub rdi, rax
mov eax, ebx
add rbx, 1
and eax, 7
cmp rbx, rbp
mov DWORD PTR [rsp], edi
mov DWORD PTR [rsp+24], eax
jne .L20
Я не совсем уверен, что происходит в сгенерированном коде для первого случая, но он явно не вызывает memcmp()
, Кажется, он не сравнивает содержимое массивов вообще. Хотя цикл все еще повторяется 5000000000 раз, он оптимизирован, чтобы ничего не делать. Тем не менее, цикл, который использует are_equal_alg(left,right)
все еще выполняет сравнение. По сути, компилятор все еще может оптимизировать ручное сравнение намного лучше, чем std::equal
шаблон.
Других решений пока нет …