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，该字段由一个新的1024元素数组初始化。原因是我们希望在不同数量的线程之间分配等量的工作——我们希望程序能够扩展

然后启动每个线程，并测量所有线程完成所需的时间。我们会进行多次测量，以抵消任何与JIT相关的影响，如下所示。每个线程执行一个循环。在循环中，线程在偶数迭代中读取数组中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：接下来，我在线程的run方法中注释Foo[] arr = array行，并在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. 逃逸分析开始了吗？如果是这样的话，这是否意味着在CASE2中使用run方法创建时，整个数组都在堆栈上分配？这种运行时优化的确切条件是什么？当然，该数组没有在堆栈上分配100万个元素

2. 即使阵列是在堆栈上分配的，而不是在 堆，不同线程的两个数组访问应该至少除以512*4bytes=2kb，即使在情况1中，无论数组在哪里！这绝对比任何一级缓存线都大。如果这些影响是由于错误共享造成的，那么写入几个完全独立的缓存线怎么会对性能产生如此大的影响？（这里的一个假设是，每个阵列占用JVM上的一个连续内存块，该内存块在创建阵列时分配。我不确定这是否有效。另一个假设是，阵列写入不会一直到内存，而是一级缓存，因为Intel Xeon确实有一个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) {}
        }
    }

}