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

Question

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

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.

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

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

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

, и я получаю эти 2 вывода для 2 версий для метода Jotedrun в 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::run@21 (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::run@15 (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::run@29 (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::run@15 (line 79)
                                        ;   {runtime_call}
  0xf3771b14: call   0xf70307a0         ;   {runtime_call}

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

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

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

Спасибо!

РЕДАКТИРОВАТЬ:

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

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 в объекте потока, которыйкак-то "закрывается" в памяти между различными экземплярами потока.

Answer 1

Давайте попробуем заставить 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® Core ™ 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 миллисекунд.В цикле while еще есть последняя ссылка this.vfoo.Предположим еще раз, что цикл 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 вместо 50 000 000):

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

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

Answer 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 во время выполнения?

Answer 3

На самом деле вы не пишете в энергозависимое поле, поэтому энергозависимое поле можно кэшировать в каждом потоке.

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

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

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

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

Answer 4

Кратко: очевидно, что ответ неверный из-за маркировки карты для GC.

Более подробные объяснения даны в этом вопросе:

Распределение массива и доступ к немувиртуальная машина Java и конфликт памяти

Answer 5

Редактировать: Этот ответ не выдержал испытания.

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

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

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