CPU緩存
CPU和主內(nèi)存之間有好幾層緩存，因為即使直接訪問主內(nèi)存也是非常慢的。如果你正在多次對一塊數(shù)據(jù)做相同的運算，那么在執(zhí)行運算的時候把它加載到離CPU很近的地方就有意義了（比如一個循環(huán)計數(shù)－你不想每次循環(huán)都跑到主內(nèi)存去取這個數(shù)據(jù)來增長它吧）。
越靠近CPU的緩存越快也越小。所以L1緩存很小但很快(譯注：L1表示一級緩存)，并且緊靠著在使用它的CPU內(nèi)核。L2大一些，也慢一些，并且仍然只能被一個單獨的 CPU 核使用。L3在現(xiàn)代多核機器中更普遍，仍然更大，更慢，并且被單個插槽上的所有?CPU 核共享。最后，你擁有一塊主存，由全部插槽上的所有 CPU 核共享。
當CPU執(zhí)行運算的時候，它先去L1查找所需的數(shù)據(jù)，再去L2，然后是L3，最后如果這些緩存中都沒有，所需的數(shù)據(jù)就要去主內(nèi)存拿。走得越遠，運算耗費的時間就越長。所以如果你在做一些很頻繁的事，你要確保數(shù)據(jù)在L1緩存中。
Martin和Mike的QCon presentation演講中給出了一些緩存未命中的消耗數(shù)據(jù)：
從CPU到大約需要的 CPU 周期大約需要的時間
主存約60-80納秒
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
如果你的目標是讓端到端的延遲只有 10毫秒，而其中花80納秒去主存拿一些未命中數(shù)據(jù)的過程將占很重的一塊。
緩存行
現(xiàn)在需要注意一件有趣的事情，數(shù)據(jù)在緩存中不是以獨立的項來存儲的，如不是一個單獨的變量，也不是一個單獨的指針。緩存是由緩存行組成的，通常是64字節(jié)（譯注：這篇文章發(fā)表時常用處理器的緩存行是64字節(jié)的，比較舊的處理器緩存行是32字節(jié)），并且它有效地引用主內(nèi)存中的一塊地址。一個Java的long類型是8字節(jié)，因此在一個緩存行中可以存8個long類型的變量。
(為了簡化，我將忽略多級緩存)
非常奇妙的是如果你訪問一個long數(shù)組，當數(shù)組中的一個值被加載到緩存中，它會額外加載另外7個。因此你能非?？斓乇闅v這個數(shù)組。事實上，你可以非?？焖俚谋闅v在連續(xù)的內(nèi)存塊中分配的任意數(shù)據(jù)結(jié)構(gòu)。我在第一篇關(guān)于ring buffer的文章中順便提到過這個，它解釋了我們的ring buffer使用數(shù)組的原因。
因此如果你數(shù)據(jù)結(jié)構(gòu)中的項在內(nèi)存中不是彼此相鄰的（鏈表，我正在關(guān)注你呢），你將得不到免費緩存加載所帶來的優(yōu)勢。并且在這些數(shù)據(jù)結(jié)構(gòu)中的每一個項都可能會出現(xiàn)緩存未命中。
不過，所有這種免費加載有一個弊端。設(shè)想你的long類型的數(shù)據(jù)不是數(shù)組的一部分。設(shè)想它只是一個單獨的變量。讓我們稱它為head，這么稱呼它其實沒有什么原因。然后再設(shè)想在你的類中有另一個變量緊挨著它。讓我們直接稱它為tail?，F(xiàn)在，當你加載head到緩存的時候，你也免費加載了tail。
聽想來不錯。直到你意識到tail正在被你的生產(chǎn)者寫入，而head正在被你的消費者寫入。這兩個變量實際上并不是密切相關(guān)的，而事實上卻要被兩個不同內(nèi)核中運行的線程所使用。
設(shè)想你的消費者更新了head的值。緩存中的值和內(nèi)存中的值都被更新了，而其他所有存儲head的緩存行都會都會失效，因為其它緩存中head不是最新值了。請記住我們必須以整個緩存行作為單位來處理（譯注：這是CPU的實現(xiàn)所規(guī)定的，詳細可參見深入分析Volatile的實現(xiàn)原理），不能只把head標記為無效。
現(xiàn)在如果一些正在其他內(nèi)核中運行的進程只是想讀tail的值，整個緩存行需要從主內(nèi)存重新讀取。那么一個和你的消費者無關(guān)的線程讀一個和head無關(guān)的值，它被緩存未命中給拖慢了。
當然如果兩個獨立的線程同時寫兩個不同的值會更糟。因為每次線程對緩存行進行寫操作時，每個內(nèi)核都要把另一個內(nèi)核上的緩存塊無效掉并重新讀取里面的數(shù)據(jù)。你基本上是遇到兩個線程之間的寫沖突了，盡管它們寫入的是不同的變量。
這叫作“偽共享”（譯注：可以理解為錯誤的共享），因為每次你訪問head你也會得到tail，而且每次你訪問tail，你也會得到head。這一切都在后臺發(fā)生，并且沒有任何編譯警告會告訴你，你正在寫一個并發(fā)訪問效率很低的代碼。
解決方案－神奇的緩存行填充
你會看到Disruptor消除這個問題，至少對于緩存行大小是64字節(jié)或更少的處理器架構(gòu)來說是這樣的（譯注：有可能處理器的緩存行是128字節(jié)，那么使用64字節(jié)填充還是會存在偽共享問題），通過增加補全來確保ring buffer的序列號不會和其他東西同時存在于一個緩存行中。
1public?long?p1, p2, p3, p4, p5, p6, p7;?// cache line padding
2????private?volatile?long?cursor = INITIAL_CURSOR_VALUE;
3????public?long?p8, p9, p10, p11, p12, p13, p14;?// cache line padding
因此沒有偽共享，就沒有和其它任何變量的意外沖突，沒有不必要的緩存未命中。
在你的Entry類中也值得這樣做，如果你有不同的消費者往不同的字段寫入，你需要確保各個字段間不會出現(xiàn)偽共享。
JAVA下的偽共享
緩存系統(tǒng)中是以緩存行（cache line）為單位存儲的。緩存行是2的整數(shù)冪個連續(xù)字節(jié)，一般為32-256個字節(jié)。最常見的緩存行大小是64個字節(jié)。當多線程修改互相獨立的變量時，如果這些變量共享同一個緩存行，就會無意中影響彼此的性能，這就是偽共享。緩存行上的寫競爭是運行在SMP系統(tǒng)中并行線程實現(xiàn)可伸縮性最重要的限制因素。有人將偽共享描述成無聲的性能殺手，因為從代碼中很難看清楚是否會出現(xiàn)偽共享。
為了讓可伸縮性與線程數(shù)呈線性關(guān)系，就必須確保不會有兩個線程往同一個變量或緩存行中寫。兩個線程寫同一個變量可以在代碼中發(fā)現(xiàn)。為了確定互相獨立的變量是否共享了同一個緩存行，就需要了解內(nèi)存布局，或找個工具告訴我們。Intel VTune就是這樣一個分析工具。本文中我將解釋Java對象的內(nèi)存布局以及我們該如何填充緩存行以避免偽共享。
圖 1.
圖1說明了偽共享的問題。在核心1上運行的線程想更新變量X，同時核心2上的線程想要更新變量Y。不幸的是，這兩個變量在同一個緩存行中。每個線程都要去競爭緩存行的所有權(quán)來更新變量。如果核心1獲得了所有權(quán)，緩存子系統(tǒng)將會使核心2中對應(yīng)的緩存行失效。當核心2獲得了所有權(quán)然后執(zhí)行更新操作，核心1就要使自己對應(yīng)的緩存行失效。這會來來回回的經(jīng)過L3緩存，大大影響了性能。如果互相競爭的核心位于不同的插槽，就要額外橫跨插槽連接，問題可能更加嚴重。
Java內(nèi)存布局(Java Memory Layout)
對于HotSpot JVM，所有對象都有兩個字長的對象頭。第一個字是由24位哈希碼和8位標志位（如鎖的狀態(tài)或作為鎖對象）組成的Mark Word。第二個字是對象所屬類的引用。如果是數(shù)組對象還需要一個額外的字來存儲數(shù)組的長度。每個對象的起始地址都對齊于8字節(jié)以提高性能。因此當封裝對象的時候為了高效率，對象字段聲明的順序會被重排序成下列基于字節(jié)大小的順序：
doubles (8) 和 longs (8)
ints (4) 和 floats (4)
shorts (2) 和 chars (2)
booleans (1) 和 bytes (1)
references (4/8)
<子類字段重復(fù)上述順序>
（譯注：更多HotSpot虛擬機對象結(jié)構(gòu)相關(guān)內(nèi)容:http://www.infoq.com/cn/articles/jvm-hotspot）
了解這些之后就可以在任意字段間用7個long來填充緩存行。在Disruptor里我們對RingBuffer的cursor和BatchEventProcessor的序列進行了緩存行填充。
為了展示其性能影響，我們啟動幾個線程，每個都更新它自己獨立的計數(shù)器。計數(shù)器是volatile long類型的，所以其它線程能看到它們的進展。
01public?final?class?FalseSharing
02????implements?Runnable
03{
04????public?final?static?int?NUM_THREADS =?4;?// change
05????public?final?static?long?ITERATIONS = 500L * 1000L * 1000L;
06????private?final?int?arrayIndex;
07?
08????private?static?VolatileLong[] longs =?new?VolatileLong[NUM_THREADS];
09????static
10????{
11????????for?(int?i =?0; i < longs.length; i++)
12????????{
13????????????longs[i] =?new?VolatileLong();
14????????}
15????}
16?
17????public?FalseSharing(final?int?arrayIndex)
18????{
19????????this.arrayIndex = arrayIndex;
20????}
21?
22????public?static?void?main(final?String[] args)?throws?Exception
23????{
24????????final?long?start = System.nanoTime();
25????????runTest();
26????????System.out.println("duration = "?+ (System.nanoTime() - start));
27????}
28?
29????private?static?void?runTest()?throws?InterruptedException
30????{
31????????Thread[] threads =?new?Thread[NUM_THREADS];
32?
33????????for?(int?i =?0; i < threads.length; i++)
34????????{
35????????????threads[i] =?new?Thread(new?FalseSharing(i));
36????????}
37?
38????????for?(Thread t : threads)
39????????{
40????????????t.start();
41????????}
42?
43????????for?(Thread t : threads)
44????????{
45????????????t.join();
46????????}
47????}
48?
49????public?void?run()
50????{
51????????long?i = ITERATIONS +?1;
52????????while?(0?!= --i)
53????????{
54????????????longs[arrayIndex].value = i;
55????????}
56????}
57?
58????public?final?static?class?VolatileLong
59????{
60????????public?volatile?long?value = 0L;
61????????public?long?p1, p2, p3, p4, p5, p6;?// comment out
62????}
63}
運行上面的代碼，增加線程數(shù)以及添加/移除緩存行的填充，下面的圖2描述了我得到的結(jié)果。這是在我4核Nehalem上測得的運行時間。
圖 2.
從不斷上升的測試所需時間中能夠明顯看出偽共享的影響。沒有緩存行競爭時，我們幾近達到了隨著線程數(shù)的線性擴展。
這并不是個完美的測試，因為我們不能確定這些VolatileLong會布局在內(nèi)存的什么位置。它們是獨立的對象。但是經(jīng)驗告訴我們同一時間分配的對象趨向集中于一塊。
所以你也看到了，偽共享可能是無聲的性能殺手。
合并寫
現(xiàn)代CPU采用大量的技術(shù)來抵消內(nèi)存訪問延遲。 從DRAM存儲中讀取或者寫入數(shù)據(jù)的時間CPU可以執(zhí)行上百個指令。
? ? 用來降低這種延遲的主要手段是使用多層次的SRAM緩存。此外，也有SMP系統(tǒng)采用消息傳遞協(xié)議來實現(xiàn)緩存之間的一致性。即便如此，現(xiàn)代CPU是如此之快，是緩存根本無法企及的。因此，為了進一步降低延遲一些鮮為人知的緩沖區(qū)（buffers?）也被使用。
? ? 本文探討“合并寫存儲緩沖區(qū)（write combining store buffers）”，以及我們?nèi)绾尉帉懘a可以有效地使用它們。
? ? ?CPU緩存是一個高效的非鏈式結(jié)構(gòu)的hash map，每個桶（bucket）通常是64個字節(jié)。被稱為之為一個“緩存行（cache line）”。緩存行（cache line）是內(nèi)存?zhèn)鬏數(shù)挠行卧?。例如，主存中地址A會映射到一個給定的緩存行C。
? ? ?如果CPU需要訪問的地址hash之后并不在緩存行（cache line）中，那么緩存中對應(yīng)位置的緩存行（cache line）會失效，以便讓新的值可以取代該位置的現(xiàn)有值。例如，如果我們有兩個地址，通過hash算法hash到同一緩存行，那么新的值會覆蓋老的值。
當CPU執(zhí)行存儲指令（store）時，它會嘗試將數(shù)據(jù)寫到離CPU最近的L1緩存。如果這時出現(xiàn)緩存失效，CPU會訪問下一級緩存。這時無論是英特爾還是許多其他廠商的CPU都會使用被稱為“合并寫（write combining）”的技術(shù)。
? ? 當請求L2緩存行的所有權(quán)的時候，最典型的是將處理器的store buffers中某一項寫入內(nèi)存的期間，?在緩存子系統(tǒng)(?cache sub-system)準備好接收、處理的數(shù)據(jù)的期間，CPU可以繼續(xù)處理其他指令。當數(shù)據(jù)不在任何緩存層中緩存時，將獲得最大的優(yōu)勢。
? ? 當連串的寫操作需要修改相同的緩存行時，會變得非常有趣。在修改提交到L2緩存之前，這連串的寫操作會首先合并到緩沖區(qū)（buffer）。 這些64字節(jié)的緩沖（buffers?）維護在一個64位的區(qū)域中，每一個字節(jié)（byte）對應(yīng)一個位（bit），當緩沖區(qū)被傳輸?shù)酵饩彺婧螅瑯酥揪彺媸欠裼行А?/p>
也許你要問如果程序要讀取一些已被寫入緩沖區(qū)（buffer）的數(shù)據(jù)，會發(fā)生什么事呢？我們的硬件會友好的處理，它們在讀取緩存之前會先讀取緩沖區(qū)。
? ? 這一切對我們的程序意味著什么呢？
如果我們可以在緩沖區(qū)被傳輸?shù)酵饩彺嬷澳軌蛱钛a這些緩沖區(qū)（buffers ），那么我們將大大提高傳輸總線的效率。如何才能做到這一點呢？大部分程序花費其大部分時間在循環(huán)的處理某項任務(wù)。
由于這些緩沖區(qū)的數(shù)量是有限的，并且它們根據(jù)CPU的型號有所不同。例如在Intel CPU，你只能保證在同一時間拿到4個。這意味著，在一個循環(huán)中，你不應(yīng)該同時寫超過4個截然不同的內(nèi)存位置，否則你講不能從合并寫（write combining）的中受益。
?代碼如下：??
public final class WriteCombining?{
private static final int ITERATIONS?=?Integer.MAX_VALUE;
private static final int ITEMS??????=1<<24;
private static final int MASK???????=?ITEMS?-1;
private static final byte[]?arrayA?????=newbyte[ITEMS];
private static final byte[]?arrayB?????=newbyte[ITEMS];
private static final byte[]?arrayC?????=newbyte[ITEMS];
private static final byte[]?arrayD?????=newbyte[ITEMS];
private static final byte[]?arrayE?????=newbyte[ITEMS];
private static final byte[]?arrayF?????=newbyte[ITEMS];
public static void main(finalString[]?args)?{
for(int i?=1;?i?<=3;?i++)?{
out.println(i?+"?SingleLoop?duration?(ns)?=?"+?runCaseOne());
out.println(i?+"?SplitLoop?duration?(ns)?=?"+?runCaseTwo());
????????}??
int result?=?arrayA[1]?+?arrayB[2]?+?arrayC[3]?+?arrayD[4]?+?arrayE[5]?+?arrayF[6];
out.println("result?=?"+?result);
????}??
public static long runCaseOne()?{
long start?=?System.nanoTime();
int i?=?ITERATIONS;
while(--i?!=0)?{
int slot?=?i?&?MASK;
byte b?=?(byte)?i;
????????????arrayA[slot]?=?b;??
????????????arrayB[slot]?=?b;??
????????????arrayC[slot]?=?b;??
????????????arrayD[slot]?=?b;??
????????????arrayE[slot]?=?b;??
????????????arrayF[slot]?=?b;??
????????}??
return System.nanoTime()?-?start;
????}??
public static long runCaseTwo()?{
long start?=?System.nanoTime();
int i?=?ITERATIONS;
while(--i?!=0)?{
int slot?=?i?&?MASK;
byte b?=?(byte)?i;
????????????arrayA[slot]?=?b;??
????????????arrayB[slot]?=?b;??
????????????arrayC[slot]?=?b;??
????????}??
????????i?=?ITERATIONS;??
while(--i?!=0)?{
int slot?=?i?&?MASK;
byte b?=?(byte)?i;
????????????arrayD[slot]?=?b;??
????????????arrayE[slot]?=?b;??
????????????arrayF[slot]?=?b;??
????????}??
return System.nanoTime()?-?start;
????}??
}??
這個程序在我的Windows 7 ?64位英特爾酷睿i7860@2.8 GHz系統(tǒng)產(chǎn)生以下的輸出：?
1 SingleLoop?duration?(ns)?=14019753545
1 SplitLoop??duration?(ns)?=8972368661
2 SingleLoop?duration?(ns)?=14162455066
2 SplitLoop??duration?(ns)?=8887610558
3 SingleLoop?duration?(ns)?=13800914725
3 SplitLoop??duration?(ns)?=7271752889
? ? 上面的例子闡明：如果在一個循環(huán)中修改6個數(shù)組位置（對應(yīng)6個內(nèi)存地址），我們的程序運行時間明顯長于拆分工作的方式，即是：先寫前3個位置，后修改后3個位置的數(shù)據(jù)。
? ? 通過拆分循環(huán)，我們可以讓程序用更少的時間完成更多的工作！歡迎來到神奇的“合并寫（write combining）”。通過使用CPU架構(gòu)的知識，正確的填充這些緩沖區(qū)，我們可以利用底層硬件加速我們的程序。
? ? 不要忘了超線程（hyper-threading），可能有2個邏輯線程在競爭同一個核的緩沖區(qū)。
文章轉(zhuǎn)載自：http://ifeve.com/false-sharing/? ? https://blog.csdn.net/aigoogle/article/details/41517293
##@sun.misc.Contended
Implementation overview. Hotspot code is currently laying out the fields to optimize the memory footprint, rearranging fields freely to both satisfy alignment requirements for fields and making the less gaps possible. We leverage the same infrastructure to exempt specific fields from the packing, and pushing them outside the dense packed block at sparse offsets, naturally making up the appropriate padding.
In order to demarcate the specific classes and/or fields eligible for such the padding, we use new @Contended annotation. Runtime discovery of annotations reuses the code John (?) laid out for some of JSR292-specific annotations.
The behavior of this annotation is as follows:
A. Marking the class as contended:
@Contended
? ? public static class ContendedTest2 {
? ? ? ? private Object plainField1;
? ? ? ? private Object plainField2;
? ? ? ? private Object plainField3;
? ? ? ? private Object plainField4;
? ? }
...makes the entire field block to be padded from the both sides:
(below is the output of new tracing -XX:+PrintFieldLayout)
TestContended$ContendedTest2: field layout? ? Entire class is marked contended? ??
?@140 --- instance fields start ---? ?
?@140 "plainField1" Ljava.lang.Object;? ??
?@144 "plainField2" Ljava.lang.Object;? ??
?@148 "plainField3" Ljava.lang.Object;? ??
?@152 "plainField4" Ljava.lang.Object;? ?
?@288 --- instance fields end ---? ??
?@288 --- instance ends ---
Note that we use 128 bytes, twice the cache line size on most hardware
to adjust for adjacent sector prefetchers extending the false sharing
collisions to two cache lines.
B. Marking the field as contended:
? ? public static class ContendedTest1 {
? ? ? ? @Contended
? ? ? ? private Object contendedField1;
? ? ? ? private Object plainField1;
? ? ? ? private Object plainField2;
? ? ? ? private Object plainField3;
? ? ? ? private Object plainField4;
? ? }
...pushes the field out of dense block and effectively applies padding:
? TestContended$ContendedTest1: field layout
? ? @ 12 --- instance fields start ---
? ? @ 12 "plainField1" Ljava.lang.Object;
? ? @ 16 "plainField2" Ljava.lang.Object;
? ? @ 20 "plainField3" Ljava.lang.Object;
? ? @ 24 "plainField4" Ljava.lang.Object;
? ? @156 "contendedField1" Ljava.lang.Object; (contended, group = 0)
? ? @288 --- instance fields end ---
? ? @288 --- instance ends ---
C. Marking multiple fields makes each field padded:
? ? public static class ContendedTest4 {
? ? ? ? @Contended
? ? ? ? private Object contendedField1;
? ? ? ? @Contended
? ? ? ? private Object contendedField2;
? ? ? ? private Object plainField3;
? ? ? ? private Object plainField4;
? ? }
...pushes both fields with individual padding for each:
? TestContended$ContendedTest4: field layout
? ? @ 12 --- instance fields start ---
? ? @ 12 "plainField3" Ljava.lang.Object;
? ? @ 16 "plainField4" Ljava.lang.Object;
? ? @148 "contendedField1" Ljava.lang.Object; (contended, group = 0)
? ? @280 "contendedField2" Ljava.lang.Object; (contended, group = 0)
? ? @416 --- instance fields end ---
? ? @416 --- instance ends ---
*** IV. Contention groups
There are cases where you want to separate the *group* of fields that
are experiencing contention with everything else but not pairwise. This
is the usual thing for some of the code updating two fields at once.
While marking both with @Contended would be sufficient, we can optimize
the memory footprint by not applying padding between them. In order to
demarcate these groups, we have the parameter in the annotation
describing the equivalence class for contention group.
So that:
? ? public static class ContendedTest5 {
? ? ? ? @Contended("updater1")
? ? ? ? private Object contendedField1;
? ? ? ? @Contended("updater1")
? ? ? ? private Object contendedField2;
? ? ? ? @Contended("updater2")
? ? ? ? private Object contendedField3;
? ? ? ? private Object plainField5;
? ? ? ? private Object plainField6;
? ? }
...is laid out as:
? TestContended$ContendedTest5: field layout
? ? @ 12 --- instance fields start ---
? ? @ 12 "plainField5" Ljava.lang.Object;
? ? @ 16 "plainField6" Ljava.lang.Object;
? ? @148 "contendedField1" Ljava.lang.Object; (contended, group = 12)
? ? @152 "contendedField2" Ljava.lang.Object; (contended, group = 12)
? ? @284 "contendedField3" Ljava.lang.Object; (contended, group = 15)
? ? @416 --- instance fields end ---
? ? @416 --- instance ends ---
Note $contendedField1 and $contendedField2 are padded from everything else, but still densely packed with each other.
The code is known to work at least on Linux x86-64, tested with a few microtests. The layout of fields without @Contended is not affected, so this is presumably a safe change. I will try to run more tests against this implementation with JPRT, but will appreciate the design, API, and draft implementation review meanwhile...
