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

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

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

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

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

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 в комментариях, весьма вероятно, что это выравнивание вызовет ложное сглаживание в модулях загрузки / сохранения или в кеше. Я поискал это в Google и обнаружил, что у Intel на самом деле есть аппаратный счетчик для частичного псевдонима адреса:

http://software.intel.com/sites/products/documentation/doclib/stdxe/2013/%7Eamplifierxe/pmw_dp/events/partial_address_alias.html

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

Регион 1:

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

Регион 2:

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

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

Регион 3:

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

Регион 4:

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

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

Регион 5:

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

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

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

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

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

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

Обратите внимание, что мой первоначальный вопрос был 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 затем загружаются с диска в RAM и обрабатываются.

другая петля

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

• cache 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];
  }
  

• cache 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 на добавить мусор памяти, интерпретируемый как двойной.

Я поиграл с различными схемами, например, поместив назначение 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 см. Попробуйте один раз закончить одну, а затем вторую строчку и попробуйте еще раз, поочередно ставя крестик в каждой строчке.

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

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

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

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