«1. Введение

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

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

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

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

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

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

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

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

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

Это может быть обработано конвейером, состоящим из сегментов Fetch, Decode, Execute, Store, как:

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

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

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

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

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

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

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

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

4. Что такое прогноз ветвления?

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

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

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

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

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

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

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

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

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

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

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

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

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

List<Long> 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
}

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

List<Long> 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);

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

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.

«