for - intel c++ compiler скачать




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

Предположим, что 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 (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_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 .)


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


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

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


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

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

Это означает, что все ваши обращения в каждом цикле будут попадать в один и тот же кеш. Однако процессоры 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.116 секундами с двумя циклами. Это точно воспроизводит результаты 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:

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

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

Регион 3:

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

Регион 4:

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

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

Регион 5:

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


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

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

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

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

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

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

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

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

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

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

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

Предложение

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


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


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

Почему один цикл настолько медленнее, чем два цикла?

Оценка проблемы

Код OP:

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

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

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

Подход

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

Перспектива

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

Что мы знаем

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

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

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

Исследуем

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

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

  • Мы дадим нашему циклу и его итерациям суммирование, начинающееся с 1 и заканчивающееся на 100000 вместо того, чтобы начинаться с 0, как в цикле, так как нам не нужно беспокоиться о схеме индексирования памяти 0, поскольку нас просто интересует сам алгоритм.
  • В обоих случаях у нас есть 4 функции для работы и 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);  }

Второй случай: - Два сумма, но каждый имеет свой собственный вызов функции.

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там, где содержатся Sum1и Sum2только содержатся F1(). Это также будет очевидно и в дальнейшем, когда мы начнем делать вывод о том, что существует некоторый оптимизм, который происходит из второго алгоритма.

Итерации в первом случае Sumвызовы f(a), которые добавят к себе, f(b)тогда он вызывает f(c)то, что будет делать то же самое, но добавлять f(d)к себе для каждого 100000 iterations. Во втором случае мы имеем 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соответственно , и , чтобы забрать некоторые пакет из них и вернуть его. По аналогии здесь сами итерации цикла или суммирования и проверки условий фактически не представляют 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и Aнаходится в 500 футах от C. Нам не нужно беспокоиться о том, как далеко Bossизначально из- Cза порядка исполнения. В обоих случаях Bossпервоначально происходит от Aпервого до этого B. Эта аналогия не означает, что это расстояние точно; это просто сценарий использования сценария, чтобы показать работу алгоритмов. Во многих случаях при распределении кучи и работе с кешем и файлами страниц эти расстояния между адресами могут не сильно различаться в отличиях или они могут значительно отличаться в зависимости от характера типов данных и размеров массива.

Испытательные случаи:

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

Второй случай: The 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% медленнее, чем Алгоритм Два; Однако, это только The 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пока рабочий не вернется. Таким образом, даже это влияет на алгоритм.

Заключение:

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

Поэтому даже глядя на это с помощью этого подхода, даже не связавшись с тем, как Hardware, OS и Compiler работают вместе, чтобы распределять кучи, которые связаны с работой с RAM, кэшем, файлами страниц и т. Д .; математика позади него уже показывает нам , какой из этих двух является лучшим решением , с использованием указанной выше аналогии , где Bossили Summationsбыть тех , кого For Loopsчто приходилось ездить между рабочими Aи B. Легко видеть, что случай 2 не менее чем на 1/2, если не немного больше, чем случай 1 из-за разницы в пройденном расстоянии и времени. И эта математика выстраивается практически практически и идеально с обоими метками скамьи, а также величиной разницы в размере инструкций по сборке.

Измененный (ые) вопрос (ы)

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

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

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

В отношении этих вопросов

Как я продемонстрировал, без сомнения, есть основная проблема еще до того, как аппаратное и программное обеспечение будет задействовано. Теперь, что касается управления памятью и кэшированием вместе с файлами страниц и т. Д., Которые все работают вместе в интегрированном наборе систем: The Architecture{Hardware, Firmware, некоторые встроенные драйверы, ядра и наборы инструкций ASM}, The OS{Системы управления файлами и памятью , Драйверы и реестр}, The Compiler{Единицы перевода и оптимизация исходного кода}, и даже Source Codeсам с его набором (ами) отличительных алгоритмов; мы уже можем видеть , что есть узкое место, что происходит в первом алгоритме , прежде чем мы даже применить его к любой машине с любым произвольным Architecture, OSиProgrammable Languageпо сравнению со вторым алгоритмом. Таким образом, уже возникла проблема, прежде чем вовлекать внутреннюю среду современного компьютера.

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

Тем не мение; это не означает, что эти новые вопросы не важны, потому что они сами, и они действительно играют роль в конце концов. Они влияют на процедуры и общую производительность, и это видно на разных графиках и оценках у многих, кто дал свои ответы и комментарии (комментарии). Если обратить внимание на аналогию Bossи двое рабочих Aи Bкоторые должны были идти и получать пакеты Cи , Dсоответственно , и принимая во внимание математические обозначения двух алгоритмов в вопросе вы можете видеть , что даже без участия компьютера Case 2составляет около 60% быстрее, чемCase 1 и когда вы смотрите на графики и диаграммы после того, как эти алгоритмы были применены к исходному коду, скомпилированы и оптимизированы и выполнены через ОС для выполнения операций с данным оборудованием, вы даже видите немного более ухудшение различий в этих алгоритмах.

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


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

один цикл: 1.577мс две петли: 1.507ms

Я запускаю VS2015 на процессоре E5-1620 3.5Ghz с 16 ГБ оперативной памяти





vectorization