Saya perlu mencari elemen maks dalam vektor jadi saya menggunakan std::max_element, tetapi saya telah menemukan bahwa itu adalah fungsi yang sangat lambat, jadi saya menulis versi saya sendiri dan berhasil mendapatkan kinerja yang lebih baik x3, berikut adalah kodenya:
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>
double getRealTime()
{
struct timeval tv;
gettimeofday(&tv, 0);
return (double) tv.tv_sec + 1.0e-6 * (double) tv.tv_usec;
}
inline int my_max_element(const std::vector<int> &vec, int size)
{
auto it = vec.begin();
int max = *it++;
for (; it != vec.end(); it++)
{
if (*it > max)
{
max = *it;
}
}
return max;
}
int main()
{
const int size = 1 << 20;
std::vector<int> vec;
for (int i = 0; i < size; i++)
{
if (i == 59)
{
vec.push_back(1000000012);
}
else
{
vec.push_back(i);
}
}
double startTime = getRealTime();
int maxIter = *std::max_element(vec.begin(), vec.end());
double stopTime = getRealTime();
double totalIteratorTime = stopTime - startTime;
startTime = getRealTime();
int maxArray = my_max_element(vec, size);
stopTime = getRealTime();
double totalArrayTime = stopTime - startTime;
std::cout << "MaxIter = " << maxIter << std::endl;
std::cout << "MaxArray = " << maxArray << std::endl;
std::cout << "Total CPU time iterator = " << totalIteratorTime << std::endl;
std::cout << "Total CPU time array = " << totalArrayTime << std::endl;
std::cout << "iter/array ratio: = " << totalIteratorTime / totalArrayTime << std::endl;
return 0;
}
Keluaran:
MaxIter = 1000000012
MaxArray = 1000000012
Total CPU time iterator = 0.000989199
Total CPU time array = 0.000293016
iter/array ratio: = 3.37592
rata-rata std::max_element membutuhkan waktu x3 lebih lama my_max_element.
Jadi mengapa saya dapat membuat fungsi std lebih cepat dengan mudah? Haruskah saya berhenti menggunakan std dan menulis fungsi saya sendiri karena std sangat lambat?
Catatan: pada awalnya saya meskipun itu karena saya menggunakan dan integer i dalam lingkaran bukan iterator, tetapi pelipit itu tidak menjadi masalah sekarang.
Info kompilasi:
g ++ (GCC) 4.8.2
g ++ -O3 -Wall -c -fmessage-length = 0 -std = c + + 0x
Sebelum memberikan suara pada jawaban ini, silakan uji (dan verifikasi) ini di mesin Anda dan komentar / tambahkan hasilnya. Perhatikan bahwa saya menggunakan ukuran vektor 1000 * 1000 * 1000 untuk pengujian saya. Saat ini, jawaban ini memiliki 19 upvotes tetapi hanya satu hasil yang diposting, dan hasil ini tidak menunjukkan efek yang dijelaskan di bawah ini (meskipun diperoleh dengan kode pengujian yang berbeda, lihat komentar).
Sepertinya ada bug / artefak pengoptimal. Bandingkan waktu:
template<typename _ForwardIterator, typename _Compare>
_ForwardIterator
my_max_element_orig(_ForwardIterator __first, _ForwardIterator __last,
_Compare __comp)
{
if (__first == __last) return __first;
_ForwardIterator __result = __first;
while(++__first != __last)
if (__comp(__result, __first))
__result = __first;
return __result;
}
template<typename _ForwardIterator, typename _Compare>
_ForwardIterator
my_max_element_changed(_ForwardIterator __first, _ForwardIterator __last,
_Compare __comp)
{
if (__first == __last) return __first;
_ForwardIterator __result = __first;
++__first;
for(; __first != __last; ++__first)
if (__comp(__result, __first))
__result = __first;
return __result;
}
Yang pertama adalah implementasi asli libstdc ++, yang kedua harus berupa transformasi tanpa perubahan dalam perilaku atau persyaratan. Clang ++ menghasilkan waktu berjalan yang sangat mirip untuk kedua fungsi tersebut, sedangkan g ++ 4.8.2 empat kali lebih cepat dengan versi kedua.
Mengikuti proposal Maxim, mengubah vektor dari int untuk int64_t, versi yang diubah tidak 4, tetapi hanya 1,7 kali lebih cepat dari versi asli (g + + 4.8.2).
Perbedaannya adalah dalam meramalkan prediktif *result, yaitu, menyimpan nilai elemen maks saat ini sehingga tidak perlu dimuat ulang dari memori setiap kali. Ini memberikan pola akses cache yang jauh lebih bersih:
w/o commoning with commoning
* *
** *
** *
** *
* * *
* * *
* * *
Inilah asm untuk perbandingan (rdi/rsi berisi iterasi pertama / terakhir):
Dengan loop while (2.88743 ms; inti):
movq %rdi, %rax
jmp .L49
.L51:
movl (%rdi), %edx
cmpl %edx, (%rax)
cmovl %rdi, %rax
.L49:
addq $4, %rdi
cmpq %rsi, %rdi
jne .L51
Dengan for loop (1235.55 μs):
leaq 4(%rdi), %rdx
movq %rdi, %rax
cmpq %rsi, %rdx
je .L53
movl (%rdi), %ecx
.L54:
movl (%rdx), %r8d
cmpl %r8d, %ecx
cmovl %rdx, %rax
cmovl %r8d, %ecx
addq $4, %rdx
cmpq %rdx, %rsi
jne .L54
.L53:
Jika saya memaksa umum dengan menyimpan secara eksplisit *result menjadi variabel prev di awal dan kapan saja result diperbarui, dan menggunakan prev dari pada *result dalam perbandingan, saya mendapatkan loop yang lebih cepat (377.601 μs):
movl (%rdi), %ecx
movq %rdi, %rax
.L57:
addq $4, %rdi
cmpq %rsi, %rdi
je .L60
.L59:
movl (%rdi), %edx
cmpl %edx, %ecx
jge .L57
movq %rdi, %rax
addq $4, %rdi
movl %edx, %ecx
cmpq %rsi, %rdi
jne .L59
.L60:
Alasannya ini lebih cepat daripada for lingkaran adalah bahwa bergerak bersyarat (cmovl) di atas adalah pesimisme karena dieksekusi sangat jarang (Kata Linus bahwa cmov hanya ide yang baik jika cabang tidak dapat diprediksi). Perhatikan bahwa untuk data yang didistribusikan secara acak, cabang diharapkan akan diambil Hn kali, yang merupakan proporsi yang dapat diabaikan (Hn tumbuh secara logaritmik, jadi Hn/ n dengan cepat mendekati 0). Kode bergerak bersyarat hanya akan lebih baik pada data patologis, mis. [1, 0, 3, 2, 5, 4, ...].
Anda mungkin menjalankan tes Anda dalam mode 64-bit, di mana sizeof(int) == 4, tapi sizeof(std::vector<>::iterator) == 8, sehingga tugas dalam pengulangan ke int(apa my_max_element tidak) lebih cepat daripada std::vector<>::iterator (ini adalah apa std::max_element tidak).
Jika kamu berubah std::vector<int> untuk std::vector<long> hasil berubah menguntungkan std::max_element:
MaxIter = 1000000012
MaxArray = 1000000012
Total CPU time iterator = 0.00429082
Total CPU time array = 0.00572205
iter/array ratio: = 0.749875
Satu catatan penting: ketika benchmarking menonaktifkan skala frekuensi CPU, sehingga CPU tidak berpindah persneling di tengah benchmark.
Tapi saya pikir ada hal lain yang bermain di sini, karena hanya mengubah variabel loop dari int untuk long tidak mengubah hasil ...
Ini masalah sederhana cache. Untuk pertama kalinya, Anda pertama kali memuat memori, dalam hal ini isi vektor, itu selalu jauh lebih lambat daripada jika baru-baru ini diakses. Saya menyalin dan menempelkan kode Anda dengan GCC 4.9.
Ketika fungsi dibalik, rasionya adalah 1. Ketika mereka berada di urutan awal, rasionya adalah 1,6.
Ini masih tampak seperti kesalahan pengoptimalan yang mendasar oleh GCC dalam kasus max_element kepada saya. Namun, waktu fungsi Anda sangat rendah, mereka akan didominasi oleh suara CPU seperti efek cache di atas, daripada perbandingan yang berarti.
Terbalik, Asli