Mini-challenge — tái cấu trúc AoS sang SoA để giảm cache miss

TL;DR: Bạn có một mảng 5 triệu hạt (particle), mỗi hạt lưu đủ vị trí, vận tốc, khối lượng, điện tích. Vòng lặp vật lý nóng chỉ cập nhật vị trí từ vận tốc. Với layout AoS (Array of Structs) hiện tại, mỗi cache line kéo về nhiều field không dùng. Nhiệm vụ của bạn: refactor sang SoA (Struct of Arrays), đo thời gian trước-sau, và giải thích vì sao layout mới nhanh hơn. Đây là bài luyện tập tổng hợp tất cả những gì khoá này dạy về bộ nhớ và cache.

🎯 Đề bài

Một hệ mô phỏng vật lý đơn giản quản lý N = 5_000_000 hạt. Mỗi hạt có:

• Vị trí: x, y, z (double, 8 byte mỗi cái)
• Vận tốc: vx, vy, vz (double, 8 byte mỗi cái)
• Khối lượng: mass (double, 8 byte)
• Điện tích: charge (double, 8 byte)

Tổng payload: 64 byte mỗi hạt (vừa bằng 1 cache line nếu là C struct liền khối; trong Java còn thêm object header và indirection — xem lưu ý JVM ở phần lời giải).

Vòng lặp vật lý chạy mỗi "tick" của simulation:

// Cap nhat vi tri tu van toc (dt = time step)
for (int i = 0; i < n; i++) {
    particles[i].x  += particles[i].vx * dt;
    particles[i].y  += particles[i].vy * dt;
    particles[i].z  += particles[i].vz * dt;
}

Vòng lặp này chỉ dùng 6 field (x, y, z, vx, vy, vz) — nhưng mỗi lần truy cập particles[i] kéo cả struct 64 byte vào cache, trong đó mass và charge không được đụng tới.

Nhiệm vụ:

1. Đo thời gian vòng lặp trên với layout AoS hiện tại.
2. Refactor sang SoA: tách mỗi field thành mảng riêng.
3. Đo lại thời gian với layout SoA.
4. So sánh và giải thích kết quả.

🔍 Phân tích I-P-O

Điều kiện đo chuẩn:

• Warmup JIT trước khi đo (chạy vài lần không tính)
• Lặp nhiều lần và lấy trung bình
• Cùng giá trị N và dt cho cả hai layout
• Không có I/O hay logic khác trong hot loop

📦 Concept mapping

Bài này tổng hợp trực tiếp các kiến thức từ khoá Bộ nhớ:

Vì sao SoA giảm cache miss ở bài này:

Với AoS, một cache line 64 byte chứa đúng 1 struct:

AoS line: [x y z vx vy vz mass charge]  -- 8 fields x 8 byte = 64 byte
           dung    dung    BO QUA BO QUA

Vòng lặp update chỉ cần x, y, z, vx, vy, vz (6 field = 48 byte). Hai field mass và charge (16 byte) bị kéo vào cache vô ích. Tỉ lệ hữu ích: 48/64 = 75%.

Với SoA, mảng xs[] chứa các x liên tục:

SoA line (xs): [x0 x1 x2 x3 x4 x5 x6 x7]  -- 8 double x 8 byte = 64 byte
                toan bo dung cho vong lap

Mỗi cache line toàn bộ là dữ liệu cần dùng. Tỉ lệ hữu ích: 100%. Số cache miss giảm tỉ lệ thuận — và với 5 triệu hạt, điều đó tạo ra chênh lệch thời gian đo được rõ ràng.

▶️ Starter code

import java.util.Random;

public class ParticleSimAoS {

    // AoS: moi hat la mot object day du field
    static class Particle {
        double x, y, z;
        double vx, vy, vz;
        double mass;
        double charge;
    }

    static final int N  = 5_000_000;
    static final double DT = 0.016; // time step ~60fps

    public static void main(String[] args) {
        Particle[] particles = new Particle[N];
        Random rng = new Random(42);
        for (int i = 0; i < N; i++) {
            Particle p = new Particle();
            p.x  = rng.nextDouble(); p.y  = rng.nextDouble(); p.z  = rng.nextDouble();
            p.vx = rng.nextDouble(); p.vy = rng.nextDouble(); p.vz = rng.nextDouble();
            p.mass   = rng.nextDouble() + 0.1;
            p.charge = rng.nextDouble() - 0.5;
            particles[i] = p;
        }

        // Warmup: chay 3 lan, khong do
        for (int w = 0; w < 3; w++) {
            updatePositions(particles, N, DT);
        }

        // Do thoi gian: trung binh 5 lan
        int RUNS = 5;
        long total = 0;
        for (int r = 0; r < RUNS; r++) {
            long start = System.nanoTime();
            updatePositions(particles, N, DT);
            total += System.nanoTime() - start;
        }
        System.out.printf("AoS avg: %.2f ms%n", total / RUNS / 1e6);
    }

    static void updatePositions(Particle[] particles, int n, double dt) {
        for (int i = 0; i < n; i++) {
            Particle p = particles[i];   // cache ref -- 1 array load thay vi 3
            p.x += p.vx * dt;
            p.y += p.vy * dt;
            p.z += p.vz * dt;
        }
    }
}

Lưu ý quan trọng về JVM: Java object (Particle) được cấp phát trên heap, mỗi object có header 12–16 byte và nằm ở địa chỉ riêng. Ngay cả khi Particle[] là mảng liên tục các tham chiếu (reference), các object Particle thật sự nằm rải rác trên heap → AoS trong Java không hoàn toàn liên tục trong bộ nhớ như C struct array. Điều này làm AoS trong Java thậm chí còn tệ hơn C về cache miss (pointer chasing thêm vào). SoA với double[] primitive thì hoàn toàn liên tục.

💡 Gợi ý

Gợi ý 1 — Cấu trúc SoA:

Thay vì mảng các object, dùng nhiều mảng primitive song song:

double[] xs, ys, zs;
double[] vxs, vys, vzs;
double[] masses, charges;

Mỗi mảng double[] trong Java là một vùng nhớ liên tục trên heap — đây là điều kiện để spatial locality hoạt động tốt.

Gợi ý 2 — Vòng lặp SoA:

Vòng lặp update trở thành:

for (int i = 0; i < n; i++) {
    xs[i] += vxs[i] * dt;
    ys[i] += vys[i] * dt;
    zs[i] += vzs[i] * dt;
}

Gợi ý 3 — Tách riêng measurement:

Dùng cùng pattern warmup + average như starter code. Chạy trên cùng máy, cùng JVM flags, đừng có I/O hay GC pressure trong vòng đo.

✅ Lời giải

import java.util.Random;

public class ParticleSimSoA {

    static final int    N  = 5_000_000;
    static final double DT = 0.016;

    // SoA: moi field la mot mang rieng biet
    static double[] xs, ys, zs;
    static double[] vxs, vys, vzs;
    static double[] masses, charges;

    public static void main(String[] args) {
        xs      = new double[N]; ys  = new double[N]; zs  = new double[N];
        vxs     = new double[N]; vys = new double[N]; vzs = new double[N];
        masses  = new double[N];
        charges = new double[N];

        Random rng = new Random(42);
        for (int i = 0; i < N; i++) {
            xs[i]  = rng.nextDouble(); ys[i]  = rng.nextDouble(); zs[i]  = rng.nextDouble();
            vxs[i] = rng.nextDouble(); vys[i] = rng.nextDouble(); vzs[i] = rng.nextDouble();
            masses[i]  = rng.nextDouble() + 0.1;
            charges[i] = rng.nextDouble() - 0.5;
        }

        // Warmup
        for (int w = 0; w < 3; w++) {
            updatePositions(N, DT);
        }

        // Do thoi gian
        int RUNS = 5;
        long total = 0;
        for (int r = 0; r < RUNS; r++) {
            long start = System.nanoTime();
            updatePositions(N, DT);
            total += System.nanoTime() - start;
        }
        System.out.printf("SoA avg: %.2f ms%n", total / RUNS / 1e6);
    }

    static void updatePositions(int n, double dt) {
        // Cache static array ref vao local -- giup JIT toi uu/vector hoa
        double[] lXs = xs, lYs = ys, lZs = zs;
        double[] lVxs = vxs, lVys = vys, lVzs = vzs;
        for (int i = 0; i < n; i++) {
            lXs[i] += lVxs[i] * dt;
            lYs[i] += lVys[i] * dt;
            lZs[i] += lVzs[i] * dt;
        }
    }
}

Kết quả kỳ vọng

Trên máy x86-64 thông thường (JDK 21, -Xmx4g):

SoA thường nhanh hơn 2–5 lần trong benchmark này. Chênh lệch phụ thuộc vào:

• CPU cache size: máy L3 lớn có thể giảm chênh lệch
• JIT optimization: JVM có thể vector hoá vòng SoA (auto-SIMD) nhưng khó làm vậy với AoS object array
• GC pressure: AoS tạo 5 triệu object → GC có thể chen vào các lần đo nếu không warmup đủ

Với AoS Java object array, còn có thêm chi phí pointer chasing: Particle[] lưu 5 triệu reference (địa chỉ), mỗi reference trỏ tới một Particle object nằm rải rác trên heap. Vòng lặp phải dereference pointer mỗi bước → cache miss kép (miss khi đọc array of refs + miss khi đọc object thật). SoA double[] thì truy cập trực tiếp, không qua tầng gián tiếp.

Đo nghiêm túc hơn với perf

Nếu đang trên Linux, bạn có thể xác nhận bằng hardware counter:

# Do cache miss cua hai chuong trinh (sau khi build thanh JAR)
perf stat -e cache-misses,cache-references java -jar aos.jar
perf stat -e cache-misses,cache-references java -jar soa.jar

Kỳ vọng: SoA có cache-misses / cache-references thấp hơn đáng kể. Đây là bằng chứng trực tiếp từ hardware performance counter thay vì chỉ đo wall time.

Layout bộ nhớ — AoS vs SoA

flowchart TB
  subgraph aos["AoS — Particle[] trong Java heap"]
    direction LR
    R0["ref[0]"] --> P0["Particle<br/>x y z<br/>vx vy vz<br/>mass charge"]
    R1["ref[1]"] --> P1["Particle<br/>x y z<br/>vx vy vz<br/>mass charge"]
    R2["ref[2]"] --> P2["Particle<br/>..."]
  end
  subgraph soa["SoA — double[] arrays lien tuc"]
    direction LR
    XS["xs[]<br/>x0 x1 x2 x3 ..."]
    YS["ys[]<br/>y0 y1 y2 y3 ..."]
    VXS["vxs[]<br/>vx0 vx1 vx2 ..."]
  end
  note1["AoS: pointer chasing + field thua<br/>trong moi cache line"]
  note2["SoA: 1 cache line = 8 gia tri cung field<br/>toan bo dung duoc"]
  aos --- note1
  soa --- note2

🎓 Mở rộng

Khi nào AoS vẫn tốt hơn SoA?

SoA không phải lúc nào cũng thắng. AoS phù hợp hơn khi:

• Vòng lặp dùng hầu hết field của một phần tử: ví dụ render một hạt cần cả position + color + size + rotation cùng lúc → AoS giữ chúng cùng cache line, một lần nạp đủ.
• Thêm/xoá phần tử thường xuyên: AoS chỉ thao tác một chỗ; SoA phải đồng bộ mọi mảng.
• Dữ liệu nhỏ vừa fit cache: khi toàn bộ dataset fit trong L2/L3, chênh lệch không đáng kể.
• Code cần rõ ràng hơn hiệu năng: SoA phá tính đóng gói, dễ lệch chỉ số.

SIMD với SoA

Vòng lặp SoA là ứng viên lý tưởng cho JIT auto-vectorization. JVM có thể biên dịch vòng lặp xs[i] += vxs[i] * dt thành lệnh SIMD (AVX/SSE) xử lý 4–8 double mỗi lệnh. Để kiểm tra JIT có vector hoá không:

java -XX:+PrintCompilation -XX:+UnlockDiagnosticVMOptions \
     -XX:+PrintAssembly -jar soa.jar 2>&1 | grep -i "vmovapd\|vmulpd\|vaddpd"
# vmulpd, vaddpd trong output = JIT da dung AVX packed double

Padding và alignment

Mảng double[] trong Java được căn chỉnh 8 byte — phù hợp với cache line 64 byte (8 phần tử × 8 byte = 64 byte). Bạn không cần thêm padding thủ công như C.

Với SIMD AVX-512, lý tưởng căn 64 byte. Trong Java, JVM xử lý alignment khi cấp phát array — bạn không kiểm soát trực tiếp nhưng thường đủ tốt.

Đo chuẩn với JMH

System.nanoTime() đủ cho demo, nhưng production benchmark nên dùng JMH (Java Microbenchmark Harness):

@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public void updateAoS(AoSState state) {
    // ... vong lap AoS
}

@Benchmark
public void updateSoA(SoAState state) {
    // ... vong lap SoA
}

JMH tự handle warmup, fork, statistical analysis — tránh nhiều pitfall của đo thủ công (dead code elimination, constant folding, GC chen).

✨ Điều bạn vừa làm được

Bạn vừa hoàn thành capstone của khoá Bộ nhớ. Hãy nhìn lại những gì bạn đã kết nối:

• Bố cục bộ nhớ: biết double[] liên tục trong heap, còn Object[] là mảng reference — pointer chasing.
• Cache line 64 byte: hiểu tại sao AoS kéo field thừa và SoA tối đa tỉ lệ dữ liệu hữu ích.
• Spatial locality: SoA biến vòng lặp sequential thành truy cập hoàn toàn liên tục — tối ưu cho prefetcher.
• Đo trước-sau: không đoán; đo thật với warmup JIT và nhiều lần lặp trước khi kết luận.
• Tradeoff thực tế: biết khi nào SoA đáng và khi nào AoS vẫn đúng.

Kỹ năng này — profiling + nhận ra bottleneck bộ nhớ + refactor có căn cứ — là thứ phân biệt engineer hiểu máy tính với người chỉ viết code chạy được.

Bài tiếp theo: Module 4 — Tổng kết & cheat sheet