Capstone — Tăng tốc một vòng lặp nóng bằng hiểu biết CPU

// Compute sum of elements greater than threshold (128).
int sum = 0;
for (int i = 0; i < data.length; i++) {
    if (data[i] > 128) {
        sum += data[i];
    }
}

import java.util.Arrays;
import java.util.Random;

public class BranchBenchmark {

    static final int SIZE      = 10_000_000;
    static final int THRESHOLD = 128;
    static final int WARMUP    = 3;
    static final int RUNS      = 5;

    // --- Data setup ---

    static int[] randomData() {
        int[] data = new int[SIZE];
        Random rng = new Random(42); // fixed seed for reproducibility
        for (int i = 0; i < SIZE; i++) {
            data[i] = rng.nextInt(256); // values in [0, 255]
        }
        return data;
    }

    // --- Version 1: naive branch ---

    static long sumNaive(int[] data) {
        long sum = 0;
        for (int v : data) {
            if (v > THRESHOLD) {
                sum += v;
            }
        }
        return sum;
    }

    // --- Version 2: sorted (branch-friendly) ---
    // TODO: sort a copy of data, then call sumNaive on it.
    // Hint: Arrays.sort() — but measure sort cost separately.
    static long sumSorted(int[] sorted) {
        // TODO: same loop as sumNaive — the trick is the DATA, not the loop.
        return 0;
    }

    // --- Version 3: branchless ---
    // TODO: replace the if-branch with an arithmetic expression.
    // Hint: int mask = -(v > THRESHOLD ? 1 : 0) gives 0xFFFFFFFF or 0x00000000.
    // Then sum += v & mask  accumulates v when condition is true, 0 otherwise.
    static long sumBranchless(int[] data) {
        // TODO
        return 0;
    }

    // --- Benchmark harness ---

    static long benchmark(String label, int[] data, java.util.function.LongSupplier fn) {
        // Warmup: let JIT compile and stabilize
        for (int i = 0; i < WARMUP; i++) fn.getAsLong();

        long best = Long.MAX_VALUE;
        long total = 0;
        for (int i = 0; i < RUNS; i++) {
            long t0 = System.nanoTime();
            long result = fn.getAsLong();
            long elapsed = System.nanoTime() - t0;
            total += elapsed;
            if (elapsed < best) best = elapsed;
            if (i == 0) System.out.printf("  [%s] first run result = %d%n", label, result);
        }
        long avg = total / RUNS;
        System.out.printf("  [%s] avg = %d ms, best = %d ms%n",
            label, avg / 1_000_000, best / 1_000_000);
        return avg;
    }

    public static void main(String[] args) {
        int[] data = randomData();
        int[] sortedData = data.clone();
        Arrays.sort(sortedData);

        System.out.println("=== Branch Prediction Benchmark ===");
        System.out.println("Array size: " + SIZE + ", threshold: " + THRESHOLD);
        System.out.println();

        long t1 = benchmark("naive",      data,       () -> sumNaive(data));
        long t2 = benchmark("sorted",     sortedData, () -> sumSorted(sortedData));
        long t3 = benchmark("branchless", data,       () -> sumBranchless(data));

        System.out.println();
        System.out.printf("Speedup sorted    vs naive: %.2fx%n", (double) t1 / t2);
        System.out.printf("Speedup branchless vs naive: %.2fx%n", (double) t1 / t3);
    }
}

javac BranchBenchmark.java
java -server BranchBenchmark

# Compile with debug info
javac BranchBenchmark.java

# Measure branch misses via perf stat
perf stat -e branches,branch-misses java -server BranchBenchmark

static long sumFourAcc(int[] data) {
    long s0 = 0, s1 = 0, s2 = 0, s3 = 0;
    int len = data.length & ~3; // round down to multiple of 4
    for (int i = 0; i < len; i += 4) {
        int m0 = -(data[i]   > THRESHOLD ? 1 : 0);
        int m1 = -(data[i+1] > THRESHOLD ? 1 : 0);
        int m2 = -(data[i+2] > THRESHOLD ? 1 : 0);
        int m3 = -(data[i+3] > THRESHOLD ? 1 : 0);
        s0 += (data[i]   & m0);
        s1 += (data[i+1] & m1);
        s2 += (data[i+2] & m2);
        s3 += (data[i+3] & m3);
    }
    // handle tail
    for (int i = len; i < data.length; i++) {
        int m = -(data[i] > THRESHOLD ? 1 : 0);
        s0 += (data[i] & m);
    }
    return s0 + s1 + s2 + s3;
}