什么是伪共享
CPU缓存系统中是以缓存行(cache line)为单位存储的。目前主流的CPU Cache的Cache Line大小都是64Bytes。在多线程情况下,如果需要修改“共享同一个缓存行的变量”,就会无意中影响彼此的性能,这就是伪共享(False Sharing)。
CPU的三级缓存
由于CPU的速度远远大于内存速度,所以CPU设计者们就给CPU加上了缓存(CPU Cache)。 以免运算被内存速度拖累。(就像我们写代码把共享数据做Cache不想被DB存取速度拖累一样),CPU Cache分成了三个级别:L1,L2,L3。级别越小越接近CPU, 所以速度也更快, 同时也代表着容量越小。
CPU获取数据回依次从L1,L2,L3中查找,如果都找不到则会直接向内存查找。
缓存行
由于共享变量在CPU缓存中的存储是以缓存行为单位,一个缓存行可以存储多个变量(存满当前缓存行的字节数);而CPU对缓存的修改又是以缓存行为最小单位的,那么就会出现上诉的伪共享问题。
Cache Line可以简单的理解为CPU Cache中的最小缓存单位,今天的CPU不再是按字节访问内存,而是以64字节为单位的块(chunk)拿取,称为一个缓存行(cache line)。当你读一个特定的内存地址,整个缓存行将从主存换入缓存,并且访问同一个缓存行内的其它值的开销是很小的。
看如下代码示例:
int[] arr = new int[64 1024 1024];
long start = System.nanoTime();
for (int i = 0; i < arr.length; i++) {
arr[i] *= 3;
}
System.out.println(System.nanoTime() - start);
long start2 = System.nanoTime();
for (int i = 0; i < arr.length; i += 16) {
arr[i] *= 3;
}
System.out.println(System.nanoTime() - start2);
表面上看,第二个循环工作量为第一个循环的1/16;但是执行时间是相差不大的,假设在内存规整的情况下,每16个int 占用4*16=64字节,正好一个缓存行,也就是说这两个循环访问内存的次数是一致的。导致耗时相差不大。
缓存关联性
目前常用的缓存设计是N路组关联(N-Way Set Associative Cache),他的原理是把一个缓存按照N个Cache Line作为一组(Set),缓存按组划为等分。每个内存块能够被映射到相对应的set中的任意一个缓存行中。比如一个16路缓存,16个Cache Line作为一个Set,每个内存块能够被映射到相对应的Set
中的16个CacheLine中的任意一个。一般地,具有一定相同低bit位地址的内存块将共享同一个Set。
下图为一个2-Way的Cache。由图中可以看到Main Memory中的Index0,2,4都映射在Way0的不同CacheLine中,Index1,3,5都映射在Way1的不同CacheLine中。
MESI协议
多核CPU都有自己的专有缓存(一般为L1,L2),以及同一个CPU插槽之间的核共享的缓存(一般为L3)。不同核心的CPU缓存中难免会加载同样的数据,那么如何保证数据的一致性呢,就是MESI协议了。
在MESI协议中,每个Cache line有4个状态,可用2个bit表示,它们分别是:
M(Modified):这行数据有效,数据被修改了,和内存中的数据不一致,数据只存在于本Cache中;
E(Exclusive):这行数据有效,数据和内存中的数据一致,数据只存在于本Cache中;
S(Shared):这行数据有效,数据和内存中的数据一致,数据存在于很多Cache中;
I(Invalid):这行数据无效。
那么,假设有一个变量i=3(应该是包括变量i的缓存块,块大小为缓存行大小);已经加载到多核(a,b,c)的缓存中,此时该缓存行的状态为S;此时其中的一个核a改变了变量i的值,那么在核a中的当前缓存行的状态将变为M,b,c核中的当前缓存行状态将变为I。如下图:
伪共享问题
那么为什么会出现伪共享问题呢?上诉的情况再扩展一下,假设在多线程情况下,x,y两个共享变量在同一个缓存行中,核a修改变量x,会导致核b,核c中的x变量和y变量同时失效。
此时对于在核a上运行的线程,仅仅只是修改了了变量x,却导致同一个缓存行中的所有变量都无效,需要重新刷缓存(并不一定代表每次都要从内存中重新载入,也有可能是从其他Cache中导入数据,具体的实现要看各个芯片厂商的实现了)。
假设此时在核b上运行的线程,正好想要修改变量Y,那么就会出现相互竞争,相互失效的情况,这就是伪共享啦。
Java对于伪共享的传统解决方案
package com.alibaba;
/**
* Created by Administrator on 2016/10/13 0013.
*/
public final class FalseSharing implements Runnable {
private final static int NUM_THREADS = 4; // change
private 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.nanoTime();
runTest();
System.out.println("duration = " + (System.nanoTime() - 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;
}
}
执行结果:
duration = 9465942893
现在,我们将VolatileLong中不使用的6个long变量注释掉,再次执行:
public final static class VolatileLong {
public volatile long value = 0L;
//public long p1, p2, p3, p4, p5, p6;
}
duration = 20362748888
可以看到,两个程序逻辑完全一致,只是注释掉了几个没有使用到的变量,却导致性能相差很大。 我们知道一条缓存行有64字节, 而Java程序的对象头固定占8字节(32位系统)或12字节(64位系统默认开启压缩, 不开压缩为16字节). 我们只需要填6个无用的长整型补上6*8=48字节, 让不同的VolatileLong对象处于不同的缓存行, 就可以避免伪共享了(64位系统超过缓存行的64字节也无所谓,只要保证不同线程不要操作同一缓存行就可以)。这个办法叫做补齐(Padding)。
Java8中的解决方案
Java8中已经提供了官方的解决方案,Java8中新增了一个注解:@sun.misc.Contended。加上这个注解的类会自动补齐缓存行,需要注意的是此注解默认是无效的,需要在jvm启动时设置-XX:-RestrictContended才会生效。
运行结果:
@sun.misc.Contended
public final static class VolatileLong {
public volatile long value = 0L;
//public long p1, p2, p3, p4, p5, p6;
}
duration = 8987991013
参考文献:
1:http://igoro.com/archive/gallery-of-processor-cache-effects/
2:http://ifeve.com/false-sharing/
3:http://blog.csdn.net/muxiqingyang/article/details/6615199