关于java:计算机组成无锁编程追求极致性能

古代计算机通常由 CPU，以及主板、内存、硬盘等次要硬件构造组成，而决定计算机性能的最核心部件是CPU+ 内存，CPU 负责处理程序指令，内存负责存储指令执行后果。在这个工作机制当中 CPU 的读写效率其实是远远高于内存的，为晋升执行效率缩小 CPU 与内存的交互，个别在 CPU 上设计了缓存构造，常见的为三级缓存构造：

L1 Cache，分为数据缓存和指令缓存，逻辑核独占
L2 Cache，物理核独占，逻辑核共享
L3 Cache，所有物理核共享

下图为 CPU-Core(TM)I7-10510U 型号缓存构造

存储器存储空间大小：内存 >L3>L2>L1> 寄存器。

存储器速度快慢排序：寄存器 >L1>L2>L3> 内存。

[root@192 ~]# getconf -a|grep CACHE
LEVEL1_ICACHE_SIZE                 32768 #L1 缓存大小
LEVEL1_ICACHE_ASSOC                8 #L1 缓存行大小
LEVEL1_ICACHE_LINESIZE             64
LEVEL1_DCACHE_SIZE                 32768
LEVEL1_DCACHE_ASSOC                8
LEVEL1_DCACHE_LINESIZE             64
LEVEL2_CACHE_SIZE                  262144 #L2 缓存大小
LEVEL2_CACHE_ASSOC                 4
LEVEL2_CACHE_LINESIZE              64 #L2 缓存行大小
LEVEL3_CACHE_SIZE                  8388608 #L3 缓存大小
LEVEL3_CACHE_ASSOC                 16
LEVEL3_CACHE_LINESIZE              64 #L3 缓存行大小
LEVEL4_CACHE_SIZE                  0
LEVEL4_CACHE_ASSOC                 0
LEVEL4_CACHE_LINESIZE              0
[root@192 ~]# cat /proc/cpuinfo |grep -i cache
cache size    : 8192 KB
cache_alignment    : 64
cache size    : 8192 KB
cache_alignment    : 64

JAVA 程序毫无疑问也必须是运行在硬件机器之上，如何利用底层硬件工作原理，晋升性能也必然是咱们须要思考的，笔者明天以无锁并发高性能框架 Disruptor 为例剖析如何高效的利用 CPU 缓存。

Disruptor 是一个开源框架，研发的初衷是为了解决高并发下队列锁的问题，最早由 LMAX（一种新型批发金融交易平台）提出并应用，可能在无锁的状况下实现队列的并发操作，并号称可能在一个线程里每秒解决 6 百万笔订单。

下方示例为 Disruptor 框架的外部代码：

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

剖析：

变量 p1~p7 自身没有实际意义，只能用于 缓存行填充，为了尽可能地用上CPU Cache！
拜访 CPU 里的 L1 Cache 或者 L2 Cache、L3 Cache，拜访延时是内存的 1 /15 乃至 1 /100（内存的访问速度，是远远慢于 CPU Cache 的）
- 因而，为了谋求极限性能，须要尽可能地从 CPU Cache 外面读取数据
CPU Cache 装载内存外面的数据，不是一个个字段加载的，而是加载一整个缓存行
- 64 位的 Intel CPU，缓存行通常是64 Bytes，一个 long 类型的数据须要 8 Bytes，因而会一下子加载 8 个 long 类型的数据

- 遍历数组元素速度很快，前面间断 7 次的数据拜访都会命中 CPU Cache，不须要从新从内存外面去读取数据

p1-p7 仅用来填充缓存行，咱们跟本用不到它，然而咱们为什么要填充斥一个缓存行呢？

CPU 在加载数据的时候，会把这个数据从内存加载到 CPU Cache 外面
此时，CPU Cache 外面除了这个数据，还会加载这个数据 前后定义 的其余变量
- 释义：在高并发场景下，假设并发拜访变量 p0，在 p0 后定义的其它变量也一并会被缓存 load
Disruptor 是一个 多线程 的服务器框架，在这个数据前后定义的其余变量，可能会被多个不同的线程去更新数据，读取数据
- 这些写入和读取申请，可能会来自于 不同的 CPU Core
- 为了保证数据的 同步更新 ，不得不把 CPU Cache 外面的数据， 从新写回 到内存外面或者从新从内存外面加载
- CPU Cache 的写回和加载，都是以整个Cache Line 作为单位的
如果常量的缓存生效，当再次读取这个值的时候，须要从新从内存读取，读取速度会大大变慢

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

abstract class RingBufferFields<E> extends RingBufferPad
{
    ...
    private final long indexMask;
    private final Object[] entries;
    protected final int bufferSize;
    protected final Sequencer sequencer;
    ...
}

public final class RingBuffer<E> extends RingBufferFields<E> implements Cursored, EventSequencer<E>, EventSink<E>
{
    ...
    protected long p1, p2, p3, p4, p5, p6, p7;
    ...
}

Disruptor 在 RingBufferFields 外面定义的变量前后别离定义了 7 个 long 类型的变量
- 后面 7 个继承自RingBufferPad，前面 7 个间接定义在RingBuffer类中
- 这 14 个变量 没有任何理论用处 ，既不会去读，也不会去写
RingBufferFields外面定义的变量都是 final 的，第一次写入之后就不会再进行批改
- 一旦被加载到 CPU Cache 之后，只有被 频繁地读取拜访 ，就 不会被换出 CPU Cache
- 无论在内存的什么地位，这些 变量所在的 Cache Line都不会有任何 写更新 的申请

Disruptor 整个框架是一个高速的生产者 - 消费者模型下的队列
- 生产者不停地往队列外面生产新的须要解决的工作
- 消费者不停地从队列外面解决掉这些工作
要实现一个队列，最合适的数据结构应该是链表，如 Java 中的LinkedBlockingQueue
Disruptor 并没有应用 LinkedBlockingQueue，而是应用了 RingBuffer 的数据结构
- RingBuffer的底层实现是一个 固定长度的数组
- 比起链表模式的实现，数组的数据在内存外面会存在空间局部性
  - 数组的间断多个元素会一并加载到 CPU Cache 外面，所以拜访遍历的速度会更快
  - 链表外面的各个节点的数据，多半不会呈现在相邻的内存空间
- 数据的遍历拜访还有一个很大的劣势，就是 CPU 层面的分支预测会很精确
  - 能够更无效地利用 CPU 外面的 多级流水线

Disruptor 作为一个高性能的生产者 - 消费者队列零碎，一个外围的设计：通过 RingBuffer 实现一个 无锁队列
Java 外面的LinkedBlockingQueue，比起 Disruptor 的 RingBuffer 要慢很多，次要起因
- 链表的数据在内存外面的布局对于 高速缓存 并不敌对
- LinkedBlockingQueue对于锁的依赖
  - 一般来说消费者比生产者快（不然队列会沉积），因为大部分时候，队列是空的，生产者和消费者一样会产生竞争
LinkedBlockingQueue的锁机制是通过ReentrantLock，须要 JVM 进行裁决
- 锁的抢夺，会把没有拿到锁的线程 挂起期待 ，也须要进行一次 上下文切换
- 上下文切换的过程，须要把以后执行线程的寄存器等信息，保留到内存中的线程栈外面
  - 象征：曾经加载到 高速缓存 外面的指令或者数据，又回到 主内存 外面，进一步拖慢性能

加锁很慢，所以 Disruptor 的解决方案是无锁（没有 操作系统 层面的锁）
Disruptor 利用了一个CPU 硬件反对的指令，称之为CAS（Compare And Swap）
Disruptor 的 RingBuffer 创立一个 Sequence 对象，用来指向以后的 RingBuffer 的头和尾
- 头和尾的标识，不是通过一个指针来实现的，而是通过一个序号
RingBuffer 在进行生产者和消费者之间的资源协调，采纳的是比照序号的形式
- 当生产者想要往队列外面退出新数据的时候，会把以后生产者的 Sequence 的序号，加上须要退出的新数据的数量
- 而后和理论的消费者所在的地位进行比照，看下队列里是不是有足够的空间退出这些数据
  - 而不是间接笼罩掉消费者还没解决完的数据
CAS 指令，既不是根底库里的一个函数，也不是操作系统外面实现的一个零碎调用，而是一个 CPU 硬件反对的机器指令
- 在 Intel CPU 上，为 cmpxchg 指令：compxchg [ax] (隐式参数，EAX 累加器), [bx] (源操作数地址), [cx] (指标操作数地址)
- 第一个操作数不在指令外面呈现，是一个隐式的操作数，即 EAX 累加寄存器 外面的值
- 第二个操作数就是源操作数，指令会比照这个操作数和下面 EAX 累加寄存器外面的值
- 伪代码：IF [ax]== [bx] THEN [ZF] = 1, [bx] = [cx] ELSE [ZF] = 0, [ax] = [bx]
- 单个指令是原子的，意味着应用 CAS 操作的时候，不须要独自进行加锁，间接调用即可

Sequence 要害代码 如下：

public long addAndGet(final long increment)
{
    long currentValue;
    long newValue;

    // 如果 CAS 操作没有胜利，会一直期待重试
    do
    {currentValue = get();
        newValue = currentValue + increment;
    }
    while (!compareAndSet(currentValue, newValue));

    return newValue;
}

public boolean compareAndSet(final long expectedValue, final long newValue)
{
    // 调用 CAS 指令
    return UNSAFE.compareAndSwapLong(this, VALUE_OFFSET, expectedValue, newValue);
}

互斥锁竞争、CAS 乐观锁与无锁测试：

public class LockBenchmark {

    private static final long MAX = 500_000_000L;

    private static void runIncrement() {
        long counter = 0;
        long start = System.currentTimeMillis();
        while (counter < MAX) {counter++;}
        long end = System.currentTimeMillis();
        System.out.println("Time spent is" + (end - start) + "ms without lock");
    }

    private static void runIncrementWithLock() {Lock lock = new ReentrantLock();
        long counter = 0;
        long start = System.currentTimeMillis();
        while (counter < MAX) {if (lock.tryLock()) {
                counter++;
                lock.unlock();}
        }
        long end = System.currentTimeMillis();
        System.out.println("Time spent is" + (end - start) + "ms with lock");
    }

    private static void runIncrementAtomic() {AtomicLong counter = new AtomicLong(0);
        long start = System.currentTimeMillis();
        while (counter.incrementAndGet() < MAX) { }
        long end = System.currentTimeMillis();
        System.out.println("Time spent is" + (end - start) + "ms with cas");
    }

    public static void main(String[] args) {runIncrement();
        runIncrementWithLock();
        runIncrementAtomic();

        // Time spent is 153ms without lock
        // Time spent is 7801ms with lock
        // Time spent is 3164ms with cas
        // 7801 / 153 ≈ 51
        // 3164 / 153 ≈ 21   
    }
}得出

论断：无锁性能要远高于 cas 与 lock，cas 要大于 lock

更多好文章，请关注公众号：奇客工夫，原创 JAVA 架构技术栈社区

关于java:计算机组成无锁编程追求极致性能

前言

缓存行大小

Who is Disruptor?

缓存行填充

缓存行生效

缓存行填充

空间局部性 + 分支预测

CAS 无锁

锁对性能的影响

RingBuffer 无锁计划

Benchmark