Как именно на R влияет предсказание ветвления?

Question

Некоторые ссылки:

_{Это продолжение этого Почему обработка отсортированного массива быстрее, чем обработка несортированного массива?}

_{Единственный пост в теге r , который, как я обнаружил, несколько связан с предсказанием ветвления, был Почему строка матрицы выборки очень медленная?}

Объяснение проблемы:

Я исследовал, быстрее ли обрабатывается отсортированный массив, чем несортированный (так же, как проблема, проверенная в Java и C - первая ссылка), чтобы увидеть, влияет ли предсказание ветвления на R таким же образом.

Посмотрите на примеры ниже:

set.seed(128)
#or making a vector with 1e7
myvec <- rnorm(1e8, 128, 128)  

myvecsorted <- sort(myvec)

mysumU = 0
mysumS = 0

SvU <- microbenchmark::microbenchmark(
  Unsorted = for (i in 1:length(myvec)) {

    if (myvec[i] > 128) {
      mysumU = mysumU + myvec[i]
    }

  } ,
  Sorted = for (i in 1:length(myvecsorted)) {

    if (myvecsorted[i] > 128) {
      mysumS = mysumS + myvecsorted[i]
    }

  } ,
  times = 10)


ggplot2::autoplot(SvU)

Вектор с элементами 1e7 Вектор с 1e8 элементами

Вопрос:

• Во-первых, я хочу знать, почему "Sorted" вектор не является самым быстрым за все время и не имеет такой же величины, как выражено в Java?
• Во-вторых, почему отсортированное время выполнения имеет более высокую вариацию по сравнению с одним из несортированных?

NB Мой процессор - i7-6820HQ при 2,70 ГГц Skylake, четырехъядерный с гиперпоточностью .

Обновление:

Чтобы исследовать вариант , я сделал microbenchmark с вектором 100 миллионов элементов (n=1e8) и повторил тест 100 раз (* 1076)*). Вот связанный сюжет с этим эталоном.

Вот мой sessioninfo:

R version 3.6.1 (2019-07-05)
Platform: x86_64-w64-mingw32/x64 (64-bit)
Running under: Windows 10 x64 (build 16299)

Matrix products: default

locale:
[1] LC_COLLATE=English_United States.1252  LC_CTYPE=English_United States.1252    LC_MONETARY=English_United States.1252
[4] LC_NUMERIC=C                           LC_TIME=English_United States.1252    

attached base packages:
[1] compiler  stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] rstudioapi_0.10      reprex_0.3.0         cli_1.1.0            pkgconfig_2.0.3      evaluate_0.14        rlang_0.4.0         
[7] Rcpp_1.0.2           microbenchmark_1.4-7 ggplot2_3.2.1 

Answer 1

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

---

R - интерпретируемый язык, а не JIT, скомпилированный для машинного кода, такого как Java, или заблаговременно, как C. ( IЯ не знаю много о внутренностях R, только о процессорах и производительности, поэтому я делаю много предположений здесь .)

Код, который работает на реальном оборудовании процессора интерпретатор R , не совсем ваша R-программа.

Управляющие зависимости в R-программе (например, if()) становятся data зависимостями в интерпретаторе. В настоящее время выполняется только данные для интерпретатора, работающего на реальном CPU.

Различные операции в программе R становятся зависимостями управления в интерпретаторе. Например, вычисляя myvec[i], оператор +, вероятно, будет выполняться двумя различными функциями в интерпретаторе. И отдельная функция для > и if() операторов.

Классический цикл интерпретатора основан на косвенной ветви, которая отправляется из таблицы указателей функций. Вместо того, чтобы быть выбранным / не принятым, ЦПУ необходим прогноз для одного из многих недавно использованных целевых адресов. Я не знаю, использует ли R одну непрямую ветвь, подобную этой, или пытается придумать что-то более похожее на то, чтобы конец каждой отправки блока интерпретатора переходил к следующей, вместо того, чтобы вернуться к главному циклу отправки.

СовременныйПроцессоры Intel (такие как Haswell и более поздние) имеют прогноз IT-TAGE (длина непрямой TAgged GEometric истории). Состояние "занято / не принято" в предыдущих ветвях на пути выполнения используется в качестве индекса в таблице прогнозов. Это в основном решает проблему предсказания ветвления интерпретатора, позволяя ему делать удивительно хорошую работу, особенно когда интерпретируемый код (код R в вашем случае) повторяет одно и то же.

• Прогнозирование ветвлений и работа переводчиков - не доверяйте фольклору (2015) - ITTAGE Haswell - огромное улучшение для переводчиков, лишающее законной силы прежнюю мудрость о том, что одна косвенная ветвь для отправки интерпретатора была катастрофой,Я не знаю, что на самом деле использует R;есть полезные приемы.
• Оптимизация предварительной загрузки X86: многопоточный код "computed goto" имеет больше ссылок.
• https://comparch.net/2013/06/30/why-tage-is-the-best/
• https://danluu.com/branch-prediction/ имеет несколько ссылок на эту тему внизу. Также упоминается, что AMD использовала предикторы Perceptron в семействах Bulldozer и Zen: как нейронная сеть.

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

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

---

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

Если Intel старше, чем Haswell илиAMD старше, чем Zen, вы можете получить много неверных прогнозов даже с отсортированным массивом, если шаблон не достаточно прост для косвенного предиктора истории ветвления, чтобы на него можно было привязаться. Это скрыло бы разницу в большем количестве шума.

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