在 64bit CPU 上計算 16bit 數字的 bit 數

最近看到《Google’s “Director of Engineering” Hiring Test》，覺得作者 Pierre Gauthier 的技術能力超標於這個初階測驗。從他的回答學到了一些東西，這篇針對第九題作個簡單的測試。

題目：There’s an array of 10,000 16-bit values, how do you count the bits most efficiently?

官方答案是查表法，用空間換取時間的技巧。想想這應該就是最佳解了吧，從演算法的角度來說已是 O(1) 了。

Pierre Gauthier 卻回答：

Me: there are faster methods processing 64-bit words with masks but I can’t explain it over the phone, I must write code.

Recruiter: the correct answer is to use a lookup table and then sum the results.

Me: on which kind of CPU? Why not let me compare my code to yours in a benchmark?

看到他的回答，才想起以前有讀過有位元計算的技巧可以快速算出 bit 數。一次取 4 個 16bit 數字當作一個 64bit 數字，再用特殊技巧算出 bit 數，的確有可能更快。

好奇兩者的效率差異，就依兩個解法的概念各寫了一份實作，原始碼和測試程式在這裡。下面是測試結果。

iMac 4 GHz Intel Core i7

Ubuntu VM (Parallel) on iMac

比較結果

取 4 個 16bit 數字當作一個 64bit 數字用 mask 計算的確比較快，而且在 g++ -O3 on Linux 的情況快了 ~2.5 倍！之後再找時間看編出來的組語，看看為什麼會有如此差異。

另外 Parallel 效能很好，VM 上的執行速度和 Host 沒什麼差。

其它

Pierre Gauthier 針對 quick sort 的看法也很有趣：

Me: “big-O” ignores data storage latencies, topology, volume, available memory, and even the computational cost of every CPU instructions involved in a given implementation — instead, it merely counts the number of algorithmic operations! Big-O can be a valuable indication when designing algorithms but the best performing and scaling solution depends on the particular constraints of any specific problem and environment.

…

The Linux kernel (that Google relies on) opted for Heapsort rather than Quicksort… for its lower memory usage and more predictable execution time.

這兩個例子提醒了我：演算法和效率分析讓我們可以避免使用明顯錯誤的方法，但實務上仍有許多細節會影響時間和空間的效率，需要多留意。

2016–10–16 Update

1. 從 Po-Wei Wang 那得知《SSSE3: fast popcount》，有更完整的比較。抓了程式在我的環境跑，其中 builtin-popcnt-unrolled-errata-manual 的效率最好，所以就將這部份實作加到我的測試裡。這個作法直接用組語呼叫 SSE4 的 popcnt。在 VM 或 Host 上跑，執行速度沒有差異。下面是在 Ubuntu VM 執行的結果：

用 SSE4 的指令 popcnt 竟然快了 ~8.5 倍，真是驚人。硬體加速才是王道啊！

2. Wens 提到 ARM 也有類似的指令，不過我懶得在 ARM 的環境測試 …。

3. 聊到關於 Pierre Gauthier 對 Big-O 的看法，Scott 提到 “Latency Numbers Every Programmer Should Know Raw”。雖然看過這個表好幾次，還是沒有印到腦子裡。藉這次的機會，有了比較深的體會。當演算法的效率到理論最佳值時，就得留意每步操作在現行計算機架構下的執行時間。即使指令數比較多，若能藉此減少 memory load/store 的次數，有可能更省時間。

4. 我後來又補上暴力法和用 8-bit 數字建表的實作。藉此觀察 memory load 和 cache miss 的影響，結果算是符合推測。下面是在 Ubuntu VM 的執行：

單從演算法效率來說， count_directly 是 count_by_table 「16倍」慢，但結果是 ~5.5 倍慢。應該是因為 count_directly 少了一次 memory load，而 memory_load 的速度比讀寫 register 慢不少，所以雖然是 16倍的操作，速度不是 16 倍慢。

count_by_table8 是用 8-bit 數字建表，查表次數是 count_by_table (用16-bit 數字的表) 的兩倍，但 count_by_table8 的表只有 256 個數字，比較不容易 cache miss，所以執行時間差不多，沒有慢兩倍。

count_by_bit_operation 編出來的組語多了相當多指令，但是它沒有查表。換句話說，處理 4 個 16-bit 數字時，少了 4 次 memory load。這應該是它之所以快的關鍵。