畫虎畫皮難畫骨,編程編碼難編譯
古語(yǔ)“畫虎畫皮難畫骨”，是說(shuō)畫老虎時(shí)要畫它的外表很容易，可要將老虎的氣勢(shì)畫出來(lái)卻很難。
對(duì)于現(xiàn)在的程序員來(lái)說(shuō)，似乎也是這樣子，可以寫出整潔的代碼，設(shè)計(jì)出優(yōu)異的程序，但卻不一定需要知道代碼在編譯之后的是如何運(yùn)行的。
但是有時(shí)候，能了解表面背后的故事，知道一些程序編譯過(guò)程，其實(shí)對(duì)寫出一個(gè)正確的正確的程序會(huì)有很大的幫助，這起源自一段很簡(jiǎn)單的問(wèn)題實(shí)現(xiàn)：兩整數(shù)交換。
簡(jiǎn)單的兩數(shù)交換不簡(jiǎn)單
最早學(xué)習(xí)到的實(shí)現(xiàn)方式，就是使用臨時(shí)變量來(lái)保存一個(gè)數(shù)進(jìn)行交換：
- int main()
- {
- int a = 21;
- int b = 7;
- int tmp = a;
- a = b;
- b = tmp;
- return 0;
- }
后來(lái)不經(jīng)意間又學(xué)習(xí)到了不用臨時(shí)變量，只用算數(shù)運(yùn)算符加減就可以進(jìn)行交換的方式：
- int main()
- {
- int a = 21;
- int b = 7;
- a = a+b;
- b = a-b;
- a = a-b;
- return 0;
- }
這個(gè)問(wèn)題在思想上講十分的巧妙，不過(guò)在計(jì)算機(jī)的世界里這并不是一個(gè)好的方法，考慮一點(diǎn)編譯后的問(wèn)題，我們就會(huì)碰到溢出的問(wèn)題，導(dǎo)致得到錯(cuò)誤的結(jié)果。
高手們又使用位運(yùn)算的異或運(yùn)算來(lái)消除臨時(shí)變量的方法，還不用擔(dān)心溢出的問(wèn)題，于是我又學(xué)習(xí)了：
- int main()
- {
- int a = 21;
- int b = 7;
- a ^= b;
- b ^= a;
- a ^= b;
- return 0;
- }
甚至有更簡(jiǎn)短地把三個(gè)異或運(yùn)算寫成一行的：
- int main()
- {
- int a = 21;
- int b = 7;
- a ^= b ^=a ^= b;
- return 0;
- }
就像我在《這些沒(méi)有可讀性的代碼，卻又體現(xiàn)出程序員對(duì)語(yǔ)言的高度理解力》一文里想表達(dá)的，這種寫法體現(xiàn)了書寫者對(duì)運(yùn)算符順序的深刻理解，對(duì)異或運(yùn)算符特殊性的充分了解。
兩數(shù)交換方法的編譯后的指令
虎皮畫得很精美，根根毛發(fā)都細(xì)致描繪，但是沒(méi)有看過(guò)老虎骨骼和肌肉，可能就感受不到萬(wàn)獸之王從骨子里散發(fā)出的那種無(wú)畏的霸氣。
沒(méi)有看過(guò)編譯后的代碼，我才會(huì)總不能理解為何那么簡(jiǎn)短優(yōu)美還“節(jié)省空間”的代碼怎么就沒(méi)有成為一種標(biāo)準(zhǔn)寫法呢？好像只是作為偶然拿出來(lái)炫給初學(xué)者們，讓他們驚訝和眼睛一亮的把戲。
在網(wǎng)上搜索了一下有關(guān)這方面的問(wèn)題，在stackoverflow上看到了這樣的一段回復(fù)：
| 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. |
從這句話看出，似乎看出算數(shù)法和異或法雖然節(jié)省了一個(gè)微不足道的空間，但是卻會(huì)浪費(fèi)時(shí)間。效率上還不及臨時(shí)變量法，更不要提其中出現(xiàn)的如溢出等隱蔽的問(wèn)題了。
在學(xué)習(xí)了一點(diǎn)gcc指令的入門之后，我使用了
- Ider$ gcc -S swap.c
來(lái)觀察了一下從C文件編譯出來(lái)的匯編指令的代碼，才發(fā)現(xiàn)：雖然在C種交換都只用了三行，但是編譯后的匯編指令行數(shù)卻不盡相同。
對(duì)比三種方式的main的匯編指令：
（每一個(gè)注釋表示指令所對(duì)應(yīng)的C代碼，一行C代碼可能對(duì)應(yīng)多個(gè)匯編指令，從注釋行開(kāi)始計(jì)算，到下一個(gè)注釋行之前那行都屬于那行C代碼對(duì)應(yīng)的指令）
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:
（對(duì)于一行的異或運(yùn)算交換法，得到匯編指令跟三行的是一樣的。）
從匯編指令的行數(shù)，可以看出正如stackoverflow上講的一樣，利用臨時(shí)變量的代碼要明顯短于其它兩個(gè)。
對(duì)于臨時(shí)變量法，每次賦值只要讀取一個(gè)變量的值到寄存器，然后再?gòu)募拇嫫鲗懟氐搅硪粋€(gè)變量中即可。
但是對(duì)于運(yùn)算操作，每次都需要讀取兩個(gè)數(shù)據(jù)到寄存器種，再進(jìn)行運(yùn)算操作。之后把結(jié)果寫回到變量中。
如果這些指令被優(yōu)化
其實(shí)如果編譯后的匯編指令不是每次都把結(jié)果寫回到變量，而是講數(shù)據(jù)保存在寄存器中，把三次運(yùn)算都執(zhí)行完后再寫回的吧，指令行數(shù)就會(huì)減少很多。以下就是那幻想出來(lái)的方式：
- _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:
如果指令像上邊那樣執(zhí)行，我們就明顯減少了指令（可惜，即使是如此優(yōu)化，指令行數(shù)還是要比使用臨時(shí)變量的方式要多一行）。
不過(guò)，編譯器并沒(méi)有這么做，因?yàn)檫@樣做破壞了編譯中很重要的一個(gè)概念：序列點(diǎn)。再者這樣實(shí)現(xiàn)很麻煩，不止要編譯當(dāng)前行，還要預(yù)測(cè)之后多行可能要做的操作才能決定是否緩存該數(shù)據(jù)在寄存器中。
而且如果運(yùn)算法可以優(yōu)化，那臨時(shí)變量法也可以優(yōu)化成：
- _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:
用到兩個(gè)寄存器，讀取數(shù)據(jù)進(jìn)來(lái)，然后寫回到對(duì)方的變量中。臨時(shí)變量也省了。
這樣看來(lái)，要想寫出高效又省空間的代碼還是要用匯編語(yǔ)言哦。不過(guò)，我相信這并不能成為讓大家都學(xué)習(xí)和使用匯編的理由，畢竟現(xiàn)在很多時(shí)候追求的不是執(zhí)行效率，還是開(kāi)發(fā)效率。
說(shuō)回那個(gè)很炫的一行實(shí)現(xiàn)的異或交換法。其實(shí)已經(jīng)違背了序列點(diǎn)的要求：在每個(gè)序列點(diǎn)，只能對(duì)變量進(jìn)行一次修改。只是湊巧，在C中編譯后讓程序的得到了正確的結(jié)果，但是不是所有編譯器都能那么好運(yùn)的。
另外，在實(shí)際中，我還碰到了另一個(gè)“不湊巧”的情況：當(dāng)把它應(yīng)用在數(shù)組中的兩個(gè)元素時(shí)，會(huì)得到錯(cuò)誤的答案：
- #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
還是把這段代碼轉(zhuǎn)成的匯編指令(不包括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
可以看出，編譯對(duì)數(shù)組做了完全不同的處理。最關(guān)鍵的是，它一共用了4個(gè)寄存器，把每次要用到的數(shù)組中的變量，都預(yù)先讀到了每個(gè)寄存器中，然后再用寄存器中不匹配的值進(jìn)行運(yùn)算。
- a[0] ^= a[1] ^= a[0] ^= a[1];
就相當(dāng)于：
- 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);
所以以后還是不要用這些看似很炫的方式來(lái)做兩數(shù)交換了，還是老老實(shí)實(shí)用個(gè)臨時(shí)變量，或者比如在用C++的話直接調(diào)用標(biāo)準(zhǔn)庫(kù)里的swap函數(shù)（臨時(shí)變量實(shí)現(xiàn)）吧，這樣也省了擔(dān)心回有不能遇見(jiàn)的問(wèn)題出現(xiàn)。
最后只感嘆一句：
虎皮雖然精美，但是虎骨才是支撐起這張表皮的精髓；
編碼雖然重要，但是編譯才是讓程序能夠運(yùn)行的重心。
原文鏈接：http://www.cnblogs.com/ider/archive/2012/05/03/xor_swap_issues.html
【編輯推薦】
