Mengapa lambdas dioptimalkan lebih baik oleh kompiler daripada fungsi biasa?

171

Dalam bukunya The C++ Standard Library (Second Edition)Nicolai Josuttis menyatakan bahwa lambdas dapat lebih dioptimalkan oleh kompiler daripada fungsi biasa.

Selain itu, kompiler C ++ mengoptimalkan lambdas lebih baik daripada mereka melakukan fungsi biasa. (Halaman 213)

Mengapa demikian?

Saya pikir ketika datang ke inlining seharusnya tidak ada perbedaan lagi. Satu-satunya alasan yang dapat saya pikirkan adalah bahwa penyusun mungkin memiliki konteks lokal yang lebih baik dengan lambdas dan seperti itu dapat membuat lebih banyak asumsi dan melakukan lebih banyak optimisasi.

Stephan Dollberg
sumber
Terkait .
iammilind
Pada dasarnya, pernyataan itu berlaku untuk semua objek fungsi , bukan hanya lambda.
Newacct
4
Itu akan salah karena pointer fungsi juga objek fungsi.
Johannes Schaub - litb
2
@ litb: Saya pikir saya tidak setuju dengan itu. ^ W ^ W ^ W ^ W ^ W ^ W (setelah melihat ke dalam standar) Saya tidak menyadari bahwa C ++ isme, meskipun saya pikir dalam bahasa umum (dan menurut wikipedia), orang berarti instance-of-some-callable-class ketika mereka mengatakan objek function.
Sebastian Mach
1
Beberapa kompiler dapat mengoptimalkan lambdas dengan lebih baik daripada fungsi biasa, tetapi tidak semua :-(
Cody Grey

Jawaban:

175

Alasannya adalah bahwa lambdas adalah objek fungsi sehingga meneruskannya ke templat fungsi akan instantiate fungsi baru khusus untuk objek itu. Dengan demikian kompiler dapat secara sepele menyejajarkan panggilan lambda.

Untuk fungsi, di sisi lain, peringatan lama berlaku: penunjuk fungsi dilewatkan ke templat fungsi, dan kompiler secara tradisional memiliki banyak masalah dalam mengurutkan panggilan melalui pointer fungsi. Mereka dapat secara teoritis inline, tetapi hanya jika fungsi sekitarnya inline juga.

Sebagai contoh, pertimbangkan templat fungsi berikut:

template <typename Iter, typename F>
void map(Iter begin, Iter end, F f) {
    for (; begin != end; ++begin)
        *begin = f(*begin);
}

Menyebutnya dengan lambda seperti ini:

int a[] = { 1, 2, 3, 4 };
map(begin(a), end(a), [](int n) { return n * 2; });

Hasil dalam Instansiasi ini (dibuat oleh kompiler):

template <>
void map<int*, _some_lambda_type>(int* begin, int* end, _some_lambda_type f) {
    for (; begin != end; ++begin)
        *begin = f.operator()(*begin);
}

... kompiler tahu _some_lambda_type::operator ()dan bisa sebaris panggilan ke itu sepele. (Dan memohon fungsi mapdengan setiap lambda lain akan membuat Instansiasi baru mapkarena masing-masing lambda memiliki tipe yang berbeda.)

Tetapi ketika dipanggil dengan function pointer, instantiation terlihat sebagai berikut:

template <>
void map<int*, int (*)(int)>(int* begin, int* end, int (*f)(int)) {
    for (; begin != end; ++begin)
        *begin = f(*begin);
}

... dan di sini fmenunjuk ke alamat berbeda untuk setiap panggilan mapdan dengan demikian kompiler tidak dapat inline panggilan ke fkecuali panggilan sekitarnya mapjuga telah diuraikan sehingga kompiler dapat menyelesaikan fke satu fungsi tertentu.

Konrad Rudolph
sumber
4
Mungkin perlu disebutkan bahwa instantiating Templat fungsi yang sama dengan ekspresi lambda yang berbeda akan membuat fungsi yang sama sekali baru dengan jenis yang unik, yang mungkin menjadi kelemahan.
dinginkan
2
@greggo Benar-benar. Masalahnya adalah ketika menangani fungsi yang tidak dapat digarisbawahi (karena terlalu besar). Di sini panggilan ke panggilan balik masih bisa digarisbawahi dalam kasus lambda, tetapi tidak dalam kasus penunjuk fungsi. std::sortadalah contoh klasik dari ini menggunakan lambdas bukannya pointer fungsi di sini membawa hingga tujuh kali lipat (mungkin lebih, tapi saya tidak punya data tentang itu!) peningkatan kinerja.
Konrad Rudolph
1
@greggo Kau membingungkan dua fungsi di sini: satu kita melewati lambda untuk (misalnya std::sort, atau mapdalam contoh saya) dan lambda itu sendiri. Lambda biasanya kecil. Fungsi lainnya - belum tentu. Kami prihatin dengan sebaris panggilan ke lambda di dalam fungsi lainnya.
Konrad Rudolph
2
@ Greggo saya tahu. Namun, inilah kalimat terakhir jawaban saya.
Konrad Rudolph
1
Yang membuat saya penasaran (baru saja menemukannya) adalah bahwa diberikan fungsi boolean sederhana predyang definisinya terlihat, dan menggunakan gcc v5.3, std::find_if(b, e, pred)tidak sebaris pred, tetapi std::find_if(b, e, [](int x){return pred(x);})tidak. Dentang berhasil inline keduanya, tetapi tidak menghasilkan kode secepat g ++ dengan lambda.
rici
26

Karena ketika Anda melewatkan "fungsi" ke suatu algoritma, Anda sebenarnya menyerahkan pointer ke fungsi sehingga harus melakukan panggilan tidak langsung melalui pointer ke fungsi. Saat Anda menggunakan lambda, Anda mengirimkan objek ke instance templat yang khusus dibuat untuk jenis itu dan panggilan ke fungsi lambda adalah panggilan langsung, bukan panggilan melalui penunjuk fungsi sehingga kemungkinan besar bisa digarisbawahi.

jcoder
sumber
5
"panggilan ke fungsi lambda adalah panggilan langsung" - memang. Dan hal yang sama berlaku untuk semua objek fungsi, bukan hanya lambda. Ini hanya fungsi pointer yang tidak dapat digariskan dengan mudah, jika sama sekali.
Pete Becker