Соблюдайте следующее определение подкласса потока (весь исходный исходный файл 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
CASE 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]
Я думал, что нелинейное масштабирование связано с конфликтом памяти. Кстати, ранние итерации действительно лучше - это может быть связано с тем, что в разных итерациях массивы выделяются в разных областях памяти.
CASE 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]
На этот раз все масштабируется так, как ожидалось. Я бы не подумал, что место, где был выделен массив, играет какую-то роль, но, очевидно, это как-то. Моя мысль заключалась в том, что массивы ранее были распределены так близко друг к другу, что возникло конфликт памяти.
CASE 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 миллион элементов? -
Даже если массив выделяется в стеке, а не выделяется на куча, два обращения к массиву различными потоками должны быть разделены по меньшей мере на 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) {}
}
}
}
