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

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

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

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

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

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


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, позволяющая уменьшить время ожидания. Она пытается "предсказать" в какую сторону пойдет выполнение и выполнить последующие команды. Затем, в момент когда можно будет проверить условие, убедиться что, догадка была верна, либо отбросить результаты предыдущего вычисления и выполнить код из "правильной" ветки.

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

cache level size
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
BranchPredictionBenchmark.invokeWitoutOptimization 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

И последняя оптимизация о которой я упомяну, будет loop unrolling
Суть ее очень проста, если процессор обладает технологией векторизации, то он имеет регистры расширенного размера. Например, обычные регистры содержат допустим 8 или 32 бита информации, а процессоры имеющие SIMD инструкции регистры размером 128 или 256 бит. Т.е. они могут хранить в них сразу набор из нескольких значений, и производить операции над ним, как над одним значением.

Приведу небольшой пример:

Данный код довольно прост, здесь считается сумма элементов в массиве (отбросим вопросы о его корректности, здесь это не важно)
Процессор не использует векторизацию, чтож, попробуем ему немного помочь:

В данном случае, он уже будет работать не над одним значением, а над несколькими и это явно быстрее:


Benchmark Mode Count Score Error Units
LoopUnrollingBenchmark.invokeWithOptimization avgt 10 0.365 ± 0.024 ms/op
LoopUnrollingBenchmark.invokeWithoutOptimization avgt 10 0.461 ± 0.022 ms/op

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