CPU Cache與緩存行

引言

先看下面這兩個循環周遊哪個快？

int[][] array = new int[ * ][];

// 橫向周遊
for(int i = ; i <  * ; i ++)
    for(int j = ; j < ; j ++)
        array[i][j] ++;

// 縱向周遊
for(int i = ; i < ; i ++)
    for(int j = ; j <  * ; j ++)
        array[j][i] ++;
           

在CPU處理器參數為 2.3 GHz Intel Core i5 的Mac上的結果是：

橫向周遊: 80ms

縱向周遊: 2139ms

橫向周遊的 CPU cache 命中率高，是以它比縱向周遊約快這麼多倍！

Gallery of Processor Cache Effects 用 7 個源碼示例生動的介紹 cache 原理，深入淺出！但是可能因作業系統的差異、編譯器是否優化，以及近些年 cache 性能的提升，有些樣例在 Mac 的效果與原文相差較大。

CPU Cache

CPU 通路記憶體時，首先查詢 cache 是否已緩存該資料。如果有，則傳回資料，無需通路記憶體；如果不存在，則需把資料從記憶體中載入 cache，最後傳回給理器。在處理器看來，緩存是一個透明部件，旨在提高處理器通路記憶體的速率，是以從邏輯的角度而言，程式設計時無需關注它，但是從性能的角度而言，了解其原理和機制有助于寫出性能更好的程式。Cache 之是以有效，是因為程式對記憶體的通路存在一種機率上的局部特征：

• Spatial Locality：對于剛被通路的資料，其相鄰的資料在将來被通路的機率高。
• Temporal Locality：對于剛被通路的資料，其本身在将來被通路的機率高。

比 mac OS 為例，可用 指令

sysctl -a

查詢 cache 資訊，機關是位元組Byte。

$ sysctl -a

hw.cachelinesize: 
hw.l1icachesize: 
hw.l1dcachesize: 
hw.l2cachesize: 
hw.l3cachesize: 
machdep.cpu.cache.L2_associativity: 
machdep.cpu.core_count: 
machdep.cpu.thread_count: 
machdep.cpu.tlb.inst.large: 
machdep.cpu.tlb.data.small: 
machdep.cpu.tlb.data.small_level1: 
           

• CacheLine size：64 Byte
• L1 Data Cache：32KB
• L1 Instruction Cache：32KB
• L2 Cache：256KB
• L3 Cache：4MB

Mac下也可以點選坐上角關于本機 -> 概覽 -> 系統報告來檢視硬體資訊：

下圖是計算機存儲的基本結構。L1、L2、L3分别表示一級緩存、二級緩存、三級緩存。越靠近CPU的緩存，速度越快，容量也越小。L1緩存小但很快，并且緊靠着在使用它的CPU核心。分為指令緩存和資料緩存；L2大一些，也慢一些，并仍然隻能被一個單獨的CPU核使用；L3更大、更慢，并且被單個插槽上的所有CPU核共享；最後是主存，由全部插槽上的所有CPU核共享。

當CPU執行運算的時候，它先去L1查找所需的資料、再去L2、然後是L3，如果最後這些緩存中都沒有，所需的資料就要去主記憶體拿。走得越遠，運算耗費的時間就越長。是以要盡量確定資料在L1緩存中。

Martin和Mike的 QCon presentation 演講中給出了一些緩存未命中的消耗資料，也就是從CPU通路不同層級資料的時間概念:

從CPU到	大約需要的CPU時鐘周期	大約需要的時間
主存	約60-80ns
QPI 總線傳輸(between sockets, not drawn)	約20ns
L3 cache	約40-45 cycles	約15ns
L2 cache	約10 cycles	約3ns
L1 cache	約3-4 cycles	約1ns
寄存器	1 cycle

可見CPU讀取主存中的資料會比從L1中讀取慢了近2個數量級。

我們在每隔 64 Byte (cache line size) 通路 array 一次，通路固定次數。随着array的增大，看看能不能測試出 L1, L2 和 L3 cache size 的大小：

/**
 * 每隔64Byte通路數組固定次數，看Array大小對耗時的影響
 */
public class Test {

    public static void main(String[] args) {
        for (int ARRAY_SIZE = ; ARRAY_SIZE <=  *  * ; ARRAY_SIZE <<= ) {

            int steps =  *  * ; // Arbitrary number of steps
            int length_mod = ARRAY_SIZE - ;
            char[] arr = new char[ARRAY_SIZE];

            marked = System.currentTimeMillis();
            for (int i = ; i < steps; i += ) {
                arr[i & length_mod]++; // (i & length_mod) is equal to (i % length_mod)
            }
            long used = (System.currentTimeMillis() - marked);
            System.out.println(formatSize(ARRAY_SIZE) + "\t" + used);
        }
    }

    /**
     * 把size機關轉化為KB, MB, GB
     */
    public static String formatSize(long size) {
        String hrSize = null;

        double b = size;
        double k = size/;
        double m = ((size/)/);
        double g = (((size/)/)/);
        double t = ((((size/)/)/)/);

        DecimalFormat dec = new DecimalFormat("0");

        if ( t> ) {
            hrSize = dec.format(t).concat(" TB");
        } else if ( g> ) {
            hrSize = dec.format(g).concat(" GB");
        } else if ( m> ) {
            hrSize = dec.format(m).concat(" MB");
        } else if ( k> ) {
            hrSize = dec.format(k).concat(" KB");
        } else {
            hrSize = dec.format(b).concat(" Bytes");
        }
        return hrSize;
    }
}
           

運作的結果如下：

可以看到32KB，256KB，4MB之後耗時均有明顯上升。

緩存行Cache Line

Cache是由很多個 Cache line 組成的。Cache line 是 cache 和 RAM 交換資料的最小機關，通常為 64 Byte。當 CPU 把記憶體的資料載入 cache 時，會把臨近的共 64 Byte 的資料一同放入同一個Cache line，因為空間局部性：臨近的資料在将來被通路的可能性大。

以大小為 32 KB，cache line 的大小為 64 Byte 的L1級緩存為例，對于不同存放規則，其硬體設計也不同，下圖簡單表示一種設計：

僞共享False Sharing

當多線程修改互相獨立的變量時，如果這些變量共享同一個緩存行，就會無意中影響彼此的性能，這就是僞共享。緩存行上的寫競争是運作在SMP系統中并行線程實作可伸縮性最重要的限制因素。有人将僞共享描述成無聲的性能殺手，因為從代碼中很難看清楚是否會出現僞共享。

下面我們通過一段代碼，看看僞共享對性能的影響。

public final class FalseSharingNo implements Runnable {

    public final static long ITERATIONS = L * L * L;
    private int arrayIndex = ;

    private static ValuePadding[] longs;
    public FalseSharingNo(final int arrayIndex) {
        this.arrayIndex = arrayIndex;
    }

    public static void main(final String[] args) throws Exception {
        for(int i = ; i < ; i++){
            System.gc();
            final long start = System.currentTimeMillis();
            runTest(i);
            System.out.println(i + " Threads, duration = " + (System.currentTimeMillis() - start));
        }

    }

    private static void runTest(int NUM_THREADS) throws InterruptedException {
        Thread[] threads = new Thread[NUM_THREADS];
        longs = new ValuePadding[NUM_THREADS];
        for (int i = ; i < longs.length; i++) {
            longs[i] = new ValuePadding();
        }
        for (int i = ; i < threads.length; i++) {
            threads[i] = new Thread(new FalseSharingNo(i));
        }

        for (Thread t : threads) {
            t.start();
        }

        for (Thread t : threads) {
            t.join();
        }
    }

    public void run() {
        long i = ITERATIONS + ;
        while ( != --i) {
            longs[arrayIndex].value = L;
        }
    }

    public final static class ValuePadding {
        protected long p1, p2, p3, p4, p5, p6, p7;
        protected volatile long value = L;
        protected long p9, p10, p11, p12, p13, p14;
        protected long p15;
    }
    public final static class ValueNoPadding {
        // protected long p1, p2, p3, p4, p5, p6, p7;
        protected volatile long value = L;
        // protected long p9, p10, p11, p12, p13, p14, p15;
    }

}
           

在分别使用 ValuePadding 和 ValueNoPadding 兩種對象，讓多線程分别通路數組中相鄰的對象，試圖建構一個僞共享的場景。在有Padding填充的情況下，看看運作結果：

1 Threads, duration = 398

2 Threads, duration = 645

3 Threads, duration = 537

4 Threads, duration = 638

5 Threads, duration = 786

6 Threads, duration = 954

7 Threads, duration = 1133

8 Threads, duration = 1286

9 Threads, duration = 1432

把代碼中 ValuePadding 都替換為 ValueNoPadding 後的結果：

1 Threads, duration = 404

2 Threads, duration = 1250

3 Threads, duration = 1283

4 Threads, duration = 1179

5 Threads, duration = 2510

6 Threads, duration = 2733

7 Threads, duration = 2451

8 Threads, duration = 2652

9 Threads, duration = 2189

Cache Line僞共享解決方案

處理僞共享的兩種方式：

1. 位元組填充：增大元素的間隔，使得不同線程存取的元素位于不同的cache line上，典型的空間換時間。
2. 在每個線程中建立對應元素的本地拷貝，結束後再寫回全局數組。

我們這裡隻看第一種位元組填充。保證不同線程的變量存在于不同的 CacheLine 即可，這樣就不會出現僞共享問題。在代碼層面如何實作圖中的位元組填充呢？

Java6 中實作位元組填充

public class PaddingObject{
    public volatile long value = L;    // 實際資料
    public long p1, p2, p3, p4, p5, p6; // 填充
}
           

PaddingObject 類中需要儲存一個 long 類型的 value 值，如果多線程操作同一個 CacheLine 中的 PaddingObject 對象，便無法完全發揮出 CPU Cache 的優勢（想象一下你定義了一個 PaddingObject[] 數組，數組元素在記憶體中連續，卻由于僞共享導緻無法使用 CPU Cache 帶來的沮喪）。

不知道你注意到沒有，實際資料 value + 用于填充的 p1~p6 總共隻占據了 7 * 8 = 56 個位元組，而 Cache Line 的大小應當是 64 位元組，這是有意而為之，在 Java 中，對象頭還占據了 8 個位元組，是以一個 PaddingObject 對象可以恰好占據一個 Cache Line。

Java7 中實作位元組填充

在 Java7 之後，一個 JVM 的優化給位元組填充造成了一些影響，上面的代碼片段

public long p1, p2, p3, p4, p5, p6;

會被認為是無效代碼被優化掉，有回歸到了僞共享的窘境之中。

為了避免 JVM 的自動優化，需要使用繼承的方式來填充。

abstract class AbstractPaddingObject{
    protected long p1, p2, p3, p4, p5, p6;// 填充
}

public class PaddingObject extends AbstractPaddingObject{
    public volatile long value = L;    // 實際資料
}
           

Tips:實際上我在本地 mac 下測試過 jdk1.8 下的位元組填充，并不會出現無效代碼的優化，個人猜測和 jdk 版本有關，不過為了保險起見，還是使用相對穩妥的方式去填充較為合适。

Java8 中實作位元組填充

//JDK 8中提供的注解
@Retention(RetentionPolicy.RUNTIME)
@Target({ElementType.FIELD, ElementType.TYPE})
public @interface Contended {

    /**
     * The (optional) contention group tag.
     * This tag is only meaningful for field level annotations.
     *
     * @return contention group tag.
     */
    String value() default "";
}
           

在 JDK 8 裡提供了一個新注解

@Contended

，可以用來減少false sharing的情況。JVM在計算對象布局的時候就會自動把标注的字段拿出來并且插入合适的大小padding。

因為這個功能暫時還是實驗性功能，暫時還沒到預設普及給使用者代碼用的程度。要在使用者代碼（非bootstrap class loader或extension class loader所加載的類）中使用@Contended注解的話，需要使用 -XX:-RestrictContended 參數。

比如在JDK 8的 ConcurrentHashMap 源碼中，使用

@sun.misc.Contended

對靜态内部類 CounterCell 進行了修飾。

/* ---------------- Counter support -------------- */

/**
 * A padded cell for distributing counts.  Adapted from LongAdder
 * and Striped64.  See their internal docs for explanation.
 */
@sun.misc.Contended 
static final class CounterCell {
        volatile long value;
        CounterCell(long x) { value = x; }
}
           

Thread

Thread 線程類的源碼中，使用 @sun.misc.Contended 對成員變量進行修飾。

// The following three initially uninitialized fields are exclusively
// managed by class java.util.concurrent.ThreadLocalRandom. These
// fields are used to build the high-performance PRNGs in the
// concurrent code, and we can not risk accidental false sharing.
// Hence, the fields are isolated with @Contended.

/** The current seed for a ThreadLocalRandom */
@sun.misc.Contended("tlr")
long threadLocalRandomSeed;

/** Probe hash value; nonzero if threadLocalRandomSeed initialized */
@sun.misc.Contended("tlr")
int threadLocalRandomProbe;

/** Secondary seed isolated from public ThreadLocalRandom sequence */
@sun.misc.Contended("tlr")
int threadLocalRandomSecondarySeed;
           

RingBuffer

來源于一款優秀的開源架構 Disruptor 中的一個資料結構 RingBuffer。

abstract class RingBufferPad {
    protected long p1, p2, p3, p4, p5, p6, p7;
}

abstract class RingBufferFields<E> extends RingBufferPad{}
           

使用位元組填充和繼承的方式來避免僞共享。

面試題擴充

問：說說數組和連結清單這兩種資料結構有什麼差別？

問：快速排序和堆排序兩種排序算法各自的優缺點是什麼？

了解了 CPU Cache 和 Cache Line 之後想想可不可以有一些特殊的回答技巧呢？

參考資料

• 7個示例科普CPU CACHE：Gallery of Processor Cache Effects
• 了解 CPU Cache
• 高性能隊列——Disruptor — 美團點評技術團隊
• JAVA 拾遺 — CPU Cache 與緩存行
• 寫Java也得了解CPU–CPU緩存
• 關于CPU Cache – 程式猿需要知道的那些事
• Java專家系列：CPU Cache與高性能程式設計