Здравствуйте, Безон, Вы писали:
Б>Тест замечательный. И действительно показывает, что при полной изоляции данных для алгоритмов, параллельное их выполнение не ведет к сильному просаживанию производительности. Правда немного смущает использование Atomic при гарантированно однопоточном доступе.
Б>Однако когда алгоритмы работают над разделяемыми данными, а тем более их модифицируют, вот тогда производительность упадет значительно больше. Насколько больше сказать не могу пока не будет теста.
При полной изоляции данных — каждый поток будет обновлять кэш данных процессора (а возможно и кэш кода), а это процедура более затратная чем переключение контекста. Как раз, полагаю, желательно для массивных по данным вычислений (обработка аудио, видео, фото, работа с большими текстами) желательно иметь максимальное кол-во общих данных на чтение. Для записи использовать какие-то неблокирующие разделяемые структуры (так понимаю обращение к атомарным переменным занимает порядка 100-200циклов). Т.е., например, для декодирования JPG в массив цветов, думаю разумнее не делить одному потоку первые 1000 квадратов, второму — вторую тысячу, а как раз динамически выделять каждому по запросу, скажем, по 10 квадратов подряд.
Само по себе переключение контекста в "чистом виде" занимает порядка 2.000-4.000 тактов процессора.
Заметно больше может уходить на сопутствующие процессы. Например, на повторную загрузку кэшей процессора данными и кодом, которые были вытеснены другими потоками.
Следственный эксперимент: класс PingPong запускает два класса Player, а они перебрасываются классом Item.
Item содержит простой счетчик типа int, считающий количество передач. Передачи осуществляются через механизм wait()/notify().
Кроме того, каждый поток пробегает по одному из массивов (считывает каждый 16-ый елемент для подгрузки массива в кэш) (четный поток читает cache_1, нечетный — cache_0).
На тестовом компьютере (AMD Duron 1300(L1_cache size=64K+64K(code+data), L2_cache size=64K), WinXP, jdk 1.0.6_13) размер кэша первого уровня для данных 64К.
Эксперимент показывает, что оптимальная производительность достигается в том случае, когда каждый поток использует массивы интов по 8192(т.е. 2 массива по 32Кб) (deltaTime/cacheSize: 779640) и производительность в 7.24 раза хуже при использовании массивово интов по 16384(т.е. 2 массива по 64Кб) (deltaTime/cacheSize: 5643590).
Во втором случае каждый из потоков полностью загружает кэш данных первого уровня своими данными выталкивая данные другого.
// в коде все размеры в интах, т.е. размеры в байтах в 4 раза больше
Результаты:
cacheSize: 2048 deltaTime: 3064966357 deltaTime/cacheSize: 1496565
cacheSize: 3072 deltaTime: 3460753253 deltaTime/cacheSize: 1126547
cacheSize: 4096 deltaTime: 4406545804 deltaTime/cacheSize: 1075816
cacheSize: 5120 deltaTime: 5075649838 deltaTime/cacheSize: 991337
cacheSize: 6144 deltaTime: 5553419778 deltaTime/cacheSize: 903876
cacheSize: 7168 deltaTime: 5848771562 deltaTime/cacheSize: 815955
cacheSize: 8192 deltaTime: 6386814526 deltaTime/cacheSize: 779640
cacheSize: 9216 deltaTime: 8158033214 deltaTime/cacheSize: 885203
cacheSize: 10240 deltaTime: 9952118216 deltaTime/cacheSize: 971886
cacheSize: 11264 deltaTime: 11804108903 deltaTime/cacheSize: 1047950
cacheSize: 12288 deltaTime: 14448519295 deltaTime/cacheSize: 1175823
cacheSize: 13312 deltaTime: 17866376034 deltaTime/cacheSize: 1342125
cacheSize: 14336 deltaTime: 28771726853 deltaTime/cacheSize: 2006956
cacheSize: 15360 deltaTime: 52159304604 deltaTime/cacheSize: 3395788
cacheSize: 16384 deltaTime: 92464582510 deltaTime/cacheSize: 5643590
Дополнительный эксперимент. Просто так, под рукой был код и я решил продемонстрировать как выглядят размеры кэшей с точки зрения явиста
:
Пусть оба потока работают с одним массивом и покажем что в тот момент когда массив перестает влезать в кэш происходит катастрофическое падение производительности.
Модифицируем строки
PingPong.java:
public static final int ARRAY_LENGTH = 16 * 1024;
заменим на
public static final int ARRAY_LENGTH = 32 * 1024;
for (int cacheSize = 2 * 1024; cacheSize <= 16 * 1024; cacheSize += 1 * 1024) {
заменим на
for (int cacheSize = 2 * 1024; cacheSize <= 32 * 1024; cacheSize += 1 * 1024) {
Player.java:
int[] cache = imOdd ? PingPong.cache_0 : PingPong.cache_1; // different players choice different arrays
заменим на
int[] cache = PingPong.cache_0;
Результаты:
cacheSize: 2048 deltaTime: 3072664821 deltaTime/cacheSize: 1500324
cacheSize: 3072 deltaTime: 3449649327 deltaTime/cacheSize: 1122932
cacheSize: 4096 deltaTime: 3889106856 deltaTime/cacheSize: 949488
cacheSize: 5120 deltaTime: 4214458821 deltaTime/cacheSize: 823136
cacheSize: 6144 deltaTime: 4461290751 deltaTime/cacheSize: 726121
cacheSize: 7168 deltaTime: 4962198827 deltaTime/cacheSize: 692271
cacheSize: 8192 deltaTime: 5531942747 deltaTime/cacheSize: 675285
cacheSize: 9216 deltaTime: 6190682336 deltaTime/cacheSize: 671732
cacheSize: 10240 deltaTime: 6941616882 deltaTime/cacheSize: 677892
cacheSize: 11264 deltaTime: 7272263374 deltaTime/cacheSize: 645619
cacheSize: 12288 deltaTime: 7696612279 deltaTime/cacheSize: 626351
cacheSize: 13312 deltaTime: 8569552275 deltaTime/cacheSize: 643746
cacheSize: 14336 deltaTime: 9151158038 deltaTime/cacheSize: 638334
cacheSize: 15360 deltaTime: 10124464423 deltaTime/cacheSize: 659144
cacheSize: 16384 deltaTime: 10504098146 deltaTime/cacheSize: 641119
cacheSize: 17408 deltaTime: 12899692838 deltaTime/cacheSize: 741020
cacheSize: 18432 deltaTime: 15345301987 deltaTime/cacheSize: 832535
cacheSize: 19456 deltaTime: 17966401317 deltaTime/cacheSize: 923437
cacheSize: 20480 deltaTime: 20462613265 deltaTime/cacheSize: 999151
cacheSize: 21504 deltaTime: 22766556922 deltaTime/cacheSize: 1058712
cacheSize: 22528 deltaTime: 25043635714 deltaTime/cacheSize: 1111667
cacheSize: 23552 deltaTime: 27430734074 deltaTime/cacheSize: 1164688
cacheSize: 24576 deltaTime: 33005879518 deltaTime/cacheSize: 1343012
cacheSize: 25600 deltaTime: 34585078551 deltaTime/cacheSize: 1350979
cacheSize: 26624 deltaTime: 37485102715 deltaTime/cacheSize: 1407944
cacheSize: 27648 deltaTime: 43297514070 deltaTime/cacheSize: 1566026
cacheSize: 28672 deltaTime: 53516617894 deltaTime/cacheSize: 1866511
cacheSize: 29696 deltaTime: 85726250403 deltaTime/cacheSize: 2886794
cacheSize: 30720 deltaTime: 115445316653 deltaTime/cacheSize: 3757985
cacheSize: 31744 deltaTime: 148583765255 deltaTime/cacheSize: 4680688
cacheSize: 32768 deltaTime: 184068212581 deltaTime/cacheSize: 5617316
Видно, что при размере массива 16384(64К) производительность(641119) близка к оптимальной(626351), а при при размере массива 32768(128К) производительность(5617316) ухудшилась в 8.76 раз.
При чем ухудшение началось ровно в тот момент, как массив перестал помещаться в кэш (переход от 16384 елементов к 17408 елементов и ухудшение производительности 1.16 раза).
Исходный код:
public class Item {
int counter = 0;
}
public class PingPong {
// constant
public static final int ITERATION_COUNT = 1000000;
public static final int ARRAY_LENGTH = 16 * 1024;
public static final int CACHE_INDEX_STEP = 16;
// global variables :(
public static int[] cache_0 = new int[ARRAY_LENGTH]; // 64K (size(int) = 4)
public static int[] cache_1 = new int[ARRAY_LENGTH]; // 64K (size(int) = 4)
public static Item item;
public static CountDownLatch start;
public static CountDownLatch stop;
public static void main(String[] args) throws InterruptedException {
for (int cacheSize = 2 * 1024; cacheSize <= 16 * 1024; cacheSize += 1 * 1024) {
// init section
item = new Item();
start = new CountDownLatch(1);
stop = new CountDownLatch(2);
new Thread(new Player(cacheSize, false)).start();
new Thread(new Player(cacheSize, true)).start();
// work section
long startTime = System.nanoTime();
start.countDown();
stop.await();
long deltaTime = System.nanoTime() - startTime;
// info-to-console section
System.out.println("cacheSize: " + cacheSize + " deltaTime: " + deltaTime + " deltaTime/cacheSize: " + deltaTime/cacheSize);
}
}
}
public class Player implements Runnable {
private final int cacheSize;
private final boolean imOdd;
public Player(int cacheSize, boolean imOdd) {
this.cacheSize = cacheSize;
this.imOdd = imOdd;
}
public void run() {
// await for start ping-ponging
try {
PingPong.start.await();
} catch (InterruptedException e) {e.printStackTrace();}
synchronized (PingPong.item) {
while (true) {
// wait for my turn (avoid spirious wakeup)
while (((PingPong.item.counter & 1) == 1) == imOdd) {
try {
PingPong.item.wait(); // wait for "Ping"
} catch (InterruptedException e) {e.printStackTrace();}
}
// increment Ping-Poin counter
PingPong.item.counter++;
// read array elements for loading caches
int sum = 0;
int[] cache = imOdd ? PingPong.cache_0 : PingPong.cache_1; // different players choice different arrays
for (int indx = 0; indx < cacheSize; indx += PingPong.CACHE_INDEX_STEP) {
sum += cache[indx];
}
// do "Pong"
PingPong.item.notify();
if (PingPong.item.counter >= PingPong.ITERATION_COUNT) {
PingPong.stop.countDown(); // show for PingPoint.class that my work doing
return; // break, thats all
}
}
}
}
}
