畫虎畫皮難畫骨,編程編碼難編譯
古語“畫虎畫皮難畫骨”，是說畫老虎時要畫它的外表很容易，可要將老虎的氣勢畫出來卻很難。
對于現在的程序員來說，似乎也是這樣子，可以寫出整潔的代碼，設計出優異的程序，但卻不一定需要知道代碼在編譯之后的是如何運行的。
但是有時候，能了解表面背后的故事，知道一些程序編譯過程，其實對寫出一個正確的正確的程序會有很大的幫助，這起源自一段很簡單的問題實現：兩整數交換。
簡單的兩數交換不簡單
最早學習到的實現方式，就是使用臨時變量來保存一個數進行交換：
- int main()
- {
- int a = 21;
- int b = 7;
- int tmp = a;
- a = b;
- b = tmp;
- return 0;
- }
后來不經意間又學習到了不用臨時變量，只用算數運算符加減就可以進行交換的方式：
- int main()
- {
- int a = 21;
- int b = 7;
- a = a+b;
- b = a-b;
- a = a-b;
- return 0;
- }
這個問題在思想上講十分的巧妙，不過在計算機的世界里這并不是一個好的方法，考慮一點編譯后的問題，我們就會碰到溢出的問題，導致得到錯誤的結果。
高手們又使用位運算的異或運算來消除臨時變量的方法，還不用擔心溢出的問題，于是我又學習了：
- int main()
- {
- int a = 21;
- int b = 7;
- a ^= b;
- b ^= a;
- a ^= b;
- return 0;
- }
甚至有更簡短地把三個異或運算寫成一行的：
- int main()
- {
- int a = 21;
- int b = 7;
- a ^= b ^=a ^= b;
- return 0;
- }
就像我在《這些沒有可讀性的代碼，卻又體現出程序員對語言的高度理解力》一文里想表達的，這種寫法體現了書寫者對運算符順序的深刻理解，對異或運算符特殊性的充分了解。
兩數交換方法的編譯后的指令
虎皮畫得很精美，根根毛發都細致描繪，但是沒有看過老虎骨骼和肌肉，可能就感受不到萬獸之王從骨子里散發出的那種無畏的霸氣。
沒有看過編譯后的代碼，我才會總不能理解為何那么簡短優美還“節省空間”的代碼怎么就沒有成為一種標準寫法呢？好像只是作為偶然拿出來炫給初學者們，讓他們驚訝和眼睛一亮的把戲。
在網上搜索了一下有關這方面的問題，在stackoverflow上看到了這樣的一段回復：
| Using this XOR might actually be slower than the usual two value swap using a temp variable; the fact that you are writing through references suggests you are forcing the compiler to do 3 memory (ok, cache line) writes, whereas temp-style swamp should only do two memory write (any intelligent compiler will put the temp in the registers). Adding the conditional check surely makes it slower. So while this might be fun, it probably isn't a practical thing to do in a sort. |
從這句話看出，似乎看出算數法和異或法雖然節省了一個微不足道的空間，但是卻會浪費時間。效率上還不及臨時變量法，更不要提其中出現的如溢出等隱蔽的問題了。
在學習了一點gcc指令的入門之后，我使用了
- Ider$ gcc -S swap.c
來觀察了一下從C文件編譯出來的匯編指令的代碼，才發現：雖然在C種交換都只用了三行，但是編譯后的匯編指令行數卻不盡相同。
對比三種方式的main的匯編指令：
（每一個注釋表示指令所對應的C代碼，一行C代碼可能對應多個匯編指令，從注釋行開始計算，到下一個注釋行之前那行都屬于那行C代碼對應的指令）
Temp
- _main:
- Leh_func_begin1:
- pushq %rbp
- Ltmp0:
- movq %rsp, %rbp
- Ltmp1:
- movl $21, -12(%rbp) ;;int a = 21
- movl $7, -16(%rbp) ;;int b = 7
- movl -12(%rbp), %eax ;;int tmp = a
- movl %eax, -20(%rbp)
- movl -16(%rbp), %eax ;;a = b
- movl %eax, -12(%rbp)
- movl -20(%rbp), %eax ;;b = tmp
- movl %eax, -16(%rbp)
- movl $0, -8(%rbp) ;;return 0
- movl -8(%rbp), %eax
- movl %eax, -4(%rbp)
- movl -4(%rbp), %eax
- popq %rbp
- ret
- Leh_func_end1:
Arithmetic
- _main:
- Leh_func_begin1:
- pushq %rbp
- Ltmp0:
- movq %rsp, %rbp
- Ltmp1:
- movl $21, -12(%rbp) ;;int a = 21
- movl $7, -16(%rbp) ;;int b = 7
- movl -12(%rbp), %eax ;;a = a+b
- movl -16(%rbp), %ecx
- addl %ecx, %eax
- movl %eax, -12(%rbp)
- movl -12(%rbp), %eax ;;b = a-b
- movl -16(%rbp), %ecx
- subl %ecx, %eax
- movl %eax, -16(%rbp)
- movl -12(%rbp), %eax ;;a = a-b
- movl -16(%rbp), %ecx
- subl %ecx, %eax
- movl %eax, -12(%rbp)
- movl $0, -8(%rbp) ;;return 0
- movl -8(%rbp), %eax
- movl %eax, -4(%rbp)
- movl -4(%rbp), %eax
- popq %rbp
- ret
- Leh_func_end1:
XOR
- _main:
- Leh_func_begin1:
- pushq %rbp
- Ltmp0:
- movq %rsp, %rbp
- Ltmp1:
- movl $21, -12(%rbp) ;;int a = 21
- movl $7, -16(%rbp) ;;int b = 7
- movl -12(%rbp), %eax ;;a ^= b
- movl -16(%rbp), %ecx
- xorl %ecx, %eax
- movl %eax, -12(%rbp)
- movl -16(%rbp), %eax ;;b ^=a
- movl -12(%rbp), %ecx
- xorl %ecx, %eax
- movl %eax, -16(%rbp)
- movl -12(%rbp), %eax ;;a ^= b
- movl -16(%rbp), %ecx
- xorl %ecx, %eax
- movl %eax, -12(%rbp)
- movl $0, -8(%rbp) ;;return 0
- movl -8(%rbp), %eax
- movl %eax, -4(%rbp)
- movl -4(%rbp), %eax
- popq %rbp
- ret
- Leh_func_end1:
（對于一行的異或運算交換法，得到匯編指令跟三行的是一樣的。）
從匯編指令的行數，可以看出正如stackoverflow上講的一樣，利用臨時變量的代碼要明顯短于其它兩個。
對于臨時變量法，每次賦值只要讀取一個變量的值到寄存器，然后再從寄存器寫回到另一個變量中即可。
但是對于運算操作，每次都需要讀取兩個數據到寄存器種，再進行運算操作。之后把結果寫回到變量中。
如果這些指令被優化
其實如果編譯后的匯編指令不是每次都把結果寫回到變量，而是講數據保存在寄存器中，把三次運算都執行完后再寫回的吧，指令行數就會減少很多。以下就是那幻想出來的方式：
- _main:
- Leh_func_begin1:
- pushq %rbp
- Ltmp0:
- movq %rsp, %rbp
- Ltmp1:
- movl $21, -12(%rbp) ;;int a = 21
- movl $7, -16(%rbp) ;;int b = 7
- movl -12(%rbp), %eax ;;a ^= b ^= a ^= b
- movl -16(%rbp), %ecx
- xorl %ecx, %eax
- xorl %eax, %ecx
- xorl %ecx, %eax
- movl %eax, -12(%rbp)
- movl %eax, -16(%rbp)
- movl $0, -8(%rbp) ;;return 0
- movl -8(%rbp), %eax
- movl %eax, -4(%rbp)
- movl -4(%rbp), %eax
- popq %rbp
- ret
- Leh_func_end1:
如果指令像上邊那樣執行，我們就明顯減少了指令（可惜，即使是如此優化，指令行數還是要比使用臨時變量的方式要多一行）。
不過，編譯器并沒有這么做，因為這樣做破壞了編譯中很重要的一個概念：序列點。再者這樣實現很麻煩，不止要編譯當前行，還要預測之后多行可能要做的操作才能決定是否緩存該數據在寄存器中。
而且如果運算法可以優化，那臨時變量法也可以優化成：
- _main:
- Leh_func_begin1:
- pushq %rbp
- Ltmp0:
- movq %rsp, %rbp
- Ltmp1:
- movl $21, -12(%rbp) ;;int a = 21
- movl $7, -16(%rbp) ;;int b = 7
- movl -12(%rbp), %eax ;;int tmp = a, a = b, b = a
- movl -16(%rbp), %ecx
- movl %ecx, -12(%rbp)
- movl %eax, -16(%rbp)
- movl $0, -8(%rbp) ;;return 0
- movl -8(%rbp), %eax
- movl %eax, -4(%rbp)
- movl -4(%rbp), %eax
- popq %rbp
- ret
- Leh_func_end1:
用到兩個寄存器，讀取數據進來，然后寫回到對方的變量中。臨時變量也省了。
這樣看來，要想寫出高效又省空間的代碼還是要用匯編語言哦。不過，我相信這并不能成為讓大家都學習和使用匯編的理由，畢竟現在很多時候追求的不是執行效率，還是開發效率。
說回那個很炫的一行實現的異或交換法。其實已經違背了序列點的要求：在每個序列點，只能對變量進行一次修改。只是湊巧，在C中編譯后讓程序的得到了正確的結果，但是不是所有編譯器都能那么好運的。
另外，在實際中，我還碰到了另一個“不湊巧”的情況：當把它應用在數組中的兩個元素時，會得到錯誤的答案：
- #include <stdio.h>
- int main()
- {
- int a[] = {21, 7};
- a[0] ^= a[1] ^= a[0] ^= a[1];
- printf("%d, %d", a[0], a[1]);
- return 0;
- }
- //output::
- //0, 21
還是把這段代碼轉成的匯編指令(不包括printf那行)，看看能不能找出其中的緣由
- _main:
- Leh_func_begin1:
- pushq %rbp
- Ltmp0:
- movq %rsp, %rbp
- Ltmp1:
- movl _C.0.1462(%rip), %eax
- movl %eax, -16(%rbp)
- movl _C.0.1462+4(%rip), %eax
- movl %eax, -12(%rbp)
- movl -16(%rbp), %eax
- movl -12(%rbp), %ecx
- movl -16(%rbp), %edx
- movl -12(%rbp), %esi
- xorl %esi, %edx
- movl %edx, -16(%rbp)
- movl -16(%rbp), %edx
- xorl %edx, %ecx
- movl %ecx, -12(%rbp)
- movl -12(%rbp), %ecx
- xorl %ecx, %eax
- movl %eax, -16(%rbp)
- movl $0, -8(%rbp)
- movl -8(%rbp), %eax
- movl %eax, -4(%rbp)
- movl -4(%rbp), %eax
- popq %rbp
- ret
- Leh_func_end1:
- .section __TEXT,__literal8,8byte_literals
- .align 2
- _C.0.1462:
- .long 21
- .long 7
可以看出，編譯對數組做了完全不同的處理。最關鍵的是，它一共用了4個寄存器，把每次要用到的數組中的變量，都預先讀到了每個寄存器中，然后再用寄存器中不匹配的值進行運算。
- a[0] ^= a[1] ^= a[0] ^= a[1];
就相當于：
- a[0] = 21^7;
- a[1] = a[0]^7 = (21^7)^21 = 21;
- a[0] = a[1]^21 = 0;
- he last line is supposed to be a[0] = a[1]^a[0] = 21^(21^7);
所以以后還是不要用這些看似很炫的方式來做兩數交換了，還是老老實實用個臨時變量，或者比如在用C++的話直接調用標準庫里的swap函數（臨時變量實現）吧，這樣也省了擔心回有不能遇見的問題出現。
最后只感嘆一句：
虎皮雖然精美，但是虎骨才是支撐起這張表皮的精髓；
編碼雖然重要，但是編譯才是讓程序能夠運行的重心。
原文鏈接：http://www.cnblogs.com/ider/archive/2012/05/03/xor_swap_issues.html
【編輯推薦】
