Два тел циклов или один (заканчиваются идентичные),

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

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

Как говориться: все зависит от ситуации.

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

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

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

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

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

Настройка кеша в лучшем случае сложна. Я регулярно демонстрирую, что даже со встроенной системой нет прерываний, одна задача, тот же исходный код. Время выполнения / производительность могут сильно различаться, просто меняя параметры оптимизации компилятора, меняя компиляторы, обе марки компиляторов или версии компиляторов, gcc 2.x vs 3.x vs 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);
}

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)

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

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

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

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