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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 миллион раз, потому что кэш недостаточно велик, чтобы вместить все эти данные.

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

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

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

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