Два тела цикла или одно (результат идентичен)

Question

Я давно задавался вопросом, что является более эффективным в отношении более эффективного использования кэшей ЦП (которые, как известно, выигрывают от локальности ссылок) - два цикла, каждый перебирающий один и тот же математический набор чисел, каждый с разным телом цикла или иметь одну петлю, которая «объединяет» два тела в одно и, таким образом, обеспечивает идентичный общий результат, но все в себе?

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

Предполагая, что:

1. Стоимость f и g каждая незначительна по сравнению со стоимостью завершения всего цикла, содержащего каждый
2. f и g используют большую часть кэша каждый по отдельности, и поэтому кэш будет аннулирован одним вызовом за другим (что было бы в случае версии с одним контуром)
3. Процессор Intel Core Duo
4. Исходный код языка C
5. gcc компилятор, без переключателей

Итерируемый набор является математическим набором, а не контейнером чисел в памяти, таким как вектор или список. Смотрите пример ниже.

Пожалуйста, не отвечайте на вопрос "преждевременная оптимизация - зло": -)

Пример версии с двумя циклами, за которую я выступаю:

int j = 0, k = 0;

for(int i = 0; i < 1000000; i++)
{
    j += f(i);
}

for(int i = 0; i < 1000000; i++)
{
    k += g(i);
}

Answer 1

Измерить - значит знать.

Answer 2

Интуитивно понятен один цикл: вы увеличиваете i на миллион раз, а все остальные операции остаются неизменными.

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

Как вы говорите: это зависит.

Answer 3

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

• Что делают f() и g()?Может ли один из них аннулировать все строки кэша команд (эффективно вытесняя другую)?Может ли это произойти и в кеше команд L2 (маловероятно)?Тогда сохранение только одного из них может быть полезным. Примечание: Обратное не означает «иметь один цикл», потому что:
• Работают ли f() и g() на больших объемах данных, в соответствии с i?Тогда было бы неплохо узнать, работают ли они на одном и том же наборе данных - опять же, вы должны подумать о том, не работает ли работа с двумя разными наборами с помощью кеша.
• Еслиf() и g() действительно так примитивны, как вы указали вначале, и я предполагаю, что как по размеру кода, так и по времени выполнения и сложности кода проблемы локальности кэша не возникнут в таких маленьких кусочках кода, как этот - вашСамая большая проблема была бы, если бы какой-то другой процесс был запланирован с фактической работой, и аннулировал бы все кэши, пока не наступил черед вашего процесса.

Заключительная мысль: учитывая, что такие процессы, как указано вышеможет быть редким явлением в вашей системе (и я использую «редкий» довольно свободно), вы могли бы рассмотреть возможность сделать обе ваши функции встроенными, и позволить компилятору развернуть цикл.Это связано с тем, что для кеша инструкций возвращение к L2 не представляет особой проблемы, и вероятность того, что одна строка кеша, содержащая i, j, k, будет аннулирована в этом цикле, выглядит не так уж ужасно.Однако, если это не так, некоторые подробности будут полезны.

Answer 4

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

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

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

Настройка кеша в лучшем случае сложна. Я регулярно демонстрирую, что даже со встроенной системой, без прерываний, с одной задачей, одним и тем же исходным кодом. Время выполнения / производительность могут сильно различаться, просто меняя параметры оптимизации компилятора, изменяя компиляторы, как марки компиляторов, так и версии компиляторов, gcc 2.x против 3.x против 4.x (gcc не обязательно производит более быстрый код с более новыми версиями, кстати) ) (и компилятор, который довольно хорош во многих целях, не очень хорош ни в одной конкретной цели). Один и тот же код различных компиляторов или опций может изменять время выполнения в несколько раз, в 3 раза быстрее, в 10 раз быстрее и т. Д. Как только вы приступите к тестированию с кешем или без него, это станет еще интереснее. Добавьте один nop в ваш стартовый код, чтобы вся ваша программа переместилась на одну инструкцию в памяти, и ваши строки кэша теперь попадают в разные места. Тот же компилятор, тот же код. Повторите это с двумя nops, тремя nops и т. Д. Один и тот же компилятор, один и тот же код, вы можете видеть различия в десятки процентов (для тестов, которые я провел в тот день на этой цели с этим компилятором) различия все лучше и хуже. Это не означает, что вы не можете настроить кеш, это просто означает, что попытка выяснить, помогает ли ваша настройка или причиняет вред, может быть трудной. Обычный ответ - просто «время и посмотри», но это больше не работает, и вы можете получить отличные результаты на своем компьютере в тот день с этой программой с этим компилятором. Но завтра на вашем компьютере или в любой другой день на чужом компьютере вы, возможно, будете делать вещи медленнее, а не быстрее. Вам нужно понять, почему те или иные изменения сделали это быстрее, возможно, это не имело никакого отношения к вашему коду, ваша программа электронной почты могла загружать много почты в фоновом режиме во время одного теста, а не во время другого.

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

Answer 5

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

Из вашего примера:

int j = 0, k = 0;

for(int i = 0; i < 1000000; i++)
{
    j += f(i);
}

for(int i = 0; i < 1000000; i++)
{
    k += g(i);
}

Я бы слил две петли в одну, как это:

int j = 0, k = 0;

for(int i = 0; i < 1000000; i++)
{
    j += f(i);
    k += g(i);
}

Если это невозможно, выполните оптимизацию под названием Loop-Tiling:

#define TILE_SIZE 1000 /* or whatever you like - pick a number that keeps   */
                       /* the working-set below your first level cache size */

int i=0; 
int elements = 100000;

do {
  int n = i+TILE_SIZE; 
  if (n > elements) n = elements;

  // perform loop A
  for (int a=i; a<n; a++)
  {
    j += f(i);
  }

  // perform loop B
  for (int a=i; a<n; a++)
  {
    k += g(i);
  }

  i += n
} while (i != elements)

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

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

Answer 6

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

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

Answer 7

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