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

Давайте представим, что у нас есть массив, содержащий 67 000 целочисленных элементов. Над этим массивом выполняются два цикла, как показано в Листинге 1. Оба эти цикла просто умножают элементы массива на три. Однако если первый цикл изменяет каждый элемент, то второй цикл изменяет только каждый 16-й элемент. Насколько быстрее будет работать второй цикл по сравнению с первым? Попробуйте угадать: в 16 раз быстрее?

Листинг 1. Какой цикл отработает быстрее?

private static final int ARRAY_SIZE = 64 * 1024 * 1024;
public int[] array = new int[ARRAY_SIZE];
for (int i = 0, n = array.length; i < n; i++) {
array[i] *= 3;
}
for (int i = 0, n = array.length; i < n; i+=16) {
array[i] *= 3;
}

Возможно, ответ на этот вопрос окажется для вас неожиданным — при выполнении кода на обычном ноутбуке оба цикла занимают примерно одинаковое время. На Рисунке 1 показаны результаты измерений на трех компьютерах, и, как видите, разница незначительна. Второй цикл выполняет лишь небольшую часть работы, так как же это возможно, что первый цикл работает с той же скоростью?

Чтобы понять причину такого поведения, нам нужно разобраться, как работают процессор и система памяти. На самом низком уровне современные компьютеры могут демонстрировать фокусы сродни квантовой механике, которая, казалось бы, противоречит повседневному опыту. Но иногда квантовая механика оказывает заметное влияние на реальный мир. И тонкости устройства процессов на аппаратном уровне тоже иногда оказывают заметное (и с первого взгляда не очевидное) влияние на программы. В этой статье мы рассмотрим работу современных компьютеров на самом низком уровне, уделив особое внимание тому, что может повлиять на производительность.

Инструкции, процессоры, память и кэш

Если мы попытаемся представить себе, как выполняются циклы в Листинге 1, то самое первое, что приходит нам в голову, это ситуация, когда массив хранится в оперативной памяти, а процессор считывает элемент за элементом, умножает каждый элемент на три и записывает результат обратно, как показано на Рисунке 2. Такая интерпретация может помочь нам понять принцип работы циклов, но это не совсем то, что в действительности происходит внутри компьютера.

На Рисунке 3 показан график относительного повышения производительности процессоров и памяти за последние десятилетия. Производительность памяти постоянно росла в течение всего этого периода, но этот рост не идет ни в какие сравнения с повышением скорости процессора, особенно в 1990-е годы. В последние годы скорость простых процессоров достигла потолка, но не стоит обманываться! Шкала на Рисунке 3 является логарифмической. Несмотря на то, что может показаться, что производительность памяти догоняет процессоры, разрыв все еще огромен.

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

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

Обычно программы обращаются к одним и тем же данным и коду несколько раз в течение короткого периода времени (временная локальность), а доступ к памяти часто ограничивается небольшими фрагментами (пространственная локальность). Это означает, что если загрузить в кэш все используемые данные, то велика вероятность того, что они снова понадобятся чуть позже. Поскольку в следующий раз, когда вам понадобятся эти данные, они, возможно, все еще будут находиться в кэше, производительность ваших программ значительно возрастает.

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

• Оперативная память намного больше кэш-памяти, и банально требуется больше времени, чтобы найти нужный адрес в пределах 16 Гбайт (типичный размер оперативной памяти на момент написания статьи), чем если бы мы искали нужный адрес в пределах 8 Кбайт (типичный размер кэш-памяти первого уровня [L1]).

• Электронные компоненты кэш-памяти гораздо более требовательные с точки зрения тепловыделения и занимаемой площади, чем те, что используются в оперативной памяти. Тепло и пространство являются лимитирующими факторами при разработке современных микросхем в частности, и при разработке современных компьютеров в целом.

Для извлечения выгоды из пространственной локальности кэш-память работает не с отдельными байтами, а со строками кэш-памяти. Кэш-строка (или кэш-линия) — это смежная часть памяти, обычно 64 байта.

Если брать во внимание кэш-строки, то то, что происходит при итерации больших циклов из Листинга 1, можно увидеть на Рисунке 5. Процессор загружает в кэш полную строку из оперативной памяти и модифицирует элементы в кэше напрямую. Первый цикл модифицирует все элементы в кэш-строке, а второй - только один элемент (из 16 целых чисел длиной 4 байта каждое).

Ограничивающим фактором при такой организации работы является загрузка строк в кэш, поэтому количество операций, выполняемых над каждой строкой кэша, практически не имеет значения. Это объясняет, почему производительность обоих циклов примерно одинакова.

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

Размер данных и кэши L1, L2 и L3

Влияет ли размер структуры данных на производительность во время выполнения? Чтобы ответить на этот вопрос, попробуем провести небольшой эксперимент с использованием кода из Листинга 2. Возьмите второй цикл из кода первого примера и запустите его несколько раз. Однако на этот раз измените размер массива и измерьте среднее время выполнения одной итерации цикла.

Цель этого эксперимента — запустить тривиальный алгоритм над структурой данных, размер которой мы можем контролировать. Этот эксперимент должен показать зависимость между размером массива и временем, необходимым для модификации одного элемента.

Листинг 2. Тест, позволяющий увидеть, как изменение размера структуры данных может повлиять на производительность во время выполнения программы.

private static final int ARRAY_CONTENT = 777;
@Param({"1024", "2048", "4096", "8192", "16384", …, "536870912"})
public int size;
public int[] array;
public int counter;
public int mask;
@Setup(Level.Iteration)
public void setUp() {
final int elements = size / 4;
final int indexes = elements / 16;
mask = indexes - 1;
array = new int[elements];
Arrays.fill(array, ARRAY_CONTENT);
counter = 0;
for (int i = 0; i < indexes; i++) {
seqIndex[i] = 16 * i;
}
}
@Benchmark
public void benchLoop() {
array[16 * counter] *= 3;
counter = (counter + 1) & mask;
}

Прежде чем посмотреть на реальные результаты, давайте немного порассуждаем о том, что мы ожидаем увидеть. Доступ к одному элементу массива происходит за определенный (константный) промежуток времени, записываемый в виде O(1) согласно нотации большого О. Следовательно, внутренняя часть цикла тоже должна выполняться за константное время. Таким образом, для достаточно больших массивов мы достигнем верхней границы этого показателя, которая будет константной. Но что происходит до достижения верхней границы? Всегда ли время выполнения будет одинаковым?

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

Почему вообще существует такая зависимость и откуда берутся эти ступени? Мы сможем ответить на этот вопрос, если вспомним о различных типах кэш-памяти в современном процессоре.

Кэш-память, как правило, не является единым блоком, а состоит из нескольких иерархических уровней с различными размерами и временем доступа. Как показано на Рисунке 7, кэш L1 является самым маленьким и самым быстрым. L2 больше и значительно медленнее. L3 еще больше и медленнее, но все равно намного быстрее основной памяти.

Насколько велики разрывы в производительности между различными уровнями кэш-памяти? Чтобы объяснить это в более доступной для понимания форме, мой бывший коллега Ричард Томпсон (Richard Thompson) придумал “пивную иерархию”. Представьте себе, что вы сидите перед телевизором, смотрите игру любимой спортивной команды, и вам хочется выпить пива.

• Кэш L1 — это бутылка пива в вашей руке. Время доступа к ней практически мгновенно (< 1 нс), но ее объем, если можно так выразиться, крайне ограничен (например, 32 КБ на моем компьютере).

• Кэш L2 — это холодильник рядом с диваном. Время доступа все еще довольно мало (7 нс), но объем значительно больше (256 КБ, что эквивалентно 8 бутылкам пива).

• Кэш L3 — это холодильник на кухне. Время доступа уже заметно больше (25 нс), но объем настолько велик, что аналогия начинает рассыпаться (8 МБ, что эквивалентно 256 бутылкам пива).

• Оперативная память — это магазин на углу. Время доступа к нему огромно (100 нс), но пива там хватит, наверное, на всю вашу жизнь (16 Гбайт, что эквивалентно более чем полумиллиону бутылок пива).

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

А теперь давайте вернемся к графику на Рисунке 6. Каждое плато на графике соответствует одному из уровней в иерархии кэш-памяти. Пока массив помещается в кэши L1 и L2, время доступа очень мало. Но как только массив становится слишком большим и его приходится считывать из кэша L3, время доступа заметно увеличивается. И то же самое происходит, когда массив не помещается в кэш L3 и его приходится читать из оперативной памяти. Если присмотреться, то на графике можно разглядеть небольшой перескок между кэшами L1 и L2.

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

Схемы доступа к данным и инструмент perf

Размер данных влияет на производительность. А влияет ли на производительность порядок (схема) доступа к данным? Чтобы найти ответ на этот вопрос, нам нужно немного изменить предыдущий эксперимент. Теперь вместо того чтобы просто пробегать по массиву по порядку, мы создадим второй массив, в котором будет храниться порядок доступа. Сначала мы выполним последовательный доступ к массиву, как и раньше, а затем – произвольный, и замерим разницу. Код обоих экспериментов приведен в Листинге 3.

Листинг 3. Разный порядок доступа к данным.

public int[] rndIndex;
@Setup(Level.Iteration)
public void setUp() {
…
rndIndex = new int[indexes];
final List<Integer> list = new ArrayList<>(indexes);
for (int i=0; i<indexes; i++) {
list.add(16 * i);
}
Collections.shuffle(list);
for (int i=0; i<indexes; i++) {
rndIndex[i] = list.get(i);
}
}

Если мы проведем этот эксперимент с массивами различной длины и на основе результатов построим график, то у нас получатся две кривые, как показано на Рисунке 8. И вот мы снова видим уже знакомую картину со ступеньками. Обе кривые демонстрируют одинаковое время доступа на двух нижних уровнях, которые соответствуют кэшам L1 и L2.

Но на третьем уровне производительность схемы последовательного доступа заметно выше. На четвертом уровне наблюдается уже существенная разница. Почему порядок доступа не оказывает особого влияния на малые массивы и так ощутим на больших?

Разобраться, что происходит внутри компьютера, нам поможет профилировщик Linux – инструмент perf, который собирает и отображает события, генерируемые процессором и системой памятью во время выполнения программы. Способ работы с perf в командной строке напоминает работу с git. Вызвать perf можно с помощью команды, которую вы хотите выполнить, например:

perf COMMAND [ARGS]

Получить список всех команд можно с помощью команды perf –help. Чтобы получить справку по конкретной команде, можно выполнить следующее:

perf help COMMAND

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

perf stat [ARGS] PROGRAM

Эта команда, введенная без каких-либо аргументов, запустит программу PROGRAM, и будет отслеживать некоторые общие события до завершения работы программы, после чего выведет статистику. На Рисунке 9 вы можете видеть типичный вывод:

С помощью опции -e можно указать, какие именно события должны отслеживаться. Чтобы увидеть список поддерживаемых событий, запустите команду perf list.

В Java обычно не требуется отслеживать всю программу целиком, поскольку это предполагает подключение виртуальной машины, just-in-time (JIT) компиляции и т.д. К счастью, в perf можно подключиться к запущенному процессу с помощью опции -p. Необходимо указать программу, которая будет выполняться – измерение закончится, как только эта программа завершится. Чтобы задать длительность теста можно использовать команду sleep.

Сначала измерим оба цикла, используя стандартные настройки perf. Это даст нам хорошее представление о быстродействии. На Рисунке 10 мы видим интересные результаты:

Количество тактов простоя (stalled front-end/back-end cycles) существенно отличается в обоих прогонах. Такт простоя означает, что процессор простаивает в ожидании чего-то. Одной из наиболее вероятных причин front-end тактов простоя является "непопадание" в кэш (cache miss — отсутствие затребованных данных в кэше), в результате которого процессор ожидает поступления данных из оперативной памяти или более медленного кэша. Для подтверждения этого предположения можно снова запустить perf, но на этот раз специально для измерения нагрузки на кэш и процента промахов. Результат можно увидеть на Рисунке 11:

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

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

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

• В первом случае, когда вы проходили массив последовательно, угадать следующую ячейку памяти было легко, и префетчер мог смягчить значительную часть потерь производительности, предварительно выбрав следующую ячейку памяти. В большинстве случаев так и надо.

• Но при случайном обращении к массиву правильно угадать следующую ячейку памяти было невозможно, и алгоритму приходилось ждать, пока данные загрузятся из оперативной памяти. Тем не менее, каких-либо минусов у префетчинга нет.

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

Использование инструментов микробенчмаркинга

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

Java Microbenchmark Harness (JMH) является, пожалуй, лучшим из существующих на сегодняшний день. JMH — это Java-инструмент для создания, запуска и анализа микробенчмарков, написанных на Java и других языках, ориентированных на JVM.

Тесты, написанные под JMH, аналогичны JUnit-тестам. Код, который вы хотите проверить, должен находиться в одном методе и должен быть аннотирован @Benchmark. Тест можно конфигурировать с помощью аннотаций на уровне класса. На Рисунке 13 показаны наиболее важные аннотации и их значение. Вам следует немного поэкспериментировать с этим инструментом, чтобы понять, как он работает.

Заключение

Чаще всего процессы на аппаратном уровне не оказывают существенного влияния на программы, но не всегда. Поэтому иметь хотя бы приблизительное представление о том, что происходит на аппаратном уровне, очень полезно.

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

Дополнительные материалы по теме

• How L1 and L2 CPU caches work, and why they’re an essential part of modern chips

• Java Microbenchmark Harness

• Comparing workload performance

• Book review: Optimizing Java

Недавно ученые открыли, что на свете бывают невнимательные разработчики, которые все делают наоборот. Ученые придумали, что таким разработчикам нужно давать не полезные, а вредные советы. Они все сделают наоборот, и получится как раз правильно.

Приглашаем всех желающих разработчиков на открытый урок сегодня в 20:00, на котором разберем вредные советы по созданию кода. После занятия вы точно будете знать, как НЕ надо писать код, чтобы успешно проходить собеседования и работать в команде на проектах. Это бесплатное занятие пройдет в рамках курса «Углубленное изучение языка Java». Записаться можно по ссылке.