轉(zhuǎn)自 CPU Cache與緩存行
引言
先看看下面這個(gè)循環(huán)遍歷哪個(gè)更快
int[][] array = new int[64 * 1024][1024];
// 橫向遍歷
long marked = System.currentTimeMillis();
for (int i = 0; i < 64 * 1024; i++) {
for (int j = 0; j < 1024; j++) {
array[i][j]++;
}
}
System.out.println("橫向遍歷 times:" + (System.currentTimeMillis() - marked) + "ms");
marked = System.currentTimeMillis();
// 縱向遍歷
for (int i = 0; i < 1024; i++) {
for (int j = 0; j < 64 * 1024; j++) {
array[j][i]++;
}
}
System.out.println("縱向遍歷 times:" + (System.currentTimeMillis() - marked) + "ms");
在 CPU處理器參數(shù)為 2.8 GHz Intel Core i7 的Mac上運(yùn)行的結(jié)果是
橫向遍歷 times:64ms
縱向遍歷 times:1689ms
Gallery of Processor Cache Effects 用7個(gè)源碼示例生動(dòng)的介紹 cache 原理织盼，深入淺出！但是可能因操作系統(tǒng)的差異、編譯器是否優(yōu)化火诸，以及近些年 cache 性能的提升，有些樣例在 Mac 的效果與原文相差較大荠察。
CPU Cache
CPU 訪問(wèn)內(nèi)存時(shí)置蜀，首先查詢(xún) cache 是否已緩存該數(shù)據(jù)。如果有悉盆，則返回?cái)?shù)據(jù)盯荤，無(wú)需訪問(wèn)內(nèi)存；如果不存在焕盟，則需把數(shù)據(jù)從內(nèi)存中載入 cache秋秤，最后返回給理器。在處理器看來(lái)脚翘，緩存是一個(gè)透明部件灼卢，旨在提高處理器訪問(wèn)內(nèi)存的速率，所以從邏輯的角度而言来农，編程時(shí)無(wú)需關(guān)注它鞋真，但是從性能的角度而言，理解其原理和機(jī)制有助于寫(xiě)出性能更好的程序沃于。Cache 之所以有效涩咖，是因?yàn)槌绦驅(qū)?nèi)存的訪問(wèn)存在一種概率上的局部特征：
- Spatial Locality： 對(duì)于剛被訪問(wèn)的數(shù)據(jù)海诲，其相鄰的數(shù)據(jù)在將來(lái)被訪問(wèn)的概率高。
- Temporal Locality： 對(duì)于剛被訪問(wèn)的數(shù)據(jù)檩互，其本身在將來(lái)被訪問(wèn)的概率高特幔。
以Mac OS 為例，可以使用命令 ysctl -a | grep hw 查詢(xún) cache 信息盾似，單位是字節(jié) Byte敬辣。
ysctl -a | grep hw
hw.cachelinesize: 64
hw.l1icachesize: 32768 一級(jí)指令緩存
hw.l1dcachesize: 32768 一級(jí)數(shù)據(jù)緩存
hw.l2cachesize: 262144
hw.l3cachesize: 6291456
- CacheLine size : 64 Byte
- L1 Data Cache：32 KB
- L1 Instruction Cache：32 KB
- L2 Cache：256KB
- L3 Cache：6MB
下圖是計(jì)算機(jī)存儲(chǔ)的基本結(jié)構(gòu)。L1零院，L2，L3分別表示一級(jí)緩存村刨、二級(jí)緩存告抄、三級(jí)緩存。越靠近CPU的緩存嵌牺，速度越快打洼，容量也越小。L1緩存小但很快逆粹，并且緊靠著在使用它的CPU內(nèi)核募疮。分為指令緩存和數(shù)據(jù)緩存；L2大一些僻弹，也慢一些阿浓，并仍然只能被一個(gè)單獨(dú)的CPU核所使用；L3更大蹋绽、更慢芭毙，并且被單個(gè)插槽上所有的CPU核共享；最后是主存卸耘，由全部插槽上的所有CPU核共享退敦。
當(dāng)CPU執(zhí)行運(yùn)算的時(shí)候，它先去L1查找所需要的數(shù)據(jù)蚣抗、再去L2侈百、然后是L3，如果最后這些緩存中都沒(méi)有翰铡，所需的數(shù)據(jù)就要去主內(nèi)存拿钝域。走的越遠(yuǎn)，運(yùn)算耗費(fèi)的時(shí)間就越長(zhǎng)两蟀。所以要盡量確保數(shù)據(jù)在L1緩存中网梢。
Martin和Mike的 QCon presentation 演講中給出了一些緩存未命中的消耗數(shù)據(jù)，也就是從CPU訪問(wèn)不同層級(jí)數(shù)據(jù)的時(shí)間概念:
| 從CPU到 | 大約需要的CPU時(shí)鐘周期 | 大約需要的時(shí)間 |
|---|---|---|
| 主存 | 約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讀取主存中的數(shù)據(jù)會(huì)比從L1中讀取慢了將近2個(gè)數(shù)量級(jí)赂毯。
我們?cè)诿扛?64 Byte (cache line size) 訪問(wèn)一次战虏，訪問(wèn)固定次數(shù)拣宰。隨著array的增大，看看能不能測(cè)試出 L1烦感，L2 和 L3 cache size的大醒采纭：
public static void main(String[] args) {
for (int ARRAY_SIZE = 512; ARRAY_SIZE < 128 * 1024 * 1024; ARRAY_SIZE = ARRAY_SIZE << 1) {
int steps = 640 * 1024 * 1024; // Arbitrary number of steps
int length_mod = ARRAY_SIZE - 1;
char[] arr = new char[ARRAY_SIZE];
long marked = System.currentTimeMillis();
for (int i = 0; i < steps; i += 64) {
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單位轉(zhuǎn)化為KB, MB, GB
*/
public static String formatSize(long size) {
String hrSize = null;
double b = size;
double k = size / 1024.0;
double m = ((size / 1024.0) / 1024.0);
double g = (((size / 1024.0) / 1024.0) / 1024.0);
double t = ((((size / 1024.0) / 1024.0) / 1024.0) / 1024.0);
DecimalFormat dec = new DecimalFormat("0");
if (t > 1) {
hrSize = dec.format(t).concat(" TB");
} else if (g > 1) {
hrSize = dec.format(g).concat(" GB");
} else if (m > 1) {
hrSize = dec.format(m).concat(" MB");
} else if (k > 1) {
hrSize = dec.format(k).concat(" KB");
} else {
hrSize = dec.format(b).concat(" Bytes");
}
return hrSize;
}
運(yùn)行結(jié)果如下：
可以看到32KB，256KB手趣，4MB之后耗時(shí)均有明顯上升晌该。
緩存行Cache Line
Cache是由很多個(gè) Cache line 組成的。Cache line 是 chche 和 RAM交換的最小單位绿渣，通常是 64 Byte朝群。當(dāng)CPU 把內(nèi)存的數(shù)據(jù)載入 cache時(shí)，會(huì)把臨近的 64 Byte 的數(shù)據(jù)一同放入同一個(gè) Cache line 中符，因?yàn)榭臻g局部性姜胖；臨近的數(shù)據(jù)在將來(lái)被訪問(wèn)的可能性最大。
以大小為 32 KB 淀散，cache line 的大小為 64 Byte 的L1級(jí)緩存為例右莱，對(duì)于不同存放規(guī)則，其硬件圖簡(jiǎn)單表示一種設(shè)計(jì)：
偽共享False Sharing
當(dāng)多線程修改互相獨(dú)立的變量時(shí)档插，如果這些變量共享同一個(gè)緩存行慢蜓，就會(huì)無(wú)意中影響彼此的性能，這就是偽共享郭膛。緩存行上的寫(xiě)競(jìng)爭(zhēng)是運(yùn)行在SMP系統(tǒng)中并行線程實(shí)現(xiàn)可伸縮性最重要的因素晨抡。有人將偽共享描述成無(wú)聲的性能殺手。
下面通過(guò)一段代碼饲鄙，看看偽共享對(duì)性能的影響凄诞。
/**
* 偽共享
*/
public class FalseSharingNo implements Runnable {
public final static long ITERATIONS = 500L * 1000L * 100L;
private int arrayIndex = 0;
private static ValuePadding[] longs;
public FalseSharingNo(final int arrayIndex) {
this.arrayIndex = arrayIndex;
}
public static void main(final String[] args) throws Exception {
for (int i = 1; i < 10; 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 = 0; i < longs.length; i++) {
longs[i] = new ValuePadding();
}
for (int i = 0; i < threads.length; i++) {
threads[i] = new Thread(new FalseSharingNo(i));
}
for (Thread t : threads) {
t.start();
}
for (Thread t : threads) {
t.join();
}
}
@Override
public void run() {
long i = ITERATIONS + 1;
while (0 != --i) {
longs[arrayIndex].value = 0L;
}
}
public final static class ValuePadding {
protected long p1, p2, p3, p4, p5, p6, p7;
protected volatile long value = 0L;
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 = 0L;
// protected long p9, p10, p11, p12, p13, p14, p15;
}
}
在分別使用 ValuePadding 和 ValueNoPadding 兩種對(duì)象，讓多線程分別訪問(wèn)數(shù)組中相鄰的對(duì)象忍级，試圖構(gòu)建一個(gè)偽共享的場(chǎng)景帆谍。在有Padding填充的情況下，看看運(yùn)行結(jié)果：
1 Threads, duration = 390
2 Threads, duration = 402
3 Threads, duration = 418
4 Threads, duration = 442
5 Threads, duration = 467
6 Threads, duration = 537
7 Threads, duration = 591
8 Threads, duration = 648
9 Threads, duration = 730
把代碼中 ValuePadding 都替換為 ValueNoPadding 后的結(jié)果：
1 Threads, duration = 390
2 Threads, duration = 2016
3 Threads, duration = 2325
4 Threads, duration = 2644
5 Threads, duration = 3621
6 Threads, duration = 3805
7 Threads, duration = 3532
8 Threads, duration = 3612
9 Threads, duration = 2944
Cache Line 偽共享解決方案
處理偽共享的兩種方式：
- 1轴咱、字節(jié)填充：增大元素的間隔汛蝙，使得不同線程存取的元素在不同的 cache line 上，典型的空間換時(shí)間朴肺。
- 2窖剑、在每個(gè)線程中創(chuàng)建對(duì)應(yīng)元素的本地拷貝，結(jié)束后再寫(xiě)回全局?jǐn)?shù)組
我們這里只看第一種字節(jié)填充戈稿。保證不同線程的變量存在于不同的 Cache line 即可西土，這樣就不會(huì)出現(xiàn)偽貢獻(xiàn)問(wèn)題。在代碼層面如何實(shí)現(xiàn)圖中的字節(jié)填充呢鞍盗？
Java6 中實(shí)現(xiàn)字節(jié)填充
public class PaddingObject{
public volatile long value = 0L; // 實(shí)際數(shù)據(jù)
public long p1, p2, p3, p4, p5, p6; // 填充
}
PaddingObject 類(lèi)中需要保存一個(gè)long類(lèi)型的value值需了，如果多線程操作同一個(gè)CacheLine中的PaddingObject對(duì)象跳昼，便無(wú)法發(fā)揮出 CPU Cache的優(yōu)勢(shì)(想象一下你定義了一個(gè) PaddingObject[] 數(shù)組，數(shù)組元素在內(nèi)存中連續(xù)肋乍，卻由于偽共享導(dǎo)致無(wú)法使用 CPU Cache 帶來(lái)的沮喪)鹅颊。
不知道你注意沒(méi)有，實(shí)際數(shù)據(jù) value + 用于填充的 p1-p6總共只占據(jù)了 7 * 8 = 56 個(gè)字節(jié)墓造，而 Cache Line 的大小應(yīng)該是64KB堪伍，這是有意為之，因?yàn)樵?Java中觅闽，對(duì)象頭還占據(jù)了 8個(gè)字節(jié)帝雇，所以一個(gè) PaddingObject 對(duì)象可以恰好占據(jù)一個(gè) Cache Line。
Java7 中實(shí)現(xiàn)字節(jié)填充
在 Java7 之后谱煤，一個(gè) JVM 的優(yōu)化給字節(jié)填充造成了一些影響摊求，上面的代碼片段 public long p1, p2, p3, p4, p5, p6; 會(huì)被認(rèn)為是無(wú)效代碼被優(yōu)化掉，有回歸到了偽共享的窘境之中刘离。
為了避免 JVM 的自動(dòng)優(yōu)化，需要使用繼承的方式來(lái)填充睹栖。
abstract class AbstractPaddingObject{
protected long p1, p2, p3, p4, p5, p6;// 填充
}
public class PaddingObject extends AbstractPaddingObject{
public volatile long value = 0L; // 實(shí)際數(shù)據(jù)
}
Java8 中實(shí)現(xiàn)字節(jié)填充
//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里提供了一個(gè)新注解@Contented硫惕，可以用來(lái)減少 false sharing 的情況。JVM 在計(jì)算對(duì)象布局的時(shí)候就會(huì)自動(dòng)把標(biāo)注的字段拿出來(lái)并且插入合適的大小Padding野来。
因?yàn)檫@個(gè)功能暫時(shí)還是實(shí)驗(yàn)性功能恼除，暫時(shí)還沒(méi)到默認(rèn)普及給用戶(hù)代碼用的程度。要在用戶(hù)代碼(非Bootstrap class loader 或 extension class loader 所加載的類(lèi)) 中使用 @Contended 注解的話(huà)曼氛，需要使用 -XX:-RestrictContended 參數(shù)豁辉。
比如在JDK8中的 ConcurrentHashMap 源碼中，使用 @sun.misc.Contended 對(duì)靜態(tài)內(nèi)部類(lèi) CounterCell 進(jìn)行了修飾舀患。
/* ---------------- 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 線程類(lèi)的源碼中徽级，使用 @sun.misc.Contended 對(duì)成員變量進(jìn)行修飾。
// 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;
