Подтвердить что ты не робот

Почему чтение volatile и запись в член поля не масштабируются в Java?

Соблюдайте следующую программу, написанную на Java (полная версия runnable следует, но важная часть программы находится в фрагменте немного ниже):

import java.util.ArrayList;



/** A not easy to explain benchmark.
 */
class MultiVolatileJavaExperiment {

    public static void main(String[] args) {
        (new MultiVolatileJavaExperiment()).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 Reader(sz));
            threads.get(i).start();
        }
        for (int i = 0; i < par; i++) {
            try {
                threads.get(i).join();
            } catch (Exception e) {}
        }
    }

    final class Foo {
        int x = 0;
    }

    final class Reader extends Thread {
        volatile Foo vfoo = new Foo();
        Foo bar = null;
        int sz;

        public Reader(int _sz) {
            sz = _sz;
        }

        public void run() {
            int i = 0;
            while (i < sz) {
                vfoo.x = 1;
                // with the following line commented
                // the scalability is almost linear
                bar = vfoo; // <- makes benchmark 2x slower for 2 processors - why?
                i++;
            }
        }
    }

}

Объяснение. Программа на самом деле очень проста. Он загружает целые числа size и par из свойств системы (переданных в jvm с флагом -D) - это длина ввода и количество потоков, которые будут использоваться позже. Затем он анализирует первый аргумент командной строки, в котором указано, сколько раз повторять программу (мы хотим быть уверены, что JIT выполнил свою работу и имеет более надежные измерения).

Метод run вызывается в каждом повторении. Этот метод просто запускает par потоки, каждый из которых будет выполнять цикл с size / par итерациями. Тело потока определено в классе Reader. Каждое повторение цикла считывает изменчивый элемент vfoo и присваивает 1 его публичному полю. После этого vfoo снова читается и назначается в поле энергонезависимой памяти bar.

Обратите внимание, как большую часть времени программа выполняет тело цикла, поэтому run в потоке является фокусом этого теста:

    final class Reader extends Thread {
        volatile Foo vfoo = new Foo();
        Foo bar = null;
        int sz;

        public Reader(int _sz) {
            sz = _sz;
        }

        public void run() {
            int i = 0;
            while (i < sz) {
                vfoo.x = 1;
                // with the following line commented
                // the scalability is almost linear
                bar = vfoo; // <- makes benchmark 2x slower for 2 processors - why?
                i++;
            }
        }
    }

Наблюдения: запуск java -Xmx512m -Xms512m -server -Dsize=500000000 -Dpar=1 MultiVolatileJavaExperiment 10 на

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)

Я получаю следующие моменты:

>>> All running times: [821, 750, 1011, 750, 758, 755, 1219, 751, 751, 1012]

Теперь, установив -Dpar=2, я получаю:

>>> All running times: [1618, 380, 1476, 1245, 1390, 1391, 1445, 1393, 1511, 1508]

По-видимому, это не масштабируется по какой-то причине - я бы ожидал, что второй выход будет в два раза быстрее (хотя, похоже, он находится в одной из ранних итераций - 380ms).

Интересно отметить, что комментируя строку bar = vfoo (которая даже не должна быть волатильной записью), для -Dpar устанавливаются следующие значения: 1,2,4,8.

>>> All running times: [762, 563, 563, 563, 563, 563, 570, 566, 563, 563]
>>> All running times: [387, 287, 285, 284, 283, 281, 282, 282, 281, 282]
>>> All running times: [204, 146, 143, 142, 141, 141, 141, 141, 141, 141]
>>> All running times: [120, 78, 74, 74, 81, 75, 73, 73, 72, 71]

Он отлично масштабируется.

Анализ. Прежде всего, здесь нет циклов сбора мусора (я добавил -verbose:gc, чтобы проверить это).

Я получаю похожие результаты на моем iMac.

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

Моя следующая мысль заключалась в том, что JIT может быть чем-то странным, потому что ранние итерации обычно масштабируются, как ожидалось, в версии без комментирования, поэтому я проверил это, распечатав сборку (см. этот пост о том, как это сделать).

java -Xmx512m -Xms512m -server -XX:CompileCommand=print,*Reader.run MultiVolatileJavaExperiment -Dsize=500000000 -Dpar=1 10

и я получаю эти 2 выхода для 2-х версий для метода Jitted run в Reader. Прокомментированная (правильно масштабируемая) версия:

[Verified Entry Point]
  0xf36c9fac: mov    %eax,-0x3000(%esp)
  0xf36c9fb3: push   %ebp
  0xf36c9fb4: sub    $0x8,%esp
  0xf36c9fba: mov    0x68(%ecx),%ebx
  0xf36c9fbd: test   %ebx,%ebx
  0xf36c9fbf: jle    0xf36c9fec
  0xf36c9fc1: xor    %ebx,%ebx
  0xf36c9fc3: nopw   0x0(%eax,%eax,1)
  0xf36c9fcc: xchg   %ax,%ax
  0xf36c9fd0: mov    0x6c(%ecx),%ebp
  0xf36c9fd3: test   %ebp,%ebp
  0xf36c9fd5: je     0xf36c9ff7
  0xf36c9fd7: movl   $0x1,0x8(%ebp)

---------------------------------------------

  0xf36c9fde: mov    0x68(%ecx),%ebp
  0xf36c9fe1: inc    %ebx               ; OopMap{ecx=Oop off=66}
                                        ;*goto
                                        ; - org.scalapool.bench.MultiVolatileJavaExperiment$Reader::[email protected] (line 83)

---------------------------------------------

  0xf36c9fe2: test   %edi,0xf7725000    ;   {poll}
  0xf36c9fe8: cmp    %ebp,%ebx
  0xf36c9fea: jl     0xf36c9fd0
  0xf36c9fec: add    $0x8,%esp
  0xf36c9fef: pop    %ebp
  0xf36c9ff0: test   %eax,0xf7725000    ;   {poll_return}
  0xf36c9ff6: ret    
  0xf36c9ff7: mov    $0xfffffff6,%ecx
  0xf36c9ffc: xchg   %ax,%ax
  0xf36c9fff: call   0xf36a56a0         ; OopMap{off=100}
                                        ;*putfield x
                                        ; - org.scalapool.bench.MultiVolatileJavaExperiment$Reader::[email protected] (line 79)
                                        ;   {runtime_call}
  0xf36ca004: call   0xf6f877a0         ;   {runtime_call}

Несмещенная bar = vfoo (не масштабируемая, более медленная) версия:

[Verified Entry Point]
  0xf3771aac: mov    %eax,-0x3000(%esp)
  0xf3771ab3: push   %ebp
  0xf3771ab4: sub    $0x8,%esp
  0xf3771aba: mov    0x68(%ecx),%ebx
  0xf3771abd: test   %ebx,%ebx
  0xf3771abf: jle    0xf3771afe
  0xf3771ac1: xor    %ebx,%ebx
  0xf3771ac3: nopw   0x0(%eax,%eax,1)
  0xf3771acc: xchg   %ax,%ax
  0xf3771ad0: mov    0x6c(%ecx),%ebp
  0xf3771ad3: test   %ebp,%ebp
  0xf3771ad5: je     0xf3771b09
  0xf3771ad7: movl   $0x1,0x8(%ebp)

-------------------------------------------------

  0xf3771ade: mov    0x6c(%ecx),%ebp
  0xf3771ae1: mov    %ebp,0x70(%ecx)
  0xf3771ae4: mov    0x68(%ecx),%edi
  0xf3771ae7: inc    %ebx
  0xf3771ae8: mov    %ecx,%eax
  0xf3771aea: shr    $0x9,%eax
  0xf3771aed: movb   $0x0,-0x3113c300(%eax)  ; OopMap{ecx=Oop off=84}
                                        ;*goto
                                        ; - org.scalapool.bench.MultiVolatileJavaExperiment$Reader::[email protected] (line 83)

-----------------------------------------------

  0xf3771af4: test   %edi,0xf77ce000    ;   {poll}
  0xf3771afa: cmp    %edi,%ebx
  0xf3771afc: jl     0xf3771ad0
  0xf3771afe: add    $0x8,%esp
  0xf3771b01: pop    %ebp
  0xf3771b02: test   %eax,0xf77ce000    ;   {poll_return}
  0xf3771b08: ret    
  0xf3771b09: mov    $0xfffffff6,%ecx
  0xf3771b0e: nop    
  0xf3771b0f: call   0xf374e6a0         ; OopMap{off=116}
                                        ;*putfield x
                                        ; - org.scalapool.bench.MultiVolatileJavaExperiment$Reader::[email protected] (line 79)
                                        ;   {runtime_call}
  0xf3771b14: call   0xf70307a0         ;   {runtime_call}

Различия в двух версиях находятся в пределах ---------. Я ожидал найти инструкции синхронизации в сборке, которые могли бы учитывать проблему производительности - в то время как несколько дополнительных команд shift, mov и inc могут влиять на абсолютные номера производительности, я не вижу, как они могут повлиять на масштабируемость.

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

Может ли кто-нибудь объяснить, что здесь происходит? Пожалуйста, будьте точны и укажите ссылки, подтверждающие ваши претензии.

Спасибо!

EDIT:

Здесь байт-код для быстрой (масштабируемой) версии:

public void run();
  LineNumberTable: 
   line 77: 0
   line 78: 2
   line 79: 10
   line 83: 18
   line 85: 24



  Code:
   Stack=2, Locals=2, Args_size=1
   0:   iconst_0
   1:   istore_1
   2:   iload_1
   3:   aload_0
   4:   getfield    #7; //Field sz:I
   7:   if_icmpge   24
   10:  aload_0
   11:  getfield    #5; //Field vfoo:Lorg/scalapool/bench/MultiVolatileJavaExperiment$Foo;
   14:  iconst_1
   15:  putfield    #8; //Field org/scalapool/bench/MultiVolatileJavaExperiment$Foo.x:I
   18:  iinc    1, 1
   21:  goto    2
   24:  return
  LineNumberTable: 
   line 77: 0
   line 78: 2
   line 79: 10
   line 83: 18
   line 85: 24

  StackMapTable: number_of_entries = 2
   frame_type = 252 /* append */
     offset_delta = 2
     locals = [ int ]
   frame_type = 21 /* same */

Медленная (не масштабируемая) версия с bar = vfoo:

public void run();
  LineNumberTable: 
   line 77: 0
   line 78: 2
   line 79: 10
   line 82: 18
   line 83: 26
   line 85: 32



  Code:
   Stack=2, Locals=2, Args_size=1
   0:   iconst_0
   1:   istore_1
   2:   iload_1
   3:   aload_0
   4:   getfield    #7; //Field sz:I
   7:   if_icmpge   32
   10:  aload_0
   11:  getfield    #5; //Field vfoo:Lorg/scalapool/bench/MultiVolatileJavaExperiment$Foo;
   14:  iconst_1
   15:  putfield    #8; //Field org/scalapool/bench/MultiVolatileJavaExperiment$Foo.x:I
   18:  aload_0
   19:  aload_0
   20:  getfield    #5; //Field vfoo:Lorg/scalapool/bench/MultiVolatileJavaExperiment$Foo;
   23:  putfield    #6; //Field bar:Lorg/scalapool/bench/MultiVolatileJavaExperiment$Foo;
   26:  iinc    1, 1
   29:  goto    2
   32:  return
  LineNumberTable: 
   line 77: 0
   line 78: 2
   line 79: 10
   line 82: 18
   line 83: 26
   line 85: 32

  StackMapTable: number_of_entries = 2
   frame_type = 252 /* append */
     offset_delta = 2
     locals = [ int ]
   frame_type = 29 /* same */

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

ИЗМЕНИТЬ 2:

Интересно, что сменить программу следующим образом:

final class Holder {
    public Foo bar = null;
}

final class Reader extends Thread {
    volatile Foo vfoo = new Foo();
    Holder holder = null;
    int sz;

    public Reader(int _sz) {
        sz = _sz;
    }

    public void run() {
        int i = 0;
        holder = new Holder();
        while (i < sz) {
            vfoo.x = 1;
            holder.bar = vfoo;
            i++;
        }
    }
}

устраняет проблему масштабирования. По-видимому, объект Holder выше создается после начала потока и, вероятно, распределяется в другом сегменте памяти, который затем изменяется одновременно, в отличие от изменения поля bar в объекте потока, который как-то "закрываются" в памяти между разными экземплярами потоков.

4b9b3361

ОТВЕТЫ

Ответ 2

Это то, что я думаю, происходит (помните, что я не знаком с HotSpot):

0xf36c9fd0: mov    0x6c(%ecx),%ebp    ; vfoo
0xf36c9fd3: test   %ebp,%ebp          ; vfoo is null?
0xf36c9fd5: je     0xf36c9ff7         ;   throw NullPointerException (I guess)
0xf36c9fd7: movl   $0x1,0x8(%ebp)     ; vfoo.x = 1
0xf36c9fde: mov    0x68(%ecx),%ebp    ; sz
0xf36c9fe1: inc    %ebx               ; i++
0xf36c9fe2: test   %edi,0xf7725000    ; safepoint on end of loop
0xf36c9fe8: cmp    %ebp,%ebx          ; i < sz?
0xf36c9fea: jl     0xf36c9fd0


0xf3771ad0: mov    0x6c(%ecx),%ebp          ; vfoo
0xf3771ad3: test   %ebp,%ebp                ; vfoo is null?
0xf3771ad5: je     0xf3771b09               ;   throw NullPointerException (I guess)
0xf3771ad7: movl   $0x1,0x8(%ebp)           ; vfoo.x = 1
0xf3771ade: mov    0x6c(%ecx),%ebp          ; \
0xf3771ae1: mov    %ebp,0x70(%ecx)          ; / bar = vfoo
0xf3771ae4: mov    0x68(%ecx),%edi          ; sz
0xf3771ae7: inc    %ebx                     ; i++
0xf3771ae8: mov    %ecx,%eax                ; 
0xf3771aea: shr    $0x9,%eax                ; ??? \ Probably replaced later
0xf3771aed: movb   $0x0,-0x3113c300(%eax)   ; ??? / by some barrier code?
0xf3771af4: test   %edi,0xf77ce000          ; safepoint
0xf3771afa: cmp    %edi,%ebx                ; i < sz ?
0xf3771afc: jl     0xf3771ad0               ;

Причина, по которой я думаю, что приведенный выше код стоит за барьером, заключается в том, что при использовании NullPointerException масштабируемая версия имеет XCHG, которая действует как барьер, в то время как в немасштабируемой версии есть NOP.

Обоснование состояло бы в том, что должно произойти следующее: перед порядком между начальной загрузкой vfoo и объединением потока. В неустойчивом случае барьер будет находиться внутри петли, поэтому ему не нужно быть в другом месте. Я не понимаю, почему XCHG не используется внутри цикла. Может быть, обнаружение времени исполнения поддержки MFENCE?

Ответ 3

Попробуйте заставить JVM вести себя немного более "последовательно". Компилятор JIT действительно отбрасывает сравнение тестовых прогонов; поэтому отключить компилятор JIT, используя -Djava.compiler=NONE. Это определенно приводит к хиту производительности, но поможет устранить неясность и последствия оптимизации JIT-компилятора.

Коллекция мусора вводит свой собственный набор сложностей. Используйте серийный сборщик мусора с помощью -XX:+UseSerialGC. Позвольте также отключить явные коллекции мусора и включить некоторые регистрации, чтобы увидеть, когда выполняется сбор мусора: -verbose:gc -XX:+DisableExplicitGC. Наконец, позвольте получить кучу, выделенную с помощью -Xmx128m -Xms128m.

Теперь мы можем запустить тест, используя:

java -XX:+UseSerialGC -verbose:gc -XX:+DisableExplicitGC -Djava.compiler=NONE -Xmx128m -Xms128m -server -Dsize=50000000 -Dpar=1 MultiVolatileJavaExperiment 10

Выполнение теста несколько раз показывает, что результаты очень согласованы (я использую Oracle Java 1.6.0_24-b07 на Ubuntu 10.04.3 LTS с процессором Intel (R) Core (TM) 2 Duo P8700 @2,53 ГГц), усредняя где-то около 2050 миллисекунд. Если я прокомментирую строку bar = vfoo, я последовательно усредняю ​​около 1280 миллисекунд. Выполнение теста с использованием -Dpar=2 приводит к тому, что в среднем около 1350 миллисекунд с bar = vfoo и около 1005 миллисекунд с комментариями.

+=========+======+=========+
| Threads | With | Without |
+=========+======+=========+
|    1    | 2050 |  1280   |
+---------+------+---------+
|    2    | 1350 |  1005   |
+=========+======+=========+

Теперь давайте посмотрим на код и посмотрим, можем ли мы выявить причины, по которым многопоточность неэффективна. В Reader.run() подходящая квалификационная переменная с this поможет определить, какие переменные являются локальными:

int i = 0;
while (i < this.sz) {
    this.vfoo.x = 1;
    this.bar = this.vfoo;
    i++;
}

Прежде всего следует отметить, что цикл while содержит четыре переменных, на которые ссылается this. Это означает, что код обращается к пулу констант времени выполнения класса и выполняет проверку типов (с помощью команды getfield bytecode). Позвольте изменить код, чтобы попытаться устранить доступ к пулу постоянной среды выполнения и посмотреть, получились ли какие-либо преимущества.

final int mysz = this.sz;
int i = 0;
while (i < mysz) {
    this.vfoo.x = 1;
    this.bar = this.vfoo;
    i++;
}

Здесь мы используем локальную переменную mysz для доступа к размеру цикла и только для доступа к sz через this один раз для инициализации. Запуск теста с двумя потоками составляет в среднем около 1295 миллисекунд; небольшое преимущество, но тем не менее.

Рассматривая цикл while, нужно ли нам дважды ссылаться на this.vfoo? Два энергозависимых чтения создают два края синхронизации, которым должна управлять виртуальная машина (и основное оборудование, если на то пошло). Пусть говорят, что нам нужен один фронт синхронизации в начале цикла while, и нам не нужны два, мы можем использовать следующее:

final int mysz = this.sz;
Foo myvfoo = null;
int i = 0;
while (i < mysz) {
    myvfoo = this.vfoo;
    myvfoo.x = 1;
    this.bar = myvfoo;
    i++;
}

Это в среднем около 1122 миллисекунд; все еще улучшается. Как насчет этой ссылки this.bar? Поскольку мы говорим о многопоточности, скажем, расчеты в цикле while - это то, что мы хотим получить многопоточную выгоду, а this.bar - это то, как мы сообщаем наши результаты другим. Мы действительно не хотим устанавливать this.bar до тех пор, пока цикл while не будет выполнен.

final int mysz = this.sz;
Foo myvfoo = null;
Foo mybar = null;
int i = 0;
while (i < mysz) {
    myvfoo = this.vfoo;
    myvfoo.x = 1;
    mybar = myvfoo;
    i++;
}
this.bar = mybar;

Это дает нам около 857 миллисекунд в среднем. Еще есть эта окончательная ссылка this.vfoo в цикле while. Предположим, что цикл while - это то, что мы хотим получить от многопоточной выгоды, отпустите this.vfoo из цикла while.

final int mysz = this.sz;
final Foo myvfoo = this.vfoo;
Foo mybar = null;
int i = 0;
while (i < mysz) {
    myvfoo.x = 1;
    mybar = myvfoo;
    i++;
}
final Foo vfoocheck = this.vfoo;
if (vfoocheck != myvfoo) {
    System.out.println("vfoo changed from " + myvfoo + " to " + vfoocheck);
}
this.bar = mybar;

Теперь мы в среднем около 502 миллисекунд; однопоточный тест составляет около 900 миллисекунд.

Так что это говорит нам? Экстраполируя нелокальные ссылки на переменные из цикла while, были значительные преимущества в производительности как в одно-, так и в двухпоточных тестах. В исходной версии MultiVolatileJavaExperiment была измерена стоимость доступа к нелокальным переменным 50 000 000 раз, в то время как окончательная версия измеряет стоимость доступа к локальным переменным 50 000 000 раз. Используя локальные переменные, вы увеличиваете вероятность того, что виртуальная машина Java и базовое оборудование смогут более эффективно управлять кэшем потоков.

Наконец, позвольте нормально запускать тесты (обратите внимание, что вместо 500 000 000 циклов размером 500 000 000):

java -Xmx128m -Xms128m -server -Dsize=500000000 -Dpar=2 MultiVolatileJavaExperiment 10

Исходная версия в среднем составляет около 1100 миллисекунд, а модифицированная версия в среднем составляет около 10 миллисекунд.

Ответ 4

Фактически вы не записываете в поле volatile, поэтому поле volatile может быть кэшировано в каждом потоке.

Использование volatile предотвращает некоторые оптимизации компилятора и в микро-контроле, вы можете видеть большую относительную разницу.

В приведенном выше примере прокомментированная версия длиннее, потому что у нее развернут цикл, чтобы разместить две итерации в одном действительном цикле. Это может почти удвоить производительность.

При использовании volatile вы можете видеть, что нет разворачивания цикла.

BTW: вы можете удалить много кода в вашем примере, чтобы было легче читать.;)

Ответ 5

Изменить: этот ответ не выдерживает тестирования.

У меня нет возможности проверить это прямо сейчас (нет многоядерного процессора в этой машине), но вот теория: экземпляры Foo могут отсутствовать в одних и тех же строках кэша, но, возможно, экземпляры Reader.

Это означает, что замедление можно объяснить записью bar, а не чтением Foo, поскольку запись в bar приведет к аннулированию этой строки кэша для другого ядра и вызовет много копий между кешами. Комментируя запись в bar (которая является единственной записью в поле Reader в цикле), останавливает замедление, что согласуется с этим объяснением.

Изменить: Согласно этой статье, макет памяти объектов таков, что ссылка bar будет последним полем в макете объекта Reader. Это означает, что, возможно, приземляется в той же строке кеша, что и следующий объект в куче. Поскольку я не уверен в порядке, в котором новые объекты выделены в куче, я предложил в приведенном ниже комментарии проложить "горячие" типы объектов со ссылками, которые будут эффективны при разделении объектов (по крайней мере, я надеюсь, что это будет, но это зависит от того, как поля одного и того же типа сортируются в памяти).