CPU缓存
CPU和主内存之间有好几层缓存，因为即使直接访问主内存也是非常慢的。如果你正在多次对一块数据做相同的运算，那么在执行运算的时候把它加载到离CPU很近的地方就有意义了（比如一个循环计数－你不想每次循环都跑到主内存去取这个数据来增长它吧）。
越靠近CPU的缓存越快也越小。所以L1缓存很小但很快(译注：L1表示一级缓存)，并且紧靠着在使用它的CPU内核。L2大一些，也慢一些，并且仍然只能被一个单独的 CPU 核使用。L3在现代多核机器中更普遍，仍然更大，更慢，并且被单个插槽上的所有 CPU 核共享。最后，你拥有一块主存，由全部插槽上的所有 CPU 核共享。
当CPU执行运算的时候，它先去L1查找所需的数据，再去L2，然后是L3，最后如果这些缓存中都没有，所需的数据就要去主内存拿。走得越远，运算耗费的时间就越长。所以如果你在做一些很频繁的事，你要确保数据在L1缓存中。
Martin和Mike的QCon presentation演讲中给出了一些缓存未命中的消耗数据：
从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纳秒去主存拿一些未命中数据的过程将占很重的一块。
缓存行
现在需要注意一件有趣的事情，数据在缓存中不是以独立的项来存储的，如不是一个单独的变量，也不是一个单独的指针。缓存是由缓存行组成的，通常是64字节（译注：这篇文章发表时常用处理器的缓存行是64字节的，比较旧的处理器缓存行是32字节），并且它有效地引用主内存中的一块地址。一个Java的long类型是8字节，因此在一个缓存行中可以存8个long类型的变量。
(为了简化，我将忽略多级缓存)
非常奇妙的是如果你访问一个long数组，当数组中的一个值被加载到缓存中，它会额外加载另外7个。因此你能非常快地遍历这个数组。事实上，你可以非常快速的遍历在连续的内存块中分配的任意数据结构。我在第一篇关于ring buffer的文章中顺便提到过这个，它解释了我们的ring buffer使用数组的原因。
因此如果你数据结构中的项在内存中不是彼此相邻的（链表，我正在关注你呢），你将得不到免费缓存加载所带来的优势。并且在这些数据结构中的每一个项都可能会出现缓存未命中。
不过，所有这种免费加载有一个弊端。设想你的long类型的数据不是数组的一部分。设想它只是一个单独的变量。让我们称它为head，这么称呼它其实没有什么原因。然后再设想在你的类中有另一个变量紧挨着它。让我们直接称它为tail。现在，当你加载head到缓存的时候，你也免费加载了tail。
听想来不错。直到你意识到tail正在被你的生产者写入，而head正在被你的消费者写入。这两个变量实际上并不是密切相关的，而事实上却要被两个不同内核中运行的线程所使用。
设想你的消费者更新了head的值。缓存中的值和内存中的值都被更新了，而其他所有存储head的缓存行都会都会失效，因为其它缓存中head不是最新值了。请记住我们必须以整个缓存行作为单位来处理（译注：这是CPU的实现所规定的，详细可参见深入分析Volatile的实现原理），不能只把head标记为无效。
现在如果一些正在其他内核中运行的进程只是想读tail的值，整个缓存行需要从主内存重新读取。那么一个和你的消费者无关的线程读一个和head无关的值，它被缓存未命中给拖慢了。
当然如果两个独立的线程同时写两个不同的值会更糟。因为每次线程对缓存行进行写操作时，每个内核都要把另一个内核上的缓存块无效掉并重新读取里面的数据。你基本上是遇到两个线程之间的写冲突了，尽管它们写入的是不同的变量。
这叫作“伪共享”（译注：可以理解为错误的共享），因为每次你访问head你也会得到tail，而且每次你访问tail，你也会得到head。这一切都在后台发生，并且没有任何编译警告会告诉你，你正在写一个并发访问效率很低的代码。
解决方案－神奇的缓存行填充
你会看到Disruptor消除这个问题，至少对于缓存行大小是64字节或更少的处理器架构来说是这样的（译注：有可能处理器的缓存行是128字节，那么使用64字节填充还是会存在伪共享问题），通过增加补全来确保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类中也值得这样做，如果你有不同的消费者往不同的字段写入，你需要确保各个字段间不会出现伪共享。
JAVA下的伪共享
缓存系统中是以缓存行（cache line）为单位存储的。缓存行是2的整数幂个连续字节，一般为32-256个字节。最常见的缓存行大小是64个字节。当多线程修改互相独立的变量时，如果这些变量共享同一个缓存行，就会无意中影响彼此的性能，这就是伪共享。缓存行上的写竞争是运行在SMP系统中并行线程实现可伸缩性最重要的限制因素。有人将伪共享描述成无声的性能杀手，因为从代码中很难看清楚是否会出现伪共享。
为了让可伸缩性与线程数呈线性关系，就必须确保不会有两个线程往同一个变量或缓存行中写。两个线程写同一个变量可以在代码中发现。为了确定互相独立的变量是否共享了同一个缓存行，就需要了解内存布局，或找个工具告诉我们。Intel VTune就是这样一个分析工具。本文中我将解释Java对象的内存布局以及我们该如何填充缓存行以避免伪共享。
图 1.
图1说明了伪共享的问题。在核心1上运行的线程想更新变量X，同时核心2上的线程想要更新变量Y。不幸的是，这两个变量在同一个缓存行中。每个线程都要去竞争缓存行的所有权来更新变量。如果核心1获得了所有权，缓存子系统将会使核心2中对应的缓存行失效。当核心2获得了所有权然后执行更新操作，核心1就要使自己对应的缓存行失效。这会来来回回的经过L3缓存，大大影响了性能。如果互相竞争的核心位于不同的插槽，就要额外横跨插槽连接，问题可能更加严重。
对于HotSpot JVM，所有对象都有两个字长的对象头。第一个字是由24位哈希码和8位标志位（如锁的状态或作为锁对象）组成的Mark Word。第二个字是对象所属类的引用。如果是数组对象还需要一个额外的字来存储数组的长度。每个对象的起始地址都对齐于8字节以提高性能。因此当封装对象的时候为了高效率，对象字段声明的顺序会被重排序成下列基于字节大小的顺序：
doubles (8) 和 longs (8)
ints (4) 和 floats (4)
shorts (2) 和 chars (2)
booleans (1) 和 bytes (1)
references (4/8)
<子类字段重复上述顺序>
（译注：更多HotSpot虚拟机对象结构相关内容:http://www.infoq.com/cn/articles/jvm-hotspot）
了解这些之后就可以在任意字段间用7个long来填充缓存行。在Disruptor里我们对RingBuffer的cursor和BatchEventProcessor的序列进行了缓存行填充。
为了展示其性能影响，我们启动几个线程，每个都更新它自己独立的计数器。计数器是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}
运行上面的代码，增加线程数以及添加/移除缓存行的填充，下面的图2描述了我得到的结果。这是在我4核Nehalem上测得的运行时间。
图 2.
从不断上升的测试所需时间中能够明显看出伪共享的影响。没有缓存行竞争时，我们几近达到了随着线程数的线性扩展。
这并不是个完美的测试，因为我们不能确定这些VolatileLong会布局在内存的什么位置。它们是独立的对象。但是经验告诉我们同一时间分配的对象趋向集中于一块。
所以你也看到了，伪共享可能是无声的性能杀手。
合并写
现代CPU采用大量的技术来抵消内存访问延迟。 从DRAM存储中读取或者写入数据的时间CPU可以执行上百个指令。
用来降低这种延迟的主要手段是使用多层次的SRAM缓存。此外，也有SMP系统采用消息传递协议来实现缓存之间的一致性。即便如此，现代CPU是如此之快，是缓存根本无法企及的。因此，为了进一步降低延迟一些鲜为人知的缓冲区（buffers ）也被使用。
本文探讨“合并写存储缓冲区（write combining store buffers）”，以及我们如何编写代码可以有效地使用它们。
CPU缓存是一个高效的非链式结构的hash map，每个桶（bucket）通常是64个字节。被称为之为一个“缓存行（cache line）”。缓存行（cache line）是内存传输的有效单元。例如，主存中地址A会映射到一个给定的缓存行C。
如果CPU需要访问的地址hash之后并不在缓存行（cache line）中，那么缓存中对应位置的缓存行（cache line）会失效，以便让新的值可以取代该位置的现有值。例如，如果我们有两个地址，通过hash算法hash到同一缓存行，那么新的值会覆盖老的值。
当CPU执行存储指令（store）时，它会尝试将数据写到离CPU最近的L1缓存。如果这时出现缓存失效，CPU会访问下一级缓存。这时无论是英特尔还是许多其他厂商的CPU都会使用被称为“合并写（write combining）”的技术。
当请求L2缓存行的所有权的时候，最典型的是将处理器的store buffers中某一项写入内存的期间， 在缓存子系统( cache sub-system)准备好接收、处理的数据的期间，CPU可以继续处理其他指令。当数据不在任何缓存层中缓存时，将获得最大的优势。
当连串的写操作需要修改相同的缓存行时，会变得非常有趣。在修改提交到L2缓存之前，这连串的写操作会首先合并到缓冲区（buffer）。 这些64字节的缓冲（buffers ）维护在一个64位的区域中，每一个字节（byte）对应一个位（bit），当缓冲区被传输到外缓存后，标志缓存是否有效。
也许你要问如果程序要读取一些已被写入缓冲区（buffer）的数据，会发生什么事呢？我们的硬件会友好的处理，它们在读取缓存之前会先读取缓冲区。
这一切对我们的程序意味着什么呢？
如果我们可以在缓冲区被传输到外缓存之前能够填补这些缓冲区（buffers ），那么我们将大大提高传输总线的效率。如何才能做到这一点呢？大部分程序花费其大部分时间在循环的处理某项任务。
由于这些缓冲区的数量是有限的，并且它们根据CPU的型号有所不同。例如在Intel CPU，你只能保证在同一时间拿到4个。这意味着，在一个循环中，你不应该同时写超过4个截然不同的内存位置，否则你讲不能从合并写（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系统产生以下的输出：
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
上面的例子阐明：如果在一个循环中修改6个数组位置（对应6个内存地址），我们的程序运行时间明显长于拆分工作的方式，即是：先写前3个位置，后修改后3个位置的数据。
通过拆分循环，我们可以让程序用更少的时间完成更多的工作！欢迎来到神奇的“合并写（write combining）”。通过使用CPU架构的知识，正确的填充这些缓冲区，我们可以利用底层硬件加速我们的程序。
不要忘了超线程（hyper-threading），可能有2个逻辑线程在竞争同一个核的缓冲区。
文章转载自：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...
网友评论