Сегодня, в этой небольшой статье, я хотел бы поделиться своими знаниями об оптимизациях центрального процессора. А именно:
- branch prediction
- cache levels
- false sharing
- prefetching
- loop unrolling
Начнем в первой. В детали вдаваться не буду, а начну сразу с примера. Допустим у нас есть следующий метод:
private static int countOfElementsLessThen(final int value,
final int[] array) {
int result = 0;
for (int anArray : array)
if (anArray < value)
result++;
return result;
}
Выглядит вполне симпатично и на первый взгляд не представляет никаких угроз, но это только на первый взгляд. Если мы померим время выполнения данного метода для произвольного массива и для него же, но только отсортированного, результат будет сильно отличаться.

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». И возникают ситуации, когда нам сильно не везет и несвязанные данные попадают на одну «линию». Тогда, происходит постоянное ее обновление в разных кэшах ядер, на которых выполняются потоки.
Приведу код, для большего понимания. Допустим есть объект:
Tuple unoptimizedTuple = new Tuple() {
private volatile int firstValue;
private volatile int secondValue;
//other methods
};
Если в одном потоке будет происходить запись в firstValue
а в другом в secondValue
, то мы можем наблюдать false sharing. Решением этой проблемы является подбор размера объекта, такого, чтобы поля не смогли оказаться на одной cache line. Например, так:
Tuple optimizedTuple = new Tuple() {
private volatile int firstValue;
//фиктивные поля для выравнивания размера
private long p1, p2, p3, p4, p5, p6, p7, p8;
private volatile int secondValue;
//other
};
На этом графике можно наблюдать разницу в работе с этими объектами:

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 бит. Т.е. они могут хранить в них сразу набор из нескольких значений, и производить операции над ним, как над одним значением.
Приведу небольшой пример:
int result = 0;
for (int i = 0; i < array.length; i++)
result += array[i];
Данный код довольно прост, здесь считается сумма элементов в массиве (отбросим вопросы о его корректности, здесь это не важно)
Процессор не использует векторизацию, чтож, попробуем ему немного помочь:
int result = 0;
for (int i = 0; i < array.length; i += 2)
result += (array[i] + array[2]);
В данном случае, он уже будет работать не над одним значением, а над несколькими и это явно быстрее:
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 |
Весь код используемый для тестов находится по ссылке ниже.