[問題] 為何這兩份程式碼的效能差異如此奇特

看板CompilerDev作者 (陽光大肥宅)時間2年前 (2022/05/03 22:12), 2年前編輯推噓5(5推 0噓 12→)
留言17則, 3人參與, 2年前最新討論串1/2 (看更多)
由於我是在 LLVM IR 最佳化階段發現這個問題， 跟編譯器最佳化有關，所以我發在這個版上。 這個問題困擾我很久了，想和版上的大大討論一番。 由於 LLVM IR 比較難讀，所以我把程式逆推成 C code 來增加可讀性。 先附上兩份程式碼的線上 diff: https://www.diffchecker.com/Thbx9sDk 然後進行這樣編譯： opt -S -passes=mem2reg more.ll -o more.ll opt -S -passes=mem2reg less.ll -o less.ll llc more.ll llc less.ll ( llc 預設 O2） 得到兩份組合語言。線上 diff 如下： https://www.diffchecker.com/NV4uuopa （可以直接拉到左方組語 85 行 if.end 那裡） 其實可以發現，左邊那份程式碼（姑且稱之 less.c）先將 foo(rem % 5) 存起來， 只計算了 rem % 5 一次、call foo 一次； 右邊的程式碼（more.c） foo(rem % 5) 計算兩次，也就是說 rem % 5 兩次、call foo 兩次， 比左邊的程式碼多一次。 理論上，應該要比較慢才對，但我用 Linux Perf 跑過一萬次發現， 多計算 rem % 5 和 call foo 的反而比較快。 perf 中，我可以得知 instruction 數量、cycles 數量等等 instruction 數量中，less.c 比 more.c 還要少，不過這是可以預料的， 畢竟人家就是比他少做運算跟呼叫函數； 然而在 "insn per cycle" 則直接輸給了 more.c，導致實際 cycles 數量 less.c 比 more.c 還要多， 也當然執行時間比較長，但我實在是不明白原因為何。 目前的實驗做到以下： 1. llc 用 O0 最佳化 -> less.c 比 more.c 更快 -> 表示 llc 的 O2 對 more.c 那份程式碼有更好的最佳化？ 但很沒道理，明明多 call 了 function 也多計算了取餘數運算，怎麼會比較快？ 2. 觀察 foo(rem % 5) 的參數 "rem % 5" 值為多少，發現都是 0 -> 也就是說，多 call 的 function 都只是進入 function 直接回傳 1 -> 把該參數改成非 0 則 less.c 比 more.c 更快。 但不管如何，還是多呼叫 function 了呀，沒道理參數影響這麼多， program counter 跳來跳去，一定會比較慢吧？ 這問題雖然很實務，但真的很玄，而且困擾我很久。 我的老闆（現為碩士生）要我把原因找出來，但我找了一整天，實在是想不到原因。 希望有高手能夠幫幫我，拜託了... -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.189.98 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/CompilerDev/M.1651587139.A.DF3.html ※ 編輯: shane87123 (1.160.189.98 臺灣), 05/03/2022 22:13:26 ※ 編輯: shane87123 (1.160.189.98 臺灣), 05/03/2022 22:19:29
推
05/04 08:42, 2年前 , 1F
是說 LLVM 有個東西叫 MCA，我沒用過，但看描述，感覺應該可
05/04 08:42, 1F
→
05/04 08:42, 2年前 , 2F
以幫到你？
05/04 08:42, 2F
謝謝，我都忘記還有這個東西了。 用 llvm-mca 分析一下，並用 bottleneck-analysis 分析，發現 O3 的 data-dependency 比較重，研判可能跟 cse 有關：資料在程式碼初期計算好，並存放在 register 內， 之後的運算需要使用到它，就需要去存取這個 register 等等... 為了驗證這個部分，我把 cse 後的程式碼還原回去，再用 llvm-mca 跑一次分析， 確實 register-dependency 下降了、時間也降下來了。 我自己得到的結論是：O3 可以有效降低指令的執行數量，但有可能因此增加 data-depende ncy， 會變差。 ※ 編輯: shane87123 (1.160.189.98 臺灣), 05/04/2022 11:59:19
推
05/04 12:54, 2年前 , 3F
那為什麼有 data dependency 就會跑比較慢呢？因為
05/04 12:54, 3F
→
05/04 12:54, 2年前 , 4F
pipeline 會 stall 嗎？
05/04 12:54, 4F
謝謝你抽空跟我一起討論。看過你的提問後，我在近一步分析。 我猜測 data dependency 應該是出在 C code 中的 a = a * call （另一份的是 a = a * foo( rem % 5 ) 我去做了 time-line 的分析 llvm-mca -timeline more.s llvm-mca -timeline less.s 根據 llvm-mca 文件提到的：當指令在排班器的 ready 狀態的時間與在排班器的總時間相比越少的話，data dependency 越高，Latency也比較高 （https://llvm.org/docs/CommandGuide/llvm-mca.html#timeline-view) 所以我去看了那個乘法指令的狀態，大致上如下： [1]: 在排班器裡面的時間 [2]: 在排班器且為 ready 的時間 [3]: 總共耗費的時間 less.s （我認為應該比較快但沒有比較快的） [1] [2] [3] 90.4 0.5 36.2 imull %ebp, %eax more.s [1] [2] [3] 112.1 1.0 31.8 imull %r14d, %eax 我去算了一下比例： less.s 的比例：0.5 / 90.4*100% = 0.56% more.s 的比例：1 / 112.1 * 100% = 0.89% 表示 less.s 的乘法因 data dependency 而 latency 比較嚴重 至於 more.s 的乘法運算之前應該還有 callq foo 這個指令，應該會很慢才對， 但 llvm-mca 有提到，面對 call function 準確度不高，加上我原文提及，more.c 比較快 的原因是因為傳入 foo 的參數為0，會 直接 return 1，所以我覺得 call foo 實際執行時間應該很短 換成傳入2以上的話應該就會比較慢了 ※ 編輯: shane87123 (49.216.29.37 臺灣), 05/04/2022 14:43:08 ※ 編輯: shane87123 (49.216.29.37 臺灣), 05/04/2022 14:44:32 ※ 編輯: shane87123 (49.216.29.37 臺灣), 05/04/2022 14:45:54 ※ 編輯: shane87123 (49.216.29.37 臺灣), 05/04/2022 14:46:48 ※ 編輯: shane87123 (49.216.29.37 臺灣), 05/04/2022 14:49:12
推
05/04 17:47, 2年前 , 5F
感謝分享
05/04 17:47, 5F
推
05/04 23:06, 2年前 , 6F
其實你後面那一串分析我就跟不上了XD，所以沒辦法給出更多的
05/04 23:06, 6F
→
05/04 23:06, 2年前 , 7F
想法，這裡就留給更厲害的大大吧
05/04 23:06, 7F
※ 編輯: shane87123 (1.160.189.98 臺灣), 05/05/2022 01:22:46
→
05/05 06:06, 2年前 , 8F
文章應該是說 long data dependencies 會使 ILP 變糟，
05/05 06:06, 8F
→
05/05 06:06, 2年前 , 9F
跟你轉換過的說法有些不太一樣？
05/05 06:06, 9F
謝謝你提醒我ILP，我昨天看文章沒看到這塊 所以我後來有做另一個實驗 就是我把兩份程式碼用單一核心去跑 發現less比more快了
→
05/05 06:13, 2年前 , 10F
「然而在 "insn per cycle" 則直接輸給了 more.c，導致
05/05 06:13, 10F
→
05/05 06:13, 2年前 , 11F
實際 cycles 數量 less.c 比 more.c 還要多」<- 因果關
05/05 06:13, 11F
→
05/05 06:13, 2年前 , 12F
係怪怪的，而且因為 more 有更多 cycle 短的指令去攤平
05/05 06:13, 12F
→
05/05 06:13, 2年前 , 13F
insn per cycle，比較 insn per cycle 不合適。
05/05 06:13, 13F
我認為的因果關係是這樣： 1. less比more多data dependency導致ILP更差 2. ILP變差，導致在多核心運算時，less的IPC比more還低 3. 多核運算中，速度上 less 比more 慢 4. 單一核心運算中，more失去了ILP比較好的優勢，而less指令比較少的優勢還在，所以單 核運算less比more快 雖然比較IPC好像真的不合適，因為他應該是從cycles和指令數量去逆推IPC 但我想不到更好的因果關係去說明這件事情OTZ ※ 編輯: shane87123 (101.12.17.166 臺灣), 05/05/2022 12:36:56 ※ 編輯: shane87123 (101.12.17.166 臺灣), 05/05/2022 12:40:10
推
05/15 05:38, 2年前 , 14F
專題生嗎?
05/15 05:38, 14F
→
05/15 16:20, 2年前 , 15F
單核跟多核比能造成影響的因素蠻多的...通常可以先考慮
05/15 16:20, 15F
→
05/15 16:20, 2年前 , 16F
差異的量級再針對可能的原因找
05/15 16:20, 16F
→
05/15 16:22, 2年前 , 17F
還有個方式是換舊舊的 CPU，比較不用考慮特殊的因素XD
05/15 16:22, 17F
‣ 更多 shane87123 的文章
文章代碼(AID): #1YSJX3tp (CompilerDev)
‣ 更多 shane87123 的文章
文章代碼(AID): #1YSJX3tp (CompilerDev)