您好,登錄后才能下訂單哦!
本篇內容主要講解“C語言中提高代碼執行效率的小技巧有哪些”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實用性強。下面就讓小編來帶大家學習“C語言中提高代碼執行效率的小技巧有哪些”吧!
ARM64 有34個寄存器,包括 31 個通用寄存器( x0-x30)、SP、PC、CPSR。
x0 - x30 是31個通用整型寄存器。每個寄存器可以存取一個 64 位大小的數。 當使用 r0 - r30 訪問時,它就是一個 64 位的數。當使用 w0 - w30 訪問時,訪問的是這些寄存器的低 32 位。
寄存器 | 位數 | 描述 |
---|---|---|
x0-x30 | 64bit | 通用寄存器,如果有需要可以當做32bit使用:WO-W30 |
FP(x29) | 64bit | 保存棧幀地址(棧底指針) |
LR(x30) | 64bit | 通常稱X30為程序鏈接寄存器,保存子程序結束后需要執行的下一條指令 |
SP | 64bit | 保存棧指針,使用 SP/WSP來進行對SP寄存器的訪問 |
PC | 64bit | 程序計數器,俗稱PC指針,總是指向即將要執行的下一條指令,在arm64中,軟件是不能改寫PC寄存器的 |
CPSR | 64bit | 狀態寄存器 |
Xcode 在真機中運行項目,添加斷點 LLDB 中查看各寄存器狀態register read
。
CPU 由寄存器、運算器、控制器三部分組成,其中寄存器的主要作用是用于存儲信息。可以理解為是內存的一種,但是比內存高效的多。ARM64 中 X0 - X7 寄存器主要用于子程序調用時的參數傳遞,如果方法傳遞的參數過多,寄存器不夠使用,此時會將多余的參數直接存放于函數調用棧中。而棧主要存在于內存中,相比寄存器而言速度會慢很多,所以 iOS 實際開發中應注意參數傳遞個數,參數傳遞過多,一定程度會降低代碼執行速度。不同平臺情況不一樣,64 位 AT&T 匯編中 %rdi、%rsi、%rdx、%rcx、%r8、%r9、%r10等寄存器用于存放函數參數,還有一些平臺可能直接使用棧保存函數參數,此種情況理論上參數個多對代碼執行效率沒有太多影響。
int sum(int a,int b,int c, int d,int e,int f,int g,int h,int i,int j,int k){ return a + b + c + d + e + f + g + h; } int main(int argc, const char * argv[]) { @autoreleasepool { int num = sum(1,2,3,4,5,6,7,8,9,10,11); NSLog(@"%d",num); } return 0; }
上述代碼對應的 64 位AT&T 匯編代碼如下。仔細觀察下面匯編代碼,從第 13 行開始,涉及 rsp 指針的加減操作,說明之后的參數存在于棧區(對棧進行讀寫的內存地址編號是由 rsp 寄存器進行管理的。push 指令和 pop 指令運行后,esp 寄存器的值會自動進行更新,push 指令 rsp 減少,pop 命令 rsp 增加)。 也即前 7 個參數存在于寄存器中(%rdi、%rsi、%rdx、%rcx、%r8、%r9、%r10),后 4 個參數保存在棧中。
0x100000eb2 <+34>: movl $0x1, %edi 0x100000eb7 <+39>: movl $0x2, %esi 0x100000ebc <+44>: movl $0x3, %edx 0x100000ec1 <+49>: movl $0x4, %ecx 0x100000ec6 <+54>: movl $0x5, %r8d 0x100000ecc <+60>: movl $0x6, %r9d 0x100000ed2 <+66>: movl $0x7, %r10d 0x100000ed8 <+72>: movl $0x8, %r11d 0x100000ede <+78>: movl $0x9, %ebx 0x100000ee3 <+83>: movl $0xa, %r14d 0x100000ee9 <+89>: movl $0xb, %r15d 0x100000eef <+95>: movl $0x7, (%rsp) 0x100000ef6 <+102>: movl $0x8, 0x8(%rsp)//第13行 0x100000efe <+110>: movl $0x9, 0x10(%rsp) 0x100000f06 <+118>: movl $0xa, 0x18(%rsp) 0x100000f0e <+126>: movl $0xb, 0x20(%rsp) 0x100000f16 <+134>: movq %rax, -0x40(%rbp) 0x100000f1a <+138>: movl %r15d, -0x44(%rbp) 0x100000f1e <+142>: movl %r14d, -0x48(%rbp) 0x100000f22 <+146>: movl %ebx, -0x4c(%rbp) 0x100000f25 <+149>: movl %r11d, -0x50(%rbp) 0x100000f29 <+153>: movl %r10d, -0x54(%rbp) 0x100000f2d <+157>: callq 0x100000e30 ; sum at main.m:11
int a = 1; if (a > 1) { NSLog(@"a > 1"); }else if(a > 2){ NSLog(@"a > 2"); }else{ NSLog(@"a <= 1"); }
上述代碼對應的匯編代碼如下。第 3 行表示比較 1 和 a 的值,第 5 行表示如果 a <= 1,則跳轉到指令0x100000f16
處,也即第 11 行,其中 jle
中的 l
和 e
的含義分別是 lower
和 equal
; 否則輸出 a > 1,對應第 6 行。后面的判斷依次類推,依次對if
、else if
分支做判斷,找到對應的分支后,直接跳過所有分支。
1 、0x100000ee6 <+22>: callq 0x100000f6a ; symbol stub for: objc_autoreleasePoolPush 2、 0x100000eeb <+27>: movl $0x1, -0x14(%rbp) 3、0x100000ef2 <+34>: cmpl $0x1, -0x14(%rbp) 4、0x100000ef6 <+38>: movq %rax, -0x20(%rbp) 5、0x100000efa <+42>: jle 0x100000f16 ; <+70> at main.m:16 6、0x100000f00 <+48>: leaq 0x121(%rip), %rax ; @"a > 1" 7、0x100000f07 <+55>: movq %rax, %rdi 8、0x100000f0a <+58>: movb $0x0, %al 9、0x100000f0c <+60>: callq 0x100000f5e ; symbol stub for: NSLog 10、0x100000f11 <+65>: jmp 0x100000f4c ; <+124> at main.m:21 11、0x100000f16 <+70>: cmpl $0x2, -0x14(%rbp) 12、0x100000f1a <+74>: jle 0x100000f36 ; <+102> at main.m 13、0x100000f20 <+80>: leaq 0x121(%rip), %rax ; @"a > 2" 14、0x100000f27 <+87>: movq %rax, %rdi 15、0x100000f2a <+90>: movb $0x0, %al 16、0x100000f2c <+92>: callq 0x100000f5e ; symbol stub for: NSLog 17、0x100000f31 <+97>: jmp 0x100000f47 ; <+119> at main.m 18、0x100000f36 <+102>: leaq 0x12b(%rip), %rax ; @"a <= 1" 19、0x100000f3d <+109>: movq %rax, %rdi 20、0x100000f40 <+112>: movb $0x0, %al 21、0x100000f42 <+114>: callq 0x100000f5e ; symbol stub for: NSLog 22、0x100000f47 <+119>: jmp 0x100000f4c ; <+124> at main.m:21 23、 0x100000f4c <+124>: movq -0x20(%rbp), %rdi 24、0x100000f50 <+128>: callq 0x100000f64 ; symbol stub for: objc_autoreleasePoolPop
順便補充一點,當編譯器的Optional Level
設置為Fastest,Smallest[-OS]
是,會發現匯編代碼少了前面兩個分支的判斷直接來到最后的else
分支,這是因為編譯器對代碼做了優化,所以一般打 release 包,往往選擇這個選項。
int a = 5; switch (a) { case 1: NSLog(@"1"); break; case 2: NSLog(@"2"); break; case 3: NSLog(@"3"); break; case 4: NSLog(@"4"); break; case 5: NSLog(@"5"); break; default: NSLog(@"default"); break; }
上述代碼對應的匯編代碼如下。第 1 行表明如果不滿足各種 case 條件,直接來到 default 分支。第 6 行中的 rdx
寄存器是重點,里面保存著下一條指令的地址,LLDB 中輸入p/x $rdx
,輸出結果為(unsigned long) $0 = 0x0000000100000f09
,也即直接到case 為 5 的分支,其中的 x 表示打印 16 進制,$
是打印寄存器值的標識符號。第四行相當于rdx = rax + rcx * 4
,也即利用基址加上 間隔 * 4 找到下一條指令的位置,總的來說內部實現是空間換時間的做法,所以理論上 switch case 的效率要優于 if else。但是有一種特殊情況,當各個 case 值相差較大時,不可能提前創建好一大片連續空間,否則會造成空間的嚴重浪費,此種情況反匯編出的代碼基本和 if else 的邏輯類似,此時兩者的效率大致是等價的。
1、0x100000e97 <+55>: ja 0x100000f1f ; <+191> at main.m 2、0x100000e9d <+61>: leaq 0xa0(%rip), %rax ; main + 228 3、0x100000ea4 <+68>: movq -0x28(%rbp), %rcx 4、0x100000ea8 <+72>: movslq (%rax,%rcx,4), %rdx 5、0x100000eac <+76>: addq %rax, %rdx 6、0x100000eaf <+79>: jmpq *%rdx 7、0x100000eb1 <+81>: leaq 0x170(%rip), %rax ; @"'1'" 8、0x100000eb8 <+88>: movq %rax, %rdi 9、0x100000ebb <+91>: movb $0x0, %al 10、0x100000ebd <+93>: callq 0x100000f58 ; symbol stub for: NSLog 11、0x100000ec2 <+98>: jmp 0x100000f30 ; <+208> at main.m:44 12、0x100000ec7 <+103>: leaq 0x17a(%rip), %rax ; @"'2'" 13、0x100000ece <+110>: movq %rax, %rdi 14、0x100000ed1 <+113>: movb $0x0, %al 15、0x100000ed3 <+115>: callq 0x100000f58 ; symbol stub for: NSLog 16、0x100000ed8 <+120>: jmp 0x100000f30 ; <+208> at main.m:44 17、0x100000edd <+125>: leaq 0x184(%rip), %rax ; @"'3'" 18、0x100000ee4 <+132>: movq %rax, %rdi 19、0x100000ee7 <+135>: movb $0x0, %al 20、0x100000ee9 <+137>: callq 0x100000f58 ; symbol stub for: NSLog 21、0x100000eee <+142>: jmp 0x100000f30 ; <+208> at main.m:44 22、0x100000ef3 <+147>: leaq 0x18e(%rip), %rax ; @"'4'" 23、0x100000efa <+154>: movq %rax, %rdi 24、0x100000efd <+157>: movb $0x0, %al 25、0x100000eff <+159>: callq 0x100000f58 ; symbol stub for: NSLog 26、0x100000f04 <+164>: jmp 0x100000f30 ; <+208> at main.m:44 27、0x100000f09 <+169>: leaq 0x198(%rip), %rax ; @"'5'" 28、 0x100000f10 <+176>: movq %rax, %rdi 29、0x100000f13 <+179>: movb $0x0, %al 30、0x100000f15 <+181>: callq 0x100000f58 ; symbol stub for: NSLog 31、 0x100000f1a <+186>: jmp 0x100000f30 ; <+208> at main.m:44 32、0x100000f1f <+191>: leaq 0x1a2(%rip), %rax ; @"default" 33、0x100000f26 <+198>: movq %rax, %rdi 34、0x100000f29 <+201>: movb $0x0, %al 35、0x100000f2b <+203>: callq 0x100000f58 ; symbol stub for: NSLog
PS:不是很熟悉匯編,只是簡單做一些了解,寫的很淺顯。
由于匯編更接近機器語言,能夠直接對硬件進行操作,生成的程序與其他的語言相比具有更高的運行速度,占用更小的內存,因此在一些對時效性要求很高的程序,大型程序的核心模塊以及工業控制方面大量應用。很多 C 語言三方庫為了提升代碼執行效率,有時會在 C 代碼中插入匯編語言,比如 OC 的 runtime 源碼中,其中就有部分代碼是匯編代碼。這里就舉個簡單的例子,以 AT&T 匯編實現int add(int a, int b)
函數。簡單說明下 AT&T 匯編中,%rax作為函數返回值使用,%rdi、%rsi、%rdx、%rcx、%r8、%r9、%r10等寄存器用于存放函數參數。
//add.h 文件 #ifndef add_h #define add_h int add(int a, int b); #endif /* add_h */
//add.s 文件 //1、.global _add 表示公開方法,否則是私有方法 //2、匯編代碼對應的函數名要加 _ //3、di 和 si 一般用于存放參數,ax用于存放返回值 .global _add _add: //rdi寄存器存放的參數賦值給rax寄存器 movq %rdi,%rax; //rsi寄存器存放的參數加上rax寄存器值,然后賦值給rax addq %rsi,%rax //函數調用結束 retq
另外,很多高級語言底層都是 C 或 C++ 編寫,一些對性能要求比較高的地方,必要時候可以混入 C 或 C++ 代碼。比如移動端高德地圖上很多線路等底層繪制都是通過 OpenGL 完成。如果想在高德地圖上繪制上自己的相關需求模型,可以借助 C++ 編寫 OpenGL 相關代碼。該種方式要比直接在地圖上直接自定義控件等方式效率要高上很多。
__builtin_expect
是對 if 語句的預言,該指令可以告訴編譯器最有可能執行的代碼,從而編譯器進行優化,通俗來講就是告訴編譯器執行 if 和 else 哪個是大概率事件。__builtin_expect(EXP, N)
表示 EXP == N
是大概率事件。
CFAbsoluteTime startTime = CFAbsoluteTimeGetCurrent(); int a = 3; for (int i = 0; i < 100000; i++) { if (a == 1) { [self doSomething]; }else if(a == 2){ [self doSomething]; }else if (a == 3){ [self doSomething]; }else{ [self doSomething]; } } CFAbsoluteTime endTime = CFAbsoluteTimeGetCurrent(); NSLog(@"%f",endTime - startTime);
CFAbsoluteTime startTime = CFAbsoluteTimeGetCurrent(); int a = 3; for (int i = 0; i < 100000; i++) { if (__builtin_expect(a,3)) { [self doSomething]; }else if(a == 2){ [self doSomething]; }else if (a == 3){ [self doSomething]; }else{ [self doSomething]; } } CFAbsoluteTime endTime = CFAbsoluteTimeGetCurrent(); NSLog(@"%f",endTime - startTime);
用上述代碼做了三次實驗,三次結果時間如下。顯然使用__builtin_expect
,代碼效率提升了不少。這里要注意,對于一些非常簡單的分支判斷,該優化可能僅在 debug 模式下有效,因為對于一些簡單的分支判斷, release 模式下編譯器會進行代碼優化。
第一次:0.001160 0.000917 第二次:0.001302 0.000598 第三次:0.001436 0.001010
實際開發中應該注意if 和 else if 或 else 分支執行的概率,對于執行概率相對比較大的分支應該放相對靠前的位置。赫夫曼壓縮技術其實主要是基于分支概率進行的,具體可以參照此篇文章 淺談赫夫曼樹及其應用(文件壓縮) 。
順便補充一下,赫夫曼壓縮技術實際上是貪心算法思路。貪心算法一般只著眼于眼前,并不會考慮后續的太多事,解決的問題比較有限,壓縮技術問題和實際生活中的找零錢問題,比較適合用此思路解決。假設我們有 1 、2 、5 、10 、20 、50、100 元這些面額的紙幣,它們的張數分別是 c1、c2、c5、、c10、c20、c50、c100。我們現在要用這些錢來支付 K 元,最少要用多少張紙幣呢?在生活中,我們肯定是先用面值最大的來支付,如果不夠,就繼續用更小一點面值的,以此類推,最后剩下的用 1 元來補齊。這其實就算是貪心算法思路。
實際上,用貪心算法解決問題的思路,并不總能給出最優解。在一個有權圖中,我們從頂點 S 開始,找一條到頂點 T 的最短路徑(路徑中邊的權值和最小)。貪心算法的解決思路是,每次都選擇一條跟當前頂點相連的權最小的邊,直到找到頂點 T。按照這種思路,我們求出的最短路徑是 S->A->E->T,路徑長度 1+4+4=9 。然而,路徑 S->B->D->T 才是最短路徑,這條路徑的長度2+2+2=6。產生錯誤的原因在于,前面的選擇,會影響后面的選擇,貪心算法僅僅看中眼前,并沒有考慮以后。
人有人的思維,計算機有計算機的思維,人的正向思維被稱為遞推,計算機的逆向思維被稱為遞歸。遞推是人本能的正向思維,如學習過程就是從易到難,有小到大,由局部到整體,數學歸納法就是遞推的典型應用。遞歸的本質是自頂向下不斷地重復。如求解 10! ,按照正向思維就是 1 x 2 x 3 x 4...... x 10。而計算機計算階乘是反著來的,會把 10! 變為 10 x 9!,9!變為 9 x 8!.......如此向下擴展一直到1! = 1。接著就是推回所有結果,知道了 1!之后,其他 2!、3! 、4! ....就都知道了。遞歸的過程是從上向下展開,再從下到上回溯,和棧的結構非常類似,即先進后出,后進先出。從上往下展開的順序是10,9.....1,從下往上回溯的順序是1.....10 。當棧里的數字清空時,遞歸算法也就結束了。計算機之所以采用這種計算方式,是因為遞歸每一步用的算法都相同,計算機僅需要自頂向下不斷地重復。如從尾到頭打印鏈表,有兩種方案,一種是借助棧,一種是遞歸。其實遞歸方案本質也是借用棧。注意在遞歸前和遞歸后打印數據的區別,遞歸前執行的代碼相當于入棧操作,遞歸后執行的代碼相當于出棧操作。
//棧方案 - (void)printListReversinglyOne:(ListNode *)list{ NSMutableArray *arr = [NSMutableArray array]; ListNode *listNode = list; while (listNode != nil) { //入棧 [arr addObject:listNode.value]; listNode = listNode.next; } for (NSInteger i = arr.count - 1; i >= 0 ; i--) { NSLog(@"棧方法:%@",arr[i]); } }
//注意在遞歸前和遞歸后打印數據的區別,遞歸前執行的代碼相當于入棧操作,遞歸后執行的代碼相當于出棧操作。 //遞歸方案 - (void)printListReversinglyTwo:(ListNode *)list{ //1、遞歸必須有終止條件 if (list == nil) { return; } //2、這里是正序輸出。相當于入棧做的操作。 //NSLog(@"遞歸方法:%@",list.value); //3、這里相當于入棧,有遞歸的時候就沒有while或者for循環。 [self printListReversinglyTwo:list.next]; //4、這里是逆序輸出。相當于出棧操作,因為這里已經出了遞歸函數內部。 NSLog(@"遞歸方法:%@",list.value); }
遞歸優點:
遞歸最大的優點是代碼簡潔,對于計算機而言只是重復,思路簡潔。但對于人類而言,雖易于理解但沒有遞推思路計算簡單。
遞歸缺點:
1、棧深度問題通常會出現在遞歸中。因為程序在遞歸時,函數調用本身也是一種消耗,函數調用需要在內存棧中分配空間保存參數、返回地址和臨時變量。一般來說棧是向下生長的,所以遞歸調用的深度過多,就會造成棧空間存儲不足。出現棧溢出現象,引發不可預知的錯誤或崩潰。
2、可能存在重復,如下面的斐波那契數列遞歸。對于遞歸方式: f(10) = f(9) + f(8); f(9) = f(8) + f(7); f(8) = f(7) + f(6).....會發現整個遞歸環節除了 f(10) 和 f(0) 是計算一遍,其他都需要計算兩次,有不少的重復計算。所以如果用 for 循環的解決的話,效率會高于遞歸。為了避免該問題,可以緩存相應的計算結果,減少重復計算。
- (int)recursionFibonacci:(int)n{ if (n == 0) { return 0; } if (n == 1) { return 1; } //這里相當于函數入棧 return [self recursionFibonacci:n-1] + [self recursionFibonacci:n-2]; }
空間換時間這里簡單列出四個例子:C++中的內聯函數、大數據排序問題、典型的歸并排序算法以及一道比較常見的算法面試
參照文章
小知識點 包體積優化中的內聯函數
參照文章
小知識點
如何給百萬數據排序
歸并排序最終的結果合并是很典型的空間換時間思路。歸并排序的核心思想把數組從中間分成前后兩部分,然后對前后兩部分分別排序,再將排好序的兩部分合并在一起,這樣整個數組就都有序了。其中的合并過程就主要利用過了空間換時間的思路,新創建一個數組,將原本產生的另個數組中的內從按照順序從小到大或從大到小依次放入到新創建的數組中。
已知一個整形數組(arr)以及一個整數(sum),判斷數組中是否存在兩個數字之和等于這個整數(sum)?
最直接的方法可能是兩層 for 循環遍歷數組,第一層循環是每次取一個值 a,第二層循是判斷這個數組中是否存在一個值等于 sum - a,這樣做的時間復雜度是 O(n^2),但是借助集合就能將時間復雜度降為 O(n)。實現思路是: 遍歷數組的時候,用集合保存已經遍歷過的元素。在下一次遍歷的過程中,如果集合中存在一個值等于 sum 減去當前遍歷的值,則說明數組中存在一個數等于sum 減去當前遍歷的數值。
func isExist(arr:[Int],sum:Int) -> Bool { var set = Set<Int>() for num in arr { if set.contains(sum - num){ return true } set.insert(num) } return false }
如果要求具體的下標,可以借助字典來實現。
func getIndex(arr:[Int],sum:Int)->[Int]{ var dict = [Int:Int]() for (i,num) in arr.enumerated(){ if let idx = dict[sum-num]{ return [idx,i] }else{ dict[num] = I } } fatalError("沒有滿足條件的下標") }
Swift中,值類型都是存在棧中的,引用類型都是存在堆中的。蘋果官網上明確指出建議開發者多使用值類型。主要有以下原因:
1、存放在棧中的數據結構較為簡單,只有一些值相關的東西。
2、存放在堆中的數據較為復雜,會包含 type、retainCount 等。
1、存放在棧中的數據從棧區底部推入 (push),從棧區頂部彈出 (pop),類似一個數據結構中的棧。由于我們只能夠修改棧的末端,因此我們可以通過維護一個指向棧末端的指針來實現這種數據結構,并且在其中進行內存的分配和釋放只需要重新分配該整數即可。所以棧上分配和釋放內存的代價是很小。
2、存放在堆中的數據并不是直接 push/pop,類似數據結構中的鏈表,需要通過一定的算法找出最優的未使用的內存塊,再存放數據。同時銷毀內存時也需要做一些額外操作。
iOS 開發者經常會聽到值類型存放在棧區,對象類型存放在堆區。但并不是所有的對象都存在堆區中,比如 C++ 中的對象可以存在去全局區、堆區也可以存在棧區。所以某些情況下,可以考慮堆、棧中創建對象的平衡性,使性能相對比較穩定。
struct Person { int m_age; }; // 全局區 Person g_person; int main() { // 棧空間 Person person; // 堆空間 Person *p = new Person(); p->m_age = 20; delete p; return 0; }
數組下標最確切的定義應該偏移(offset),如果用 a 來表示數組的首地址,a[0] 就是偏移為 0 的位置,也就是首地址,a[k] 就表示偏移 k 個 type_size 的位置,所以計算 a[k] 的內存地址只需要用這個公式:
a[k]_address = base_address + k * type_size
但是,如果數組從 1 開始計數,那我們計算數組元素 a[k]的內存地址就會變為:
a[k]_address = base_address + (k-1)*type_size
對比兩個公式,不難發現,從 1 開始編號,每次隨機訪問數組元素都多了一次減法運算,對于 CPU 來說,就是多了一次減法指令。數組作為非常基礎的數據結構,通過下標隨機訪問數組元素又是其非常基礎的編程操作,效率的優化就要盡可能做到極致。所以為了減少一次減法操作,數組選擇了從 0 開始編號,而不是從 1 開
到此,相信大家對“C語言中提高代碼執行效率的小技巧有哪些”有了更深的了解,不妨來實際操作一番吧!這里是億速云網站,更多相關內容可以進入相關頻道進行查詢,關注我們,繼續學習!
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。