Java虚拟机上的数组分配和访问以及内存争用

Question

观察线程子类的以下定义(为方便起见,整个可运行的Java源文件包含在问题的末尾):

final class Worker extends Thread {
    Foo[] array = new Foo[1024];
    int sz;

    public Worker(int _sz) {
        sz = _sz;
    }

    public void run() {
        //Foo[] arr = new Foo[1024];
        Foo[] arr = array;
        loop(arr);
    }

    public void loop(Foo[] arr) {
        int i = 0;
        int pos = 512;
        Foo v = new Foo();
        while (i < sz) {
            if (i % 2 == 0) {
                arr[pos] = v;
                pos += 1;
            } else {
                pos -= 1;
                v = arr[pos];
            }
            i++;
        }
    }
}

说明:程序启动-Dpar此类线程,并在运行程序时sz将每个线程的设置设置为-Dsize / -Dpar,在何处-Dsize以及-Dpar通过命令行设置.每个线程对象都有一个array用1024new -element数组初始化的字段.原因是我们希望在不同数量的线程之间划分相同数量的工作 - 我们希望程序可以扩展.

然后启动每个线程并测量所有线程完成所需的时间.我们进行多次测量以抵消任何与JIT相关的影响,如下所示.每个线程都循环.在循环内,线程512在偶数迭代中读取数组中位置的元素,并512在奇数迭代中写入相同的元素.否则只修改局部变量.

完整的计划如下.

分析:

测试-verbose:gc- 在此程序运行期间没有发生垃圾收集.

运行命令:

java -Xmx512m -Xms512m -server -Dsize=500000000 -Dpar=1 org.scalapool.bench.MultiStackJavaExperiment 7

情况1:1,2,4,8线程的运行时间,按顺序(7次重复):

>>> All running times: [2149, 2227, 1974, 1948, 1803, 2283, 1878]
>>> All running times: [1140, 1124, 2022, 1141, 2028, 2004, 2136]
>>> All running times: [867, 1022, 1457, 1342, 1436, 966, 1531]
>>> All running times: [915, 864, 1245, 1243, 948, 790, 1007]

我的想法是非线性缩放是由于内存争用.顺便提一下,早期的迭代实际上做得更好 - 这可能是由于在不同的迭代中数组被分配在不同的存储区域中.

情况2:接下来,我在线程方法中注释该Foo[] arr = array行,run并在run方法本身中分配一个新数组:Foo[] arr = new Foo[1024].测量:

>>> All running times: [2053, 1966, 2089, 1937, 2046, 1909, 2011]
>>> All running times: [1048, 1178, 1100, 1194, 1367, 1271, 1207]
>>> All running times: [578, 508, 589, 571, 617, 643, 645]
>>> All running times: [330, 299, 300, 322, 331, 324, 575]

这一次,一切都像预期的那样扩展.我不会想到分配数组的位置起任何作用,但显然它确实以某种方式.我的想法是,之前分配的阵列彼此如此接近,以至于发生了一些内存争用.

情况3:为了验证这个假设,我Foo[] arr = array再次取消注释该行,但是这次将array字段初始化new Foo[32000]为确保写入的内存中的位置彼此相距足够远.所以,这里我们再次使用在创建线程对象期间分配的数组,与CASE1的区别仅在于数组更大.

>>> All running times: [2113, 1983, 2430, 2485, 2333, 2359, 2463]
>>> All running times: [1172, 1106, 1163, 1181, 1142, 1169, 1188]
>>> All running times: [578, 677, 614, 604, 583, 637, 597]
>>> All running times: [343, 327, 320, 330, 353, 320, 320]

因此,内存争用似乎是导致这种情况的原因.

平台信息:

Ubuntu Server 10.04.3 LTS
8 core Intel(R) Xeon(R) CPU  X5355  @2.66GHz
~20GB ram
java version "1.6.0_26"
Java(TM) SE Runtime Environment (build 1.6.0_26-b03)
Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02, mixed mode)

问题:这显然是一个内存争用问题.但为什么会这样呢？

1. 逃脱分析是否正在进行？如果是这样,是否意味着run在CASE2 中的方法中创建时,整个数组是否在堆栈上分配？此运行时优化的确切条件是什么？当然,数组没有在堆栈上分配100万个元素？

2. 即使数组是在堆栈上分配而不是在堆上分配,不同线程的两个数组访问应该被划分至少512*4bytes = 2kb,即使在CASE1中,无论数组在哪里!这绝对比任何L1缓存行都要大.如果这些影响是由于错误共享造成的,那么如何写入几个完全独立的缓存行会影响性能呢？(这里的一个假设是每个数组占用JVM上的一个连续的内存块,它在创建数组时分配.我不确定它是否有效.另一个假设是数组写入不会一直到内存,但L1缓存,因为英特尔至强确实有一个ccNUMA架构 - 纠正我,如果我错了)

3. 是否有可能每个线程都有自己的本地堆部分,它独立地分配新对象,这是在线程中分配数组时导致较低争用的原因？如果是这样,如果引用被共享,那么堆垃圾的收集区域如何？

4. 为什么增加数组大小到~32000个元素提高了可伸缩性(减少了内存争用)？内存层次结构到底是什么原因造成的？

请准确并通过参考支持您的声明.

谢谢!

---

整个可运行的Java程序:

import java.util.ArrayList;

class MultiStackJavaExperiment {

    final class Foo {
        int x = 0;
    }

    final class Worker extends Thread {
        Foo[] array = new Foo[1024];
        int sz;

        public Worker(int _sz) {
            sz = _sz;
        }

        public void run() {
            Foo[] arr = new Foo[1024];
            //Foo[] arr = array;
            loop(arr);
        }

        public void loop(Foo[] arr) {
            int i = 0;
            int pos = 512;
            Foo v = new Foo();
            while (i < sz) {
                if (i % 2 == 0) {
                    arr[pos] = v;
                    pos += 1;
                } else {
                    pos -= 1;
                    v = arr[pos];
                }
                i++;
            }
        }
    }

    public static void main(String[] args) {
        (new MultiStackJavaExperiment()).mainMethod(args);
    }

    int size = Integer.parseInt(System.getProperty("size"));
    int par = Integer.parseInt(System.getProperty("par"));

    public void mainMethod(String[] args) {
        int times = 0;
        if (args.length == 0) times = 1;
        else times = Integer.parseInt(args[0]);
        ArrayList < Long > measurements = new ArrayList < Long > ();

        for (int i = 0; i < times; i++) {
            long start = System.currentTimeMillis();
            run();
            long end = System.currentTimeMillis();

            long time = (end - start);
            System.out.println(i + ") Running time: " + time + " ms");
            measurements.add(time);
        }

        System.out.println(">>>");
        System.out.println(">>> All running times: " + measurements);
        System.out.println(">>>");
    }

    public void run() {
        int sz = size / par;
        ArrayList < Thread > threads = new ArrayList < Thread > ();

        for (int i = 0; i < par; i++) {
            threads.add(new Worker(sz));
            threads.get(i).start();
        }
        for (int i = 0; i < par; i++) {
            try {
                threads.get(i).join();
            } catch (Exception e) {}
        }
    }

}

Answer 1

解

使用-XX:+UseCondCardMark标志运行JVM ,仅在JDK7中可用.这解决了这个问题.

说明

实质上,大多数托管堆环境使用卡表来标记发生写入的内存区域.一旦写入发生,这种存储区域在卡表中被标记为脏.垃圾收集需要此信息 - 不必扫描非脏存储区域的引用.卡是连续的内存块,通常为512字节.卡表通常每个卡有1个字节 - 如果设置了该字节,则卡是脏的.这意味着具有64字节的卡表覆盖64*512字节的内存.通常,今天的缓存行大小为64字节.

因此,每次发生对象字段的写入时,必须将卡表中相应卡的字节设置为脏.单线程程序中有用的优化是通过简单地标记相关字节来做到这一点 - 每次都写一次.首先检查字节是否设置和条件写入的替代方案需要额外的读取和条件跳转,这稍微慢一些.

然而,在存在多个处理器写入存储器的情况下,这种优化可能是灾难性的,因为被写入的相邻卡需要写入卡表中的相邻字节.因此写入的内存区域(上面数组中的条目)不在同一缓存行中,这是内存争用的常见原因.真正的原因是写入的脏字节位于同一缓存行中.

上面标志的作用是 - 它通过首先检查字节是否已经设置来实现卡表脏字节写​​入,并且只有在不设置时才设置它.这样,内存争用仅在第一次写入该卡时发生 - 在此之后,仅发生对该缓存行的读取.由于只读取缓存行,因此可以跨多个处理器复制它们,并且它们不必同步即可读取它.

我观察到这个标志在1线程的情况下增加了大约15-20%的运行时间.

该博客文章和此错误报告中-XX:+UseCondCardMark解释了该标志.

相关的并发邮件列表讨论:JVM上的数组分配和访问.