先提出這樣一個(gè)問(wèn)題，是我昨天去一家公司面試時(shí)遇到的問(wèn)題，
模塊一：
1 for（int i= 0；i<N; i++）
2 {
3 A;
4 B;
5 C;
6 }
7
模塊二：
1 for（int i= 0；i<N; i++）
2 {
3 A;
4 }
5 for（int i= 0；i<N; i++）
6 {
7 B;
8 }
9
10 for（int i= 0；i<N; i++）
11 {
12 C;
13 }
舉出3個(gè)例子說(shuō)明模塊一比模塊二執(zhí)行效率高，同樣舉出3個(gè)例子證明模塊二比模塊一執(zhí)行效率高。
頭一次遇到這種問(wèn)題，很棘手，我當(dāng)時(shí)的思路是從cpu執(zhí)行效率、內(nèi)存使用效率這兩個(gè)方面來(lái)考慮，列舉了一些可能的情況，應(yīng)付了過(guò)去。
回來(lái)仔細(xì)想了一下，查了一些相關(guān)的帖子好像都有提過(guò)，但都不是很全面，先把問(wèn)題拋在這個(gè)地方等搞清楚了在寫(xiě)。
我以前遇到的問(wèn)題大概都是這種類型的：
1 for(
int i = 0;i<100;i++)
2 {
3 for(
int j = 0;j<10000;j++)
4 {
5 //balabala
6 }
7 }
8 和
9 for(
int i = 0;i<10000;i++)
10 {
11 for(
int j = 0;j<100;j++)
12 {
13 //balabala
14 }
15 }
這兩個(gè)程序那個(gè)執(zhí)行效率高，如果是以前我會(huì)毫不猶豫的說(shuō)是第一個(gè)效率高，這是由于cpu切換的次數(shù)比較多導(dǎo)致性能下降，知道這句話不理解什么原理。我比較贊同下面的說(shuō)法，
1. 最長(zhǎng)循環(huán)放到內(nèi)部可以提高I cache的效率,降低因?yàn)檠h(huán)跳轉(zhuǎn)造成cache的miss以及流水線flush造成的延時(shí)
2. 多次相同循環(huán)后也能提高跳轉(zhuǎn)預(yù)測(cè)的成功率，提高流水線效率
3. 編譯器會(huì)自動(dòng)展開(kāi)循環(huán)提高效率, 這個(gè)不一定是必然有效的
但不是絕對(duì)正確的，比如: 1 int x[1000][100];
2 for(i=0;i<1000;i++)
3 for(j=0;j<100;j++)
4 {
5 //access x[i][j]
6 }
7
8 int x[1000][100];
9 for(j=0;j<100;j++)
10 for(i=0;i=1000;i++)
11 {
12 //access x[i][j]
13 }
14
這時(shí)候第一個(gè)的效率就比第二個(gè)的高，原因嘛和硬件也有一些關(guān)系，CPU對(duì)于內(nèi)存的訪問(wèn)都是通過(guò)數(shù)據(jù)緩存(cache)來(lái)進(jìn)行的。
比如一個(gè)通用CPU,一級(jí)緩存(L1-Cache)的大小為16K,而其組織結(jié)構(gòu)為每32個(gè)字節(jié)一組(cache line size=32byte),
也就是每次從二級(jí)緩存或內(nèi)存取數(shù)據(jù)到一級(jí)緩存，都是一次性取32個(gè)字節(jié)。
對(duì)于上面的第一段代碼，每次取數(shù)據(jù)到一級(jí)緩存，都有連續(xù)8次內(nèi)存訪問(wèn)可以共享一條緩存。
而對(duì)于第二段代碼，每次取數(shù)據(jù)到一級(jí)緩存后，訪問(wèn)一次后，基本上就沒(méi)有機(jī)會(huì)被再次使用了；
上面這兩段代碼的區(qū)別在于第一段代碼，每次內(nèi)存訪問(wèn)后，地址值需要加常數(shù)4，而第二段代碼，每次訪問(wèn)后，地址值加400。
如果沒(méi)有對(duì)于緩存訪問(wèn)的區(qū)別，那么這時(shí)我們的確可以將長(zhǎng)的循環(huán)放在里層，短的放在外層。但是而其主要原因不是一般人所想象的指令數(shù)目的區(qū)別的問(wèn)題，
而主要由于分支預(yù)測(cè)錯(cuò)誤會(huì)引起的流水線中斷從而導(dǎo)致性能的降低。
最后一個(gè)問(wèn)題，有人說(shuō)while比f(wàn)or循環(huán)效率高,不知道這個(gè)假設(shè)是否正確，先立在這搞清楚再補(bǔ)充。