Распределение массива и доступ на виртуальной машине 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 в массиве в четных итерациях и записывает тот же элемент в 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]

Таким образом, нехватка памяти кажется причинойthis.

Информация о платформе:

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?Каковы точные условия для этой оптимизации времени выполнения?Конечно, массив не выделен в стеке для 1 миллиона элементов?

2. Даже если массив размещается в стеке, а не в куче, два массива обращаются к разнымпотоки должны быть разделены не менее чем на 512 * 4 байта = 2 КБ даже в CASE1, где бы ни находились массивы!Это определенно больше, чем любая строка кэша L1.Если эти эффекты связаны с ложным разделением, как записи в несколько полностью независимых строк кэша могут так сильно повлиять на производительность?(Одно из предположений здесь состоит в том, что каждый массив занимает непрерывный блок памяти в JVM, который выделяется при создании массива. Я не уверен, что это допустимо. Другое предположение состоит в том, что записи в массив не идут полностьюпамять, но вместо этого кэш L1, поскольку 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) {}
        }
    }

}

Answer 1

Решение

Запустите JVM с флагом -XX:+UseCondCardMark, доступным только в JDK7.Это решает проблему.

Объяснение

По существу, большинство сред с управляемой кучей используют таблицы карт для разметки областей памяти, в которые происходили записи.Такие области памяти помечаются как грязные в таблице карточек, когда происходит запись.Эта информация необходима для сборки мусора - ссылки на незапятнанные области памяти не нужно сканировать.Карта - это непрерывный блок памяти, обычно 512 байт.Таблица карт обычно имеет 1 байт для каждой карты - если этот байт установлен, карта загрязнена.Это означает, что карточный стол с 64 байтами занимает 64 * 512 байтов памяти.Как правило, размер строки кэша сегодня составляет 64 байта.

Таким образом, каждый раз, когда происходит запись в поле объекта, байт соответствующей карты в таблице карт должен быть установлен как грязный.Полезная оптимизация в однопоточных программах заключается в том, чтобы сделать это, просто пометив соответствующий байт - каждый раз производите запись.Альтернатива первой проверки, установлен ли байт и требует ли условная запись дополнительного чтения и условного перехода, который немного медленнее.

Однако эта оптимизация может иметь катастрофические последствия в случае записи нескольких процессоров.в память, поскольку соседние карты записываются, чтобы требовать записи в соседние байты в таблице карт.Таким образом, область памяти, в которую записывается (запись в массиве выше), не находится в той же строке кэша, что является обычной причиной конфликта памяти.Настоящая причина в том, что записанные грязные байты находятся в одной и той же строке кэша.

То, что делает вышеупомянутый флаг, - это реализует грязную запись таблицы карт, сначала проверяя, установлен ли уже байт,и установить его, только если это не так.Таким образом, конфликт памяти происходит только во время первой записи на эту карту - после этого происходят только чтения в эту строку кэша.Поскольку строка кэша только для чтения, она может быть реплицирована на несколько процессоров, и им не нужно синхронизироваться для чтения.

Я заметил, что этот флаг увеличивает время выполнения примерно на 15-20%.в случае с 1 потоком.

Флаг -XX:+UseCondCardMark объясняется в этом сообщении в блоге и в этом сообщении об ошибке .

Соответствующий параллелизмобсуждение списка рассылки: Распределение массива и доступ к JVM .

Answer 2

Я считаю, что вам нужно уменьшить свой код, чтобы он не делал много случайных вещей, которые могли бы сбить с толку.После сокращения кода мне становится ясно, что вы каждый раз обращаетесь к одному и тому же массиву.то есть позиция 512.

Если вы минимизируете свой код, повторно используйте ваши потоки, чтобы не останавливать / запускать их, вы получите гораздо более воспроизводимые результаты.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class MultiStackJavaExperiment {
    static final int size = Integer.getInteger("size", 500000000);

    public static void main(String... args) throws ExecutionException, InterruptedException {
        int par = 8;
        for (int s = 64; s <= 64 * 1024; s *= 2) {
            int times = args.length == 0 ? 1 : Integer.parseInt(args[0]);
            long[] measurements = new long[times];

            ExecutorService es = Executors.newFixedThreadPool(par);
            List<Future<?>> futures = new ArrayList<Future<?>>(times);
            for (int i = 0; i < times; i++) {
                long start = System.currentTimeMillis();
                final int sz = size / par;
                futures.clear();
                for (int j = 0; j < par; j++) {
                    final Object[] arr = new Object[s];
                    futures.add(es.submit(new Runnable() {
                        @Override
                        public void run() {
                            final int bits = 7, arraySize = 1 << bits;
                            int i = 0;
                            int pos = 32;
                            Object v = new Object();
                            while (i < sz) {
                                if (i % 2 == 0) {
                                    arr[pos] = v;
                                    pos += 1;
                                } else {
                                    pos -= 1;
                                    v = arr[pos];
                                }
                                i++;
                            }
                        }
                    }));
                }
                for (Future<?> future : futures)
                    future.get();

                long time = System.currentTimeMillis() - start;
//                System.out.println(i + ") Running time: " + time + " ms");
                measurements[i] = time;
            }
            es.shutdown();
            System.out.println("par = " + par + " arr.length= "+ s  + " >>> All running times: " + Arrays.toString(measurements));
        }
    }
}

это показывает расстояние между значениями доступавопросы.Выделяя массив каждому потоку, вы используете разные TLAB (которые распределяют данные в блоках)

par = 8 arr.length= 64 >>> All running times: [539, 413, 444, 444, 457, 444, 456]
par = 8 arr.length= 256 >>> All running times: [398, 527, 514, 529, 445, 441, 445]
par = 8 arr.length= 1024 >>> All running times: [419, 507, 477, 422, 412, 452, 396]
par = 8 arr.length= 4096 >>> All running times: [316, 282, 250, 232, 242, 229, 238]
par = 8 arr.length= 16384 >>> All running times: [316, 207, 209, 212, 208, 208, 208]
par = 8 arr.length= 65536 >>> All running times: [211, 211, 208, 208, 208, 291, 206]
par = 8 arr.length= 262144 >>> All running times: [366, 210, 210, 210, 210, 209, 211]
par = 8 arr.length= 1048576 >>> All running times: [296, 211, 215, 216, 213, 211, 211]

если вы перемещаете массив внутри потока, вы получаете

par = 8 arr.length= 64 >>> All running times: [225, 151, 151, 150, 152, 153, 152]
par = 8 arr.length= 256 >>> All running times: [155, 151, 151, 151, 151, 151, 155]
par = 8 arr.length= 1024 >>> All running times: [153, 152, 151, 151, 151, 155, 152]
par = 8 arr.length= 4096 >>> All running times: [155, 156, 151, 152, 151, 155, 155]
par = 8 arr.length= 16384 >>> All running times: [154, 157, 152, 152, 158, 153, 153]
par = 8 arr.length= 65536 >>> All running times: [155, 157, 152, 184, 181, 154, 153]
par = 8 arr.length= 262144 >>> All running times: [240, 159, 166, 151, 172, 154, 160]
par = 8 arr.length= 1048576 >>> All running times: [165, 162, 163, 162, 163, 162, 163]

Turnс tlab с -XX:-UseTLAB и тот же код дает syou

par = 8 arr.length= 64 >>> All running times: [608, 467, 467, 457, 468, 461, 428]
par = 8 arr.length= 256 >>> All running times: [437, 437, 522, 512, 522, 369, 535]
par = 8 arr.length= 1024 >>> All running times: [394, 395, 475, 525, 470, 440, 478]
par = 8 arr.length= 4096 >>> All running times: [347, 215, 238, 226, 236, 204, 271]
par = 8 arr.length= 16384 >>> All running times: [291, 157, 178, 151, 150, 151, 152]
par = 8 arr.length= 65536 >>> All running times: [163, 152, 162, 151, 159, 159, 154]
par = 8 arr.length= 262144 >>> All running times: [164, 172, 152, 169, 160, 161, 160]
par = 8 arr.length= 1048576 >>> All running times: [295, 153, 164, 153, 166, 154, 163]