Питання Чому елементарні додатки значно швидше в окремих циклах, ніж у комбінованому циклі?


Припустимо 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-бітної на a 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: Ось повний код. Він використовує ТББ  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.)

enter image description here


1996
2017-12-17 20:40


походження


Можна бути операційною системою, яка сповільнюється під час пошуку в фізичній пам'яті кожного разу, коли ви отримуєте доступ до неї, і має щось подібне до кеш-пам'яті у випадку вторинного доступу до того самого мемблоку. - AlexTheo
Ви компілюєте з оптимізацією? Це виглядає як великий код ASM для O2 ... - Luchian Grigore
Просто бути примхливим, ці два фрагменти коду не є еквівалентними через потенційно дублюючих покажчиків. C99 має restrictключове слово для таких ситуацій. Я не знаю, чи має MSVC щось подібне. Звичайно, якщо це було питання, то код SSE був би невірним. - user510306
Це може мати щось з псевдонімом пам'яті. З одним циклом d1[j] можеш псевдонімом a1[j], тому компілятор може відмовитися від оптимізації пам'яті. Хоча це не відбудеться, якщо ви розділяєте записи на пам'ять у двох циклах. - rturrado
@RocketRoy Перед тим, як обійти людей, що змушують вас робити речі, чому ти насправді не намагаєшся звернути увагу на деякі подробиці? Ви скажете у відповідь, що ви не можете його відтворити. Це питання - 5 років. Ви розглядали можливість того, що процесори з того часу покращилися? Подивіться на мою відповідь, це показує, що він відтворює великий час на Core 2, але менш як на Nehalem і пізніше. - Mysticial


Відповіді:


Після подальшого аналізу цього я вважаю, що це (принаймні частково) викликане вирівнюванням даних чотирьох вказівників. Це призведе до певного рівня конфлікту банківських / шляхових кеш-пам'яті.

Якщо я правильно визначив, як ви виділяєте свої масиви, вони скоріш за все, будуть вирівняні по лінії сторінки.

Це означає, що всі ваші звернення в кожному циклі потраплять на той самий кеш-пам'ять. Тим не менш, процесори 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;
}

Результати тесту:

EDIT: результати на фактичний Основна 2 архітектурна машина:

2 х 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/~amplifierxe/pmw_dp/events/partial_address_alias.html


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

Регіон 1:

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

Регіон 2:

Тут, коли дані збільшуються, кількість відносних витрат знижується, а продуктивність "насичує". Тут два цикли повільніше, тому що він має в два рази більше циклу і розгалуження накладних витрат.

Я не знаю точно, що тут відбувається ... Вирівнювання все-таки може відтворити ефект, згаданий Agner Fog кеш-банк конфліктів. (Ця посилання стосується 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


1546
2017-12-17 21:17



+1: Я думаю, що це відповідь. На відміну від того, що говорять всі інші відповіді, мова йде не про варіант одиночної петлі, яка за своєю суттю має більше прогалин кеша, це стосується конкретного вирівнювання масивів, що спричиняє втрату кеша. - Oliver Charlesworth
Це; a фальшиві псевдоніми стійло - це найбільш ймовірне пояснення. - Stephen Canon
@ VictorT Я використовував код, з яким пов'язано ОП. Він генерує файл .csss, який я можу відкрити в Excel і зробити з нього графік. - Mysticial
@Nawaz Сторінка, як правило, 4 Кб. Якщо ви подивитесь на шістнадцяткові адреси, які я роздруковую, окремо розподілені тести мають однаковий модуль 4096 (тобто 32 бати з початку границі 4KB). Можливо, GCC не має такої поведінки. Це може пояснити, чому ви не бачите відмінностей. - Mysticial
Для всіх бажаючих ось хороше читання на вирівнювання пам'яті і Ось декілька  посилання на дорозі  дані кешуються в пам'яті - New Alexandria


Гаразд, правильна відповідь, безумовно, має щось зробити з кеш-пам'яттю процесора. Але використовувати аргумент кешу може бути досить складним, особливо без даних.

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

@ Відповідь Mysticial переконала багатьох людей (у тому числі і мене), мабуть, тому, що це був єдиний, який, здається, покладався на факти, але це був лише "точка даних" правди.

Ось чому я об'єднав його тест (використовуючи неперервний чи окремий розподіл) та пораду @James 'Answer.

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

Зауважте, що моє перше запитання було в n = 100.000. Цей момент (випадково) виявляє особливу поведінку:

  1. Вона має найбільше розбіжність між однією і двома циклічними версіями (майже в три рази)

  2. Це єдиний момент, коли один цикл (а саме при безперервному розподілі) перевершує двоколінгову версію. (Це дозволило зробити відповідь Містіці взагалі.)

Результат використання ініціалізованих даних:

Enter image description here

Результат, використовуючи неініціалізовані дані (це тестування Mysticial):

Enter image description here

І це складно пояснити: ініціалізовані дані, які виділяються один раз і повторно використовуються для кожного наступного тесту з різним розміром векторів:

Enter image description here

Пропозиція

Кожне запитання про низький рівень продуктивності, пов'язане з перезавантаженням стаканів, повинно бути необхідним для надання інформації MFLOPS для всього діапазону відповідних розмірів даних кешу! Це марнотрат всіх часів, щоб думати про відповіді, і особливо обговорити їх з іншими без цієї інформації.


195
2017-12-18 01:29



+1 Хороший аналіз. Я не мав намір залишити дані, ініціалізовані в першу чергу. Вийшло, що асистент у будь-якому випадку зрівняв їх. Тож ініціалізовані дані мають значення. Я просто редагував мою відповідь з результатами на фактичний Основна 2 архітектурна машина, і вони набагато ближчі до того, що ви спостерігаєте. Інша справа, що я протестував різні розміри n і це показує такий же розрив продуктивності для n = 80000, n = 100000, n = 200000і т. д. - Mysticial
@Mysticial Я думаю, що ОС реалізує обнулення сторінки при кожному додаванні нових сторінок до процесу, щоб уникнути можливих шпигунів між процесами. - v.oddou


Другий цикл вимагає значно меншої активності кеша, тому процесорові простіше виконувати вимоги щодо пам'яті.


63
2017-12-17 20:47



Ви кажете, що другий варіант має меншу кількість помилок в кеші? Чому? - Oliver Charlesworth
@Oli: У першому варіанті процесор повинен мати доступ до чотирьох рядків пам'яті, a[i], b[i], c[i] і d[i] У другому варіанті потрібно всього два. Це робить набагато життєздатнішим доповнення цих ліній під час додавання. - Puppy
Але до тих пір, поки масиви не стикаються в кеш-пам'яті, кожен варіант вимагає точно такого ж числа зчитує і записує з / до основної пам'яті. Отже, висновок (я думаю), що ці два масиви постійно стикаються. - Oliver Charlesworth
Я не слідую. За інструкцію (наприклад, за екземпляр x += y), є два читання і один - написати. Це вірно для будь-якого варіанту. Таким чином, вимога про пропускну здатність кешу <-> CPU однакова. Поки не існує конфліктів, вимога пропускної здатності кеша <-> ОЗ теж однакова .. - Oliver Charlesworth
Як зазначалося в stackoverflow.com/a/1742231/102916, апаратний попередній вибір Pentium M може відслідковувати 12 різних прямих потоків (і я вважаю, що пізніший апаратний пристрій буде принаймні здатним). Лип 2 досі читає лише чотири потоки, тому добре в межах цієї межі. - Brooks Moses


Уявіть, що ви працюєте на машині, де 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

Це класичний кеш-сценарій.


37
2017-12-18 01:36



Це неправильно. Посилання на певний елемент масиву не призводить до вилучення всього масиву з диска (або з не кешованої пам'яті); вказується лише відповідна сторінка або рядок кешу. - Brooks Moses
@ Brooks Мойсей - Якщо ви пройдете весь масив, як це відбувається тут, то це буде. - OldCurmudgeon
Ну, так, але це відбувається протягом всієї операції, а не те, що відбувається щоразу навколо циклу. Ви стверджували, що друга форма "виведе два масиви та дві сторінки в інші два", і це я заперечую. Незалежно від розміру загальних масивів, в середині цього циклу оперативна пам'ять буде мати сторінку з кожного з чотирьох масивів, і нічого не буде вилучено до тих пір, поки цикл не закінчить з ним. - Brooks Moses
У конкретному випадку, де n було лише правильним значенням для того, щоб мати змогу одночасно тримати два масиви в пам'яті потім доступ до всіх елементів чотири масиви в одній петлі обов'язково повинні закінчуватися ударом. - OldCurmudgeon
Чому ви залишаєте цей цикл на 2 сторінках в цілому a1 і b1 для першого призначення, а не просто перша сторінка кожного з них? (Ви берете на себе 5-байтові сторінки, так що сторінка складає половину вашої оперативної пам'яті? Це не просто масштабування, це абсолютно відрізняється від реального процесора). - Brooks Moses


Це відбувається не через інший код, а через кешування: оперативна пам'ять повільніше, ніж регістри процесора, а кеш-пам'ять знаходиться всередині процесора, щоб уникнути записування оперативної пам'яті при кожному зміні змінної. Але кеш-пам'ять не велика, оскільки оперативна пам'ять, отже, відображає лише частину його.

Перший код модифікує адреси віддаленої пам'яті, змінюючи їх на кожному циклі, що вимагає постійного припинення кешування.

Другий код не чергується: він просто надходить на суміжні адреси двічі. Це робить всю роботу, яка буде завершена в кеш-пам'яті, і стане недійсною тільки після початку другої петлі.


27
2017-12-17 20:49



Чому це призводить до постійного припинення кешування? - Oliver Charlesworth
@ OliCharlesworth: Подумайте про кеш як про друковану копію сусіднього діапазону адрес пам'яті. Якщо ви прикидаєте доступу до адреси, яка не є частиною, вам потрібно буде завантажити кеш знову. І якщо щось в кеші було змінено, його потрібно записати в оперативну пам'ять, або вона буде втрачена. У коді зразка, 4 вектора 100'000 цілих чисел (400kBytes), швидше за все, більше, ніж ємність кеша L1 (128 або 256K). - Emilio Garavaglia
Розмір кеша не впливає на цей сценарій. Кожен елемент масиву використовується лише один раз, після чого не має значення, чи його виселять. Розмір кешу має значення лише в тому випадку, якщо у вас є тимчасова локалізація (тобто ви збираєтеся повторно використовувати ті самі елементи в майбутньому). - Oliver Charlesworth
@OliCharlesworth: Якщо мені потрібно завантажити нове значення в кеш-пам'ять, і в ньому вже є значення, яке було змінено, я спочатку повинен записати його, і це змушує мене чекати, поки написане буде. - Emilio Garavaglia
Але в обох варіантах коду OP кожне значення змінюється точно один раз. Ви робите таку ж кількість записів у кожному варіанті. - Oliver Charlesworth


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

Я не знаю, чи звинувачують чи поганий код контрольного коду, чи що, але два способи в межах 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
2017-12-30 01:34



Накладення невідповідності, яке ви згадуєте тут, - це індивідуальне навантаження / магазин, який не пов'язаний з точністю (включаючи незбалансоване завантаження / зберігання SSE). Але справа тут не так, оскільки продуктивність чутлива до відносних розташувань різних масивів. На рівні інструкцій немає розбіжностей. Кожне навантаження / магазин правильно вирівняно. - Mysticial


Це тому, що у процесора не вистачає стільки кеша (де він повинен чекати, поки дані масиву надходять з мікросхем оперативної пам'яті). Вам було б цікаво постійно коригувати розмір масивів, щоб ви перевищували розміри кеш рівня 1 (L1), а потім - кеш рівня 2 (L2) вашого процесора та закріпіть час, потрібний для виконання вашого коду, за розмірами масивів. Графік не повинен бути прямим, як ви очікуєте.


14
2017-12-17 20:52



Я не вірю, що взаємодія між розміром кешу та розміром масиву не існує. Кожен елемент масиву використовується лише один раз, а потім його можна безпечно виселити. Там цілком може бути взаємодія між кешем лінія розмір і розмір масиву, однак, якщо це спричинить конфлікт чотирьох масивів. - Oliver Charlesworth
Ви маєте рацію, це неприкладний приклад продемонструвати цей ефект - James


Перший цикл чергував запис у кожній змінній. Другий і третій лише роблять невеликі стрибки розмірів елементів.

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


12
2017-08-17 15:23





Початкове питання

Чому одна петля набагато повільніше, ніж у два цикли?


Оцінюючи проблему

Код ОП:

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

Розгляд

Беручи до уваги первинне питання ОП щодо двох варіантів для циклів і його зміненого питання щодо поведінки кеш-пам'яті разом з багатьма іншими відмінними відповідями та корисними коментарями; Я хотів би спробувати зробити щось інше, використовуючи інший підхід до цієї ситуації та проблеми.


Підхід

Враховуючи два цикли та всю дискусію щодо кешування та подання сторінок, я хотів би застосувати інший підхід, щоб розглянути це з іншої точки зору. Один з них, який не включає кеш-пам'ять і файли сторінок, ані виконання, щоб розподіляти пам'ять, насправді цей підхід навіть не стосується фактично апаратного забезпечення або програмного забезпечення взагалі.


Перспектива

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


Що ми знаємо

Ми знаємо, що його цикл буде працювати в 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 що робить ітерації як a Boss що наказує двом людям A & B і що їх робота - це м'ясо C & D відповідно, забрати пакет з них і повернути його. Подібна аналогія тут для циклів або підсумкових ітерацій і перевірки стану сама фактично не являє собою Boss. Що насправді являє собою Boss тут не безпосередньо від реальних математичних алгоритмів, а від фактичного поняття Scope і Code Block в рамках рутинної або підпрограми, методу, функції, одиниці перекладу тощо. Перший алгоритм має 1 сферу, де другий алгоритм має 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 це класична проблема інтерполяції, яка, як видається, є неефективною. Я також думаю, що це була одна з провідних причин того, чому багато архітектури та розробники машин закінчували будівництво та проектування багатоядерних систем з можливістю виконання багатопотокових додатків, а також паралельного програмування.

Тому навіть дивлячись на це з цього підходу, навіть не зачіпаючи, як Апаратне забезпечення, ОС і Компілятор працюють разом, щоб виконувати розподіл купу, що включає роботу з RAM, Cache, Page Files і т. Д .; математика за нею вже показує нам, який з цих двох є кращим рішенням з використанням вище аналогії, де Boss або Summations будучи такими For Loops що довелося подорожувати між робітниками A & B. Ми можемо легко це побачити Справа 2 є як мінімум 1/2 швидким, якщо не трохи більше Випадок 1 через різницю в віддаленому пройденому проїзді та часу, що береться. І ця математика майже практично і ідеально збігається як з Bench Mark Times, так і з кількістю різниці в кількості інструкцій з монтажу.



Поправлені питання (ів) ОП

РЕДАГУВАННЯ: питання виявилося нецікавим, оскільки поведінка суворо залежить від розмірів масивів (n) та кеша процесора. Отже, якщо є подальший інтерес, я перефразовую питання:

Не могли б ви навести тверду уявлення про подробиці, що призводять до різної поведінки кешу, як показано п'ятьма регіонами на наступному графіку?

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


Що стосується цих питань

Як я без сумніву продемонстрував, існує основна проблема навіть до того, як обладнання та програмне забезпечення залучаються. Тепер для керування пам'яттю та кешуванням разом з файлами сторінок і т. Д., Які працюють разом у інтегрованому наборі систем між: The Architecture {Апаратні засоби, прошивки, деякі вбудовані драйвери, ядра та набори інструкцій 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 the Boss Довелося їхати до Росії A раз і після того, як це робиться A він повинен був їздити на максимальну відстань лише один раз, коли йдеш з A до C.

Так намагаюся мати Boss зосередивши увагу на тому, як робити дві подібні речі відразу і жонглювати їх назад і вперед, замість того, щоб зосереджуватися на подібних послідовних завданнях, на кінець дня змусить його злитися, тому що він повинен був подорожувати і працювати вдвічі. Тому не втрачайте ситуацію, дозволяючи своєму начальнику потрапити в інтерпольований вузький кут, тому що його дружина та діти боса не оцінять це.


3
2018-01-30 14:00



Через деякий час я опублікував цю відповідь, але я також хотів додати швидкий коментар, який також може допомогти зрозуміти це: у моїй аналогії з Босом як для циклу, підсумовування або ітерацій через цикл, ми також могли б розгляньте цей бос як комбінацію між вказівником Stack Frame і Stack, який керує обсягом та змінами стека та адресацією пам'яті для циклів. - Francis Cugler


Може бути, старий C ++ та оптимізація. У моєму комп'ютері я отримав майже таку ж швидкість:

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

Я запускаю VS2015 на процесорі E5-1620 3,5 ГГц з 16 Гб оперативної пам'яті


0
2017-07-11 07:00