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

05/04/2020

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

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

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

java

izebit