Вопрос: Почему в отдельных циклах стигментные добавления намного быстрее, чем в комбинированном цикле?


предполагать a1, b1, c1, а также d1указывают на кучу памяти, а мой цифровой код имеет следующий цикл ядра.

const int n = 100000;

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
    c1[j] += d1[j];
}

Этот цикл выполняется 10 000 раз через другой внешний forпетля. Чтобы ускорить его, я изменил код на:

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
}

for (int j = 0; j < n; j++) {
    c1[j] += d1[j];
}

Составлено на MS Visual C ++ 10.0 с полной оптимизацией и SSE2 для 32-разрядных Intel Core 2 Duo (x64), первый пример занимает 5,5 секунды, а пример с двумя циклами занимает всего 1,9 секунды. Мой вопрос: (Пожалуйста, обратитесь к моему перефразированному вопросу внизу)

PS: Я не уверен, если это поможет:

Разборка для первого цикла в основном выглядит так (этот блок повторяется примерно пять раз в полной программе):

movsd       xmm0,mmword ptr [edx+18h]
addsd       xmm0,mmword ptr [ecx+20h]
movsd       mmword ptr [ecx+20h],xmm0
movsd       xmm0,mmword ptr [esi+10h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [edx+20h]
addsd       xmm0,mmword ptr [ecx+28h]
movsd       mmword ptr [ecx+28h],xmm0
movsd       xmm0,mmword ptr [esi+18h]
addsd       xmm0,mmword ptr [eax+38h]

Каждый цикл примера двойного цикла создает этот код (следующий блок повторяется примерно три раза):

addsd       xmm0,mmword ptr [eax+28h]
movsd       mmword ptr [eax+28h],xmm0
movsd       xmm0,mmword ptr [ecx+20h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [ecx+28h]
addsd       xmm0,mmword ptr [eax+38h]
movsd       mmword ptr [eax+38h],xmm0
movsd       xmm0,mmword ptr [ecx+30h]
addsd       xmm0,mmword ptr [eax+40h]
movsd       mmword ptr [eax+40h],xmm0

Вопрос оказался нецелесообразным, так как поведение сильно зависит от размеров массивов (n) и кэша ЦП. Поэтому, если есть еще больший интерес, я перефразирую вопрос:

Не могли бы вы подробно рассказать о деталях, которые приводят к различным типам поведения кэша, как показано пятью областями на следующем графике?

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

PPS: Вот полный код. Оно использует TBB Tick_Countдля более высокого разрешения, которое можно отключить, не определяя TBB_TIMINGMacro:

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>

//#define TBB_TIMING

#ifdef TBB_TIMING   
#include <tbb/tick_count.h>
using tbb::tick_count;
#else
#include <time.h>
#endif

using namespace std;

//#define preallocate_memory new_cont

enum { new_cont, new_sep };

double *a1, *b1, *c1, *d1;


void allo(int cont, int n)
{
    switch(cont) {
      case new_cont:
        a1 = new double[n*4];
        b1 = a1 + n;
        c1 = b1 + n;
        d1 = c1 + n;
        break;
      case new_sep:
        a1 = new double[n];
        b1 = new double[n];
        c1 = new double[n];
        d1 = new double[n];
        break;
    }

    for (int i = 0; i < n; i++) {
        a1[i] = 1.0;
        d1[i] = 1.0;
        c1[i] = 1.0;
        b1[i] = 1.0;
    }
}

void ff(int cont)
{
    switch(cont){
      case new_sep:
        delete[] b1;
        delete[] c1;
        delete[] d1;
      case new_cont:
        delete[] a1;
    }
}

double plain(int n, int m, int cont, int loops)
{
#ifndef preallocate_memory
    allo(cont,n);
#endif

#ifdef TBB_TIMING   
    tick_count t0 = tick_count::now();
#else
    clock_t start = clock();
#endif

    if (loops == 1) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                a1[j] += b1[j];
                c1[j] += d1[j];
            }
        }
    } else {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a1[j] += b1[j];
            }
            for (int j = 0; j < n; j++) {
                c1[j] += d1[j];
            }
        }
    }
    double ret;

#ifdef TBB_TIMING   
    tick_count t1 = tick_count::now();
    ret = 2.0*double(n)*double(m)/(t1-t0).seconds();
#else
    clock_t end = clock();
    ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC);
#endif

#ifndef preallocate_memory
    ff(cont);
#endif

    return ret;
}


void main()
{   
    freopen("C:\\test.csv", "w", stdout);

    char *s = " ";

    string na[2] ={"new_cont", "new_sep"};

    cout << "n";

    for (int j = 0; j < 2; j++)
        for (int i = 1; i <= 2; i++)
#ifdef preallocate_memory
            cout << s << i << "_loops_" << na[preallocate_memory];
#else
            cout << s << i << "_loops_" << na[j];
#endif

    cout << endl;

    long long nmax = 1000000;

#ifdef preallocate_memory
    allo(preallocate_memory, nmax);
#endif

    for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2)))
    {
        const long long m = 10000000/n;
        cout << n;

        for (int j = 0; j < 2; j++)
            for (int i = 1; i <= 2; i++)
                cout << s << plain(n, m, j, i);
        cout << endl;
    }
}

(Он показывает FLOP / s для разных значений n.)

enter image description here


1974


источник


Ответы:


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

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

Это означает, что все ваши обращения в каждом цикле будут попадать в один и тот же кеш. Однако процессоры Intel на некоторое время имели 8-стороннюю ассоциативность кэша L1. Но на самом деле производительность не полностью единообразна. Доступ к 4-канальным каналам все еще медленнее, чем двухсторонний.

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

Вот тестовый код:

int main(){
    const int n = 100000;

#ifdef ALLOCATE_SEPERATE
    double *a1 = (double*)malloc(n * sizeof(double));
    double *b1 = (double*)malloc(n * sizeof(double));
    double *c1 = (double*)malloc(n * sizeof(double));
    double *d1 = (double*)malloc(n * sizeof(double));
#else
    double *a1 = (double*)malloc(n * sizeof(double) * 4);
    double *b1 = a1 + n;
    double *c1 = b1 + n;
    double *d1 = c1 + n;
#endif

    //  Zero the data to prevent any chance of denormals.
    memset(a1,0,n * sizeof(double));
    memset(b1,0,n * sizeof(double));
    memset(c1,0,n * sizeof(double));
    memset(d1,0,n * sizeof(double));

    //  Print the addresses
    cout << a1 << endl;
    cout << b1 << endl;
    cout << c1 << endl;
    cout << d1 << endl;

    clock_t start = clock();

    int c = 0;
    while (c++ < 10000){

#if ONE_LOOP
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
            c1[j] += d1[j];
        }
#else
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
        }
        for(int j=0;j<n;j++){
            c1[j] += d1[j];
        }
#endif

    }

    clock_t end = clock();
    cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << endl;

    system("pause");
    return 0;
}

Результаты тестов:

EDIT: результаты на фактический Архитектура архитектуры Core 2:

2 x Intel Xeon X5482 Harpertown @ 3,2 ГГц:

#define ALLOCATE_SEPERATE
#define ONE_LOOP
00600020
006D0020
007A0020
00870020
seconds = 6.206

#define ALLOCATE_SEPERATE
//#define ONE_LOOP
005E0020
006B0020
00780020
00850020
seconds = 2.116

//#define ALLOCATE_SEPERATE
#define ONE_LOOP
00570020
00633520
006F6A20
007B9F20
seconds = 1.894

//#define ALLOCATE_SEPERATE
//#define ONE_LOOP
008C0020
00983520
00A46A20
00B09F20
seconds = 1.993

Замечания:

  • 6.206 секунд с одним циклом и 2,166 секунды с двумя петлями. Это точно воспроизводит результаты OP.

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

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

Как отмечает @Stephen Cannon в комментариях, существует очень вероятная вероятность того, что это выравнивание вызывает ложное сглаживание в блоках загрузки / хранения или в кеше. Я задумался об этом и обнаружил, что у Intel на самом деле есть аппаратный счетчик для частичное наложение адресов киоски:

http://software.intel.com/sites/products/documentation/doclib/stdxe/2013/~amplifierxe/pmw_dp/events/partial_address_alias.html


5 регионов - Пояснения

Регион 1:

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

Регион 2:

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

Я точно не знаю, что здесь происходит ... Выравнивание все равно может сыграть эффект, как упоминает Агнер Фог конфликты банковского кэша , (Эта ссылка касается Sandy Bridge, но идея все равно должна быть применима к Core 2.)

Регион 3:

На данный момент данные больше не вписываются в кеш L1. Таким образом, производительность ограничена полосой пропускания L1 <-> L2.

Регион 4:

Снижение производительности в одном цикле - это то, что мы наблюдаем. И, как уже упоминалось, это связано с выравниванием, которое (скорее всего) вызывает ложное сглаживание киосков в блоках загрузки / хранения процессора.

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

Регион 5:

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


2 x Intel X5482 Harpertown @ 3.2 GHz Intel Core i7 870 @ 2.8 GHz Intel Core i7 2600K @ 4.4 GHz


1528



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

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

@ Ответ Mystical убедил многих людей (включая меня), вероятно, потому, что это был единственный, который, казалось, полагался на факты, но это был только один «информационный пункт» истины.

Вот почему я объединил его тест (используя непрерывное или отдельное распределение) и совет @James's Answer.

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

Обратите внимание, что мой первоначальный вопрос был n = 100 000 , Этот момент (случайно) проявляет особое поведение:

  1. Он обладает наибольшим несоответствием между одной и двумя версиями цикла (почти в три раза)

  2. Это единственный момент, когда однопетное (а именно, непрерывное распределение) превосходит двухпетлевую версию. (Это сделало ответ Мистицисом вообще возможным).

Результат с использованием инициализированных данных:

Enter image description here

Результат с использованием неинициализированных данных (это то, что тестировалось Mystical):

Enter image description here

И это трудно объяснить: Инициализированные данные, которые выделяются один раз и повторно используются для каждого следующего тестового примера с различным размером вектора:

Enter image description here

Предложение

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


191



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


62



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

Предполагая простую политику кэширования LIFO, этот код:

for(int j=0;j<n;j++){
    a[j] += b[j];
}
for(int j=0;j<n;j++){
    c[j] += d[j];
}

в первую очередь aа также bдля загрузки в ОЗУ, а затем полностью работать в ОЗУ. Когда начинается второй цикл, cа также dзатем будет загружаться с диска в оперативную память и работать дальше.

другой цикл

for(int j=0;j<n;j++){
    a[j] += b[j];
    c[j] += d[j];
}

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

Вероятно, вы не видите кэширование дисков в своих тестах, но вы, вероятно, видите побочные эффекты какой-либо другой формы кеширования.


Кажется, здесь немного путаницы / недоразумения, поэтому я попытаюсь немного придумать пример.

Сказать n = 2и мы работаем с байтами. В моем сценарии мы, таким образом, имеем всего 4 байта кеша и остальная часть нашей памяти значительно медленнее (скажем, в 100 раз больше доступа).

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

  • С

    for(int j=0;j<n;j++){
     a[j] += b[j];
    }
    for(int j=0;j<n;j++){
     c[j] += d[j];
    }
    
  • кэш a[0]а также a[1]тогда b[0]а также b[1]и установить a[0] = a[0] + b[0]в кеше - в кеше теперь четыре байта, a[0], a[1]а также b[0], b[1], Стоимость = 100 + 100.

  • задавать a[1] = a[1] + b[1]в кеше. Стоимость = 1 + 1.
  • Повторите для cа также d,
  • Общая стоимость = (100 + 100 + 1 + 1) * 2 = 404

  • С

    for(int j=0;j<n;j++){
     a[j] += b[j];
     c[j] += d[j];
    }
    
  • кэш a[0]а также a[1]тогда b[0]а также b[1]и установить a[0] = a[0] + b[0]в кеше - в кеше теперь четыре байта, a[0], a[1]а также b[0], b[1], Стоимость = 100 + 100.

  • выталкивать a[0], a[1], b[0], b[1]из кеша и кеша c[0]а также c[1]тогда d[0]а также d[1]и установить c[0] = c[0] + d[0]в кеше. Стоимость = 100 + 100.
  • Я подозреваю, что вы начинаете видеть, куда я иду.
  • Общая стоимость = (100 + 100 + 100 + 100) * 2 = 800

Это классический сценарий трэша.


36



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

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

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


27



Я не могу воспроизвести результаты, обсуждаемые здесь.

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

Размеры массива варьировались от 2 ^ 16 до 2 ^ 24, используя восемь петель. Я старался инициализировать исходные массивы, поэтому +=задание не запрашивало FPU чтобы добавить мусор памяти, интерпретируемый как двойной.

Я играл с различными схемами, такими как постановка задания b[j], d[j]в InitToZero[j]внутри петель, а также с использованием += b[j] = 1а также += d[j] = 1, и я получил довольно последовательные результаты.

Как и следовало ожидать, инициализация bа также dвнутри цикла, используя InitToZero[j]дал комбинированный подход преимущество, так как они выполнялись вплотную перед заданиями aа также c, но все же в пределах 10%. Идите фигуру.

Аппаратное обеспечение Dell XPS 8500 с поколением 3 Core i7 @ 3,4 ГГц и 8 ГБ памяти. При 2 ^ 16 до 2 ^ 24, используя восемь петель, суммарное время составляло 44.987 и 40.965 соответственно. Visual C ++ 2010, полностью оптимизирован.

PS: Я сменил петли на обратный отсчет до нуля, и комбинированный метод был немного быстрее. Поцарапал голову. Обратите внимание на новый размер массива и количество циклов.

// MemBufferMystery.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <string>
#include <time.h>

#define  dbl    double
#define  MAX_ARRAY_SZ    262145    //16777216    // AKA (2^24)
#define  STEP_SZ           1024    //   65536    // AKA (2^16)

int _tmain(int argc, _TCHAR* argv[]) {
    long i, j, ArraySz = 0,  LoopKnt = 1024;
    time_t start, Cumulative_Combined = 0, Cumulative_Separate = 0;
    dbl *a = NULL, *b = NULL, *c = NULL, *d = NULL, *InitToOnes = NULL;

    a = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    b = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    c = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    d = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    InitToOnes = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    // Initialize array to 1.0 second.
    for(j = 0; j< MAX_ARRAY_SZ; j++) {
        InitToOnes[j] = 1.0;
    }

    // Increase size of arrays and time
    for(ArraySz = STEP_SZ; ArraySz<MAX_ARRAY_SZ; ArraySz += STEP_SZ) {
        a = (dbl *)realloc(a, ArraySz * sizeof(dbl));
        b = (dbl *)realloc(b, ArraySz * sizeof(dbl));
        c = (dbl *)realloc(c, ArraySz * sizeof(dbl));
        d = (dbl *)realloc(d, ArraySz * sizeof(dbl));
        // Outside the timing loop, initialize
        // b and d arrays to 1.0 sec for consistent += performance.
        memcpy((void *)b, (void *)InitToOnes, ArraySz * sizeof(dbl));
        memcpy((void *)d, (void *)InitToOnes, ArraySz * sizeof(dbl));

        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
                c[j] += d[j];
            }
        }
        Cumulative_Combined += (clock()-start);
        printf("\n %6i miliseconds for combined array sizes %i and %i loops",
                (int)(clock()-start), ArraySz, LoopKnt);
        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
            }
            for(j = ArraySz; j; j--) {
                c[j] += d[j];
            }
        }
        Cumulative_Separate += (clock()-start);
        printf("\n %6i miliseconds for separate array sizes %i and %i loops \n",
                (int)(clock()-start), ArraySz, LoopKnt);
    }
    printf("\n Cumulative combined array processing took %10.3f seconds",
            (dbl)(Cumulative_Combined/(dbl)CLOCKS_PER_SEC));
    printf("\n Cumulative seperate array processing took %10.3f seconds",
        (dbl)(Cumulative_Separate/(dbl)CLOCKS_PER_SEC));
    getchar();

    free(a); free(b); free(c); free(d); free(InitToOnes);
    return 0;
}

Я не уверен, почему было решено, что MFLOPS является релевантной метрикой. Хотя идея заключалась в том, чтобы сосредоточиться на доступе к памяти, поэтому я попытался свести к минимуму количество вычислений с плавающей запятой. Я ушел в +=, но я не уверен, почему.

Прямое назначение без вычисления будет более чистым испытанием времени доступа к памяти и создаст тест, который будет равномерным независимо от количества циклов. Возможно, я пропустил что-то в разговоре, но стоит подумать дважды. Если плюс не учитывается при назначении, то суммарное время почти равно 31 секунде.


16



It's because the CPU doesn't have so many cache misses (where it has to wait for the array data to come from the RAM chips). It would be interesting for you to adjust the size of the arrays continually so that you exceed the sizes of the level 1 cache (L1), and then the level 2 cache (L2), of your CPU and plot the time taken for your code to execute against the sizes of the arrays. The graph shouldn't be a straight line like you'd expect.


14



The first loop alternates writing in each variable. The second and third ones only make small jumps of element size.

Try writing two parallel lines of 20 crosses with a pen and paper separated by 20 cm. Try once finishing one and then the other line and try another time by writting a cross in each line alternately.


12



The Original Question

Why is one loop so much slower than two loops?


Assessing The Problem

The OP's code:

const int n=100000;

for(int j=0;j<n;j++){
    a1[j] += b1[j];
    c1[j] += d1[j];
}

And

for(int j=0;j<n;j++){
    a1[j] += b1[j];
}
for(int j=0;j<n;j++){
    c1[j] += d1[j];
}

The Consideration

Considering the OP's original question about the 2 variants of the for loops and his amended question towards the behavior of caches along with many of the other excellent answers and useful comments; I'd like to try and do something different here by taking a different approach about this situation and problem.


The Approach

Considering the two loops and all of the discussion about cache and page filing I'd like to take another approach as to looking at this from a different perspective. One that doesn't involve the cache and page files nor the executions to allocate memory, in fact this approach doesn't even concern the actual hardware or the software at all.


The Perspective

After looking at the code for a while it became quite apparent what the problem is and what is generating it. Lets break this down into an algorithmic problem and look at it from the perspective of using mathematical notations then apply an analogy to the math problems as well as to the algorithms.


What We Do Know

We know is that his loop will run 100,000 times. We also know that a1, b1, c1 & d1 are pointers on a 64-bit architecture. Within C++ on a 32-bit machine all pointers are 4 bytes and on a 64-bit machine they are 8 bytes in size since pointers are of a fixed length. We know that we have 32 bytes in which to allocate for in both cases. The only difference is we are allocating 32 bytes or 2 sets of 2-8bytes on each iteration where in the 2nd case we are allocating 16 bytes for each iteration for both of the independent loops. So both loops still equals 32 bytes in total allocations. With this information let's go ahead and show the general math, algorithm and analogy of it. We do know the amount of times that the same set or group of operations will have to be performed in both cases. We do know the amount of memory that needs to be allocated in both cases. We can asses that the overall work load of the allocations between both cases will be approximately the same.


What We Don't Know

We do not know how long it will take for each case unless if we set a counter and run a bench mark test. However the bench marks were already included from the original question and from some of the answers and comments as well and we can see a significant difference between the two and this is the whole reasoning of this question to this problem and for the answering of it to begin with.


Let's Investigate

It is already apparent that many have already done this by looking at the heap allocations, bench mark tests, looking at RAM, Cache and Page Files. Looking at specific data points and specific iteration indexes was also included and the various conversations about this specific problem has many people starting to question other related things about it. So how do we begin to look at this problem by using mathematical algorithms and applying an analogy to it? We start off by making a couple of assertions! Then we build out our algorithm from there.


Our Assertions:

  • We will let our loop and its iterations be a Summation that starts at 1 and ends at 100000 instead of starting with 0 as in the loops for we don't need to worry about the 0 indexing scheme of memory addressing since we are just interested in the algorithm itself.
  • In both cases we have 4 functions to work with and 2 function calls with 2 operations being done on each function call. So we will set these up as functions and function calls to be F1(), F2(), f(a), f(b), f(c) and f(d).

The Algorithms:

1st Case: - Only one summation but two independent function calls.

Sum n=1 : [1,100000] = F1(), F2();
                       F1() = { f(a) = f(a) + f(b); }
                       F2() = { f(c) = f(c) + f(d);  }

2nd Case: - Two summations but each has its own function call.

Sum1 n=1 : [1,100000] = F1();
                        F1() = { f(a) = f(a) + f(b); }

Sum2 n=1 : [1,100000] = F1();
                        F1() = { f(c) = f(c) + f(d); }

If you noticed F2() only exists in Sum where both Sum1 and Sum2 only contains F1(). This will also be evident later on as well when we begin to conclude that there is sort of an optimization happening from the second algorithm.

The iterations through the first case Sum calls f(a) that will add to its self f(b) then it calls f(c) that will do the same but add f(d) to itself for each 100000 iterations. In the second case we have Sum1 and Sum2 And both act the same as if they were the same function being called twice in a row. In this case we can treat Sum1 and Sum2 as just plain old Sum where Sum in this case looks like this: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); } and now this looks like an optimization where we can just consider it to be the same function.


Summary with Analogy

With what we seen in the second case it almost appears as if there is optimization since both for loops have the same exact signature, but this isn't the real issue. The issue isn't the work that is being done by f(a),f(b),f(c)&f(d) in both cases and the comparison between the two it is the difference in the distance that the Summation has to travel in both cases that gives you the difference in time execution.

Think of the For Loops as being the Summations that does the iterations as being a Boss that is giving orders to two people A & B and that their jobs are to meat C & D respectively and to pick up some package from them and return it. In the analogy here the for loop or summation iterations and condition checks themselves doesn't actually represent the Boss. What actually represents the Boss here is not from the actual mathematical algorithms directly, but from the actual concept of Scope and Code Block within a routine or sub-routine, method, function, translation unit, etc. The first algorithm has 1 scope where the 2nd algorithm has 2 consecutive scopes.

Within the first case on each call slip the Boss goes to A and gives the order and A goes off to fetch B's package then the Boss goes to C and gives the orders to do the same and receive the package from D on each iteration.

Within the second case the Boss works directly with A to go and fetch B's package until all packages are received. Then the Boss works with C to do the same for getting all of D's packages.

Since we are working with an 8 byte pointer and dealing with Heap allocation let's consider this problem here. Let us say that the Boss is 100 feet from A and that A is 500 feet from C. We don't need to worry about how far the Boss is initially from C because of the order of executions. In both cases the Boss initially travels from A first then to B. This analogy isn't to say that this distance is exact; it is just a use test case scenario to show the workings of the algorithms. In many cases when doing heap allocations and working with the cache and page files, these distances between address locations may not vary that much in differences or they can very significantly depending on the nature of the data types and the array sizes.


The Test Cases:

First Case: On first iteration the Boss has to initially go 100 feet to give the order slip to A and A goes off and does his thing, but then the Boss has to travel 500 feet to C to give him his order slip. Then on the next iteration and every other iteration after the Boss has to go back and forth 500 feet between the two.

Second Case: The Boss has to travel 100 feet on the first iteration to A, but after that he is already there and just waits for A to get back until all slips are filled. Then the Boss has to travel 500 feet on the first iteration to C because C is 500 feet from A since this Boss( Summation, For Loop ) is being called right after working with A and then just waits like he did with A until all of C's order slips are done.


The Difference In Distances Traveled

const n = 100000
distTraveledOfFirst = (100 + 500) + ((n-1)*(500 + 500); 
// Simplify
distTraveledOfFirst = 600 + (99999*100);
distTraveledOfFirst = 600 + 9999900;
distTraveledOfFirst =  10000500;
// Distance Traveled On First Algorithm = 10,000,500ft

distTraveledOfSecond = 100 + 500 = 600;
// Distance Traveled On Second Algorithm = 600ft;    

The Comparison of Arbitrary Values

We can easily see that 600 is far less than 10 million. Now this isn't exact, because we don't know the actual difference in distance between which address of RAM or from which Cache or Page File each call on each iteration is going to be due to many other unseen variables, but this is just an assessment of the situation to be aware of and trying to look at it from the worst case scenario.

So by these numbers it would almost look as if Algorithm One should be 99% slower than Algorithm Two; however, this is only the The Boss's part or responsibility of the algorithms and it doesn't account for the actual workers A, B, C, & D and what they have to do on each and every iteration of the Loop. So the bosses job only accounts for about 15 - 40% of the total work being done. So the bulk of the work which is done through the workers has a slight bigger impact towards keeping the ratio of the speed rate differences to about 50-70%


The Observation: - The differences between the two algorithms

In this situation it is the structure of the process of the work being done and it does go to show that Case 2 is more efficient from both that partial optimization of having a similar function declaration and definition where it is only the variables that differ by name. And we also see that the total distance traveled in Case 1 is much farther than it is in Case 2 and we can consider this distance traveled our Time Factor between the two algorithms. Case 1 has considerable more work to do than Case 2 does. This was also seen in the evidence of the ASM that was shown between both cases. Even with what was already said about these cases, it also doesn't account for the fact that in Case 1 the boss will have to wait for both A & C to get back before he can go back to A again on the next iteration and it also doesn't account for the fact that if A or B is taking an extremely long time then both the Boss and the other worker(s) are also waiting at an idle. In Case 2 the only one being idle is the Boss until the worker gets back. So even this has an impact on the algorithm.


Conclusion:

Case 1 is a classic interpolation problem that happens to be an inefficient one. I also think that this was one of the leading reasons of why many machine architectures and developers ended up building and designing multi-core systems with the ability to do multi-threaded applications as well as parallel programming.

So even looking at it from this approach without even involving how the Hardware, OS and Compiler works together to do heap allocations that involves working with RAM, Cache, Page Files, etc.; the mathematics behind it already shows us which of these two is the better solution from using the above analogy where the Boss or the Summations being those the For Loops that had to travel between Workers A & B. We can easily see that Case 2 is at least as 1/2 as fast if not a little more than Case 1 due to the difference in the distanced traveled and the time taken. And this math lines up almost virtually and perfectly with both the Bench Mark Times as well as the Amount of difference in the amount of Assembly Instructions.



The OPs Amended Question(s)

EDIT: The question turned out to be of no relevance, as the behavior severely depends on the sizes of the arrays (n) and the CPU cache. So if there is further interest, I rephrase the question:

Could you provide some solid insight into the details that lead to the different cache behaviors as illustrated by the five regions on the following graph?

It might also be interesting to point out the differences between CPU/cache architectures, by providing a similar graph for these CPUs.


Regarding These Questions

As I have demonstrated without a doubt, there is an underlying issue even before the Hardware and Software becomes involved. Now as for the management of memory and caching along with page files, etc. which all works together in an integrated set of systems between: The Architecture { Hardware, Firmware, some Embedded Drivers, Kernels and ASM Instruction Sets }, The OS{ File and Memory Management systems, Drivers and the Registry }, The Compiler { Translation Units and Optimizations of the Source Code }, and even the Source Code itself with its set(s) of distinctive algorithms; we can already see that there is a bottleneck that is happening within the first algorithm before we even apply it to any machine with any arbitrary Architecture, OS, and Programmable Language compared to the second algorithm. So there already existed a problem before involving the intrinsics of a modern computer.


The Ending Results

However; it is not to say that these new questions are not of importance because they themselves are and they do play a role after all. They do impact the procedures and the overall performance and that is evident with the various graphs and assessments from many who have given their answer(s) and or comment(s). If you pay attention to the analogy of the Boss and the two workers A & B who had to go and retrieve packages from C & D respectively and considering the mathematical notations of the two algorithms in question you can see that without even the involvement of the computer Case 2 is approximately 60% faster than Case 1 and when you look at the graphs and charts after these algorithms have been applied to source code, compiled and optimized and executed through the OS to perform operations on the given hardware you even see a little more degradation between the differences in these algorithms.

Now if the "Data" set is fairly small it may not seem all that bad of a difference at first but since Case 1 is about 60 - 70% slower than Case 2 we can look at the growth of this function as being in terms of the differences in time executions:

DeltaTimeDifference approximately = Loop1(time) - Loop2(time)
//where 
Loop1(time) = Loop2(time) + (Loop2(time)*[0.6,0.7]) // approximately
// So when we substitute this back into the difference equation we end up with 
DeltaTimeDifference approximately = (Loop2(time) + (Loop2(time)*[0.6,0.7])) - Loop2(time)
// And finally we can simplify this to
DeltaTimeDifference approximately = [0.6,0.7]*(Loop2(time)

And this approximation is the average difference between these two loops both algorithmically and machine operations involving software optimizations and machine instructions. So when the data set grows linearly, so does the difference in time between the two. Algorithm 1 has more fetches than algorithm 2 which is evident when the Boss had to travel back and forth the maximum distance between A & C for every iteration after the first iteration while Algorithm 2 the Boss had to travel to A once and then after being done with A he had to travel a maximum distance only one time when going from A to C.

So trying to have the Boss focusing on doing two similar things at once and juggling them back and forth instead of focusing on similar consecutive tasks is going to make him quite angry by the end of the day because he had to travel and work twice as much. Therefor do not lose the scope of the situation by letting your boss getting into an interpolated bottleneck because the boss's spouse and children wouldn't appreciate it.


3