為什麼(a*b!= 0)在Java中比(a!= 0 && b!= 0)更快?




performance processing-efficiency (4)

我在Java中編寫了一些代碼,在某些時候,程序的流程由兩個int變量“a”和“b”是否非零來確定(注意:a和b從不是負數,以及從不在整數溢出範圍內)。

我可以用它評估它

if (a != 0 && b != 0) { /* Some code */ }

或者可選

if (a*b != 0) { /* Some code */ }

因為我希望每段代碼運行數百萬次,所以我想知道哪一個會更快。 我通過在一個巨大的隨機生成的數組上進行比較來做了實驗,我也很好奇看看數組的稀疏性(數據分數= 0)如何影響結果:

long time;
final int len = 50000000;
int arbitrary = 0;
int[][] nums = new int[2][len];

for (double fraction = 0 ; fraction <= 0.9 ; fraction += 0.0078125) {
    for(int i = 0 ; i < 2 ; i++) {
        for(int j = 0 ; j < len ; j++) {
            double random = Math.random();

            if(random < fraction) nums[i][j] = 0;
            else nums[i][j] = (int) (random*15 + 1);
        }
    }

    time = System.currentTimeMillis();

    for(int i = 0 ; i < len ; i++) {
        if( /*insert nums[0][i]*nums[1][i]!=0 or nums[0][i]!=0 && nums[1][i]!=0*/ ) arbitrary++;
    }
    System.out.println(System.currentTimeMillis() - time);
}

結果表明,如果你期望“a”或“b”等於0超過〜3%的時間, a*b != 0a!=0 && b!=0更快:

我很想知道為什麼。 任何人都可以點亮一下嗎? 它是編譯器還是硬件級別的?

編輯: 出於好奇...現在我了解了分支預測,我想知道模擬比較對於OR b顯示的是非零的:

我們的確看到了與預期相同的分支預測效果,有趣的是該圖沿著X軸有些翻轉。

更新

我添加了!(a==0 || b==0)來分析,看看會發生什麼。

我還包括a != 0 || b != 0 在了解分支預測之後,出於好奇, a != 0 || b != 0(a+b) != 0(a|b) != 0 。 但是它們在邏輯上不等同於其他表達式,因為只有一個OR b需要非零才能返回true,所以它們不能用於處理效率的比較。

我還添加了我用於分析的實際基準,它只是迭代一個任意的int變量。

4-有些人建議包括a != 0 & b != 0而不是a != 0 && b != 0 ,預測它會更接近a*b != 0因為我們會刪除分支預測效果。 我不知道&可以與布爾變量一起使用,我認為它僅用於具有整數的二元運算。

注意:在我正在考慮所有這些的情況下,int溢出不是一個問題,但這在一般情況下絕對是一個重要的考慮因素。

CPU:Intel Core i7-3610QM @ 2.3GHz

Java版本:1.8.0_45
Java(TM)SE運行時環境(build 1.8.0_45-b14)
Java HotSpot(TM)64位服務器虛擬機(構建25.45-b02,混合模式)


我忽略了您的基準測試可能存在缺陷的問題,並以結果為準。

它是編譯器還是硬件級別的?

後者,我認為:

  if (a != 0 && b != 0)

將編譯為2個內存負載和兩個條件分支

  if (a * b != 0)

將編譯為2個內存加載,一個乘法和一個條件分支。

如果硬件級分支預測無效,則乘法可能比第二個條件分支更快。 隨著您提高比率...分支預測變得不那麼有效。

條件分支較慢的原因是它們導致指令執行管道停頓。 分支預測是通過預測分支將要去哪個方向並基於此推測選擇下一條指令來避免失速。 如果預測失敗,則加載另一個方向的指令時出現延遲。

(注意:上面的解釋過於簡單,為了更準確的解釋,您需要查看CPU製造商為彙編語言編碼器和編譯器編寫者提供的文獻, 分支預測器上的維基百科頁面是良好的背景。)

但是,有一件事你需要注意這個優化。 有a * b != 0會給出錯誤答案的任何值嗎? 考慮計算產品導致整數溢出的情況。

UPDATE

你的圖表傾向於證實我說的話。

  • 在條件分支a * b != 0情況下,還存在“分支預測”效果,並且這在圖中出現。

  • 如果將X軸上的曲線投影到0.9以上,看起來像1)它們將在大約1.0和2處相遇),會合點將大致與X = 0.0時的Y值相同。

更新2

我不明白為什麼a + b != 0a | b != 0的曲線不同 a | b != 0例。 分支預測器邏輯中可能有一些聰明的東西。 或者它可能表明別的東西。

(請注意,這種事情可能是特定的芯片型號或甚至是版本,您的基準測試結果可能與其他系統不同。)

但是,它們都具有為ab所有非負值工作的優點。


我認為你的基準有一些缺陷,可能對推斷真正的節目沒有用處。 這是我的想法:

  • (a*b)!=0對於溢出的值會做錯誤的事情,並且(a+b)!=0會額外地對總和為零的正值和負值做錯誤的事情,所以您不能使用在一般情況下,即使他們在這里工作的表達式。

  • (a|b)!=0a != 0 && b != 0正在測試是否兩個值都是非零值, (a*b)!=0非零。 這兩種情況在相同百分比的數據上不會成立。

  • 虛擬機將在外部( fraction )循環的前幾次運行期間優化表達式,當fraction為0時,幾乎不會採用分支。 如果您以0.5開始fraction ,優化程序可能會做不同的事情。

  • 除非虛擬機能夠消除這裡的一些數組邊界檢查,否則表達式中還有其他四個分支只是由於邊界檢查,這是一個複雜的因素,當試圖找出低層發生的事情時。 如果將二維數組拆分為兩個平面數組,將nums[0][i]nums[1][i]改為nums0[i]nums1[i]可能會得到不同的結果。

  • CPU分支預測器嘗試檢測數據中的短模式,或者運行所有分支採取或不採取。 隨機生成的基準數據是分支預測器嘗試處理的最糟糕的事情。 如果您的真實數據具有可預測的模式,或者長時間運行全零和全非零值,則分支可能會花費很多。

  • 滿足條件後執行的特定代碼可能會影響評估條件本身的性能,因為它會影響事件,如是否可以展開循環,哪些CPU寄存器可用,以及是否有任何獲取的nums值需要在評估條件後重新使用。 僅僅增加基準中的計數器對於真實代碼的作用並不是一個完美的佔位符。

  • System.currentTimeMillis()在大多數係統上不會比+/- 10毫秒更準確。 System.nanoTime()通常更準確。

正如你所看到的那樣存在很多不確定性,並且通過這種微型優化很難說明確任何事情,因為一個VM或CPU上更快的技巧在另一個VM上可能會變慢。 如果您的虛擬機是HotSpot,請注意有兩種更多的變體,“客戶機”虛擬機與“服務器”虛擬機相比具有不同(較弱)的優化。

如果您可以反彙編虛擬機生成的機器碼 ,那麼不要試圖猜測它做什麼!


您正在使用隨機輸入數據,導致分支不可預知。 在實踐中,分支往往(〜90%)可預測,所以在實際代碼中分支代碼可能會更快。

這就是說。 我看不到a*b != 0可以比(a|b) != 0更快。 一般而言,整數乘法比按位“或”更昂貴。 但這樣的事情偶爾會變得怪異。 例如,請參閱處理器緩存效果庫中的“示例7:硬件複雜性”示例。


這裡的答案很好,但我有一個想法可以改善事情。

由於兩個分支和相關的分支預測是可能的罪魁禍首,我們可能能夠在不改變邏輯的情況下將分支減少到單個分支。

bool aNotZero = (nums[0][i] != 0);
bool bNotZero = (nums[1][i] != 0);
if (aNotZero && bNotZero) { /* Some code */ }

它也可能有用

int a = nums[0][i];
int b = nums[1][i];
if (a != 0 && b != 0) { /* Some code */ }

原因是,根據短路規則,如果第一個布爾值為假,則不應評估第二個布爾值。 如果nums[0][i]為假,它必須執行額外的分支來避免評估nums[1][i] 。 現在,你可能並不在意nums[1][i]被評估,但是編譯器不能確定它會在你這樣做時拋出超出範圍或null參考。 通過將if塊減少到簡單的布爾值,編譯器可以足夠聰明地認識到,不必要地評估第二個布爾值不會產生負面影響。





branch-prediction