[[251190]]

引言

public class Main { 
    static long[][] arr; 
 
    public static void main(String[] args) { 
        arr = new long[1024 * 1024][8]; 
        // 橫向遍歷 
        long marked = System.currentTimeMillis(); 
        for (int i = 0; i < 1024 * 1024; i += 1) { 
            for (int j = 0; j < 8; j++) { 
                sum += arr[i][j]; 
            } 
        } 
        System.out.println("Loop times:" + (System.currentTimeMillis() - marked) + "ms"); 
 
        marked = System.currentTimeMillis(); 
        // 縱向遍歷 
        for (int i = 0; i < 8; i += 1) { 
            for (int j = 0; j < 1024 * 1024; j++) { 
                sum += arr[j][i]; 
            } 
        } 
        System.out.println("Loop times:" + (System.currentTimeMillis() - marked) + "ms"); 
    } 
} 

如上述代碼所示，定義了一個二維數組 long[][] arr 并且使用了橫向遍歷和縱向遍歷兩種順序對這個二位數組進行遍歷，遍歷總次數相同，只不過循環的方向不同，代碼中記錄了這兩種遍歷方式的耗時，不妨先賣個關子，他們的耗時會有區別嗎?

這問題問的和中小學試卷中的：“它們之間有區別嗎?如有，請說出區別。”一樣沒有水準，沒區別的話文章到這兒就結束了。事實上，在我的機器上(64 位 mac)多次運行后可以發現：橫向遍歷的耗時大約為 25 ms，縱向遍歷的耗時大約為 60 ms，前者比后者快了 1 倍有余。如果你了解上述現象出現的原因，大概能猜到，今天這篇文章的主角便是他了— CPU Cache&Cache Line。

在學生生涯時，不斷收到這樣建議：《計算機網絡》、《計算機組成原理》、《計算機操作系統》、《數據結構》四門課程是至關重要的，而在我這些年的工作經驗中也不斷地意識到前輩們如此建議的原因。作為一個 Java 程序員，你可以選擇不去理解操作系統，組成原理(相比這二者，網絡和數據結構跟日常工作聯系得相對緊密)，這不會降低你的 KPI，但了解他們可以使你寫出更加計算機友好(Mechanical Sympathy)的代碼。

下面的章節將會出現不少操作系統相關的術語，我將逐個介紹他們，并最終將他們與 Java 聯系在一起。

什么是 CPU 高速緩存?

CPU 是計算機的心臟，最終由它來執行所有運算和程序。主內存(RAM)是數據(包括代碼行)存放的地方。這兩者的定義大家應該不會陌生，那 CPU 高速緩存又是什么呢?

在計算機系統中，CPU高速緩存是用于減少處理器訪問內存所需平均時間的部件。在金字塔式存儲體系中它位于自頂向下的第二層，僅次于CPU寄存器。其容量遠小于內存，但速度卻可以接近處理器的頻率。

當處理器發出內存訪問請求時，會先查看緩存內是否有請求數據。如果存在(***)，則不經訪問內存直接返回該數據;如果不存在(失效)，則要先把內存中的相應數據載入緩存，再將其返回處理器。

緩存之所以有效，主要是因為程序運行時對內存的訪問呈現局部性(Locality)特征。這種局部性既包括空間局部性(Spatial Locality)，也包括時間局部性(Temporal Locality)。有效利用這種局部性，緩存可以達到極高的***率。

在處理器看來，緩存是一個透明部件。因此，程序員通常無法直接干預對緩存的操作。但是，確實可以根據緩存的特點對程序代碼實施特定優化，從而更好地利用緩存。

— 維基百科

CPU 緩存架構

左圖為最簡單的高速緩存的架構，數據的讀取和存儲都經過高速緩存，CPU 核心與高速緩存有一條特殊的快速通道;主存與高速緩存都連在系統總線上(BUS)，這條總線還用于其他組件的通信。簡而言之，CPU 高速緩存就是位于 CPU 操作和主內存之間的一層緩存。

為什么需要有 CPU 高速緩存?

隨著工藝的提升，最近幾十年 CPU 的頻率不斷提升，而受制于制造工藝和成本限制，目前計算機的內存在訪問速度上沒有質的突破。因此，CPU 的處理速度和內存的訪問速度差距越來越大，甚至可以達到上萬倍。這種情況下傳統的 CPU 直連內存的方式顯然就會因為內存訪問的等待，導致計算資源大量閑置，降低 CPU 整體吞吐量。同時又由于內存數據訪問的熱點集中性，在 CPU 和內存之間用較為快速而成本較高(相對于內存)的介質做一層緩存，就顯得性價比極高了。

為什么需要有 CPU 多級緩存?

結合 圖片 -- CPU 緩存架構，再來看一組 CPU 各級緩存存取速度的對比

1. 各種寄存器，用來存儲本地變量和函數參數，訪問一次需要1cycle，耗時小于1ns;
2. L1 Cache，一級緩存，本地 core 的緩存，分成 32K 的數據緩存 L1d 和 32k 指令緩存 L1i，訪問 L1 需要3cycles，耗時大約 1ns;
3. L2 Cache，二級緩存，本地 core 的緩存，被設計為 L1 緩存與共享的 L3 緩存之間的緩沖，大小為 256K，訪問 L2 需要 12cycles，耗時大約 3ns;
4. L3 Cache，三級緩存，在同插槽的所有 core 共享 L3 緩存，分為多個 2M 的段，訪問 L3 需要 38cycles，耗時大約 12ns;

大致可以得出結論，緩存層級越接近于 CPU core，容量越小，速度越快，同時，沒有披露的一點是其造價也更貴。所以為了支撐更多的熱點數據，同時追求***的性價比，多級緩存架構應運而生。

什么是緩存行(Cache Line)?

上面我們介紹了 CPU 多級緩存的概念，而之后的章節我們將嘗試忽略“多級”這個特性，將之合并為 CPU 緩存，這對于我們理解 CPU 緩存的工作原理并無大礙。

緩存行 (Cache Line) 便是 CPU Cache 中的最小單位，CPU Cache 由若干緩存行組成，一個緩存行的大小通常是 64 字節(這取決于 CPU)，并且它有效地引用主內存中的一塊地址。一個 Java 的 long 類型是 8 字節，因此在一個緩存行中可以存 8 個 long 類型的變量。

多級緩存

試想一下你正在遍歷一個長度為 16 的 long 數組 data[16]，原始數據自然存在于主內存中，訪問過程描述如下

• 訪問 data[0]，CPU core 嘗試訪問 CPU Cache，未***。
• 嘗試訪問主內存，操作系統一次訪問的單位是一個 Cache Line 的大小 — 64 字節，這意味著：既從主內存中獲取到了 data[0] 的值，同時將 data[0] ~ data[7] 加入到了 CPU Cache 之中，for free~
• 訪問 data[1]~data[7]，CPU core 嘗試訪問 CPU Cache，***直接返回。
• 訪問 data[8]，CPU core 嘗試訪問 CPU Cache，未***。

• 嘗試訪問主內存。重復步驟 2

CPU 緩存在順序訪問連續內存數據時揮發出了***的優勢。試想一下上一篇文章中提到的 PageCache，其實發生在磁盤 IO 和內存之間的緩存，是不是有異曲同工之妙?只不過今天的主角— CPU Cache，相比 PageCache 更加的微觀。

再回到文章的開頭，為何橫向遍歷 arr = new long[1024 * 1024][8] 要比縱向遍歷更快?此處得到了解答，正是更加友好地利用 CPU Cache 帶來的優勢，甚至有一個專門的詞來修飾這種行為 — Mechanical Sympathy。

偽共享

通常提到緩存行，大多數文章都會提到偽共享問題(正如提到 CAS 便會提到 ABA 問題一般)。

偽共享指的是多個線程同時讀寫同一個緩存行的不同變量時導致的 CPU 緩存失效。盡管這些變量之間沒有任何關系，但由于在主內存中鄰近，存在于同一個緩存行之中，它們的相互覆蓋會導致頻繁的緩存未***，引發性能下降。偽共享問題難以被定位，如果系統設計者不理解 CPU 緩存架構，甚至永遠無法發現 — 原來我的程序還可以更快。

偽共享

正如圖中所述，如果多個線程的變量共享了同一個 CacheLine，任意一方的修改操作都會使得整個 CacheLine 失效(因為 CacheLine 是 CPU 緩存的最小單位)，也就意味著，頻繁的多線程操作，CPU 緩存將會徹底失效，降級為 CPU core 和主內存的直接交互。

偽共享問題的解決方法便是字節填充。

偽共享-字節填充

我們只需要保證不同線程的變量存在于不同的 CacheLine 即可，使用多余的字節來填充可以做點這一點，這樣就不會出現偽共享問題。在代碼層面如何實現圖中的字節填充呢?

Java6 中實現字節填充

public class PaddingObject{ 
    public volatile long value = 0L;    // 實際數據 
    public long p1, p2, p3, p4, p5, p6; // 填充 
} 
PaddingOb 

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 = 0L;    // 實際數據 
} 

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

如果你對這個現象感興趣，測試代碼如下：

public final class FalseSharing implements Runnable { 
    public final static int NUM_THREADS = 4; // change 
    public final static long ITERATIONS = 500L * 1000L * 1000L; 
    private final int arrayIndex; 
 
    private static VolatileLong[] longs = new VolatileLong[NUM_THREADS]; 
 
    static { 
        for (int i = 0; i < longs.length; i++) { 
            longs[i] = new VolatileLong(); 
        } 
    } 
 
    public FalseSharing(final int arrayIndex) { 
        this.arrayIndex = arrayIndex; 
    } 
 
    public static void main(final String[] args) throws Exception { 
        final long start = System.currentTimeMillis(); 
        runTest(); 
        System.out.println("duration = " + (System.currentTimeMillis() - start)); 
    } 
 
    private static void runTest() throws InterruptedException { 
        Thread[] threads = new Thread[NUM_THREADS]; 
 
        for (int i = 0; i < threads.length; i++) { 
            threads[i] = new Thread(new FalseSharing(i)); 
        } 
        for (Thread t : threads) { 
            t.start(); 
        } 
        for (Thread t : threads) { 
            t.join(); 
        } 
    } 
 
    public void run() { 
        long i = ITERATIONS + 1; 
        while (0 != --i) { 
            longs[arrayIndex].value = i; 
        } 
    } 
 
    public final static class VolatileLong { 
        public volatile long value = 0L; 
        public long p1, p2, p3, p4, p5, p6; // 填充，可以注釋后對比測試 
    } 
 
 
} 

Java8 中實現字節填充

@Retention(RetentionPolicy.RUNTIME) 
@Target({ElementType.FIELD, ElementType.TYPE}) 
public @interface Contended { 
    String value() default ""; 
} 

Java8 中終于提供了字節填充的官方實現，這無疑使得 CPU Cache 更加可控了，無需擔心 jdk 的無效字段優化，無需擔心 Cache Line 在不同 CPU 下的大小究竟是不是 64 字節。使用 @Contended 注解可以***的避免偽共享問題。

一些***實踐

可能有讀者會問：作為一個普通開發者，需要關心 CPU Cache 和 Cache Line 這些知識點嗎?這就跟前幾天比較火的話題：「程序員有必要懂 JVM 嗎?」一樣，仁者見仁了。但確實有不少優秀的源碼在關注著這些問題。他們包括：

ConcurrentHashMap

面試中問到要吐的 ConcurrentHashMap 中，使用 @sun.misc.Contended 對靜態內部類 CounterCell 進行修飾。另外還包括并發容器 Exchanger 也有相同的操作。

/* ---------------- 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{} 

使用字節填充和繼承的方式來避免偽共享。