庄周梦蝶

生活、程序、未来

声明:本博客所有文章,未经允许,禁止转载。谢谢。

Java 与 CPU 高速缓存

| Comments

上周在公司临时做了个小分享,科普了下 CPU 高速缓存,以及 Java 程序员应该关注的问题,比如利用时空局部性原理,避免多核下的伪共享(False Sharing)等,因为是下午临时写的 PPT,可能有一些谬误,有兴趣的不妨看看

或者直接看链接: http://www.slideshare.net/killme2008/java-cpu-64198539

最近关注这个问题是因为在阅读《现代体系结构上的 Unix 系统——内核程序员的对称处理和缓存技术》一书,这是伞哥推荐的书,确实非常棒,澄清了我很多概念,推荐有兴趣的朋友阅读下。

Java 里伪共享的问题(False Sharing)已经被谈论了很多,甚至 Java8 都引入了 @Contended来帮助你做数据对齐,但是还有一个问题似乎没什么人谈过,那就是在获得自旋锁时减少对高速缓存行的争用,为了说明这个问题,我写了个例子:

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
81
82
83
84
85
86
87
88
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.atomic.AtomicInteger;

public class BusyLock {

  private int count;
  // 自旋锁状态
  private AtomicInteger state;

  private BusyLock() {
      this.count = 0;
      this.state = new AtomicInteger(0);
  }

  /**
  * 利用 CAS 实现自旋锁
  */
  private void lock() {
      while (!state.compareAndSet(0, 1))
          ;
  }

  /**
  * 解锁
  */
  private void unlock() {
      state.set(0);
  }

  /**
  * 递增 count,使用自旋锁保护 count
  */
  public void incr() {
      lock();
      count = count + 1;
      unlock();
  }

  /**
  * 测试,开启 50 个线程递增 count,每个线程循环 10 万次。
  * 
  * @param warnUp
  * @throws Exception
  */
  public static void runTests(boolean warnUp) throws Exception {
      int threads = 50;
      int n = 100000;
      BusyLock bl = new BusyLock();
      Thread[] ts = new Thread[threads];
      long start = System.nanoTime();
      CyclicBarrier barrier = new CyclicBarrier(threads + 1);
      for (int i = 0; i < threads; i++) {
          ts[i] = new Thread(new Runnable() {

              @Override
              public void run() {
                  try {
                      barrier.await();
                      for (int j = 0; j < n; j++)
                          bl.incr();
                      barrier.await();
                  } catch (Exception e) {

                  }
              }
          });
          ts[i].start();
      }
      barrier.await();
      barrier.await();
      for (Thread t : ts) {
          t.join();
      }
      long duration = (System.nanoTime() - start) / 1000000;
      if (!warnUp)
          System.out.println("count= " + bl.count + ",cost:" + duration
                  + "ms");

  }

  public static void main(String[] args) throws Exception {
      // 测试,先 warm up
      runTests(true);
      // 实际测试
      runTests(false);
  }

}

代码稍微注释了下,熟悉 Java 类库的都应该可以理解。为了演示这个问题,这里没有用 ReentrantLock,而是使用 AtomicInteger 来实现自旋锁保护 count 这个资源,incr 方法会递增 count,启动 50 个线程并发循环调用 incr,然后计算耗时。

我们关注的是 lock 方法的实现:

1
2
3
4
private void lock() {
  while (!state.compareAndSet(0, 1))
      ;
}

利用 compareAndSet 来尝试更新 state,1 表示锁定状态,0 表示空闲,每个线程都尝试去取得锁的所有权,如果失败,进入 while 忙等待。compare-and-set 都是利用 CPU 提供的原子指令(一般是 test_and_set)来实现。

这个实现没有问题,但是当考虑到多核状态下的高速缓存的时候,如果对于锁的争用非常激烈,那么会有很多的线程在 while 上的 compareAndSet 原子操作上等待,保存 state 的缓存行就会在多个 CPU 之间『颠簸』,导致了不必要的总线争用。

为了减少总线争用,我们可以改进下 lock:

1
2
3
4
5
6
7
8
private void lock() {
  while (!state.compareAndSet(0, 1))
      //对于未能取得锁所有权的线程,在内层循环上等待
      //因为获取了 state 一份共享的高速缓存副本,
      //不会再进一步产生总线通信量
      while (state.get() == 1)
          ;
}

通过增加一个内循环 while (state.get() == 1),让没有获得锁的线程在 state 状态上等待,避免原子操作,可以减少总线争用。每个忙等待的 CPU 都将获得 state 状态的共享副本,以后的循环都将在共享副本上执行,不会再产生总线通信。

当占有锁的线程释放锁(原子地设置 state 为 0)的时候,这些共享的副本会失效(write-invalidate 策略,比如常见的 MESI 协议)或者被更新到最新状态(write-update 策略),这时候才会产生总线通信。

测试两个版本的 lock 方法,在我的机器上有比较明显的差异,没有内层循环的 lock 版本耗时在 6-8 秒,而增加了内层循环的 lock 耗时在 2.5 -5 秒。

声明:本博客所有文章,未经允许,禁止转载。谢谢。

cache, java, 性能

« Clojure method missing 迷思 Xmemcached 2.0.1 is out! »

Comments