[入門] Javaを10倍高速化する実践テクニック集 #初心者 – Qiita

import java.util.*;

public class BranchPredictionOptimization {
    
    // 遅い例：予測困難な分岐（ランダムデータ）
    public static int countWithBranch(int[] array) {
        int count = 0;
        for (int value : array) {
            if (value >= 128) {  // 50%の確率で分岐
                count++;
            }
        }
        return count;
    }
    
    // 速い例1：データをソートして予測しやすくする
    public static int countWithSortedData(int[] array) {
        // ソート済みデータは分岐予測が容易
        int count = 0;
        for (int value : array) {
            if (value >= 128) {
                count++;
            }
        }
        return count;
    }
    
    // 速い例2：分岐を算術演算に置き換える（ブランチレス）
    public static int countBranchless(int[] array) {
        int count = 0;
        for (int value : array) {
            // 条件演算を使わず、ビット演算で0か1を生成
            // value >= 128 なら 0、そうでなければ -1
            int mask = (value - 128) >> 31;
            count += ~mask & 1;
        }
        return count;
    }
    
    // 速い例3：JDK8以降ならStreamで条件付きカウント
    public static int countWithStream(int[] array) {
        return (int) Arrays.stream(array)
                           .filter(v -> v >= 128)
                           .count();
    }
    
    // より厳密な測定のための別メソッド
    public static void preciseBenchmark() {
        int size = 10_000_000;
        int[] randomArray = new int[size];
        int[] sortedArray = new int[size];
        
        Random rand = new Random(42);
        for (int i = 0; i  size; i++) {
            int value = rand.nextInt(256);
            randomArray[i] = value;
            sortedArray[i] = value;
        }
        Arrays.sort(sortedArray);
        
        // より多くのウォームアップを実施
        for (int i = 0; i  20000; i++) {
            countWithBranch(Arrays.copyOf(randomArray, 1000));
            countWithBranch(Arrays.copyOf(sortedArray, 1000));
            countBranchless(Arrays.copyOf(randomArray, 1000));
        }
        
        // JITコンパイルの安定化のため少し待機
        try { Thread.sleep(100); } catch (InterruptedException e) {}
        
        // 測定（5回実行して最速値を採用）
        long bestRandomTime = Long.MAX_VALUE;
        long bestSortedTime = Long.MAX_VALUE;
        long bestBranchlessTime = Long.MAX_VALUE;
        
        for (int run = 0; run  5; run++) {
            long start = System.nanoTime();
            int result1 = countWithBranch(randomArray);
            long randomTime = System.nanoTime() - start;
            bestRandomTime = Math.min(bestRandomTime, randomTime);
            
            start = System.nanoTime();
            int result2 = countWithSortedData(sortedArray);
            long sortedTime = System.nanoTime() - start;
            bestSortedTime = Math.min(bestSortedTime, sortedTime);
            
            start = System.nanoTime();
            int result3 = countBranchless(randomArray);
            long branchlessTime = System.nanoTime() - start;
            bestBranchlessTime = Math.min(bestBranchlessTime, branchlessTime);
        }
        
        System.out.println("=== Branch Prediction Impact (Best of 5 runs) ===");
        System.out.printf("Random array (branch): %.4f seconds%n", 
                         bestRandomTime / 1_000_000_000.0);
        System.out.printf("Sorted array (branch): %.4f seconds%n", 
                         bestSortedTime / 1_000_000_000.0);
        System.out.printf("Branchless: %.4f seconds%n", 
                         bestBranchlessTime / 1_000_000_000.0);
        System.out.printf("Sorted speedup vs Random: %.1fx%n", 
                         (double) bestRandomTime / bestSortedTime);
        System.out.printf("Branchless speedup vs Random: %.1fx%n", 
                         (double) bestRandomTime / bestBranchlessTime);
    }
    
    public static void main(String[] args) {
        // より厳密な測定を実行
        preciseBenchmark();
    }
}