Re: [問題] XOR交換值問題

[Hazukashiine (みなさん、こんにちは)]

這樣的寫法要追朔到手工撰寫組合語言

當時連對記憶體和暫存器的使用都斤斤計較

所以如果用一個額外的暫存器去儲存值的話

代表 register spilling 的可能性會增加

因為為了要確保這個跳到 label 處理完後

要把我們剛 push 出去的值再 pop 回來要不少的時間

這段時間是有點久故也被稱為 von Neumann bottleneck

用來描述資料在匯流排上的傳輸瓶頸



--- 題外話 ---

說到 XOR 的神奇技巧

我們更常用的，甚至到現今都有在用的是：

使用 XOR REG, REG

來把一個暫存器的值清零

這樣做是確實會比 MOV 指令來得好

現今的 CPU 為了拉高時脈跟吞吐量

通常都把處理器做成管線式的 (pipelined)

這樣以來常常需要去處理 data hazard

因此 MOV 指令可能觸發

partial register stall

這跟指令的順序有很大的關係

因此在 Intel 的規格書上有明確指出

希望用 XOR 還有另外五種指令來清零

Intel 把它稱作 zero idioms

這些指令已經被 hard-coded 在晶片上

讓處理器明確知道這個指令只是要清零

而不會觸發額外的事件

這樣可能會在一些關鍵的時刻提升效率



--- 結尾語 ---

無論如何在編譯器很聰明的年代

把 code 寫得好懂真的比較實際

甚至還更好優化

寫了 XOR SWAP 一定一定比較慢

因為 x86 提供 XCHG 來交換暫存器的值

如果用一般的寫法（宣告額外的變數）

優化器很容易優化你的程式碼

挑選出這顆處理器最適當的指令出來

所以說

Premature optimization is evil.

在沒確定這是效能瓶頸前過早進行一些優化

可能會適得其反


※ 引述《ptt0720 (濕濕)》之銘言：
: 語言：CPP
: 今天寫quick sort的時候發現原本常用的交數值方法好像有觀念上的問題
: https://i.imgur.com/GwH4NbM.png
: 我習慣的用法是第二十七行 直接用參考交換兩個值
: 但是發現印出來後都是一堆0
: 後來交叉比對後發現是XOR交換值的問題
: 想請問一下是不是陣列用XOR交換數值會出錯？
: 想請問一下原因 麻煩各位大大了

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.185.23
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1511674682.A.71C.html
※ 編輯: Hazukashiine (61.230.0.89), 11/26/2017 13:47:07
推 alan23273850: 專業推
推 galic: XOR超神奇的阿 Parity check很常用 但說到跟XOR Swap比較相
→ galic: 關的大概是 XOR Linked List...
推 chuegou: 這篇剛好也跟上面那篇問組語效率的相關
推 VictorTom: 推:)
推 final01: 當時是多久以前？
→ Hazukashiine: 很久很久以前（ 大誤
推 ersfw4418: 感謝教學
推 ilikekotomi: 感謝分享 現在只知道有XOR SWAP 但沒想過要去用
推 chengcti: 其實 現在已經沒人考慮這個 但是MCU 還是需要
推 TitanEric: 推個
→ PkmX: 最初用跟自己xor清成零不是因為他指令最短嗎= =?
→ PkmX: 且通常編譯器最佳化後 分配reg的時候就直接幫你把交換的值
→ PkmX: 寫到交換過後的reg了 連xchg都不需要XD
推 james732: 推
推 xvid: 推
推 friendever: 專業推