пятница, 22 декабря 2017 г.

CPU оптимизации

Сегодня, в этой небольшой статье, я хотел бы поделиться своими знаниями об оптимизациях центрального процессора. А именно:

  1. branch prediction
  2. cache levels
  3. false sharing
  4. prefetching

Начнем в первой. В детали вдаваться не буду, а начну сразу с примера. Допустим у нас есть следующий метод:

Выглядит вполне симпатично и на первый взгляд не представляет никаких угроз, но это только на первый взгляд. Если мы померим время выполнения данного метода для произвольного массива и для него же, но только отсортированного, результат будет сильно отличаться.

Benchmark                                           Mode   Count Score    Error  Units
BranchPredictionBenchmark.invokeWithOptimization    avgt   10    0.631 ±  0.035  ms/op
BranchPredictionBenchmark.invokeWitoutOptimization  avgt   10    3.957 ±  0.142  ms/op

Дело в том, что современные процессоры выполняют инструкции не строго очередно, а в виде так называемого "конвейера" . Т.е. команда проходит несколько этапов, и как правило, одновременно разные команды находятся на разных этапах выполнения.

Но существующий код, плохо ложится на данную концепцию. Потому что, каждой последующей команде необходимо дождаться этапа проверки условия, чтобы можно было понять какой далее код следует выполнять. В процессоре, для таких случаев, существует оптимизация branch prediction, позволяющая уменьшить время ожидания. Она пытается "предсказать" в какую сторону пойдет выполнение и выполнить последующие команды. Затем, в момент когда можно будет проверить условие, убедиться что, догадка была верна, либо отбросить результаты предыдущего вычисления и выполнить код из "правильной" ветки.

Следующая оптимизация - это кэши различного уровня в процессоре. Как известно процессор работает очень быстро и ждать каждый раз когда данные будут загруженны из оперативной памяти не рационально. Для решения этой проблемы решили использовать кэширование, причем различного уровня. Количество уровней варьируется от модели и производителя процессора. На моем ноутбуке следующая конфигурация кэшей:

first level : 256KB
second level: 1MB
third level : 6MB

При том, что первые два имеются для каждого ядра, а кэш третьего уровня является общим. Код используемый для тестирования приводить здесь не буду, покажу только результаты:

Benchmark                                  Mode  Count  Score     Error  Units
CpuCacheLevelBenchmark.firstCacheLevel     ss    10     12.528 ±  1.804  ms/op
CpuCacheLevelBenchmark.secondCacheLevel    ss    10     15.938 ±  1.361  ms/op
CpuCacheLevelBenchmark.thirdCacheLevel     ss    10     21.886 ±  6.798  ms/op
CpuCacheLevelBenchmark.ramCacheLevel       ss    10     49.141 ± 11.880  ms/op

Далее идет false sharing. Скажу сразу, это не является оптимизацией, это довольно "вредный" эффект, вытекающий из предыдущей оптимизации. Данные в кэшах хранятся в так называемых "cache line". И возникают ситуации, когда нам сильно не везет и несвязанные данные попадают на одну "линию". Тогда, происходит постоянное ее обновление в разных кэшах ядер, на которых выполняются потоки.

Приведу код, для большего понимания. Допустим есть объект:

Если в одном потоке будет происходить запись в firstValue а в другом в secondValue, то мы можем наблюдать false sharing. Решением этой проблемы является подбор размера объекта, такого, чтобы поля не смогли оказаться на одной cache line. Например, так:

На этом графике можно наблюдать разницу в работе с этими объектами:

Benchmark                                           Mode   Count    Score    Error  Units
FalseSharingBenchmark.invokeWithOptimization          ss   10       62.584 ±  6.625  ms/op
FalseSharingBenchmark.invokeWithoutOptimization       ss   10      289.808 ± 26.294  ms/op

Как было сказано ранее, процессору не выгодно делать паузы между загрузкой данных из оперативной памяти, поэтому придумали кэширование. Когда данные запрашиваются из кэша, их там может не оказаться, это называется "cache miss". Тогда, их загружают из кэша более высокого уровня или же из оперативной памяти. Очевидно, что это не очень быстро. Чтобы уменьшить количество кэш промахов, используется prefetching.

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

Данную оптимизацию можно наблюдать при обходе связанного списка и массива. Т.к. данные в массиве находятся последовательно, то для процессора не составляет труда определить следующий участок памяти для загрузки, а вот со связанными списками prefetching не справляется 😔. Там каждый элемент ссылается на произвольную область памяти, в которой находится следующий элемент и это является проблемой.

Разницу можно увидеть на графике:

Benchmark                                           Mode  Count  Score   Error  Units
PrefetchingBenchmark.invokeWithOptimization         avgt   10    5.570 ± 0.229  ms/op
PrefetchingBenchmark.invokeWithoutOptimization      avgt   10    8.341 ± 0.206  ms/op

Весь код используемый для тестов находится здесь: Github репозиторий