伪共享（false sharing）和缓存填充行_false sharing miss

作者：喵喵爱编程 | 2024-07-07 15:04:39

踩

false sharing miss

伪共享（false sharing）和缓存填充行

前言

最近在看Disruptor源码的时候，底层RingBuffer的实现涉及到了“伪共享”概念，并用缓存填充行去解决以提高性能。搜索了下，其中Jdk也有实现，如Striped64类当中的Cell，jdk8以上用sun.misc.Contended注解解决操作系统的不同差异（在appclassloader下使用jvm启动行需要加上-XX:-RestrictContended）。

1. 伪共享的含义

关于伪共享的含义似乎没有官方的描述，它更多的是一种现象，是基于CPU多级缓存带来共享问题。可参考What Is False Sharing和False Sharing。

伪共享的非标准定义为：CPU的多级缓存是以缓存行（cache line）为单位存储的，当不同的进程修改互相独立的变量时，如果这些变量共享同一个缓存行（包含了不同进程的数据），每次的更新操作会在缓存行和主存相互复制，就会无意中影响彼此的性能，这就是伪共享。为此，较好的解决方式是，每个进程之间的数据不要共享缓存行的数据。

这里就涉及到了CPU缓存的概念了。

2. CPU缓存

百度百科的定义

在计算机系统中，CPU高速缓存（英语：CPU Cache，在本文中简称缓存）是用于减少处理器访问内存所需平均时间的部件。在金字塔式存储体系中它位于自顶向下的第二层，仅次于CPU寄存器。其容量远小于内存，但速度却可以接近处理器的频率。

CPU缓存的容量比内存小的多但是交换速度却比内存要快得多。缓存的出现主要是为了解决CPU运算速度与内存读写速度不匹配的矛盾，因为CPU运算速度要比内存读写速度快很多，这样会使CPU花费很长时间等待数据到来或把数据写入内存

在《深入理解计算机系统（第三版）》中也描述CPU缓存的含义和示例。
在这里插入图片描述

存储器层次结构的主要思想是上一层的存储器作为低一层存储器的高速花奴出纳。因为，寄存器文件就是L1的高速缓存，L1是L2的高速缓存，L2是L3的高速缓存，L3是主存的高速缓存。

3. 缓存行

一般主流的64位的操作系统的L3级缓存是64byte。
一个 Java 的 long 类型是 8 字节，因此在一个缓存行中可以存 8 个 long 类型的变量。所以，如果你访问一个 long 数组，当数组中的一个值被加载到缓存中，它会额外加载另外 7 个，以致你能非常快地遍历这个数组。事实上，你可以非常快速的遍历在连续的内存块中分配的任意数据结构。而如果你在数据结构中的项在内存中不是彼此相邻的（如链表），你将得不到免费缓存加载所带来的优势，并且在这些数据结构中的每一个项都可能会出现缓存未命中。

如果存在这样的场景，有多个线程操作不同的成员变量，但是相同的缓存行，这个时候会发生什么？。没错，伪共享（False Sharing）问题就发生了！有张 Disruptor 项目的经典示例图，如下：
在这里插入图片描述
上图中，一个运行在处理器 core1上的线程想要更新变量 X 的值，同时另外一个运行在处理器 core2 上的线程想要更新变量 Y 的值。但是，这两个频繁改动的变量都处于同一条缓存行。两个线程就会轮番发送 RFO 消息，占得此缓存行的拥有权。当 core1 取得了拥有权开始更新 X，则 core2 对应的缓存行需要设为 I 状态。当 core2 取得了拥有权开始更新 Y，则 core1 对应的缓存行需要设为 I 状态(失效态)。轮番夺取拥有权不但带来大量的 RFO 消息，而且如果某个线程需要读此行数据时，L1 和 L2 缓存上都是失效数据，只有 L3 缓存上是同步好的数据。从前一篇我们知道，读 L3 的数据非常影响性能。更坏的情况是跨槽读取，L3 都要 miss，只能从内存上加载。

表面上 X 和 Y 都是被独立线程操作的，而且两操作之间也没有任何关系。只不过它们共享了一个缓存行，但所有竞争冲突都是来源于共享。

4. 如何避免“伪共享”

http://ifeve.com/false-sharing/当中给出了一个示例，利用缓存填充行来避免“伪共享”。

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 static class VolatileLong
    {
        public volatile long value = 0L;
        public long p1, p2, p3, p4, p5, p6; // comment out
    }
//性能对差，出现多个核心“伪共享”
    public static class VolatileLong1
    {
        public volatile long value = 0L;
    }
    //这种会独占
    public static class VolatileLong2
    {
        long p1, p2, p3, p4, p5, p6, p7; // cache line padding
        volatile long value;
        long p8, p9, p10, p11, p12, p13, p14; // cache line padding
    }

    @sun.misc.Contended
    public static class VolatileLong3
    {
        volatile long value;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

本机电脑的配置为：

处理器	英特尔 第四代酷睿 i5-4570 @ 3.20GHz 四核
速度	3.20 GHz (107 MHz x 30.0)
处理器数量	核心数: 4 / 线程数: 4
核心代号	Haswell
生产工艺	22 纳米
插槽/插座	Socket H3 (LGA 1150)
一级数据缓存	2 x 32 KB, 8-Way, 64 byte lines
一级代码缓存	2 x 32 KB, 8-Way, 64 byte lines
二级缓存	2 x 256 KB, 8-Way, 64 byte lines
三级缓存	6 MB, 12-Way, 64 byte lines
特征	MMX, SSE, SSE2, SSE3, SSSE3, SSE4.1, SSE4.2, EM64T, EIST, Turbo Boost
1
2
3
4
5
6
7
8
9
10
11

多次测试的平均数据为：

VolatileLong   duration = 17363
VolatileLong1  duration = 45369
VolatileLong2  duration = 4842
VolatileLong3  duration = 4885
1
2
3
4

简单分析了原因，VolatileLong本身源代码里只填充到了p6，猜测原先的博主可能是32位机器，对象头好像是再32位机器和64位机器不一样，object header长度，object header 两部分组成，第一部分在64位机器占8个字节，在32位机器上占4个字节，第二部分是一个对象引用。
对象引用在32位机器上占4个字节，在64位机器上有两种情况，开启指针压缩时4个字节；未开启指针压缩是8个字节。
如果是64位机器对象头本身占用16个字节另外value 8个字节，应该填充p1-p5才是最优的。但其实填充到p5效率只是偶先会提升，这种情况是随机和存在不确定性的。
另外用volatile修饰的变量，每次读写，都会直接访问主内存（L3 cache）。每次访问主内存的时候，由于是volatile long，所以都需要对主内存进行加锁。假设主内存加锁也是加在一个cache line上，性能就变慢了。
一个核心上同时会运行许多线程cache line会自动进行所有线程数据的padding，直到填满当前cache line，然后继续向下一个cache line填充，可能刚好cache line 1填充完毕，然后我们启动了测试程序，这个时候就算直接写
public volatile long value = 0L;
假设没有后续线程进行数据填充，我们的数据就独自占用了一个cache line，这个时候不用padding也是最优。
而这样写
long p1, p2, p3, p4, p5, p6, p7; // cache line padding
volatile long value;
long p8, p9, p10, p11, p12, p13, p14; // cache line padding
则是无论当前cache line被填充到了什么位置，我们都能保证value这个值都独自占用一个cache line，性能是最优的，所以VolatileLong2的测试效果较好，另外用@sun.misc.Contended注释的效果和VolatileLong2类似，jvm屏蔽了平台的差异。

实际上在disruptor的com.lmax.disruptor包中，

package com.lmax.disruptor;

import sun.misc.Unsafe;

import com.lmax.disruptor.util.Util;


class LhsPadding
{
    protected long p1, p2, p3, p4, p5, p6, p7;
}

class Value extends LhsPadding
{
    protected volatile long value;
}

class RhsPadding extends Value
{
    protected long p9, p10, p11, p12, p13, p14, p15;
}

/**
 * <p>Concurrent sequence class used for tracking the progress of
 * the ring buffer and event processors.  Support a number
 * of concurrent operations including CAS and order writes.
 *
 * <p>Also attempts to be more efficient with regards to false
 * sharing by adding padding around the volatile field.
 */
public class Sequence extends RhsPadding
{
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

也是填充多行的，保证Cache Line独占。

5. Java8中用到sun.misc.Contended的地方

jdk8中已经使用sun.misc.Contended的地方：

java.lang
Thread
    @sun.misc.Contended("tlr")
    @sun.misc.Contended("tlr")
    @sun.misc.Contended("tlr")
java.util.concurrent
ConcurrentHashMap.CounterCell
    @sun.misc.Contended static final class CounterCell {
Exchanger.Node
    @sun.misc.Contended static final class Node {
ForkJoinPool
@sun.misc.Contended
ForkJoinPool.WorkQueue
    @sun.misc.Contended
java.util.concurrent.atomic
Striped64.Cell
    @sun.misc.Contended static final class Cell {
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

在appclassloader下使用@sun.misc.Contended注解是需要添加vm启动时设置-XX:-RestrictContended，但是比如Thread类和LongAdder里面使用就不需要加了，因为这些类不是在user classpath下的类。

最后总结

主要介绍了伪共享发生的原因，还有常用的解决方法。当然本文参考了很多其他博主写的资料，算是自己的一个总结，对此的认识也很浅薄，深入了解需要掌握更多的计算机基础知识。
CPU具有多级缓存，越接近CPU的缓存越小也越快。
CPU缓存中的数据是以缓存行为单位处理的。
CPU缓存行也带来了弊端，多线程处理不相干的变量时会相互影响，也就是伪共享。
总体来说避免伪共享的主要思路就是让不相干的变量不要出现在同一个缓存行中。
一般用缓存填充行（或者注解）的地方，必然会有volatile修饰的变量。

参考资料

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/喵喵爱编程/article/detail/796050