Приветствую, в этой заметке я рассажу, как можно с незначительными усилиями ускорить создание org.springframework.util.ConcurrentReferenceHashMap.


Интересуетесь прокачиванием производительности? Добро пожаловать!


Разведка


Начнём мы, разумеется, с измерений и попробуем понять, что именно будем улучшать. Для этого возьмём JMH 1.21, JDK 8 и JDK 11, а также async-profiler.


Чтобы выяснить, сколько занимает создание пустого словаря поставим простой опыт:


@Benchmark
public Object original() {
  return new ConcurrentReferenceHashMap();
}

Профиль выглядит так:


55.21%  2429743  o.s.u.ConcurrentReferenceHashMap.calculateShift
20.30%   891404  o.s.u.ConcurrentReferenceHashMap$Segment.<init>
 8.79%   387198  o.s.u.ConcurrentReferenceHashMap.<init>
 3.35%   147651  java.util.concurrent.locks.ReentrantLock.<init>
 2.34%   102804  java.lang.ref.ReferenceQueue.<init>
 1.61%    70748  o.s.u.ConcurrentReferenceHashMap.createReferenceManager
 1.53%    67265  o.s.u.ConcurrentReferenceHashMap$Segment.createReferenceArray
 0.78%    34493  java.lang.ref.ReferenceQueue$Lock.<init>
 0.76%    33546  o.s.u.ConcurrentReferenceHashMap$ReferenceManager.<init>
 0.36%    15948  o.s.u.Assert.isTrue

Направление понятно, можно приступать.


Математика


Итак, львиную долю времени мы проводим в методе calculateShift. Вот он:


protected static int calculateShift(int minimumValue, int maximumValue) {
  int shift = 0;
  int value = 1;
  while (value < minimumValue && value < maximumValue) {
    value <<= 1;
    shift++;
  }
  return shift;
}

Здесь сложно придумать что-то новое, поэтому переключимся на его использование:


public ConcurrentReferenceHashMap(/*...*/ int concurrencyLevel, /*...*/) {
  //...
  this.shift = calculateShift(concurrencyLevel, MAXIMUM_CONCURRENCY_LEVEL);
  //...
}

// ConcurrentReferenceHashMap$Segment
public Segment(int initialCapacity) {
  this.referenceManager = createReferenceManager();
  this.initialSize = 1 << calculateShift(initialCapacity, MAXIMUM_SEGMENT_SIZE);
  this.references = createReferenceArray(this.initialSize);
  this.resizeThreshold = (int) (this.references.length * getLoadFactor());
}

Обратите внимание на использование конструктора Segment:


int roundedUpSegmentCapacity = (int) ((initialCapacity + size - 1L) / size);
//...
for (int i = 0; i < this.segments.length; i++) {
  this.segments[i] = new Segment(roundedUpSegmentCapacity);
}

Значение roundedUpSegmentCapacity постоянно при проходе по циклу, следовательно исполняемое в конструкторе Segment выражение 1 << calculateShift(initialCapacity, MAXIMUM_SEGMENT_SIZE), также всегда будет постоянным. Таким образом, мы можем вынести указанное выражение за пределы конструктора и цикла.


Это же утверждение справедливо для выражения (int) (this.references.length * getLoadFactor()), поскольку массив references создаётся с использованием переменной initialCapacity и его размер постоянен при создании каждого сегмента. Вынесем выражение за пределы конструктора и цикла.


Массивы


Рассмотрим метод createReferenceArray:


private Reference<K, V>[] createReferenceArray(int size) {
  return (Reference<K, V>[]) Array.newInstance(Reference.class, size);
}

Использование Array::newInstance явно избыточно, ничто не мешает нам создавать массив используя конструктор:


private Reference<K, V>[] createReferenceArray(int size) {
  return new Reference[size];
}

Производительность конструктора не уступает вызову Array::newInstance на уровне С2, но значительно превосходит его для небольших массивов в режимах С1 (свойство -XX:TieredStopAtLevel=1) и интерпретатора (свойство -Xint):


//C2
               length  Mode  Cnt    Score   Error  Units
constructor        10  avgt   50      5,6   ± 0,0  ns/op
constructor       100  avgt   50     29,7   ± 0,1  ns/op
constructor      1000  avgt   50    242,7   ± 1,3  ns/op

newInstance        10  avgt   50      5,5   ± 0,0  ns/op
newInstance       100  avgt   50     29,7   ± 0,1  ns/op
newInstance      1000  avgt   50    249,3   ± 9,6  ns/op

//C1
               length  Mode  Cnt    Score   Error  Units
constructor        10  avgt   50      6,8   ± 0,1  ns/op
constructor       100  avgt   50     36,3   ± 0,6  ns/op
constructor      1000  avgt   50    358,6   ± 6,4  ns/op

newInstance        10  avgt   50     91,0   ± 2,4  ns/op
newInstance       100  avgt   50    127,2   ± 1,8  ns/op
newInstance      1000  avgt   50    322,8   ± 7,2  ns/op

//-Xint
               length  Mode  Cnt    Score   Error  Units
constructor        10  avgt   50    126,3  ±  5,9  ns/op
constructor       100  avgt   50    154,7  ±  2,6  ns/op
constructor      1000  avgt   50    364,2  ±  6,2  ns/op

newInstance        10  avgt   50    251,2  ± 11,3  ns/op
newInstance       100  avgt   50    287,5  ± 11,4  ns/op
newInstance      1000  avgt   50    486,5  ±  8,5  ns/op

На нашем бенчмарке замена не отразится, но ускорит код при запуске приложения, когда С2 ещё не отработал. Подробнее об этом режиме будет сказано в конце статьи.


Ключевые мелочи


Вновь обратимся к конструктору ConcurrentReferenceHashMap


ConcurrentReferenceHashMap(/*...*/) {
  Assert.isTrue(initialCapacity >= 0, "Initial capacity must not be negative");
  Assert.isTrue(loadFactor > 0f, "Load factor must be positive");
  Assert.isTrue(concurrencyLevel > 0, "Concurrency level must be positive");
  Assert.notNull(referenceType, "Reference type must not be null");
  this.loadFactor = loadFactor;
  this.shift = calculateShift(concurrencyLevel, MAXIMUM_CONCURRENCY_LEVEL);
  int size = 1 << this.shift;
  this.referenceType = referenceType;
  int roundedUpSegmentCapacity = (int) ((initialCapacity + size - 1L) / size);
  this.segments = (Segment[]) Array.newInstance(Segment.class, size);
  for (int i = 0; i < this.segments.length; i++) {
    this.segments[i] = new Segment(roundedUpSegmentCapacity);
  }
}

Из любопытного для нас: замена Array.newInstance на конструктор приводит к ошибке компиляции, проходим мимо. А вот цикл очень любопытный, точнее обращение к полю segments. Чтоб убедиться, насколько разрушительным (иногда) для производительности может быть такое обращение, советую статью Ницана Вакарта The volatile read suprise.


Описанный в статье случай, как мне кажется, соотносится с рассматриваемым кодом. Сосредоточимся на сегментах:


this.segments = (Segment[]) Array.newInstance(Segment.class, size);
for (int i = 0; i < this.segments.length; i++) {
  this.segments[i] = new Segment(roundedUpSegmentCapacity);
}

Сразу после создания массива он записывается в поле ConcurrentReferenceHashMap.segments, и именно с этим полем взаимодействует цикл. Внутри же конструктора Segment происходит запись в волатильное поле references:


private volatile Reference<K, V>[] references;

public Segment(int initialCapacity) {
  //...
  this.references = createReferenceArray(this.initialSize);
  //...
}

Это означает невозможность улучшить обращение к полю segments, иными словами его содержимое считывается при каждом обороте цикла. Как проверить истинность этого утверждения? Простейший способ — это скопировать код в отдельный пакет и удалить volatile из объявления поля Segment.references:


protected final class Segment extends ReentrantLock {
  // было
  private volatile Reference<K, V>[] references;
  // стало
  private Reference<K, V>[] references;
}

Проверим, изменилось ли что-то:


@Benchmark
public Object original() {
  return new tsypanov.map.original.ConcurrentReferenceHashMap();
}

@Benchmark
public Object nonVolatileSegmentReferences() {
  return new tsypanov.map.nonvolatile.ConcurrentReferenceHashMap();
}

Обнаруживаем значительный прирост производительности (JDK 8):


Benchmark                      Mode  Cnt  Score   Error  Units
original                       avgt  100  732,1  ± 15,8  ns/op
nonVolatileSegmentReferences   avgt  100  610,6  ± 15,4  ns/op

На JDK 11 затраченное время уменьшилось, но относительный разрыв почти не изменился:


Benchmark                      Mode  Cnt  Score   Error  Units
original                       avgt  100  473,8  ± 11,2  ns/op
nonVolatileSegmentReferences   avgt  100  401,9  ± 15,5  ns/op

Разумеется, volatile нужно вернуть на место и искать другой способ. Узкое место обнаружено — это обращение к полю. А раз так, то можно создать переменную segments, заполнить массив и только после этого записать его в поле:


Segment[] segments = (Segment[]) Array.newInstance(Segment.class, size);
for (int i = 0; i < segments.length; i++) {
  segments[i] = new Segment(roundedUpSegmentCapacity);
}
this.segments = segments;

В итоге с помощью даже таких простых улучшений удалось добиться неплохого прироста:


JDK 8


Benchmark                           Mode  Cnt  Score   Error  Units
originalConcurrentReferenceHashMap  avgt  100  712,1   ± 7,2  ns/op
patchedConcurrentReferenceHashMap   avgt  100  496,5   ± 4,6  ns/op

JDK 11


Benchmark                           Mode  Cnt  Score    Error  Units
originalConcurrentReferenceHashMap  avgt  100  536,0   ±  8,4  ns/op
patchedConcurrentReferenceHashMap   avgt  100  486,4   ±  9,3  ns/op

Что даёт замена 'Arrays::newInstance' на 'new T[]'


При запуске Спринг Бут приложения из "Идеи" разработчики часто выставляют флаг 'Enable launch optimizations', который добавляет -XX:TieredStopAtLevel=1 -noverify к аргументам ВМ, что ускоряет запуск за счёт отключения профилирования и С2. Сделаем замер с указанными аргументами:


// JDK 8 -XX:TieredStopAtLevel=1 -noverify

Benchmark                           Mode  Cnt   Score  Error  Units
originalConcurrentReferenceHashMap  avgt  100  1920,9 ± 24,2  ns/op
patchedConcurrentReferenceHashMap   avgt  100   592,0 ± 25,4  ns/op

// JDK 11 -XX:TieredStopAtLevel=1 -noverify

Benchmark                           Mode  Cnt   Score  Error  Units
originalConcurrentReferenceHashMap  avgt  100  1838,9 ±  8,0  ns/op
patchedConcurrentReferenceHashMap   avgt  100   549,7 ±  6,7  ns/op

Более чем 3-х кратный прирост!


Для чего это нужно?


В частности это нужно для ускорения запросов, возвращающих проекции в Spring Data JPA.



Профиль JMC показывает, что создание ConcurrentReferenceHashMap занимает почти пятую часть времени, затраченного на выполнение запроса вида


public interface SimpleEntityRepository extends JpaRepository<SimpleEntity, Long> {
  List<HasIdAndName> findAllByName(String name);
}

где HasIdAndName — проекция вида


public interface HasIdAndName {
  int getId();
  String getName();
}

Также ConcurrentReferenceHashMap несколько десятков раз используется в коде "Спринга", так что лишним точно не будет.


Выводы


  • улучшать производительность не столь сложно, как кажется на первый взгляд
  • волатильный доступ в окрестностях цикла — одно из возможных узких мест
  • ищите инварианты и выносите их из циклов

Что почитать


Статья Ницана Вакарта


Код примеров


Изменения:
https://github.com/spring-projects/spring-framework/pull/1873
https://github.com/spring-projects/spring-framework/pull/2051

Комментарии (5)


  1. a_e_tsvetkov
    19.12.2018 09:19

    calculateShift можно ускорить.
    Вот тут несколько способов как это сделать.

    Не считая банальной замены двух сравнений на сравнение с минимумом двух параметров.


    1. tsypanov Автор
      19.12.2018 11:48

      Спасибо вам за ссылку! Попробую копнуть в этом направлении.


    1. Danilcha
      19.12.2018 17:12

      Как-то так:

      protected static int calculateShift(int minimumValue, int maximumValue) {
        int target = Math.min(minimumValue, maximumValue);	
        if (target > 1)
          return Integer.highestOneBit(target - 1) << 1;
        else
          return 1;
      }
      


      1. a_e_tsvetkov
        20.12.2018 06:52

        У вас возвращается старший бит, оригинальный метод возвращает его позицию.

        Например для 7 вы вернете 8, а надо 3.

        Правильная реализация будет выглядеть примерно так.

        int calculateShift(int minimumValue, int maximumValue) {
          int target = Math.min(minimumValue, maximumValue);	
          return 32-Integer.numberOfLeadingZeros(target);
        }


        1. Danilcha
          20.12.2018 13:30

          Да, действительно. Тогда вот так (а если ни один из аргументов не может быть нулем, то еще проще):

              protected static int calculateShift(int minimumValue, int maximumValue)
              {
                  int target = Math.min(minimumValue, maximumValue);
                  if (target > 0)
                      return 32 - Integer.numberOfLeadingZeros(target - 1);
                  else
                      return 0;
              }