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

const int n = 100000;

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

Этот цикл выполняется 10000 раз через другой внешний 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) и кэша ЦП. Так что, если есть дальнейший интерес, я перефразирую вопрос:

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

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

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

#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.)

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

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

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

РЕДАКТИРОВАТЬ: На самом деле это выглядит так, как будто вы распределяете все массивы отдельно. Обычно, когда запрашиваются такие большие выделения, распределитель запрашивает свежие страницы из ОС. Следовательно, существует высокая вероятность того, что большие выделения появятся при том же смещении от границы страницы.

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

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;
}

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

РЕДАКТИРОВАТЬ: результаты на фактическом 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,116 секунды с двумя петлями. Это точно воспроизводит результаты ОП.

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

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

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

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

5 регионов - объяснения

Регион 1:

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

Регион 2:

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

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

Регион 3:

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

Регион 4:

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

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

Регион 5:

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

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

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

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

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

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

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

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

2. Это единственная точка, где однопетлевая (а именно с непрерывным распределением) превосходит двухконтурную версию. (Это сделало возможным ответ Mysticial.)

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

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

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

Предложение

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

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

Представьте, что вы работаете на машине, где 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

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

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

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

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

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

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

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

Я играл с различными схемами, такими как сдача задания 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 секунда.

Это связано с тем, что в процессоре не так много промахов кэша (когда ему приходится ждать получения данных массива из микросхем ОЗУ). Было бы интересно непрерывно корректировать размер массивов так, чтобы вы превышали размеры кэша 1-го уровня (L1), а затем кэша 2-го уровня (L2) вашего ЦП и отображали время, необходимое для вашего кода. выполнить по размерам массивов. График не должен быть прямой линией, как вы ожидаете.

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

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

Оригинальный вопрос

Почему один цикл намного медленнее двух?

Вывод:

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

Рассматривая его с точки зрения такого подхода, без учета того, как аппаратное обеспечение, ОС и компилятор (-ы) работают вместе для распределения кучи, включающей работу с ОЗУ, кэш-памятью, файлами подкачки и т. Д .; математика, лежащая в основе этих алгоритмов, показывает нам, какой из этих двух вариантов является лучшим решением.

Мы можем использовать аналогию Bossсущества, Summationкоторое будет представлять собой For Loopпутешествующее между работниками A& B.

Мы легко видим, что Случай 2 по меньшей мере вдвое быстрее, если не чуть больше, чем Случай 1, из-за разницы в расстоянии, необходимом для перемещения, и времени, которое требуется рабочим. Эта математика почти виртуально соответствует идеям BenchMark Times, а также количеству различий в инструкциях по сборке.

Теперь я начну объяснять, как все это работает ниже.

Оценивая проблему

Код ОП:

const int n=100000;

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

А также

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

Рассмотрение

Рассматривая оригинальный вопрос ОП о двух вариантах циклов for и его исправленный вопрос о поведении кэшей, а также множество других превосходных ответов и полезных комментариев; Я хотел бы попытаться сделать что-то другое здесь, используя другой подход к этой ситуации и проблеме.

Подход

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

Перспектива

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

Что мы знаем

Мы знаем, что этот цикл будет выполняться 100 000 раз. Мы также знаем , что a1, b1, c1иd1 являются указателями на 64-битной архитектуре. В C ++ на 32-разрядной машине все указатели имеют размер 4 байта, а на 64-разрядной машине они имеют размер 8 байтов, поскольку указатели имеют фиксированную длину.

Мы знаем, что у нас есть 32 байта для выделения в обоих случаях. Единственное отличие состоит в том, что мы выделяем 32 байта или 2 набора по 2-8 байт на каждую итерацию, тогда как во втором случае мы выделяем 16 байтов для каждой итерации для обоих независимых циклов.

Оба цикла по-прежнему равны 32 байта в общем распределении. С этой информацией давайте теперь продолжим и покажем общую математику, алгоритмы и аналогию этих понятий.

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

Что мы не знаем

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

Давайте расследовать

Уже очевидно, что многие уже сделали это, взглянув на распределение кучи, тесты производительности, на RAM, Cache и Page Files. Рассмотрение конкретных точек данных и конкретных итерационных индексов также было включено, и различные разговоры об этой конкретной проблеме заставили многих людей начать сомневаться в других связанных с этим вещах. Как мы начинаем смотреть на эту проблему, используя математические алгоритмы и применяя к ней аналогию? Начнем с того, что сделаем пару утверждений! Затем мы строим наш алгоритм оттуда.

Наши утверждения:

• Мы позволим нашему циклу и его итерациям быть суммированием, которое начинается с 1 и заканчивается на 100000 вместо того, чтобы начинаться с 0, как в циклах, поскольку нам не нужно беспокоиться о схеме индексации адресации памяти 0, поскольку нас просто интересует сам алгоритм.
• В обоих случаях у нас есть 4 функции для работы и 2 вызова функций с 2 ​​операциями, выполняемыми для каждого вызова функции. Мы установим эти меры , как функции и вызовы функций , как: F1(), F2(), f(a), f(b), f(c)и f(d).

Алгоритмы:

1-й случай: - только одно суммирование, но два независимых вызова функций.

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

2-й случай: - Два суммирования, но у каждого свой вызов функции.

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); }

Если вы заметили , F2()существует только в Sumот Case1где F1()содержится в Sumиз Case1и в обоих Sum1и Sum2от Case2. Это станет очевидным позже, когда мы начнем делать вывод, что во втором алгоритме происходит оптимизация.

Итерации по первым Sumвызовам case f(a), которые добавят к себе, f(b)затем вызовы f(c), которые сделают то же самое, но добавят f(d)к себе для каждого100000 итерации. Во втором случае мы имеем Sum1и Sum2то, и другое действует одинаково, как если бы они были одной и той же функцией, вызываемой дважды подряд.

В этом случае мы можем рассматривать Sum1и Sum2просто как старый, Sumгде Sumв этом случае выглядит так: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }и теперь это выглядит как оптимизация, где мы можем просто считать, что это та же самая функция.

Резюме с аналогией

С тем, что мы видели во втором случае, это выглядит почти так, как будто есть оптимизация, так как оба цикла имеют одинаковую точную сигнатуру, но это не является реальной проблемой. Проблема не в работе, которая выполняется f(a),f(b) , f(c)и f(d). В обоих случаях и при сравнении между ними разница в расстоянии, которое должно пройти суммирование в каждом случае, дает вам разницу во времени выполнения.

Подумайте о For Loopsкак являющийся , Summationsчто делает итерации , как быть , Bossчто дает приказ двум людям Aи , Bи что их рабочие места для мяса Cи , Dсоответственно , и , чтобы забрать некоторые пакет из них и вернуть его. В этой аналогии сами циклы for или итерации суммирования и проверки условий фактически не представляют Boss. То, что на самом деле представляет, Bossне непосредственно из фактических математических алгоритмов, а из фактической концепции Scopeи Code Blockвнутри подпрограммы или подпрограммы, метода, функции, единицы перевода и т. Д. Первый алгоритм имеет 1 область действия, где 2-й алгоритм имеет 2 последовательных области действия.

В первом случае в каждом вызове квитанция Bossотправляется Aи дает заказ и Aуходит, чтобы получить B'sпакет, а затем Bossотправляется вC и дает приказы сделать то же самое и получить пакет Dна каждой итерации.

Во втором случае Bossработает непосредственно, Aчтобы пойти и получить B'sпакет, пока все пакеты не будут получены. Затем Bossработает, Cчтобы сделать то же самое для получения всехD's пакетов.

Поскольку мы работаем с 8-байтовым указателем и имеем дело с распределением кучи, давайте рассмотрим следующую проблему. Скажем, Bossэто 100 футов от Aи это A500 футов от C. Нам не нужно беспокоиться о том, как далеко они Bossизначально находятся из- Cза порядка выполнения. В обоих случаях Bossизначально путешествует изA затем к B. Эта аналогия не говорит о том, что это расстояние является точным; это просто полезный сценарий тестового примера, демонстрирующий работу алгоритмов.

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

Тестовые случаи:

Первый случай: на первой итерацииBossон должен сначала пройти 100 футов, чтобы сдать ордер,AиAуйти ивыполнитьсвое дело, но затемBossон должен пройти 500 футов,Cчтобы дать ему промах. Затем на следующей итерации и на каждой другой итерации послеBoss нее нужно идти вперед и назад на 500 футов между ними.

Второй случай:Boss должен проехать 100 футов на первой итерации кA, но после этого, он уже тами только ждетAчтобы вернутьсяпока все промахи не будут заполнены. ЗатемBossон должен пройти 500 футов на первой итерации,Cпотому чтоCэто 500 футов отA. Так как этоBoss( Summation, For Loop )вызывается сразу после работы с ним,Aон просто ждет там, как он делал,Aпока всеC'sордера не будут выполнены.

Разница в пройденных расстояниях

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;    

Сравнение произвольных значений

Мы легко видим, что 600 - это гораздо меньше, чем 10 миллионов. Теперь, это не точно, потому что мы не знаем фактической разницы в расстоянии между тем, какой адрес ОЗУ или какой файл кэша или файла подкачки будет вызывать каждый вызов на каждой итерации из-за многих других невидимых переменных. Это просто оценка ситуации, которую нужно знать, и смотреть на нее с наихудшего сценария.

Из этих чисел это будет выглядеть так, как будто Алгоритм Один должен быть 99%медленнее, чем Алгоритм Два; Однако, это только Boss'sчасть или ответственность алгоритмов и не учитывает реальных рабочих A, B, C, и Dи что они должны делать на каждом и каждой итерации цикла. Таким образом, работа босса составляет только около 15-40% всей выполняемой работы. Большая часть работы, выполняемой рабочими, оказывает несколько большее влияние на сохранение отношения разницы скоростей примерно до 50-70%.

Наблюдение: - Различия между двумя алгоритмами

В этой ситуации это структура процесса выполняемой работы. Это показывает, что Случай 2 более эффективен как при частичной оптимизации, так и при наличии аналогичного объявления и определения функции, где только переменные отличаются по имени и пройденному расстоянию.

Мы также видим, что общее расстояние, пройденное в случае 1 , намного больше, чем в случае 2, и мы можем считать это расстояние пройденным нашим Фактором времени между двумя алгоритмами. Дело 1 требует гораздо больше работы, чем дело 2 .

Это ASMвидно из свидетельств инструкций, которые были показаны в обоих случаях. Наряду с тем, что уже было сказано об этих случаях, это не учитывает тот факт, что в случае 1 боссу придется ждать обоих Aи Cвернуться, прежде чем он сможет вернуться к Aкаждой следующей итерации. Это также не учитывает тот факт, что если Aили Bзанимает очень много времени, то оба Bossи другие работники бездействуют в ожидании выполнения.

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

Измененные вопросы ОП

РЕДАКТИРОВАТЬ: Вопрос оказался неактуальным, так как поведение сильно зависит от размеров массивов (n) и кэш-памяти ЦП. Так что, если есть дальнейший интерес, я перефразирую вопрос:

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

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

Относительно этих вопросов

Без сомнения, я продемонстрировал, что существует основная проблема еще до того, как в нее вступят аппаратное и программное обеспечение.

Теперь что касается управления памятью и кэшированием вместе с файлами подкачки и т. Д., Которые все работают вместе в интегрированном наборе систем между следующими:

• The Architecture {Аппаратное обеспечение, прошивка, некоторые встроенные драйверы, ядра и наборы инструкций ASM}.
• The OS{Системы управления файлами и памятью, драйверы и реестр}.
• The Compiler {Единицы перевода и оптимизация исходного кода}.
• И даже Source Codeсам с его набором (-ами) отличительных алгоритмов.

Мы уже видим , что есть узкое место, что происходит в первом алгоритме , прежде чем мы даже применить его к любой машине с любым произвольным Architecture, OSи по Programmable Languageсравнению со вторым алгоритмом. Там уже существовала проблема, прежде чем задействовать внутренности современного компьютера.

Конечные результаты

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

Если вы обратили внимание на аналогию Bossи двое рабочих Aи Bкоторые должны были идти и получать пакеты Cи , Dсоответственно , и с учетом математических обозначений двух алгоритмов в вопросе; Вы можете увидеть без участия компьютерного оборудования и программного обеспечения Case 2примерно 60%быстрее, чем Case 1.

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

Если Dataнабор довольно мал, на первый взгляд может показаться, что разница не так уж и плоха. Тем не менее, поскольку Case 1это примерно 60 - 70%медленнее, чем Case 2мы можем посмотреть на рост этой функции с точки зрения различий во времени выполнения:

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)

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

Когда набор данных растет линейно, увеличивается и разница во времени между ними. Алгоритм 1 имеет больше выборок, чем алгоритм 2, что очевидно, когда Bossон должен перемещаться назад и вперед по максимальному расстоянию между A& Cдля каждой итерации после первой итерации, в то время как алгоритм 2 Bossдолжен проходить Aодин раз, а затем, после того как он закончил, Aон должен путешествовать максимальное расстояние только один раз при переходе от Aк C.

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

Поправка: Принципы разработки программного обеспечения

- Разница между Local Stackи Heap Allocatedвычисления в итерационных для петель и разница между их использований, их эффективность и эффективность -

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

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

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

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

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

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

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

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

Вот псевдо-пример: две простые структуры, один алгоритм.

struct A {
    int data;
    A() : data{0}{}
    A(int a) : data{a}{} 
};
struct B {
    int data;
    B() : data{0}{}
    A(int b) : data{b}{}
}                

template<typename T>
void Foo( T& t ) {
    // do something with t
}

// some looping operation: first stack then heap.

// stack data:
A dataSetA[10] = {};
B dataSetB[10] = {};

// For stack operations this is okay and efficient
for (int i = 0; i < 10; i++ ) {
   Foo(dataSetA[i]);
   Foo(dataSetB[i]);
}

// If the above two were on the heap then performing
// the same algorithm to both within the same loop
// will create that bottleneck
A* dataSetA = new [] A();
B* dataSetB = new [] B();
for ( int i = 0; i < 10; i++ ) {
    Foo(dataSetA[i]); // dataSetA is on the heap here
    Foo(dataSetB[i]); // dataSetB is on the heap here
} // this will be inefficient.

// To improve the efficiency above, put them into separate loops... 

for (int i = 0; i < 10; i++ ) {
    Foo(dataSetA[i]);
}
for (int i = 0; i < 10; i++ ) {
    Foo(dataSetB[i]);
}
// This will be much more efficient than above.
// The code isn't perfect syntax, it's only psuedo code
// to illustrate a point.

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

Это может быть старый C ++ и оптимизации. На моем компьютере я получил почти такую ​​же скорость:

Один цикл: 1,577 мс

Два цикла: 1,507 мс

Я использую Visual Studio 2015 на процессоре E5-1620 с частотой 3,5 ГГц и 16 ГБ ОЗУ.