能要求
編寫一個控制臺應用程序,使用for循環輸出10“我不敢了!”
實現步驟
for i in range(1, 11):
print("%d:我不敢了!" % i)
運行結果
代碼分析
for i in range(1, 11):
print("%d:我不敢了!" % i:循環變量i在1~11之間,包括1但不包括11,i從1開始,執行循環體中的print("%d:我不敢了!" % i語句后,i加1,循環結構繼續執行,直到i等于11時,跳出循環體,執行循環體后面的語句,即結束循環。
功能要求
編寫一個控制臺應用程序,使用for循環計算出5的階乘,即求1到5的成績,求1 * 2 * 3 * 4 * 5的值。
實現步驟
sum = 1
for i in range(1, 6):
sum *= i
print("1 * 2 * 3 * 4 * 5 = %d" % sum)
運行結果
代碼分析
for i in range(1, 6):
sum *= i:循環變量i在1~6之間,包括1但不包括6,i從1開始,執行循環體中的sum *= i語句后,sum的值變為sum = sum * i,i加1,循環結構繼續執行,直到i等于6時,跳出循環體,結束循環。執行循環體后面的print("1 * 2 * 3 * 4 * 5 = %d" % sum)語句,即將1~5的乘積結果打印輸出,結束程序。
知識說明
循環語句:可以在滿足循環條件的情況下,反復執行某一段代碼。這段被重復執行的代碼被稱為循環體。當反復執行這個循環體時,需要在合適的時候把循環條件改為假,從而結束循環;否則循環將一直執行下去,形成死循環。
for循環格式
for 變量 in 范圍:
循環執行語句
當循環“變量”的值在一定的“范圍”內,執行“循環語句”,當循環“變量”的值不在“范圍”內時跳出循環體,循環程序結構結束。
range函數
range意為在……范圍內,其語法如下:
range([start, ]end[, step])
其中,start是循環開始的地方,可以省略不寫,若省略,默認為0;end是循環結束的地方,但不包含end。step這個參數也可以不寫,若省略,默認步長為1。
歸是一種編程技術,其中一個函數直接或間接調用自身。在C#中,遞歸通常用于解決可以分解為更小相似問題的問題,例如計算階乘、斐波那契數列等。
下面是一個使用C#編寫的遞歸函數的簡單例子,用于計算一個整數的階乘。階乘函數是遞歸的一個經典例子,因為計算n的階乘(記為n!)涉及到計算(n-1)的階乘,以此類推,直到達到最基本的情況(例如0的階乘是1)。
csharp
復制
using System;
class RecursionExample
{
static void Main()
{
Console.WriteLine("請輸入一個整數以計算其階乘:");
int number = int.Parse(Console.ReadLine());
// 檢查輸入是否為非負整數
if (number < 0)
{
Console.WriteLine("負數沒有階乘。");
}
else
{
// 調用遞歸函數
long factorial = Factorial(number);
Console.WriteLine($"階乘 {number}! = {factorial}");
}
}
// 遞歸函數計算階乘
static long Factorial(int n)
{
if (n == 0) // 遞歸的基本情況
{
return 1;
}
else
{
// 遞歸調用:n的階乘是n乘以(n-1)的階乘
return n * Factorial(n - 1);
}
}
}
在這個例子中,Factorial 函數將一直遞歸調用自身,直到它達到基本情況(n == 0),此時它返回1。每次遞歸調用返回時,它會乘以當前的n值,從而計算出階乘。
請注意,遞歸函數需要有一個終止條件,否則它會無限遞歸下去,這可能會導致堆棧溢出錯誤。此外,遞歸函數可能不是解決某些問題的最有效方法,因為它們可能會占用大量的內存和處理器時間。在某些情況下,使用循環和迭代可能是更好的選擇。
文講解一個非常重要的性能調優方法,會涉及到CPU內部非常重要的一些基礎知識,為講解清楚,篇幅較長,請務必看完,你一定會有收獲!
一切都要從一個面試題說起!
有朋友私信給我,聊了下自己的一段面試經歷,有這么一段代碼:
面試官:這段求階乘的代碼怎么樣?
答:挺簡潔的,簡單易懂。不過如果參數n值比較大的話,會導致fact溢出,結果是錯的。
面試官:嗯,是的。不過,咱們先不考慮溢出的問題,你覺得這段代碼的性能怎么樣?
答:時間復雜度是O(n),而且代碼比較精煉,性能應該還挺不錯的吧?(心虛ing...)
面試官:你能想辦法把它優化一下,讓性能更好嗎?
思考ing...
答:在多CPU系統上,如果n的值比較大的話,可以考慮用多線程來實現。
面試官:嗯,這是一個思路。如果是單CPU呢?
再次思考ing...
答:用GCC編譯的話,可以加上優化選項-O3,應該能提高性能。
面試官:嗯,還有嗎?
答:沒了。
面試官:好了,感謝來參加面試,回去等通知吧!
思考一下,如果是你的話,會怎么回答呢?
下面,來深入講解一下,隱藏在這道題背后的深層次知識!
本文較長,且涉及到CPU內部很底層的知識,請耐心看完,一定會有收獲!
測試程序test.c非常簡單,計算1000000000的階乘:
注:calc()加__attribute__((noinline))是禁止GCC把calc內聯在main()中,只是為了方便對比性能,不必糾結。
編譯一下,然后用time命令測量下運行耗時:
然后,把程序稍微改一下,命名為test_2.c:
編譯,并用time命令測量下運行耗時:
運行耗時從原來的3.29秒降到了1秒,性能提升了200%!
看到這里,有人會說,不就是循環展開嘛,很簡單的,沒什么好研究的,而且加了優化選項之后,編譯器會自動進行循環展開的,沒必要手動去展開,也就沒有研究的價值了!
真的是這樣嗎?先嘗試回答下面幾個問題:
第一個問題后面會詳細講解,我們先用實例回答下第2個和第3個問題。
先看第2個問題。
我們把test_2.c稍微改一下,命令為test_3.c:
仍然是循環展開,只不過把循環展開的方式稍微改了一下。 再編譯一下,用time命令測量下運行耗時:
和test.c相比運行耗時只減少了0.2秒!為什么同樣是循環展開,test_2.c只需要1.6秒,而test_3.c卻要3秒,為什么性能差異這么大呢?別著急,后面細講。
再看第三個問題,加了優化選項,編譯器一定會幫我們自動進行循環展開優化嗎?一試便知!
重新編譯下test.c, test_2.c, 和test_3.c,只不過,這次我們加上-O3優化選項,然后分別用time命令再測量下運行時間。
先是test.c:
加了-O3優化后,程序耗時從原來的3.29秒降到了1.07秒,性能提升確實非常明顯! 是否好奇,-O3選項對test.c做了什么樣的優化,能夠把程序耗時降到三分之一?這個后面再講。
現在,我們先試下test_2.c:
同樣,加了-O3后,程序耗時從原來的1秒降到了0.368秒! 此外,在同樣加了-O3的情況下,使用了手段循環展開的test_2.c,程序耗時仍然是test.c的三分之一! 可見,編譯器確實優化了一些東西,但是,無論是否加-O3優化選項,進行手動循環展開的test.c仍然是性能最好的!
最后,再試下test_3.c:
看到了吧?同樣加了-O3優化選項的前提下,性能仍然與test_2.c相差甚遠!
小結一下我們現在得到的幾組測試結果:
在解釋這些性能差異的原因之前,必須要先補充一些CPU相關的基礎知識,否則無法真正理解這背后的原因!所以,請務必認真看完!
這會涉及到CPU內部實現細節的知識,相對比較底層,而且對絕大多數程序員是透明的,因此很多人甚至都沒聽說過這些概念。不過,也不用擔心,跟之前一樣,我會盡量用通俗易懂的語言來解釋這些概念。
所謂流水線,是把指令的執行過程分成多個階段,每個階段使用CPU內部不通的硬件資源來完成。以經典的5級流水線為例,一條指令的執行被分為5個階段:
在時鐘信號的驅動下,CPU依次來執行這些步驟,這就構成了指令流水線(pipeline)。如下圖所示:
在CPU內部,執行每個階段使用不同的硬件資源,從而可以讓多條指令的執行時間相互重疊。當第一條指令完成取指,進入譯碼階段時,第二條指令就可以進入取指階段了。以此類推,在一個5級流水線中,理想情況下,可以有5條不同的指令的不同階段在同時執行,因此每個時鐘周期都會有一條指令完成執行,從而大大提高了CPU執行指令的吞吐率,從而提高CPU整體性能。這就叫做ILP - 指令級并行(Instruction Level Parallelism)。如下圖所示:
通過把指令執行分為多個階段,CPU每個時鐘周期只處理一個階段的工作,這樣大大簡化了CPU內部負責每個階段的功能單元,每個時鐘周期要做的事情少了,提高時鐘頻率也變得簡單了。
前面說過,有了流水線技術,理想情況下,每個時鐘周期,CPU可以完成一條指令的執行。那有沒有什么方法,可以讓CPU在每個時鐘周期,完成多條指令的執行呢,這豈不是會大大提高CPU整體性能嗎?
當然有!這就是Superscalar技術!(除此之外還有VLIW,不是本文重點,不再展開討論。)
Superscalar,通過在CPU內部實現多條指令流水線,可以真正實現多條命令并行執行,也被稱為多發射數據通路技術。以雙發射流水線為例,每個時鐘周期,CPU可以同時讀取兩條指令,然后同時對這兩條指令進行譯碼,同時執行,然后同時寫回。如下圖所示:
目前為止,這一切看起來都很完美,對吧?然而,現實往往沒有理想那么豐滿!接著往下看吧。
大家可能注意到了,前面多次強調過,“在理想狀態下”,為什么呢?
現實中程序的指令序列之間往往存在各種各樣的依賴和相關性,而CPU為了解決這種指令間的依賴和相關性,有時候不得不“停頓”下來,直到這些依賴得到解決,這就導致CPU指令流水線無法總是保持“全速運行”。
這種現象被稱之為Pipeline Hazard,很多資料翻譯為“流水線冒險”,我覺得“流水線沖突”更為貼切易懂。
歸結起來,有三種情況:
下面分別舉例解釋這三種類型的沖突。
所謂數據沖突,簡單講,就是兩條在流水線中并行執行的指令,第二條指令需要用到第一條指令的執行結果,因此第二條指令的執行不得不暫停,一直到可以獲取到第一條指令的執行結果為止。
比如,用偽代碼舉例:
x = 1;
y = x;
要對y進行賦值,必須要先得到x的值,因此這兩條語句無法完全并行執行。
這只是其中的一種典型情況,其他情況不再贅述。
所謂控制沖突,簡單講,就是在CPU在執行分支跳轉時,無法預知下一條要執行的指令。
比如:
if(a > 100) {
x = 1;
} else {
y = 2;
}
在CPU計算出a > 100這個條件是否成立之前,無法確定接下來是應該執行x = 1 還是執行 y = 2。
為了解決這個問題,CPU可以簡單的讓流水線停頓一直到確定下一條要執行的指令,也可以采取如分支預測(branch prediction)和推測執行(speculation execution)等手段,但是,預測失敗的話,流水線往往會受到比較嚴重的性能懲罰。之后會有專門的文章分析這個問題,感興趣的話,可以右上角關注一下!
結構沖突,簡單來說,就是多條指令同時競爭同一個硬件資源,由于硬件資源短缺,無法同時滿足所有指令的執行請求。如兩條并行執行的命令需要同時訪問內存,而內存地址譯碼單元可能只有一個,這就產生了結構沖突。
有了上面這些基礎知識做鋪墊,接下來就可以開始真正分析這個問題了。
對于計算階乘,test.c可能是最簡單直觀、可讀性最強的算法。不過可惜的是,它也是性能最差的。
我們再看一下test.c的源碼:
說它性能最差,主要有三點原因:
注意,這里說的無用指令,是指對計算階乘本身不產生直接影響的指令,但是它們對整個算法的正確性仍然是必不可少的!
為例方便理解,我們來分別看下test.c不解優化選項和加了-O3編譯之后的匯編代碼。
先是不加優化選項的:
綠色方框標注出來的8 ~ 14行是for循環,也就是主循環體。其中,藍色方框標注出來的8 ~ 11行是真正計算階乘的代碼,12 ~ 14行是循環控制代碼,對計算階乘來說,則是無用代碼。
不難看出:
那加了-O3優化選項之后,編譯器能不能幫我們解決這些問題呢?
現在我們看下加了-O3之后的匯編代碼:
首先,不得不感嘆,現在的編譯器的優化真的是太強大了!直接把整個for循環優化成了4條指令!
不難看出,對于test.c而言,加了-O3之后,GCC做的最大的優化是把所有變量存放在寄存器中,消除了所有的內存訪問操作!
可以回過頭去看下優化之前的匯編代碼,整個函數一共有10個內存訪問操作,其中6個是在循環體內,而加了-O3之后,整個函數沒有任何內存訪問操作!難怪-O3編譯后性能提升那么多!由此可見,內存訪問相對寄存器訪問的開銷實在是太大了!當然,即便不使用-O3,也有優化內存操作的辦法,這個后面再講。
但是,也不難看出,對于其他兩個問題,GCC并沒有幫我們解決:現在無用指令占比是 2/4 = 50%! 整個階乘計算過程,仍然需要執行1000000000次條件跳轉指令,仍然無法充分發揮流水線和superscalar的指令并行執行能力!
知道了test.c性能差的原因之后,現在我們來看看,通過手動循環展開,test_2.c又幫我們解決什么問題呢?
再看下test_2.c的源碼:
通過對循環進行4次展開,之前每次循環執行1次乘法,現在每次循環執行4次,這就帶來了三點很重要的變化:
這也就是為什么在使用同樣的編譯選項時,test_2.c比test.c的性能提升了200%!不過,熱點路徑上內存訪問操作太多的問題仍然存在。其實,這個其實很好解決,我會在下文給出解決方法。我們先把注意里放在這里所說的三點變化上。
對于第1點和第2點,有了前面介紹的指令流水線的背景知識,即便從C語言的角度也很好理解,不需要過多解釋。
至于第3點,為了便于理解,我們和test_3.c對比來看。
再看下test_3.c的代碼:
test_3.c雖然也把循環進行了4次展開,但是展開的方式和test_2.c是不一樣的。
test_2.c是這樣展開的:
fact0 *= i;
fact1 *= i + 1;
fact2 *= i + 2;
fact3 *= i + 3;
而test_3.c則是這樣做的:
fact *= i;
fact *= i + 1;
fact *= i + 2;
fact *= i + 3;
很明顯,后面一條指令執行前,必須要先知道前面一條語句計算的結果。還記得前面講過的造成流水線沖突的三個原因嗎?這就是典型的數據依賴,會造成流水線沖突!
可見,雖然test_3.c也通過循環展開,減少了無用指令,也減少了熱點路徑上分支跳轉引起的流水線控制沖突,但它同時引入了數據依賴,進而導致流水線沖突,仍然無法發揮流水線和superscalar的指令級并行執行的能力!
這就是為什么,用同樣的選項編譯時,test_3.c雖然比未經過循環展開的test.c性能稍微提升了一點點,但相比同樣循環展開且沒有引入數據相關性的test_2.c來說,性能仍然是非常差的!
講到這里,本想演示下用perf測量出來的性能指標的,但由于篇幅過長,就不再展開討論了,以后會專門更新文章介紹perf相關工具的使用,感興趣的童鞋,歡迎右上角關注!
最后,來看一下前面遺留的那個問題:不加優化選項的情況下,怎么解決熱點路徑內存訪問過多的問題。
其實很簡單,只需要把test_2.c中定義局部變量的時候加上register關鍵字就可以了:
C語言中,register關鍵字的作用是建議編譯器,盡可能地把變量存放在寄存器中,以加快其訪問速度。
我們現在看下,加了register關鍵字后,test_2.c的性能如何呢?
為方便對比,我們再看下添加register之前,test_2.c的耗時:
然后是加了register關鍵字之后的耗時:
看到差異了吧,相差3倍!加了register后,幾乎達到了和加-O3優化選項一樣的性能!
當然,register的使用還有很多限制,而且它只是給編譯器的一種建議,不是強制要求,編譯器只能盡量滿足,當變量太多,寄存器不夠用的時候,還是不得不把變量放到棧中,這和-O3的行為是一樣的。
register不是本文重點,限于篇幅,不在贅述,感興趣的童鞋可以留言討論或私信,如果感興趣童鞋比較多的話,我會專門更新一篇文章來講解register關鍵字,歡迎關注。
循環展開是一種非常重要的優化方法,也是編譯器后端中常用的一種優化方式,它可以通過減少熱點路徑上的“無用指令”以及分支指令的個數,來更好地發揮CPU指令流水線的指令并行執行能力,從而提高程序整體性能。
很多時候,我們可以借助編譯器來幫我們實現這種優化,但編譯器也有失效的時候,比如文中這個例子。這時,我們就不得不手動來進行循環展開來優化程序性能。循環展開時,必須盡量減少語句間的相互依賴。
此外,循環展開的次數并沒有一個固定的公式,需要根據具體代碼和CPU來決定,通常需要多次嘗試來找到一個最優值。
不過,手動循環展開往往是以犧牲代碼可讀性為代價的,因此使用時也做好取舍。此外,循環展開還會在一定程度上增加程序代碼段的大小,還可能會影響到程序局部性,對cache產生影響,因此使用時候,要小心評估。
如果你對本文感興趣,那這一篇文章你肯定也會喜歡,介紹另外一種非常實用卻很少人知道的性能調優手段,強烈推薦:
<<改一行代碼,數組遍歷耗時從10.3秒降到0.5秒!>>
最近會更新一系列涉及CPU底層相關的文章,如Cache、指令流水線、分支預測、指令亂序、內存屏障等,如果對這些方面感興趣,歡迎右上角關注!
原創不易,別忘了留言點贊!右上角關注!有任何疑問或建議,歡迎留言、私信討論!
*請認真填寫需求信息,我們會在24小時內與您取得聯系。