前言

古代计算机通常由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 CACHELEVEL1_ICACHE_SIZE                 32768 #L1缓存大小LEVEL1_ICACHE_ASSOC                8 #L1缓存行大小LEVEL1_ICACHE_LINESIZE             64LEVEL1_DCACHE_SIZE                 32768LEVEL1_DCACHE_ASSOC                8LEVEL1_DCACHE_LINESIZE             64LEVEL2_CACHE_SIZE                  262144 #L2缓存大小LEVEL2_CACHE_ASSOC                 4LEVEL2_CACHE_LINESIZE              64 #L2缓存行大小LEVEL3_CACHE_SIZE                  8388608 #L3缓存大小LEVEL3_CACHE_ASSOC                 16LEVEL3_CACHE_LINESIZE              64 #L3缓存行大小LEVEL4_CACHE_SIZE                  0LEVEL4_CACHE_ASSOC                 0LEVEL4_CACHE_LINESIZE              0[root@192 ~]# cat /proc/cpuinfo |grep -i cachecache size    : 8192 KBcache_alignment    : 64cache size    : 8192 KBcache_alignment    : 64

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

Who is Disruptor?

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

缓存行填充

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

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

剖析：

  1. 变量p1~p7自身没有实际意义，只能用于缓存行填充，为了尽可能地用上CPU Cache！

  2. 拜访CPU里的L1 Cache或者L2 Cache、L3 Cache，拜访延时是内存的1/15乃至1/100（内存的访问速度，是远远慢于CPU Cache的）

    • 因而，为了谋求极限性能，须要尽可能地从CPU Cache外面读取数据

  3. CPU Cache装载内存外面的数据，不是一个个字段加载的，而是加载一整个缓存行

    • 64位的Intel CPU，缓存行通常是64 Bytes，一个long类型的数据须要8 Bytes，因而会一下子加载8个long类型的数据

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

缓存行生效

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

  1. CPU在加载数据的时候，会把这个数据从内存加载到CPU Cache外面

  2. 此时，CPU Cache外面除了这个数据，还会加载这个数据前后定义的其余变量

    • 释义：在高并发场景下，假设并发拜访变量p0，在p0后定义的其它变量也一并会被缓存load

  3. Disruptor是一个多线程的服务器框架，在这个数据前后定义的其余变量，可能会被多个不同的线程去更新数据，读取数据

    • 这些写入和读取申请，可能会来自于不同的CPU Core
    • 为了保证数据的同步更新，不得不把CPU Cache外面的数据，从新写回到内存外面或者从新从内存外面加载
    • CPU Cache的写回和加载，都是以整个Cache Line作为单位的
  4. 如果常量的缓存生效，当再次读取这个值的时候，须要从新从内存读取，读取速度会大大变慢

缓存行填充

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;    ...}

  1. Disruptor在RingBufferFields外面定义的变量前后别离定义了7个long类型的变量

    • 后面7个继承自RingBufferPad，前面7个间接定义在RingBuffer类中
    • 这14个变量没有任何理论用处，既不会去读，也不会去写

  2. RingBufferFields外面定义的变量都是final的，第一次写入之后就不会再进行批改

    • 一旦被加载到CPU Cache之后，只有被频繁地读取拜访，就不会被换出CPU Cache
    • 无论在内存的什么地位，这些变量所在的Cache Line都不会有任何写更新的申请

空间局部性+分支预测

  1. Disruptor整个框架是一个高速的生产者-消费者模型下的队列

    • 生产者不停地往队列外面生产新的须要解决的工作
    • 消费者不停地从队列外面解决掉这些工作
  2. 要实现一个队列，最合适的数据结构应该是链表，如Java中的LinkedBlockingQueue

  3. Disruptor并没有应用LinkedBlockingQueue，而是应用了RingBuffer的数据结构

    • RingBuffer的底层实现是一个固定长度的数组

    • 比起链表模式的实现，数组的数据在内存外面会存在空间局部性

      • 数组的间断多个元素会一并加载到CPU Cache外面，所以拜访遍历的速度会更快
      • 链表外面的各个节点的数据，多半不会呈现在相邻的内存空间

    • 数据的遍历拜访还有一个很大的劣势，就是CPU层面的分支预测会很精确

      • 能够更无效地利用CPU外面的多级流水线

CAS无锁

锁对性能的影响

  1. Disruptor作为一个高性能的生产者-消费者队列零碎，一个外围的设计：通过RingBuffer实现一个无锁队列

  2. Java外面的LinkedBlockingQueue，比起Disruptor的RingBuffer要慢很多，次要起因

    • 链表的数据在内存外面的布局对于高速缓存并不敌对

    • LinkedBlockingQueue对于锁的依赖

      • 一般来说消费者比生产者快（不然队列会沉积），因为大部分时候，队列是空的，生产者和消费者一样会产生竞争

  3. LinkedBlockingQueue的锁机制是通过ReentrantLock，须要JVM进行裁决

    • 锁的抢夺，会把没有拿到锁的线程挂起期待，也须要进行一次上下文切换

    • 上下文切换的过程，须要把以后执行线程的寄存器等信息，保留到内存中的线程栈外面

      • 象征：曾经加载到高速缓存外面的指令或者数据，又回到主内存外面，进一步拖慢性能

RingBuffer 无锁计划

  1. 加锁很慢，所以Disruptor的解决方案是无锁（没有操作系统层面的锁）
  2. Disruptor利用了一个CPU硬件反对的指令，称之为CAS（Compare And Swap）

  3. Disruptor的RingBuffer创立一个Sequence对象，用来指向以后的RingBuffer的头和尾

    • 头和尾的标识，不是通过一个指针来实现的，而是通过一个序号

  4. RingBuffer在进行生产者和消费者之间的资源协调，采纳的是比照序号的形式

    • 当生产者想要往队列外面退出新数据的时候，会把以后生产者的Sequence的序号，加上须要退出的新数据的数量

    • 而后和理论的消费者所在的地位进行比照，看下队列里是不是有足够的空间退出这些数据

      • 而不是间接笼罩掉消费者还没解决完的数据

  5. 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);}

Benchmark

互斥锁竞争、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架构技术栈社区