Выделение массивов и доступ к ним на виртуальной машине Java и конфликт памяти
Обратите внимание на следующее определение подкласса потока (весь исполняемый исходный файл 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 устанавливаются через командная строка при запуске программы. Каждый объект потока имеет массив полей , который инициализируется новым массивом 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]
Итак, причиной этого, похоже, является нехватка памяти.
Информация о платформе:
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)
Вопрос : Очевидно, это проблема нехватки памяти.Но почему это происходит?
Начинается ли анализ побега? Если да, означает ли это, что весь массив размещается в стеке при создании в методе
runв CASE2? Каковы точные условия этой оптимизации времени выполнения? Разве массив не выделяется в стеке для 1 миллиона элементов?Даже если массив размещается в стеке, а не в стеке. heap, два доступа к массиву разными потоками должны быть разделены как минимум на 512 * 4 байта = 2 КБ даже в CASE1, где бы ни находились массивы! Это определенно больше, чем любая строка кэша L1. Если эти эффекты вызваны ложным совместным использованием, как запись в несколько полностью независимых строк кэша может так сильно повлиять на производительность? (Одно из предположений заключается в том, что каждый массив занимает непрерывный блок памяти на JVM,который выделяется при создании массива. Я не уверен, что это правда. Другое предположение состоит в том, что записи массива идут не полностью в память, а в кеш L1, поскольку Intel Xeon имеет архитектуру ccNUMA - поправьте меня, если я ошибаюсь)
Возможно ли, что каждый поток имеет свой собственный часть локальной кучи, в которой он независимо выделяет новые объекты, и это является причиной меньшего количества конфликтов, когда массив выделяется в потоке? Если да, то как эта область кучи мусора собирается, если ссылки становятся общими?
Почему увеличение размера массива до ~ 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) {}
}
}
}