CPU Cache

Trong lập trình đồng thời, chúng ta thường tập trung vào cách kiểm soát truy cập biến chia sẻ (ở cấp độ mã), nhưng ít người chú ý đến các yếu tố ảnh hưởng từ phần cứng hệ thống và JVM;

Tương tự như trình duyệt web lưu cache dữ liệu đã xem để tăng tốc độ, hoặc cơ sở dữ liệu truyền thống/NoSQL sử dụng bộ nhớ cache để giảm IO đĩa (chậm), CPU cũng có cache để bù đắp tốc độ truy cập bộ nhớ chậm hơn.

Vì tốc độ CPU tăng nhanh hơn tốc độ bộ nhớ, giữa CPU và bộ nhớ đã đưa ra các cấp cache:

• Cache L1: Gần CPU nhất, dung lượng nhỏ (ví dụ 32KB), tốc độ nhanh nhất. Mỗi nhân CPU có một L1 Cache (thực chất mỗi nhân có hai L1 Cache: một cho dữ liệu L1d Cache, một cho chỉ thị L1i Cache).
• Cache L2: Dung lượng lớn hơn (ví dụ 256KB), tốc độ chậm hơn. Thường mỗi nhân có một L2 Cache riêng.
• Cache L3: Dung lượng lớn nhất (ví dụ 12MB), tốc độ chậm nhất, được chia sẻ giữa các nhân trong cùng một socket CPU.

Thứ tự tốc độ: Đăng ký > L1 Cache > L2 Cache > L3 Cache > Bộ nhớ chính

CPU Cache được định nghĩa là:

Bộ nhớ đệm CPU (Cache Memory) là bộ nhớ tạm thời nằm giữa CPU và RAM, dung lượng nhỏ hơn RAM rất nhiều nhưng tốc độ trao đổi nhanh hơn RAM rất nhiều. Bộ nhớ cache xuất hiện chủ yếu để giải quyết mâu thuẫn giữa tốc độ xử lý của CPU và tốc độ đọc/ghi của RAM, vì tốc độ xử lý của CPU nhanh hơn tốc độ đọc/ghi RAM rất nhiều, điều này sẽ khiến CPU phải chờ đợi dữ liệu đến hoặc ghi dữ liệu vào RAM.

Hệ thống cache lưu dữ liệu theo đơn vị là cache line (dòng cache). Hiệu suất chương trình phụ thuộc rất nhiều vào cách sử dụng cache line này.

Cache Line

Cache được tạo thành từ các cache line. Một cache line thường có 64 byte. Điều này có nghĩa là CPU không truy cập từng byte riêng lẻ mà theo từng cache line.

Nếu không tận dụng tốt cache line, chương trình có thể gặp vấn đề về hiệu suất:

public class CacheMissDemo {
    private static final int RUNS = 10;
    private static final int ROWS = 1024 * 1024;
    private static final int COLS = 62;
    private static long[][] data;

    public static void main(String[] args) throws Exception {
        data = new long[ROWS][];
        for (int i = 0; i < ROWS; i++) {
            data[i] = new long[COLS];
            for (int j = 0; j < COLS; j++) {
                data[i][j] = 0L;
            }
        }
        System.out.println("Bắt đầu chạy...");

        final long start = System.currentTimeMillis();
        long sum = 0L;
        for (int r = 0; r < RUNS; r++) {
            // Cách 1 - chậm
//            for (int j = 0; j < COLS; j++) {
//                for (int i = 0; i < ROWS; i++) {
//                    sum += data[i][j];
//                }
//            }
            
            // Cách 2 - nhanh
            for (int i = 0; i < ROWS; i++) {
                for (int j = 0; j < COLS; j++) {
                    sum += data[i][j];
                }
            }
        }
        System.out.println("Thời gian thực thi = " + (System.currentTimeMillis() - start));
    }
}

Cách 2 nhanh hơn đáng kể so với cách 1, dù mã nguồn gần như giống nhau. Đây là sự khác biệt khi tận dụng tốt cache line.

Trên hệ thống 64-bit, header của mảng Java chiếm 16 byte, trong khi long chiếm 8 byte. Vậy 16 + 8*6 = 64 byte, đúng bằng kích thước một cache line (một cache line chứa được 6 long).

Lý do cách 2 nhanh:

Khi chạy vòng lặp bên trong, dữ liệu lấy từ bộ nhớ thực chất bao phủ toàn bộ data[i][0] đến data[i][5] (đúng 64 byte). Do đó, tất cả dữ liệu đều nằm trong L1 cache, việc duyệt sẽ rất nhanh.

Lý do cách 1 chậm:

Khi chạy, mỗi lần lấy dữ liệu từ bộ nhớ là cùng hàng khác cột (như data[i][0] đến data[i][5]), nhưng mục tiêu tiếp theo của vòng lặp lại là cùng cột khác hàng (như data[0][0] tiếp theo là data[1][0]), khiến data[0][1]-data[0][5] không thể tái sử dụng.

False Sharing

False sharing (chia sẻ giả) được định nghĩa không chính thức là: Trong hệ thống cache, dữ liệu được lưu theo đơn vị cache line. Khi nhiều thread cập nhật các biến độc lập với nhau nhưng các biến này lại nằm cùng một cache line, chúng sẽ vô ảnh hưởng đến hiệu suất lẫn nhau. Đây chính là false sharing.

Nhiều người cho rằng false sharing là "kẻ giết hiệu suất thầm lặng" trong lập trình đồng thời, vì rất khó nhận biết từ mã nguồn.

Sơ đồ minh họa false sharing:

Hình trên minh họa vấn đề false sharing. Thread chạy trên nhân 1 muốn cập nhật biến X, đồng thời thread trên nhân 2 muốn cập nhật biến Y. Rất tiếc, cả hai biến này nằm trong cùng một cache line. Mỗi thread phải cạnh tranh quyền sở hữu cache line để cập nhật biến. Nếu nhân 1 giành được quyền sở hữu, hệ thống cache sẽ làm cho cache line tương ứng trên nhân 2 trở nên không hợp lệ. Khi nhân 2 giành được quyền sở hữu và thực hiện cập nhật, nhân 1 lại phải làm cho cache line tương ứng của mình trở nên không hợp lệ. Quá trình này lặp đi lặp lại qua L3 cache, ảnh hưởng lớn đến hiệu suất. Nếu các nhân cạnh tranh nằm ở các socket khác nhau, vấn đề có thể còn nghiêm trọng hơn.

Giải pháp False Sharing

Trong thiết kế lớp Java, cần tối ưu hóa bằng cách xác định rõ:

• Biến nào không thay đổi
• Biến nào thay đổi thường xuyên
• Biến nào thay đổi hoàn toàn độc lập
• Thuộc tính nào thường thay đổi cùng nhau

Ví dụ:

public class DataRecord{
    long modifyTime; // Thời gian sửa giá trị
    boolean flag; // Dấu hiệu
    long createTime; // Thời gian tạo
    char key; // Tồn tại ngay từ lần tạo đầu tiên
    int value;
}

Giả sử lớp trên có đặc điểm:

1. Khi biến value thay đổi, modifyTime chắc chắn thay đổi
2. Biến createTime và key sau khi tạo sẽ không thay đổi
3. Biến flag cũng thay đổi thường xuyên, nhưng không liên quan đến modifyTime và value

Giải pháp trước JDK 1.8 - Padding

Trước JDK 1.8, chúng ta thường thêm biến long để phân cách các thuộc tính:

public class DataPadding{
    long p1, p2, p3, p4, p5, p6, p7, p8; // Ngăn chia sẻ với đối tượng trước
    int value;
    long modifyTime;
    long p9, p10, p11, p12, p13, p14, p15, p16; // Ngăn chia sẻ biến không liên quan
    boolean flag;
    long p17, p18, p19, p20, p21, p22, p23, p24;
    long createTime;
    char key;
    long p25, p26, p27, p28, p29, p30, p31, p32; // Ngăn chia sẻ với đối tượng sau
}

Giải pháp từ JDK 1.8 - Sử dụng @Contended

Từ JDK 1.8, Java thêm annotation @sun.misc.Contended để tách các biến vào các cache line riêng biệt:

Lưu ý: JVM cần thêm tham số -XX:-RestrictContended để kích hoạt tính năng này. Có thể sử dụng annotation trên lớp hoặc thuộc tính:

// Áp dụng cho cả lớp - mỗi biến sẽ ở cache line riêng
@sun.misc.Contended
@SuppressWarnings("restriction")
public class ContendedData {
    int value;
    long modifyTime;
    boolean flag;
    long createTime;
    char key;
}

// Hoặc áp dụng theo nhóm
@SuppressWarnings("restriction")
public class ContendedGroupData {
    @sun.misc.Contended("group1")
    int value;
    @sun.misc.Contended("group1")
    long modifyTime;
    @sun.misc.Contended("group2")
    boolean flag;
    @sun.misc.Contended("group3")
    long createTime;
    @sun.misc.Contended("group3")
    char key;
}