好文共賞 — 如何用單核心 CPU 打天下

說到怎麼處理效能問題,大家直覺應該都是做 parallelism 或者 concurrency, 不過其實也可以選擇改變演算法做效能的改善,這種做法的好處是可以不用額外處理 parallelism 或者 concurrency 所帶來的複雜性(例如處理 shared resources, race conditions, thread safety 等等),同時也不用提高運算資源的等級,用單核心 CPU 也能戰!

Speeding up your code when multiple cores aren’t an option 一文就介紹如何透過改變演算法提升效能,該文使用 Python 實作 Floyd-Steinberg dithering 演算法作為示範,示範如何一步步透過改善演算法,將時間從 2.3ms 縮到只有 0.55ms 減少約 76% 的執行時間,其中透過增加圖片長寬各 2 個 pixels 的作法,讓判斷角落像素的 if-else 可以簡化的作法,非常的聰明,非常花點時間推薦閱讀。

這篇文章中有幾個重點值得學習:

  1. 單核心 CPU 沒你想像中的弱,它還是具備同時執行多個指令的能力,只要這些指令沒有彼此相依,這個功能稱為 ILP (Instruction-level parallelism)
  2. CPU 遇到 branch 指令時也會嘗試預測哪些指令是有可能要執行的,如果預測錯誤,就會導致 CPU 運作較慢,因為它就得重新再預測一遍
  3. 只要用對 CPU 指令, CPU 也能用 1 個指令同時對多個資料進行操作,這個稱為 SIMD (Single Instruction, Multiple Data)
  4. 善用 CPU 的快取,也可以加速執行速度

綜合上述 4 點,簡單來說可以透過減少或簡化 if-else 的情況,以及使用 CPU 快取,盡量讓資料快取在 CPU level, 減少對記憶體的讀取或寫入的次數,就能很大程度提升程式效能,而且這些技巧各種語言都適用。

最後補充一下, Floyd-Steinberg dithering 演算法是一種抖動(dithering)演算法,用在數位訊號處理可以降低量化誤差(quantization error)。簡單來說我們在處理訊號時,只能用近似值來表示,不可能用無窮的位元去表示,舉灰階圖片轉黑白圖片為例,我們用 0 到 255 之間的數值來表示灰階色彩,當要轉黑白圖片時,就是用近似值的方式,看數值比較接近 0 還是 255, 如果接近 0 一點,就直接以 0 表示,如果接近 255 一點,改以 255 表示,但是這種近似值的方式會讓圖片看起來較不順眼,所以加上抖動(dithering),也就是針對鄰近的像素加入數值(或稱誤差值/雜訊)的方式進行調整,讓黑白圖片看起來更自然順眼(如下圖, no dithering 的突兀白點比較多)。

dithering-demo.png

原文: Speeding up your code when multiple cores aren’t an option

對抗久坐職業傷害

研究指出每天增加 2 小時坐著的時間,會增加大腸癌、心臟疾病、肺癌的風險,也造成肩頸、腰背疼痛等常見問題。

然而對抗這些問題,卻只需要工作時定期休息跟伸展身體即可!

你想輕鬆改變現狀嗎?試試看我們的 PomodoRoll 番茄鐘吧! PomodoRoll 番茄鐘會根據你所設定的專注時間,定期建議你 1 項辦公族適用的伸展運動,幫助你打敗久坐所帶來的傷害!

追蹤新知

看完這篇文章了嗎?還意猶未盡的話,追蹤粉絲專頁吧!

我們每天至少分享 1 篇文章/新聞或者實用的軟體/工具,讓你輕鬆增廣見聞提升專業能力!如果你喜歡我們的文章,或是想了解更多特定主題的教學,歡迎到我們的粉絲專頁按讚、留言讓我們知道。你的鼓勵,是我們的原力!

贊助我們的創作

看完這篇文章了嗎? 休息一下,喝杯咖啡吧!

如果你覺得 MyApollo 有讓你獲得實用的資訊,希望能看到更多的技術分享,邀請你贊助我們一杯咖啡,讓我們有更多的動力與精力繼續提供高品質的文章,感謝你的支持!