Java编程如何高效利用CPU缓存？
15 minutes read (About 2247 words) 0 visits

Java编程如何高效利用CPU缓存？

首先我们来看一个Java的例子:

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
/**
 * @author Shuai Junlan[shuaijunlan@gmail.com].
 * @since Created in 1:43 PM 1/17/19.
 */
public class ArrayTraverse {
    private static long[][] arrs = new long[1024*1024][8];
    public static void main(String[] args) {
        long temp = 0;
        long start = System.currentTimeMillis();

        // Vertical traverse
        for (int i = 0; i < 8; i ++){
            for (int j = 0; j < 1024 * 1024; j++){
                temp = arrs[j][i];
            }
        }
        System.out.println("Vertical traverse spending time: " + (System.currentTimeMillis() - start) + "ms");

        start = System.currentTimeMillis();
        // Horizontal traverse
        for (int i = 0; i < 1024 * 1024; i++){
            for (int j = 0; j < 8; j++){
                temp = arrs[i][j];
            }
        }
        System.out.println("Horizontal traverse spending time: " + (System.currentTimeMillis() - start) + "ms");
    }
}

上述代码中定义了一个二维数组，分别从横向遍历和纵向遍历了；两个方面来计算耗时，相信通过上面的代码大家也都能知道两种遍历方式耗时差距很大，结果确实是这样的：

1
2
Vertical traverse spending time: 75ms
Horizontal traverse spending time: 13ms

看上面的输出结果，耗时差距确实很大，但是为什么会有这个大的差距呢？显然跟我们这篇文章的题目有关，那就是横向遍历充分利用了CPU高速缓存机制，使得遍历速度要快于纵向遍历，那么……

什么是CPU缓存

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

当处理器发出内存访问请求时，会先查看缓存内是否有请求数据。如果存在（命中），则不经访问内存直接返回该数据；如果不存在（失效），则要先把内存中的相应数据载入缓存，再将其返回处理器。

缓存之所以有效，主要是因为程序运行时对内存的访问呈现局部性（Locality）特征。这种局部性既包括空间局部性（Spatial Locality），也包括时间局部性（Temporal Locality）。有效利用这种局部性，缓存可以达到极高的命中率。

在处理器看来，缓存是一个透明部件。因此，程序员通常无法直接干预对缓存的操作。但是，确实可以根据缓存的特点对程序代码实施特定优化，从而更好地利用缓存。—From 维基百科【CPU缓存】

现在主流的多核CPU缓存架构采用了三级缓存模式，如下图：

每个core共享L3 Cache，为什么要设计三级缓存可以参考这么文章《[译] 为什么 CPU 有多层缓存》，下面我们来详细说说，缓存与RAM如何进行数据交换的，数据传输的基本单位是什么？。

Cache Line（缓存行）

缓存行 (Cache Line) 便是 CPU Cache 中的最小单位，CPU Cache 由若干缓存行组成，一个缓存行的大小通常是 64 字节（这取决于 CPU），并且它有效地引用主内存中的一块地址。一个 Java 的 long 类型是 8 字节，因此在一个缓存行中可以存 8 个 long 类型的变量。

试想一下你正在遍历一个长度为 16 的 long 数组 data[16]，原始数据自然存在于主内存中，访问过程描述如下

  1. 访问 data[0]，CPU core 尝试访问 CPU Cache，未命中。
  2. 尝试访问主内存，操作系统一次访问的单位是一个 Cache Line 的大小 — 64 字节，这意味着：既从主内存中获取到了 data[0] 的值，同时将 data[0] ~ data[7] 加入到了 CPU Cache 之中，for free~
  3. 访问 data[1]~data[7]，CPU core 尝试访问 CPU Cache，命中直接返回。
  4. 访问 data[8]，CPU core 尝试访问 CPU Cache，未命中。
  5. 尝试访问主内存。重复步骤 2

CPU 缓存在顺序访问连续内存数据时挥发出了最大的优势。再回到文章的开头例子，为何横向遍历 arrs[1024 * 1024][8] 要比纵向遍历更快？此处得到了解答，正是更加友好地利用 CPU Cache 带来的优势，甚至有一个专门的词来修饰这种行为 —Mechanical Sympathy。

上面我们已经提到了，在多核CPU缓存架构中，缓存在多个线程共享某个缓存行的情况，这样就会导致False Sharing（伪共享）问题，下面我将详细介绍什么是False Sharing，以及为什么会产生False Sharing？

False Sharing（伪共享）

如果两个或多个处理器正在向同一缓存行的不同部分中写入数据，那么很多缓存和总线通信可能会导致其他处理器上的旧行的每个缓存副本失效或进行更新。这称为 “伪共享” 或者也称为 “CPU 缓存行干扰”。和两个或多个线程共享同一数据（因此需要程序化的同步机制来确保按顺序访问）的真正共享不同，当两个或多个线程访问位于同一缓存行上的无关数据时，就会产生伪共享。

关于具体的伪共享是如何产生的可以参考这篇文章《CPU cache结构和缓存一致性（MESI协议）》和《伪共享（false sharing），并发编程无声的性能杀手》。

Java中是如何避免伪共享的呢？

Java6 中实现字节填充

1
2
3
4
public class PaddingObject{
    public volatile long value = 0L;    // 实际数据
    public long p1, p2, p3, p4, p5, p6; // 填充
}

PaddingObject 类中需要保存一个 long 类型的 value 值，如果多线程操作同一个 CacheLine 中的 PaddingObject 对象，便无法完全发挥出 CPU Cache 的优势（想象一下你定义了一个 PaddingObject[] 数组，数组元素在内存中连续，却由于伪共享导致无法使用 CPU Cache 带来的沮丧）。

不知道你注意到没有，实际数据 value + 用于填充的 p1~p6 总共只占据了 7 * 8 = 56 个字节，而 Cache Line 的大小应当是 64 字节，这是有意而为之，在 Java 中，对象头还占据了 8 个字节，所以一个 PaddingObject 对象可以恰好占据一个 Cache Line。

Java7 中实现字节填充

在 Java7 之后，一个 JVM 的优化给字节填充造成了一些影响，上面的代码片段 public long p1, p2, p3, p4, p5, p6; 会被认为是无效代码被优化掉，又回归到了伪共享的窘境之中。

为了避免 JVM 的自动优化，需要使用继承的方式来填充。

1
2
3
4
5
6
7
abstract class AbstractPaddingObject{
    protected long p1, p2, p3, p4, p5, p6;// 填充
}

public class PaddingObject extends AbstractPaddingObject{
    public volatile long value = 0L;    // 实际数据
}

Java8中实现字节填充

Java8 中终于提供了字节填充的官方实现，这无疑使得 CPU Cache 更加可控了，无需担心 jdk 的无效字段优化，无需担心 Cache Line 在不同 CPU 下的大小究竟是不是 64 字节。使用 @Contended 注解可以完美的避免伪共享问题。

1
2
3
4
5
@Retention(RetentionPolicy.RUNTIME)
@Target({ElementType.FIELD, ElementType.TYPE})
public @interface Contended {
    String value() default "";
}

更多关于避免伪共享的一些Java实践可以参考《CPU Cache 与缓存行》。

最后

在这篇文章我们主要介绍了CPU高速缓存架构，多核CPU带来的伪共享问题以及Java实战中是如何利用CPU缓存来提高性能。

在这里，我想到了一问题，在软件系统架构中经常会用到缓存，那么是如何设计这个缓存的？跟CPU缓存架构有什么异同点？也请各位知道的在下方评论区中留言。

REFERENCE

# , ,
Java TreeMap源码分析
CAS and Lock-Free in Java

Comments

Follow

Tag Cloud

AQS Algorithm B+Tree CentOS DirectIO KVM LRU LeetCode Linux Micro Service MutliThread MyBatis3 MySQL Netty SPI Spring Spring Cloud TreeMap WebSystem cache cpu dubbo http java javassist log4j mmap nio zookeeper 网络配置 虚拟化

Links

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×