Рубрики
Без рубрики

Прогнозирование ветвей на Java

Краткий и практический обзор прогнозирования ветвей в Java.

Автор оригинала: Graham Cox.

1. введение

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

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

2. Что Такое Конвейеры Инструкций?

Когда мы пишем любую компьютерную программу, мы пишем набор команд, которые, как мы ожидаем, компьютер будет выполнять последовательно.

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

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

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

Например, у нас может быть простая программа:

int a = 0;
a += 1;
a += 2;
a += 3;

Это может быть обработано конвейером, состоящим из сегментов выборки, декодирования, выполнения и хранения, как:

Здесь мы можем видеть, как общее выполнение четырех команд выполняется параллельно, что делает всю последовательность быстрее.

3. Каковы опасности?

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

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

Давайте изменим нашу простую программу, чтобы ввести ветвь:

int a = 0;
a += 1;
if (a < 10) {
  a += 2;
}
a += 3;

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

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

4. Что Такое Прогнозирование Ветвей?

Предсказание ветвей-это дополнение к вышесказанному, когда наш компьютер попытается предсказать, в какую сторону пойдет ветвь, а затем действовать соответственно.

В нашем приведенном выше примере процессор может предсказать, что if (a < 10) , скорее всего, будет true , и поэтому он будет действовать так, как если бы команда a была следующей для выполнения. Это приведет к тому, что поток будет выглядеть примерно так:

Мы сразу видим, что это улучшило производительность нашей программы – теперь она занимает девять тиков, а не 11, так что это на 19% быстрее.

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

Давайте повернем наше условное условие так, чтобы оно было теперь ложным :

int a = 0;
a += 1;
if (a > 10) {
  a += 2;
}
a += 3;

Это может выполнить что-то вроде:

Теперь это происходит медленнее, чем в предыдущем потоке, хотя мы делаем меньше! Процессор неправильно предсказал , что ветвь будет оценена как true , начал ставить в очередь инструкцию a , а затем должен был отбросить ее и начать сначала, когда ветвь будет оценена как false.

5. Реальное влияние на код

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

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

5.1. Подсчет записей в Списке

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

List numbers = LongStream.range(0, top)
    .boxed()
    .collect(Collectors.toList());

if (shuffle) {
    Collections.shuffle(numbers);
}

long cutoff = top / 2;
long count = 0;

long start = System.currentTimeMillis();
for (Long number : numbers) {
    if (number < cutoff) {
        ++count;
    }
}
long end = System.currentTimeMillis();

LOG.info("Counted {}/{} {} numbers in {}ms",
    count, top, shuffle ? "shuffled" : "sorted", end - start);

Обратите внимание, что мы только синхронизируем цикл, который выполняет подсчет, потому что это

Если мы генерируем достаточно маленькие списки, то код выполняется так быстро, что его невозможно синхронизировать — список размером 100 000 все еще показывает время 0 мс. Однако, когда список становится достаточно большим, чтобы мы могли его рассчитать, мы можем увидеть значительную разницу, основанную на том, перетасовали ли мы список или нет. Для списка из 10 000 000 номеров:

  • Сортировка – 44 мс
  • Перетасовка – 221 мс

То есть для подсчета перетасованного списка требуется в 5 раз больше времени, чем для отсортированного списка, даже если фактические подсчитываемые числа одинаковы.

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

5.2. Порядок филиалов

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

if (mostLikely) {
  // Do something
} else if (lessLikely) {
  // Do something
} else if (leastLikely) {
  // Do something
}

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

List numbers = LongStream.range(0, top)
  .boxed()
  .collect(Collectors.toList());
if (shuffle) {
    Collections.shuffle(numbers);
}

long cutoff = (long)(top * cutoffPercentage);
long low = 0;
long high = 0;

long start = System.currentTimeMillis();
for (Long number : numbers) {
    if (number < cutoff) {
        ++low;
    } else {
        ++high;
    }
}
long end = System.currentTimeMillis();

LOG.info("Counted {}/{} numbers in {}ms", low, high, end - start);

Этот код выполняется примерно за одно и то же время – ~35 мс для отсортированных чисел, ~200 мс для перетасованных чисел – при подсчете 10 000 000 чисел, независимо от значения cutoffPercentage .

Это происходит потому, что предсказатель ветвей одинаково обрабатывает обе ветви и правильно угадывает, в какую сторону мы пойдем за ними.

5.3. Комбинирование условий

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

Например, если мы сравниваем два числа с 0, альтернативный подход состоит в том, чтобы умножить их вместе и сравнить результат с 0. Затем это означает замену условия умножением. Но стоит ли это того?

Давайте рассмотрим пример:

long[] first = LongStream.range(0, TOP)
  .map(n -> Math.random() < FRACTION ? 0 : n)
  .toArray();
long[] second = LongStream.range(0, TOP)
  .map(n -> Math.random() < FRACTION ? 0 : n)
  .toArray();

long count = 0;
long start = System.currentTimeMillis();
for (int i = 0; i < TOP; i++) {
    if (first[i] != 0 && second[i] != 0) {
        ++count;
    }
}
long end = System.currentTimeMillis();

LOG.info("Counted {}/{} numbers using separate mode in {}ms", count, TOP, end - start);

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

  • Отдельные условия – 40 мс
  • Множественное и одиночное условие – 22 мс

Таким образом, вариант, который использует два разных условия, на самом деле занимает в два раза больше времени для выполнения.

6. Заключение

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

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

Примеры примеров из этой статьи доступны на GitHub .