Consider using bitwise operations to reduce complex loop + if-then-else statements

今天跟同事一起處理某段需要最佳化的程式碼，經過 profiling 後，發現瓶頸出現在某段程式碼片段，類似如下：

for (i = 0; i < num_irqs ; i++) {
    if (irq_pending(i) & irq_not_masked(i)) {
        continue;
    } else {
        irq_ack(i);
    }
}
此處的邏輯很清楚，依序檢查所有 irq ，如果 irq 目前正 pending 並且也沒有被 masked 的話，就 bypass ，反之就將其 ack 。由於讀取與設定 irq 的 register 是在一個 32bit word 中涵蓋 32 個 irq 設定，所以解決的方法似乎也顯而易見：直接使用 bitwise operation 取代上述程式。如下：

for (i = 0; i < num_irq_regs ; i++) {
    should_ack_vector = ~(irq_pending_vector(i) & irq_not_masked_vector(i));
    irq_ack_vector(should_ack_vector);
}
似乎很簡單？對吧？不過考慮如果是更複雜的情況呢？如果 loop 中還有更多的條件判斷呢？是否存在系統化手法將複雜的條件判斷轉成 bitwise operation？以下是我目前採用的手法：

1. 將條件判斷式視為 input
2. 將欲執行動作視為 output
3. 建出 truth table or boolean 運算式
4. 化簡 step 3 (手算 or 利用現有工具[1])

根據以上步驟，我們逐一清查整個流程，經過一番整理後，效能提昇了百倍。一方面是因為 register read/write 本來就是相對耗時的動作（相對於 CPU 其他指令），一方面也透過 boolean 化簡得到精簡的讀寫次數。後來在 Hacker's Delight 一書中[2]，找到了更多此類技巧的更完整論述，看來是該唸書的時候了。 :-)

[1] http://electronics-course.com/boolean-algebra
[2] http://www.hackersdelight.org/