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-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. Even if the array is being allocated on the stack as opposed to being allocated on the heap, two array accesses by different threads should be divided by at least 512 * 4bytes = 2kb even in CASE1, wherever the arrays are! That’s definitely larger than any L1 cache-line. If these effects are due to false sharing, how can writes to several totally independent cache-lines affect performance this much? (One assumption here is that each array occupies a contiguous block of memory on the JVM, which is allocated when the array is created. I’m not sure this is valid. Another assumption is that array writes don’t go all the way to memory, but L1 cache instead, as Intel Xeon does have a ccNUMA architecture - correct me if I’m wrong)

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使用仅在JDK7中可用的标志运行JVM 。这样就解决了问题。

说明

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

因此，每次写入对象字段时，必须将卡表中相应卡的字节设置为脏。单线程程序中一个有用的优化方法是通过简单地标记相关字节来做到这一点-
每次都执行写操作。另一种方法是先检查是否设置了字节，然后执行条件写入，这需要额外的读取和条件跳转，这稍慢一些。

但是，如果有多个处理器写入存储器，则这种优化可能是灾难性的，因为写入相邻卡需要写入卡表中的相邻字节。因此，要写入的内存区域（上面数组中的条目）不在同一高速缓存行中，这是内存争用的常见原因。真正的原因是写入的脏字节在同一高速缓存行中。

上面的标志所做的是-它首先检查是否已设置字节，然后才进行设置，从而实现卡表脏字节写​​入。这样，内存争用仅发生在第一次写入该卡的过程中-
之后，仅发生对该缓存行的读取。由于仅读取高速缓存行，因此可以在多个处理器之间复制高速缓存行，并且它们不必同步即可读取它。

我观察到，在1线程的情况下，此标志会使运行时间增加15-20％。

-XX:+UseCondCardMark在此博客文章和此错误报告中说明了该标志。

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