Apakah lebih cepat untuk menghitung mundur daripada menghitung?

Guru sains komputer kami pernah mengatakan bahwa untuk beberapa alasan lebih efisien menghitung mundur daripada menghitung mundur. Sebagai contoh jika Anda perlu menggunakan loop UNTUK dan indeks loop tidak digunakan di suatu tempat (seperti mencetak garis N * ke layar) Maksud saya kode seperti ini:

for (i = N; i >= 0; i--)  
  putchar('*');  

lebih baik dari:

for (i = 0; i < N; i++)  
  putchar('*');  

Benarkah itu benar? Dan jika demikian, adakah yang tahu mengapa?

Benarkah itu benar? dan jika ada yang tahu mengapa?

Di zaman kuno, ketika komputer masih pecah dari silika menyatu dengan tangan, ketika mikrokontroler 8-bit berkeliaran di Bumi, dan ketika guru Anda masih muda (atau guru guru Anda masih muda), ada instruksi mesin yang umum disebut decrement dan skip jika nol (DSZ). Programmer hotshot assembly menggunakan instruksi ini untuk mengimplementasikan loop. Kemudian mesin mendapat instruksi yang lebih bagus, tetapi masih ada beberapa prosesor yang lebih murah untuk membandingkan sesuatu dengan nol daripada membandingkannya dengan yang lain. (Memang benar bahkan pada beberapa mesin RISC modern, seperti PPC atau SPARC, yang memesan seluruh register agar selalu nol.)

Jadi, jika Anda memasang loop untuk membandingkan dengan nol, bukan N , apa yang mungkin terjadi?

• Anda mungkin menyimpan register
• Anda mungkin mendapatkan instruksi pembanding dengan pengkodean biner yang lebih kecil
• Jika instruksi sebelumnya terjadi untuk menyetel flag (kemungkinan hanya pada mesin keluarga x86), Anda mungkin bahkan tidak memerlukan instruksi pembanding eksplisit

Apakah perbedaan ini cenderung menghasilkan peningkatan terukur pada program nyata pada prosesor modern yang rusak? Sangat tidak mirip. Bahkan, saya akan terkesan jika Anda bisa menunjukkan peningkatan yang terukur bahkan pada microbenchmark.

Ringkasan: Aku memukul gurumu terbalik! Anda seharusnya tidak belajar fakta pseudo-usang tentang bagaimana mengatur loop. Anda harus belajar bahwa hal terpenting dari loop adalah memastikan bahwa loop itu berakhir , menghasilkan jawaban yang benar , dan mudah dibaca . Saya berharap gurumu akan fokus pada hal-hal penting dan bukan mitologi.

Inilah yang mungkin terjadi pada beberapa perangkat keras tergantung pada apa yang dapat disimpulkan oleh kompiler tentang kisaran angka yang Anda gunakan: dengan putaran yang bertambah Anda harus menguji i<Nsetiap kali putaran loop. Untuk versi penurunan, flag carry (ditetapkan sebagai efek samping dari pengurangan) dapat secara otomatis memberi tahu Anda jika i>=0. Itu menghemat tes per putaran waktu loop.

Pada kenyataannya, pada perangkat keras prosesor pipelined modern, hal ini hampir pasti tidak relevan karena tidak ada pemetaan 1-1 sederhana dari instruksi ke siklus jam. (Meskipun saya bisa membayangkannya muncul jika Anda melakukan hal-hal seperti menghasilkan sinyal video tepat waktu dari mikrokontroler. Tetapi, Anda tetap akan menulis dalam bahasa assembly.)

Dalam set instruksi Intel x86, membangun loop untuk menghitung mundur ke nol biasanya dapat dilakukan dengan instruksi yang lebih sedikit daripada loop yang menghitung hingga kondisi keluar yang tidak nol. Secara khusus, register ECX secara tradisional digunakan sebagai penghitung loop dalam x86 asm, dan set instruksi Intel memiliki instruksi jcxz jump khusus yang menguji register ECX untuk nol dan melompat berdasarkan pada hasil tes.

Namun, perbedaan kinerja akan diabaikan kecuali loop Anda sudah sangat sensitif terhadap jumlah siklus jam. Menghitung mundur ke nol mungkin mencukur 4 atau 5 siklus clock dari setiap iterasi loop dibandingkan dengan menghitung, jadi itu benar-benar lebih baru daripada teknik yang berguna.

Juga, kompiler pengoptimal yang baik hari ini harus dapat mengubah kode sumber loop count up Anda menjadi mundur ke nol kode mesin (tergantung pada bagaimana Anda menggunakan variabel indeks loop) sehingga benar-benar tidak ada alasan untuk menulis loop Anda di cara aneh hanya dengan memeras satu atau dua siklus di sana-sini.

Iya..!!

Menghitung dari N ke 0 sedikit lebih cepat dari Menghitung dari 0 hingga N dalam arti bagaimana perangkat keras akan menangani perbandingan ..

Perhatikan perbandingan di setiap loop

i>=0
i<N

Sebagian besar prosesor memiliki perbandingan dengan nol instruksi..jadi yang pertama akan diterjemahkan ke kode mesin sebagai:

1. Muat i
2. Bandingkan dan lompat jika Kurang dari atau sama dengan nol

Tapi yang kedua perlu memuat N dari Memory setiap kali

1. memuat i
2. memuat N
3. Sub i dan N
4. Bandingkan dan lompat jika Kurang dari atau sama dengan nol

Jadi bukan karena menghitung mundur atau naik .. Tapi karena bagaimana kode Anda akan diterjemahkan ke dalam kode mesin ..

Jadi menghitung dari 10 hingga 100 sama dengan menghitung bentuk 100 hingga 10
Tetapi menghitung dari i = 100 ke 0 lebih cepat daripada dari i = 0 hingga 100 - dalam banyak kasus
Dan menghitung dari i = N ke 0 lebih cepat daripada dari i = 0 hingga N

• Perhatikan bahwa saat ini kompiler dapat melakukan optimasi ini untuk Anda (jika cukup cerdas)
• Perhatikan juga bahwa pipa dapat menyebabkan efek seperti anomali Belady (tidak dapat memastikan apa yang akan lebih baik)
• Akhirnya: harap dicatat bahwa 2 untuk loop yang Anda sajikan tidak setara .. yang pertama mencetak satu lagi * ....

Terkait: Mengapa n ++ mengeksekusi lebih cepat daripada n = n + 1?

Dalam C ke psudo-assembly:

for (i = 0; i < 10; i++) {
    foo(i);
}

berubah menjadi

    clear i
top_of_loop:
    call foo
    increment i
    compare 10, i
    jump_less top_of_loop

sementara:

for (i = 10; i >= 0; i--) {
    foo(i);
}

berubah menjadi

    load i, 10
top_of_loop:
    call foo
    decrement i
    jump_not_neg top_of_loop

Perhatikan kurangnya perbandingan dalam psudo-assembly kedua. Pada banyak arsitektur ada bendera yang diatur oleh operasi aritmatik (menambah, mengurangi, mengalikan, membagi, menambah, mengurangi) yang dapat Anda gunakan untuk melompat. Ini sering memberi Anda apa yang pada dasarnya perbandingan hasil operasi dengan 0 secara gratis. Bahkan pada banyak arsitektur

x = x - 0

secara semantik sama dengan

compare x, 0

Juga, bandingkan dengan 10 pada contoh saya bisa menghasilkan kode yang lebih buruk. 10 mungkin harus tinggal dalam register, jadi jika persediaannya sedikit, biayanya dan dapat menghasilkan kode tambahan untuk memindahkan barang-barang atau memuat ulang 10 setiap kali melalui loop.

Compiler kadang-kadang dapat mengatur ulang kode untuk mengambil keuntungan dari ini, tetapi seringkali sulit karena mereka sering tidak dapat memastikan bahwa membalikkan arah melalui loop secara semantik setara.

Hitung mundur lebih cepat jika seperti ini:

for (i = someObject.getAllObjects.size(); i >= 0; i--) {…}

karena someObject.getAllObjects.size()dijalankan sekali di awal.

Tentu, perilaku serupa dapat dicapai dengan memanggil size()keluar dari lingkaran, seperti yang disebutkan Peter:

size = someObject.getAllObjects.size();
for (i = 0; i < size; i++) {…}

Apakah lebih cepat menghitung mundur daripada naik?

Mungkin. Tetapi jauh lebih dari 99% dari waktu itu tidak masalah, jadi Anda harus menggunakan tes yang paling 'masuk akal' untuk mengakhiri perulangan, dan dengan masuk akal, saya maksudkan bahwa dibutuhkan paling sedikit pemikiran oleh pembaca untuk mencari tahu apa yang dilakukan loop (termasuk apa yang membuatnya berhenti). Buat kode Anda cocok dengan model mental (atau didokumentasikan) dari apa yang dilakukan kode.

Jika pengulangan bekerja dengan cara yang melalui array (atau daftar, atau apa pun), penghitung kenaikan akan sering lebih cocok dengan bagaimana pembaca mungkin memikirkan apa yang dilakukan pengulangan - beri kode pengulangan Anda dengan cara ini.

Tetapi jika Anda bekerja melalui wadah yang memiliki Nitem, dan menghapus item saat Anda pergi, mungkin lebih masuk akal secara kognitif untuk menghitung.

Sedikit lebih detail pada 'mungkin' dalam jawabannya:

Memang benar bahwa pada sebagian besar arsitektur, pengujian untuk perhitungan yang menghasilkan nol (atau berubah dari nol menjadi negatif) tidak memerlukan instruksi pengujian eksplisit - hasilnya dapat diperiksa secara langsung. Jika Anda ingin menguji apakah suatu perhitungan menghasilkan angka lain, aliran instruksi umumnya harus memiliki instruksi eksplisit untuk menguji nilai itu. Namun, terutama dengan CPU modern, tes ini biasanya akan menambah waktu tambahan tingkat kebisingan kurang dari untuk membangun perulangan. Terutama jika loop itu melakukan I / O.

Di sisi lain, jika Anda menghitung mundur dari nol, dan menggunakan penghitung sebagai indeks array, misalnya, Anda mungkin menemukan kode bekerja melawan arsitektur memori sistem - memori yang dibaca sering menyebabkan cache untuk 'melihat ke depan' beberapa lokasi memori melewati yang sekarang dalam mengantisipasi pembacaan berurutan. Jika Anda bekerja mundur melalui memori, sistem caching mungkin tidak mengantisipasi pembacaan lokasi memori pada alamat memori yang lebih rendah. Dalam hal ini, ada kemungkinan bahwa pengulangan 'mundur' dapat merusak kinerja. Namun, saya mungkin masih mengkodekan loop dengan cara ini (selama kinerja tidak menjadi masalah) karena kebenaran adalah yang terpenting, dan membuat kode cocok dengan model adalah cara yang bagus untuk membantu memastikan kebenaran. Kode yang salah sama tidak optimalnya seperti yang Anda dapatkan.

Jadi saya cenderung melupakan nasihat profesor (tentu saja, bukan pada ujiannya - Anda harus tetap pragmatis sejauh ruang kelas berjalan), kecuali dan sampai kinerja kode benar-benar penting.

Pada beberapa CPU lama ada / ada instruksi seperti DJNZ== "decrement and jump if not zero". Ini memungkinkan loop yang efisien di mana Anda memasukkan nilai hitungan awal ke dalam register dan kemudian Anda dapat secara efektif mengelola loop pengurangan dengan satu instruksi. Kita berbicara tentang ISA tahun 1980-an di sini - guru Anda benar-benar tidak dapat dihubungi jika menurutnya "aturan praktis" ini masih berlaku pada CPU modern.

Bob,

Tidak sampai Anda melakukan optimasi mikro, di mana Anda akan memiliki manual untuk CPU Anda. Selanjutnya, jika Anda melakukan hal semacam itu, Anda mungkin tidak perlu mengajukan pertanyaan ini. :-) Tapi, gurumu jelas tidak berlangganan ide itu ....

Ada 4 hal yang perlu dipertimbangkan dalam contoh loop Anda:

for (i=N; 
 i>=0;             //thing 1
 i--)             //thing 2
{
  putchar('*');   //thing 3
}

• Perbandingan

Perbandingan (seperti yang telah ditunjukkan orang lain) relevan dengan arsitektur prosesor tertentu . Ada lebih banyak jenis prosesor daripada yang menjalankan Windows. Secara khusus, mungkin ada instruksi yang menyederhanakan dan mempercepat perbandingan dengan 0.

• Pengaturan

Dalam beberapa kasus, lebih cepat untuk menyesuaikan ke atas atau ke bawah. Biasanya kompiler yang baik akan mencari tahu dan mengulangi loop jika bisa. Tidak semua kompiler bagus.

• Lingkaran Tubuh

Anda mengakses syscall dengan putchar. Itu sangat lambat. Plus, Anda merender ke layar (secara tidak langsung). Itu bahkan lebih lambat. Pikirkan rasio 1000: 1 atau lebih. Dalam situasi ini, badan loop benar-benar dan benar-benar melebihi biaya penyesuaian / perbandingan loop.

• Cache

Cache dan tata letak memori dapat memiliki efek besar pada kinerja. Dalam situasi ini, itu tidak masalah. Namun, jika Anda mengakses array dan membutuhkan kinerja optimal, sebaiknya Anda menyelidiki bagaimana kompiler dan prosesor Anda meletakkan akses memori dan menyesuaikan perangkat lunak Anda untuk memaksimalkannya. Contoh stok adalah yang diberikan sehubungan dengan perkalian matriks.

Yang lebih penting dari apakah Anda menambah atau mengurangi penghitung Anda adalah apakah Anda naik memori atau turun memori. Sebagian besar cache dioptimalkan untuk naik memori, bukan memori turun. Karena waktu akses memori adalah hambatan yang dihadapi sebagian besar program saat ini, ini berarti bahwa mengubah program Anda sehingga Anda meningkatkan memori dapat menghasilkan peningkatan kinerja bahkan jika ini mengharuskan membandingkan penghitung Anda dengan nilai yang tidak nol. Dalam beberapa program saya, saya melihat peningkatan kinerja yang signifikan dengan mengubah kode saya untuk naik memori, bukan turun.

Skeptis? Cukup tulis sebuah program untuk waktu loop naik / turun memori. Inilah hasil yang saya dapat:

Average Up Memory   = 4839 mus
Average Down Memory = 5552 mus

Average Up Memory   = 18638 mus
Average Down Memory = 19053 mus

(di mana "mus" berarti mikrodetik) dari menjalankan program ini:

#include <chrono>
#include <iostream>
#include <random>
#include <vector>

//Sum all numbers going up memory.
template<class Iterator, class T>
inline void sum_abs_up(Iterator first, Iterator one_past_last, T &total) {
  T sum = 0;
  auto it = first;
  do {
    sum += *it;
    it++;
  } while (it != one_past_last);
  total += sum;
}

//Sum all numbers going down memory.
template<class Iterator, class T>
inline void sum_abs_down(Iterator first, Iterator one_past_last, T &total) {
  T sum = 0;
  auto it = one_past_last;
  do {
    it--;
    sum += *it;
  } while (it != first);
  total += sum;
}

//Time how long it takes to make num_repititions identical calls to sum_abs_down().
//We will divide this time by num_repitions to get the average time.
template<class T>
std::chrono::nanoseconds TimeDown(std::vector<T> &vec, const std::vector<T> &vec_original,
                                  std::size_t num_repititions, T &running_sum) {
  std::chrono::nanoseconds total{0};
  for (std::size_t i = 0; i < num_repititions; i++) {
    auto start_time = std::chrono::high_resolution_clock::now();
    sum_abs_down(vec.begin(), vec.end(), running_sum);
    total += std::chrono::high_resolution_clock::now() - start_time;
    vec = vec_original;
  }
  return total;
}

template<class T>
std::chrono::nanoseconds TimeUp(std::vector<T> &vec, const std::vector<T> &vec_original,
                                std::size_t num_repititions, T &running_sum) {
  std::chrono::nanoseconds total{0};
  for (std::size_t i = 0; i < num_repititions; i++) {
    auto start_time = std::chrono::high_resolution_clock::now();
    sum_abs_up(vec.begin(), vec.end(), running_sum);
    total += std::chrono::high_resolution_clock::now() - start_time;
    vec = vec_original;
  }
  return total;
}

template<class Iterator, typename T>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, T a, T b) {
  std::random_device rnd_device;
  std::mt19937 generator(rnd_device());
  std::uniform_int_distribution<T> dist(a, b);
  for (auto it = start; it != one_past_end; it++)
    *it = dist(generator);
  return ;
}

template<class Iterator>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, double a, double b) {
  std::random_device rnd_device;
  std::mt19937_64 generator(rnd_device());
  std::uniform_real_distribution<double> dist(a, b);
  for (auto it = start; it != one_past_end; it++)
    *it = dist(generator);
  return ;
}

template<class ValueType>
void TimeFunctions(std::size_t num_repititions, std::size_t vec_size = (1u << 24)) {
  auto lower = std::numeric_limits<ValueType>::min();
  auto upper = std::numeric_limits<ValueType>::max();
  std::vector<ValueType> vec(vec_size);

  FillWithRandomNumbers(vec.begin(), vec.end(), lower, upper);
  const auto vec_original = vec;
  ValueType sum_up = 0, sum_down = 0;

  auto time_up   = TimeUp(vec, vec_original, num_repititions, sum_up).count();
  auto time_down = TimeDown(vec, vec_original, num_repititions, sum_down).count();
  std::cout << "Average Up Memory   = " << time_up/(num_repititions * 1000) << " mus\n";
  std::cout << "Average Down Memory = " << time_down/(num_repititions * 1000) << " mus"
            << std::endl;
  return ;
}

int main() {
  std::size_t num_repititions = 1 << 10;
  TimeFunctions<int>(num_repititions);
  std::cout << '\n';
  TimeFunctions<double>(num_repititions);
  return 0;
}

Keduanya sum_abs_updan sum_abs_downmelakukan hal yang sama (jumlah vektor angka) dan diatur waktunya dengan cara yang sama dengan satu-satunya perbedaan adalah yang sum_abs_upnaik memori saat sum_abs_downturun memori. Saya bahkan melewati vecreferensi sehingga kedua fungsi mengakses lokasi memori yang sama. Namun demikian, sum_abs_upsecara konsisten lebih cepat daripada sum_abs_down. Coba jalankan sendiri (saya kompilasi dengan g ++ -O3).

Penting untuk dicatat seberapa ketat pengulangan yang saya lakukan. Jika tubuh loop besar, maka kemungkinan tidak akan masalah apakah iteratornya naik atau turun memori karena waktu yang dibutuhkan untuk mengeksekusi tubuh loop kemungkinan akan mendominasi sepenuhnya. Juga, penting untuk menyebutkan bahwa dengan beberapa loop yang jarang, memori turun terkadang lebih cepat daripada naik itu. Tetapi bahkan dengan loop seperti itu tidak pernah terjadi bahwa naik memori selalu lebih lambat daripada turun (tidak seperti loop bertubuh kecil yang naik memori, yang sebaliknya sering benar; pada kenyataannya, untuk segelintir kecil loop aku ' Sudah waktunya, peningkatan kinerja dengan naik memori adalah 40 +%).

Intinya adalah, sebagai aturan praktis, jika Anda memiliki pilihan, jika tubuh loop kecil, dan jika ada sedikit perbedaan antara loop Anda naik memori, bukan turun, maka Anda harus naik memori.

FYI vec_originalada untuk eksperimen, untuk membuatnya mudah untuk berubah sum_abs_updan sum_abs_downdengan cara yang membuat mereka berubah vecsementara tidak membiarkan perubahan ini mempengaruhi waktu di masa depan. Saya sangat merekomendasikan bermain-main dengan sum_abs_updan sum_abs_downdan waktu hasil.

terlepas dari arahnya selalu gunakan formulir awalan (++ i bukannya i ++)!

for (i=N; i>=0; --i)  

atau

for (i=0; i<N; ++i) 

Penjelasan: http://www.eskimo.com/~scs/cclass/notes/sx7b.html

Selanjutnya Anda bisa menulis

for (i=N; i; --i)  

Tetapi saya berharap kompiler modern dapat melakukan persis optimasi ini.

Ini adalah pertanyaan yang menarik, tetapi sebagai hal praktis saya tidak berpikir itu penting dan tidak membuat satu loop lebih baik dari yang lain.

Menurut halaman wikipedia ini: Lompatan kedua , "... hari matahari menjadi 1,7 ms lebih lama setiap abad terutama karena gesekan pasang surut." Tetapi jika Anda menghitung hari sampai hari ulang tahun Anda, apakah Anda benar-benar peduli dengan perbedaan kecil waktu ini?

Lebih penting bahwa kode sumbernya mudah dibaca dan dipahami. Kedua loop tersebut adalah contoh bagus mengapa keterbacaan penting - mereka tidak mengulangi jumlah yang sama.

Saya berani bertaruh bahwa kebanyakan programmer membaca (i = 0; i <N; i ++) dan segera mengerti bahwa ini loop N kali. Lingkaran (i = 1; i <= N; i ++), bagi saya, sedikit kurang jelas, dan dengan (i = N; i> 0; i--) Saya harus memikirkannya sejenak . Paling baik jika maksud kode masuk langsung ke otak tanpa perlu berpikir.

Anehnya, ada perbedaan. Paling tidak, di PHP. Pertimbangkan tolok ukur berikut:

<?php

print "<br>".PHP_VERSION;
$iter = 100000000;
$i=$t1=$t2=0;

$t1 = microtime(true);
for($i=0;$i<$iter;$i++){}
$t2 = microtime(true);
print '<br>$i++ : '.($t2-$t1);

$t1 = microtime(true);
for($i=$iter;$i>0;$i--){}
$t2 = microtime(true);
print '<br>$i-- : '.($t2-$t1);

$t1 = microtime(true);
for($i=0;$i<$iter;++$i){}
$t2 = microtime(true);
print '<br>++$i : '.($t2-$t1);

$t1 = microtime(true);
for($i=$iter;$i>0;--$i){}
$t2 = microtime(true);
print '<br>--$i : '.($t2-$t1);

Hasilnya menarik:

PHP 5.2.13
$i++ : 8.8842368125916
$i-- : 8.1797409057617
++$i : 8.0271911621094
--$i : 7.1027431488037


PHP 5.3.1
$i++ : 8.9625310897827
$i-- : 8.5790238380432
++$i : 5.9647901058197
--$i : 5.4021768569946

Jika seseorang tahu mengapa, alangkah baiknya untuk mengetahui :)

SUNTING : Hasilnya sama bahkan jika Anda mulai menghitung bukan dari 0, tetapi nilai arbitrer lainnya. Jadi mungkin tidak hanya perbandingan dengan nol yang membuat perbedaan?

Itu bisa lebih cepat.

Pada prosesor NIOS II saya sedang bekerja dengan, tradisional untuk loop

for(i=0;i<100;i++)

menghasilkan perakitan:

ldw r2,-3340(fp) %load i to r2
addi r2,r2,1     %increase i by 1
stw r2,-3340(fp) %save value of i
ldw r2,-3340(fp) %load value again (???)
cmplti r2,r2,100 %compare if less than equal 100
bne r2,zero,0xa018 %jump

Jika kita menghitung mundur

for(i=100;i--;)

kami mendapatkan perakitan yang membutuhkan 2 instruksi lebih sedikit.

ldw r2,-3340(fp)
addi r3,r2,-1
stw r3,-3340(fp)
bne r2,zero,0xa01c

Jika kita memiliki loop bersarang, di mana loop dalam dieksekusi banyak, kita dapat memiliki perbedaan yang terukur:

int i,j,a=0;
for(i=100;i--;){
    for(j=10000;j--;){
        a = j+1;
    }
}

Jika loop dalam ditulis seperti di atas, waktu eksekusi adalah: 0,12199999999999999734 detik. Jika loop dalam ditulis dengan cara tradisional, waktu eksekusi adalah: 0,1719999999999999998623 detik. Jadi loop menghitung mundur sekitar 30% lebih cepat.

Tetapi: tes ini dilakukan dengan semua optimasi GCC dimatikan. Jika kita menyalakannya, kompiler sebenarnya lebih pintar daripada optimisasi tangan ini dan bahkan menyimpan nilai dalam register selama seluruh loop dan kita akan mendapatkan perakitan seperti

addi r2,r2,-1
bne r2,zero,0xa01c

Dalam contoh khusus ini, kompiler bahkan memperhatikan, variabel a akan selalu menjadi 1 setelah eksekusi loop dan melewatkan semua loop bersama-sama.

Namun saya mengalami bahwa kadang-kadang jika badan loop cukup kompleks, kompiler tidak dapat melakukan optimasi ini, jadi cara teraman untuk selalu mendapatkan eksekusi loop cepat adalah menulis:

register int i;
for(i=10000;i--;)
{ ... }

Tentu saja ini hanya berfungsi, jika tidak masalah bahwa loop dieksekusi secara terbalik dan seperti yang dikatakan Betamoo, hanya jika Anda menghitung mundur ke nol.

Apa yang dikatakan guru Anda adalah pernyataan miring tanpa banyak klarifikasi. BUKAN bahwa pengurangan lebih cepat daripada menambah tetapi Anda dapat membuat loop jauh lebih cepat dengan penurunan daripada dengan kenaikan.

Tanpa panjang lebar tentang hal itu, tanpa perlu menggunakan penghitung lingkaran dll - yang penting di bawah ini hanya kecepatan dan jumlah loop (bukan nol).

Inilah cara kebanyakan orang menerapkan loop dengan 10 iterasi:

int i;
for (i = 0; i < 10; i++)
{
    //something here
}

Untuk 99% kasus, semua itu mungkin diperlukan tetapi bersama dengan PHP, PYTHON, JavaScript ada seluruh dunia perangkat lunak penting (biasanya tertanam, OS, game, dll.) Di mana kutu CPU sangat penting, jadi lihat sebentar pada kode perakitan:

int i;
for (i = 0; i < 10; i++)
{
    //something here
}

setelah kompilasi (tanpa optimasi) versi kompilasi mungkin terlihat seperti ini (VS2015):

-------- C7 45 B0 00 00 00 00  mov         dword ptr [i],0  
-------- EB 09                 jmp         labelB 
labelA   8B 45 B0              mov         eax,dword ptr [i]  
-------- 83 C0 01              add         eax,1  
-------- 89 45 B0              mov         dword ptr [i],eax  
labelB   83 7D B0 0A           cmp         dword ptr [i],0Ah  
-------- 7D 02                 jge         out1 
-------- EB EF                 jmp         labelA  
out1:

Seluruh loop adalah 8 instruksi (26 byte). Di dalamnya - sebenarnya ada 6 instruksi (17 byte) dengan 2 cabang. Ya ya saya tahu ini bisa dilakukan dengan lebih baik (ini hanya sebuah contoh).

Sekarang pertimbangkan ini sering membangun yang sering Anda temukan ditulis oleh pengembang tertanam:

i = 10;
do
{
    //something here
} while (--i);

Itu juga berulang 10 kali (ya saya tahu saya nilainya berbeda dibandingkan dengan yang ditunjukkan untuk loop tetapi kami peduli dengan iterasi yang dihitung di sini). Ini dapat dikompilasi menjadi ini:

00074EBC C7 45 B0 01 00 00 00 mov         dword ptr [i],1  
00074EC3 8B 45 B0             mov         eax,dword ptr [i]  
00074EC6 83 E8 01             sub         eax,1  
00074EC9 89 45 B0             mov         dword ptr [i],eax  
00074ECC 75 F5                jne         main+0C3h (074EC3h)  

5 instruksi (18 byte) dan hanya satu cabang. Sebenarnya ada 4 instruksi di loop (11 byte).

Yang terbaik adalah bahwa beberapa CPU (termasuk x86 / x64 termasuk) memiliki instruksi yang dapat mengurangi register, kemudian membandingkan hasil dengan nol dan melakukan cabang jika hasilnya berbeda dari nol. Hampir semua PC CPU menerapkan instruksi ini. Menggunakannya, loop sebenarnya hanya satu (ya satu) instruksi 2 byte:

00144ECE B9 0A 00 00 00       mov         ecx,0Ah  
label:
                          // something here
00144ED3 E2 FE                loop        label (0144ED3h)  // decrement ecx and jump to label if not zero

Apakah saya harus menjelaskan mana yang lebih cepat?

Sekarang bahkan jika CPU tertentu tidak mengimplementasikan instruksi di atas semua yang diperlukan untuk meniru itu adalah penurunan diikuti oleh lompatan bersyarat jika hasil dari instruksi sebelumnya adalah nol.

Jadi, terlepas dari beberapa kasus yang Anda tunjukkan sebagai komentar mengapa saya salah, dll, saya menekankan. - YA BERMANFAAT UNTUK MELIHAT KE BAWAH KE BAWAH jika Anda tahu bagaimana, mengapa dan kapan.

PS. Ya saya tahu bahwa kompiler bijak (dengan tingkat optimasi yang sesuai) akan menulis ulang untuk loop (dengan counter loop menaik) menjadi do..sementara setara untuk iterasi loop konstan ... (atau membuka gulungannya) ...

Tidak, itu tidak sepenuhnya benar. Satu situasi di mana itu bisa lebih cepat adalah ketika Anda seharusnya memanggil fungsi untuk memeriksa batas-batas selama setiap iterasi loop.

for(int i=myCollection.size(); i >= 0; i--)
{
   ...
}

Tetapi jika kurang jelas melakukannya seperti itu, itu tidak bermanfaat. Dalam bahasa modern, Anda harus menggunakan loop foreach jika memungkinkan. Anda secara spesifik menyebutkan kasus di mana Anda harus menggunakan loop foreach - ketika Anda tidak membutuhkan indeks.

Intinya adalah bahwa ketika menghitung mundur Anda tidak perlu memeriksa i >= 0 secara terpisah untuk melakukan decrementing i. Mengamati:

for (i = 5; i--;) {
  alert(i);  // alert boxes showing 4, 3, 2, 1, 0
}

Baik perbandingan dan pengurangan idapat dilakukan dalam satu ekspresi.

Lihat jawaban lain untuk alasan ini bermuara pada lebih sedikit instruksi x86.

Seperti apakah itu membuat perbedaan yang berarti dalam aplikasi Anda, baik saya kira itu tergantung pada berapa banyak loop yang Anda miliki dan seberapa dalam mereka bersarang. Tetapi bagi saya, sama mudahnya melakukannya dengan cara ini, jadi saya tetap melakukannya.

Sekarang, saya pikir Anda punya cukup banyak kuliah perakitan :) Saya ingin memberi Anda alasan lain untuk pendekatan top-> down.

Alasan untuk pergi dari atas sangat sederhana. Di tubuh loop, Anda mungkin secara tidak sengaja mengubah batas, yang mungkin berakhir dengan perilaku yang salah atau bahkan loop yang tidak berakhir.

Lihatlah sebagian kecil kode Java ini (bahasa tidak masalah saya kira karena alasan ini):

    System.out.println("top->down");
    int n = 999;
    for (int i = n; i >= 0; i--) {
        n++;
        System.out.println("i = " + i + "\t n = " + n);
    }
    System.out.println("bottom->up");
    n = 1;
    for (int i = 0; i < n; i++) {
        n++;
        System.out.println("i = " + i + "\t n = " + n);
    }

Jadi poin saya adalah Anda harus mempertimbangkan memilih pergi dari atas ke bawah atau memiliki konstanta sebagai batas.

Pada tingkat assembler, sebuah loop yang menghitung mundur ke nol pada umumnya sedikit lebih cepat daripada yang menghitung hingga nilai yang diberikan. Jika hasil perhitungan sama dengan nol, sebagian besar prosesor akan menetapkan tanda nol. Jika mengurangi satu membuat perhitungan membungkus melewati nol lalu ini biasanya akan mengubah bendera carry (pada beberapa prosesor itu akan mengaturnya pada orang lain itu akan menghapusnya), sehingga perbandingan dengan nol pada dasarnya datang secara gratis.

Ini bahkan lebih benar ketika jumlah iterasi bukan konstanta tetapi variabel.

Dalam kasus sepele kompiler mungkin dapat mengoptimalkan arah hitungan loop secara otomatis tetapi dalam kasus yang lebih kompleks mungkin bahwa programmer tahu bahwa arah loop tidak relevan dengan perilaku keseluruhan tetapi kompiler tidak dapat membuktikannya.