好文共賞 — 如何用單核心 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 可以簡化的作法，非常的聰明，非常花點時間推薦閱讀。
這篇文章中有幾個重點值得學習：
- 單核心 CPU 沒你想像中的弱，它還是具備同時執行多個指令的能力，只要這些指令沒有彼此相依，這個功能稱為 ILP (Instruction-level parallelism)
- CPU 遇到 branch 指令時也會嘗試預測哪些指令是有可能要執行的，如果預測錯誤，就會導致 CPU 運作較慢，因為它就得重新再預測一遍
- 只要用對 CPU 指令， CPU 也能用 1 個指令同時對多個資料進行操作，這個稱為 SIMD (Single Instruction, Multiple Data)
- 善用 CPU 的快取，也可以加速執行速度
綜合上述 4 點，簡單來說可以透過減少或簡化 if-else 的情況，以及使用 CPU 快取，盡量讓資料快取在 CPU level, 減少對記憶體的讀取或寫入的次數，就能很大程度提升程式效能，而且這些技巧各種語言都適用。
最後補充一下， Floyd-Steinberg dithering 演算法是一種抖動(dithering)演算法，用在數位訊號處理可以降低量化誤差(quantization error)。簡單來說我們在處理訊號時，只能用近似值來表示，不可能用無窮的位元去表示，舉灰階圖片轉黑白圖片為例，我們用 0 到 255 之間的數值來表示灰階色彩，當要轉黑白圖片時，就是用近似值的方式，看數值比較接近 0 還是 255, 如果接近 0 一點，就直接以 0 表示，如果接近 255 一點，改以 255 表示，但是這種近似值的方式會讓圖片看起來較不順眼，所以加上抖動(dithering)，也就是針對鄰近的像素加入數值(或稱誤差值/雜訊)的方式進行調整，讓黑白圖片看起來更自然順眼（如下圖， no dithering 的突兀白點比較多）。
原文： Speeding up your code when multiple cores aren’t an option
