Как вы можете выделить разветвления из узкой петли? - PullRequest
Новая
       3

Как вы можете выделить разветвления из узкой петли?

0 голосов
/ 27 сентября 2011

У меня вопрос: как я могу добавить функции в цикл обработки без лишних затрат на проверку истинности / ложности пользовательских настроек для навигации по ветвям?Настройки одинаковы для всех итераций цикла.Делают ли современные процессоры с предсказанием ветвления это ненужным?

Мои программы следуют этой схеме:

  1. Пользователь настраивает параметры, флажки, ползунки, числовые записи.
  2. Данныеобрабатывается при запуске обновления
    1. Применение настроек к локальным переменным
    2. Запуск цикла по большому набору данных
      • добавление операторов if для обхода неиспользуемого кода из пользовательских настроек.
      • возврат из цикла
    3. возврат преобразованных данных

Как можно заранее запрограммировать или встроить все перестановки?

пример: 

bool setting1 = true;
bool setting2 = false;
vector<float> data;

for(int i=0;i<100000;i++)
    data.push_back(i);

for(int i=0;i<100000;i++) {
    if (setting1)
    {
       doStuff(data[i]);
       ....
    }
    if (setting2)
    {
       doMoreStuff(data[i]);
       .....
    }

    .... //etc
}

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

Ответы [ 4 ]

4 голосов
/ 27 сентября 2011

Использовать шаблоны для основного цикла. 

template <bool A, bool B>
void loop() {
  while (1) {
      if (A) // will get compiled out if A == false
      {
         doStuff(data[i]);
         ....
      }
      if (B)
      {
         doMoreStuff(data[i]);
         .....
      }

      .... //etc
  }
}

Когда вы меняете настройки: (возможно, вы могли бы сделать это меньше кода) 

if (setting1) {
  if (setting2)
    loop<1,1>;
  else 
    loop<1,0>;
}
else {
  if (setting2)
    loop<0,1>;
  else 
    loop<0,0>;
}

Вы хотите оставаться в цикле (), пока настройки не изменятся.

Это следует использовать с осторожностью, поскольку это может привести к вздутию живота.

Профилированные ответы (оптимизация G ++ O2): 

 %Time
 46.15      0.84     0.84                             fb() (blackbear)
 38.37      1.53     0.69                             fa() (OP)
 16.13      1.82     0.29                             fc() (pubby8)
2 голосов
/ 27 сентября 2011

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

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

Факторизация условий вне цикла, чтобы создать несколько циклов, поначалу может показаться хорошей идеей, однако, если большинство настроекв основном включены, и ваши фактические операции достаточно дешевы, чтобы вообще затруднить загрузку, вы можете обнаружить, что производительность практически не меняется - каждый новый цикл имеет стоимость за каждую итерацию!

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

1 голос
/ 27 сентября 2011

Если размер набора данных известен во время компиляции, то компилятор потенциально может выполнить:

  • развертывание цикла

Если это математическая операция

  • Векторизация может войти в игру

Вы также можете сделать логику наизнанку: 

if (epic-setting)
{
//massive for loop
}

Это это плохо длялокальность памяти, как сказал один человек.

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

Если ваша операция с данными полностью параллельна, т. Е. Вы используете SIMD, вы можете исследовать потоки операций: например, открыть 3 потока и заставить всех 3 выполнить операцию i % t, tявляется индексом потока, i является индексом данных.(Вы можете разделить данные по-разному).Для достаточно большого набора данных, если у вас нет операций синхронизации, вы увидите линейное ускорение.

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

1 голос
/ 27 сентября 2011

Таким образом вы можете избежать накладных расходов (предположим, что settingx не влияет на settingy): 

if(setting1) {
    for(int i=0;i<100000;i++) {
        // ...
    }
}

if(setting3) {
    for(int i=0;i<100000;i++) {
        // ...
    }
}

if(setting3) {
    for(int i=0;i<100000;i++) {
        // ...
    }
}

Но, на мой взгляд, лучшее решение - сохранить ваш код. Сегодняшние единицы предсказания ветвлений очень мощные, и, учитывая, что вы будете повторять много тысяч раз, когда каждая ветвь будет иметь одинаковый результат, вы можете позволить себе несколько циклов прогрева;)

EDIT:
Я сравнил наши подходы к проблеме с простой консольной программой ( sources , хотя это c #). Цикл выполняется 1000000 раз, и я использовал тригонометрические функции вместе с операциями с плавающей запятой двойной точности. Тест 2 - это решение, которое я показал выше, а три буквы - это значение настройки1, настройки2 и настройки3.
Результаты: 

test 1 - fft: 13974 ms
test 2 - fft: 14106 ms

test 1 - tft: 27728 ms
test 2 - tft: 28081 ms

test 1 - ttt: 41833 ms
test 2 - ttt: 41982 ms

Я также выполнил тестовый прогон со всеми тремя тестовыми функциями пустыми, чтобы доказать цикл, и издержки на вызов минимальны: 

test 1 - fft: 4 ms
test 2 - fft: 4 ms

test 1 - tft: 8 ms
test 2 - tft: 8 ms

test 1 - ttt: 12 ms
test 2 - ttt: 12 ms

Фактически, мое решение примерно на 1% медленнее . Второй пункт моего ответа, тем не менее, оказался верным: накладные расходы на петли полностью просматриваются.

...