Эффективность цикла: объединение циклов

Question

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

Я создал следующую программу на C ++, которая измеряет время двух разных функций:

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

Полный код теста:

    #include <iostream>
    #include <chrono>

    using namespace std;

    int* list1; int* list2;
    int* list3; int* list4;
    int* list5; int* list6;
    int* list7; int* list8;
    int* list9; int* list10;

    const int n = 1e7;

    // **************************************
    void myFunc1()
    {
        for (int i = 0; i < n; i++)
        {
            list1[i] = 2;
            list2[i] = 4;
            list3[i] = 8;
            list4[i] = 16;
            list5[i] = 32;
            list6[i] = 64;
            list7[i] = 128;
            list8[i] = 256;
            list9[i] = 512;
            list10[i] = 1024;
        }

        return;
    }

    // **************************************
    void myFunc2()
    {

        for (int i = 0; i < n; i++)
        {
            list1[i] = 2;
        }
        for (int i = 0; i < n; i++)
        {
            list2[i] = 4;
        }
        for (int i = 0; i < n; i++)
        {
            list3[i] = 8;
        }
        for (int i = 0; i < n; i++)
        {
            list4[i] = 16;
        }
        for (int i = 0; i < n; i++)
        {
            list5[i] = 32;
        }
        for (int i = 0; i < n; i++)
        {
            list6[i] = 64;
        }
        for (int i = 0; i < n; i++)
        {
            list7[i] = 128;
        }
        for (int i = 0; i < n; i++)
        {
            list8[i] = 256;
        }

        for (int i = 0; i < n; i++)
        {
            list9[i] = 512;
        }
        for (int i = 0; i < n; i++)
        {
            list10[i] = 1024;
        }

        return;
    }


    // **************************************
    int main()
    {
        list1 = new int[n]; list2 = new int[n];
        list3 = new int[n]; list4 = new int[n];
        list5 = new int[n]; list6 = new int[n];
        list7 = new int[n]; list8 = new int[n];
        list9 = new int[n]; list10 = new int[n];

        auto start = chrono::high_resolution_clock::now();

        myFunc1();

        auto elapsed = chrono::high_resolution_clock::now() - start;

        long long microseconds = chrono::duration_cast<chrono::microseconds>(elapsed).count();

        cout << "Time taken by func1 (micro s):" << microseconds << endl << endl;

        //

        start = chrono::high_resolution_clock::now();

        myFunc2();

        elapsed = chrono::high_resolution_clock::now() - start;

        microseconds = chrono::duration_cast<chrono::microseconds>(elapsed).count();

        cout << "Time taken by func2 (micro s):" << microseconds << endl << endl;

        delete[] list1; delete[] list2; delete[] list3; delete[] list4;
        delete[] list5; delete[] list6; delete[] list7; delete[] list8;
        delete[] list9; delete[] list10;

        return 0;
    }

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

Результат был удивительным.На моем ПК func1() занимает около 280 миллисекунд, а func2() - около 180 миллисекунд, первая функция на самом деле медленнее, а не быстрее.

Теперь вопрос : мой тестправильный?Полезно ли объединять циклы for для минимизации общего числа итераций?У людей разный опыт?

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

РЕДАКТИРОВАТЬ: я попытался все это снова с оптимизацией -O3.Хотя точные измерения были, конечно, разными, результат остался прежним.

Answer 1

Ваши предположения в основном ошибочны:

1. Итерация цикла не требует значительных затрат.

   Это то, для чего оптимизированы ЦП: узкие циклы.Оптимизация ЦП может пойти настолько далеко, чтобы использовать выделенную схему для счетчика цикла (например, инструкцию PPCs bdnz), так что накладные расходы счетчика цикла будут точно равны нулю.X86 действительно нужен цикл процессора или два afaik, но это все.

2. Как правило, ваша производительность убивает доступ к памяти .

   Получение значенияиз L1 кеша уже занимает от трех до четырех циклов ЦП.Одна загрузка из кэша L1 имеет большую задержку, чем ваш цикл управления!Больше для кэшей более высокого уровня.Доступ к ОЗУ занимает вечность.

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

• Предотвращение доступа к памяти.

  Наиболее эффективная и наиболее легко забываемая оптимизация.Вы не платите за то, что не делаете.

• Распараллеливание доступа к памяти.

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

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

  Кроме того, как справедливо указывает MSalters в комментариях: ЦП имеет ограниченное количество регистров.Сколько зависит от архитектуры, 32-битный процессор X86 имеет только восемь, например.Таким образом, он просто не может обрабатывать десять разных указателей одновременно.Для этого потребуется хранить некоторые указатели в стеке, что обеспечивает еще больший доступ к памяти.Что, очевидно, является нарушением вышеприведенного пункта о избегании обращений к памяти.

• Секвенизация обращений к памяти.

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

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

Answer 2

Здесь есть три важные вещи:

1) Бенчмаркинг без оптимизации не имеет смысла .Оказывается, в этом есть реальный эффект, который не уходит с оптимизацией.Фактически, антиоптимизированная отладочная сборка скрывала большую разницу при дополнительной стоимости хранения счетчиков циклов в памяти (ограничение циклов до 1 на 6 тактов против 1 за такт), плюс не автоматическое-векторизация циклов хранилища.

Если вы еще не знали микроархитектурные детали asm + CPU о причинах разницы в скорости, было бы небезопасно или бесполезно измерять ее с отключенной оптимизацией.

---

2) Отсутствует конфликт кеша (если все массивы выровнены одинаково относительно границы страницы). Наклонение массивов относительно друг друга может сильно помочь.Это может происходить естественным образом в зависимости от того, как они распределены, даже если их размеры не имеют больших степеней 2.

Все массивы большие и были выделены отдельно с помощью new, поэтому они, вероятно, всевыравнивание по странице (или смещение на 16В от границы страницы в реализациях, которые помещают некоторую информацию (например, размер) перед объектом).В Linux glibc malloc / new обычно обрабатывает большие выделения, выделяя свежие страницы из ОС с помощью mmap() (и используя первые 16 байтов для учета этого блока), вместо перемещения brk().

Псевдонимы 4k означают, что все они идут к одному и тому же набору в типичном L1d-кэше, который является 8-сторонним ассоциативным на типичных процессорах x86. Почему размер кэша L1 меньше размера кэша L2 в большинстве процессоров? объясняет, почему не случайно 64 устанавливает * 64B / line = 4096B size page (size 8-way =32kiB), потому что это делает кэш VIPT L1d работать как PIPT без проблем с омонимами и синонимами.См. Также Какой метод отображения кэша используется в процессоре Intel Core i7?

В 9-м хранилище будет удалена строка кэша из 1-го хранилища , поэтому строки будут удаленыодин раз в каждом магазине, не полностью написано, как в смежном случае.(Если компилятор не выполняет автоматическую векторизацию и не выполняет всю строку кэша, заполненную хранилищами, до одного массива, прежде чем двигаться дальше.) Модель строго упорядоченной памяти x86 требует фиксации хранилищ из буфера хранилищ в L1d в программном порядке, поэтому она не может объединятьсянесмежные хранилища к одной и той же строке в одну запись перед фиксацией или фиксацию нескольких ожидающих хранилищ, если строка поступает, если они не последовательные.

(Политика замены - псевдо-LRU, а не истинное LRU, так что иногда вы можете обнаружить, что линия остается горячей после 8 или 9 выселений в одном и том же наборе.)

Напоминание: вышеприведенное применимо, только если все массивы имеют одинаковое выравнивание относительно страницы.Чрезмерное распределение и выполнение ptr = 128 + malloc(128 + size) для одного из указателей может исказить его относительно других, и иногда это стоит делать.

Вы говорите, что у вас есть компьютер, поэтому я предполагаю процессор Intel.(У Райзена L1d та же геометрия, но у семейства Бульдозеров нет.)

---

( Руководство по оптимизации Intel раздел 3.6.10 Комбинирование записи рекомендует деление цикла для циклов, которые записывают более 4 выходных потоков Этот совет содержится в разделе о хранилищах NT и памяти WC; его можно использовать только в этом случае. В любом случае 4 не являетсяПравильное число для современного Intel, если вы не проявляете осторожность в учете другой гиперпотоки.

(Intel) Правило кодировки сборки / компиляции 58. (H-влияние, L-общность) Есливнутренний цикл записывает данные более чем в четыре массива (четыре отдельные строки кэша), применяет деление цикла, чтобы разбить тело цикла так, чтобы в каждую итерацию каждого из результирующих циклов записывалось только четыре массива.

TL: DR: для хранилищ NT (обход кеша) до 12 выходных потоков нормально работает на Skylake и новее или 10 на Broadwell / Haswell и старше.(Или меньше, если вы читаете какую-либо память одновременно).Это количество LFB (Line Fill Buffers) на этих процессорах.Более ранние процессоры (до Nehalem) имели менее 10, и, возможно, не могли использовать их все для магазинов NT.( Где находится буфер объединения записи? X86 ) LFB используются для всех передач линий в / из L1d, поэтому, например, для ожидающего пропуска нагрузки требуется LFB, выделенный для ожидания этой линии из L2.

(С гиперпоточностью имейте в виду, что другая гиперпотока конкурирует за LFB на том же физическом ядре, поэтому не полагайтесь на использование всех 12 LFB, если вы не можете отключить HT.)

Но вы не работаете с магазинами NT.

Обычное мнение было , что этот предел эффективности с 4 выходами применялся к обычному(не NT) также сохраняет в памяти WB, но это , а не в случае с современным Intel .Это было совпадением, что производительность для обычных (WB = с обратной записью) хранилищ упала примерно на том же количестве выходных потоков, что и для хранилищ NT.В этой статье о механической симпатии приводятся некоторые предположения о причине, но мы уверены, что они звучат неправильно.

См. https://github.com/Kobzol/hardware-effects/issues/1, чтобы узнать о некоторых микробенчмарках.(И посмотрите обсуждение между мной, BeeOnRope и Хади Брейсом о LFB, где вышло это руководство с 4 выходами: https://chat.stackoverflow.com/transcript/message/45474939#45474939, которое ранее было в комментариях под Размер буферов хранилища на оборудовании Intel?буфер хранилища?

@ BeeOnRope также опубликовал гистограмму для обычных (не NT) хранилищ, чередующихся с 1 до 15 выходными потоками на Skylake. Производительность несколько постояннадля любого количества потоков вплоть до 6 на Skylake , затем оно начинает ухудшаться в 7 и 8 (возможно, из-за пропадания L1d, если все массивы были выровнены одинаково), и, что более важно, от 9 и доприближается к плато с 13 до 15. (Примерно в 1/3 производительности хорошего потока в 1-6).

Опять же, с Hyperthreading, другое логическое ядро ​​почти наверняка будетгенерировать некоторый трафик памяти, если он вообще работает, поэтому консервативный предел, такой как 4 потока вывода, не плохой план. Но производительность не падаетскала на 7 или 8, поэтому не обязательно делить ваши циклы, если это стоит больше общей работы.

---

См. также Расширенный REP MOVSB ​​для memcpy для получения дополнительной информации о обычных магазинах RFOпо сравнению с хранилищами без RFO NT и множеством проблем с пропускной способностью памяти x86.(Особенно из-за того, что задержка памяти / кэш-памяти третьего уровня ограничивает пропускную способность одноядерных процессоров на большинстве процессоров, но она хуже на многоядерных Xeons: они удивительно имеют более низкую одноядерную пропускную способность памяти, чем четырехъядерные десктопы. При достаточном количестве занятых ядер вы можете насыщать их высокую совокупную полосу пропускания с помощью четырех- или 6-канальных контроллеров памяти; это ситуация, для которой они оптимизированы.)

2.5) Локализация страниц DRAM : обратная запись в память происходит, когда данные в конечном итоге извлекаются из L3 (кэш последнего уровня).Грязные строки кэша отправляются контроллеру памяти, который может буферизовать и группировать их по группам, но все равно будет сохранено множество хранилищ (и загрузок RFO) для всех 10 массивов.Двухканальный контроллер памяти не может одновременно открывать 10 страниц DRAM.(Я думаю, что только 1 на канал, но я не эксперт по таймингу DRAM. См. Ульриха Дреппера, что каждый программист должен знать о памяти , в котором есть некоторые детали.) https://pubweb.eng.utah.edu/~cs6810/pres/12-6810-15c.pdf упоминает DRAMполитики открытых / закрытых страниц для потоковой передачи по сравнению с разрозненными хранилищами.

Суть в том, что даже если кэш может обрабатывать много выходных потоков, DRAM, вероятно, будет счастливее с меньшим количеством.Обратите внимание, что размер «страницы» DRAM не совпадает с размером страницы виртуальной памяти (4 КБ) или огромной страницы (2 МБ).

Говоря о виртуальной памяти, TLB должен работать с 10 выходными потоками: современные процессоры x86 имеют намного больше 10 записей L1dTLB.Надеюсь, они достаточно ассоциативны, или записи не все псевдонимы, поэтому мы не получаем TLB-пропустить в каждом магазине!

---

3) Анализ псевдонимов во время компиляции

@ RichardHodges заметил это)

Ваш большой комбинированный цикл не автоматически векторизуется с помощью gcc или clang .Они не могут доказать, что list1[10] также не list4[9] или что-то еще, поэтому они не могут хранить list1[8..11] в одном 16-байтовом хранилище.

Но циклы с одним массивом могут легкоавтоматическая векторизация с SSE или AVX.(Удивительно, но не для вызова wmemset или чего-то другого, просто с обычным автоматическим векторизатором только на gcc -O3 или clang -O2. Это может переключиться на хранилища NT для больших размеров, что поможет большинству, если несколько ядер конкурируют заПропускная способность памяти. Распознавание образов memset полезно / полезно даже без автоматической векторизации.)

Единственный анализ псевдонимов, который требуется здесь, это доказать, что list1[i] = 2 не изменяет само значение указателя list1 (потому что функция читает глобальное внутри цикла, а не копирует значение в локальное).Анализ псевдонимов на основе типов (-fstrict-aliasing включен по умолчанию) позволяет компилятору доказать это и / или тот факт, что если бы list1 указывал на себя, было бы неопределенное поведение при доступе вне объекта в последующих итерациях цикла.

Интеллектуальные компиляторы могут и действительно проверяют перекрытие перед автоматической векторизацией в некоторых случаях (например, выходные массивы против входных массивов), когда вы не можете использовать ключевое слово __restrict (заимствованное несколькими компиляторами из ограничения C),Если есть перекрытие, они возвращаются к безопасному скалярному циклу.

Но в этом случае этого не происходит: gcc и clang вообще не генерируют векторизованный цикл, они просто делают скаляр в myFunc1.Если каждое хранилище вызывает пропадание конфликта в L1d, это делает это в 4 раза хуже, чем если бы вы предоставили компилятору достаточно информации, чтобы выполнить свою работу.(Или 8x с AVX для 32-байтовых хранилищ).Обычно разница между 16B и 32B хранилищами незначительна, когда пропускная способность основной памяти является узким местом (не кеш L1d), но здесь это может иметь большое значение, потому что 10 выходных потоков нарушают эффект объединения L1d, если все они являются псевдонимами.

Кстати, глобальные переменные static int *__restrict line1 и т. Д. Позволяют gcc автоматически векторизовать хранилища в myFunc1.Это не делит петлю, хотя.(Это было бы разрешено, но я думаю, что эта оптимизация не нужна. Это зависит от программиста.)

// global modifier allows auto-vec of myFunc1
#define GLOBAL_MODIFIER  __restrict
#define LOCAL_MODIFIER  __restrict  // inside myFunc1

static int *GLOBAL_MODIFIER list1, *GLOBAL_MODIFIER list2,
       *GLOBAL_MODIFIER list3, *GLOBAL_MODIFIER list4,
       *GLOBAL_MODIFIER list5, *GLOBAL_MODIFIER list6,
       *GLOBAL_MODIFIER list7, *GLOBAL_MODIFIER list8,
       *GLOBAL_MODIFIER list9, *GLOBAL_MODIFIER list10;

Я поместил ваш код в проводник компилятора Godbolt с помощью gcc8.1 и clang6.0 , с этим изменением + функция, которая читает из одного из массивов, чтобы остановить их от полной оптимизации (что они и сделали бы, потому что я сделал их static.)

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

.L12:    # myFunc1 inner loop from gcc8.1 -O3  with __restrict pointers
    movups  XMMWORD PTR [rbp+0+rax], xmm9       # MEM[base: l1_16, index: ivtmp.87_52, offset: 0B], tmp108
    movups  XMMWORD PTR [rbx+rax], xmm8 # MEM[base: l2_17, index: ivtmp.87_52, offset: 0B], tmp109
    movups  XMMWORD PTR [r11+rax], xmm7 # MEM[base: l3_18, index: ivtmp.87_52, offset: 0B], tmp110
    movups  XMMWORD PTR [r10+rax], xmm6 # MEM[base: l4_19, index: ivtmp.87_52, offset: 0B], tmp111
    movups  XMMWORD PTR [r9+rax], xmm5  # MEM[base: l5_20, index: ivtmp.87_52, offset: 0B], tmp112
    movups  XMMWORD PTR [r8+rax], xmm4  # MEM[base: l6_21, index: ivtmp.87_52, offset: 0B], tmp113
    movups  XMMWORD PTR [rdi+rax], xmm3 # MEM[base: l7_22, index: ivtmp.87_52, offset: 0B], tmp114
    movups  XMMWORD PTR [rsi+rax], xmm2 # MEM[base: l8_23, index: ivtmp.87_52, offset: 0B], tmp115
    movups  XMMWORD PTR [rcx+rax], xmm1 # MEM[base: l9_24, index: ivtmp.87_52, offset: 0B], tmp116
    movups  XMMWORD PTR [rdx+rax], xmm0 # MEM[base: l10_25, index: ivtmp.87_52, offset: 0B], tmp117
    add     rax, 16   # ivtmp.87,
    cmp     rax, 40000000     # ivtmp.87,
    jne     .L12      #,

(Это, конечно, компиляция для x86-64. 32-битной x86 недостаточнорегистры для хранения всех указателей в регистрах, так что у вас будет несколько нагрузок, но они будут попадать в кэш L1d и фактически не будут являться узким местом пропускной способности: при узком месте в 1 хранилище на тактовую частоту есть много пропускной способности, чтобы получить некоторыебольше работы, проделанной в этом случае, когда вы просто храните константы.)

Эта оптимизация похожа на развертывание цикла 4x и реорганизацию для хранения группы 4 в каждом массиве together.Вот почему этого нельзя сделать, если компилятор не знает, что они не перекрываются.кланг не делает этого даже с __restrict, к сожалению.Обычное использование __restrict для обещания неперекрытия - это аргументы функций, а не локальные или глобальные, но я этого не пробовал.

При использовании глобальных массивов вместо глобальных указателей компилятор знал бы, что они не перекрываются (и значение указателя не будет храниться где-либо в памяти; адреса массивов будут константами времени ссылки.) В вашей версии Сами массивы имеют динамическое хранилище, и только указатели на них имеют статическое хранилище.

---

Чередующиеся полные строки кэша:

Что если myFunc1 сохранил 64 байта в одном массиве, прежде чем перейти к следующему? Тогда ваш компилятор может безопасно скомпилировать его в 4 (SSE), 2 (AVX) или 1 (AVX512) векторных хранилищ на массив за одну итерацию, покрывая полные 64 байта.

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

Это поможет избежать L1d-конфликтов, верно? Возможно, но если вы не используете хранилища NT, чтобы избежать RFO, то предварительные сборщики HW должны протянуть линии в L2, а затем в L1d, прежде чем хранилища попытаются зафиксировать. Так что это не так просто, как вы думаете, но буферы объединения записи, объединяющие хранилища и строки кэширования, которые еще не поступили, могут помочь.

Средство предварительной выборки L2-стримера в процессорах Intel может отслеживать 1 прямой и 1 обратный доступ на страницу, поэтому все должно быть в порядке (если массивы не имеют псевдонимов в L2). Это большая проблема с предварительной загрузкой L1d.

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

AVX512 может иметь значение; IDK, если выровненный vmovdqa64 [mem], zmm0 на Skylake-AVX512 может пропустить загрузку старого значения при переводе строки кэша в состояние MESI Modified, поскольку он знает, что перезаписывает всю строку кэша. (Если сделано без маскирования слиянием).

gcc8.1 не заботится о выравнивании выходных указателей даже с AVX512; возможно, перекрывающиеся первый и последний вектор, вероятно, будут хорошей стратегией для простых случаев, таких как этот, когда запись одной и той же памяти дважды не является проблемой. (Выравнивание имеет большее значение для AVX512, чем для AVX2 на оборудовании Skylake.)

---

4) Неожиданно низкая и странно бимодальная производительность для цикла хранения в Intel Skylake показывает, что чередование фиктивных записей (в то же местоположение) с потоком хранилища могут сделать это хуже, чем 1 непрерывный поток, для пропускной способности L1d / L2.

Возможно, из-за слияния / слияния хранилища в буфере хранилища перед фиксацией в кэш L1d. Но только для смежных хранилищ с одной и той же строкой кэша (поскольку строго упорядоченная модель памяти в x86 не позволяет хранилищам фиксировать L1d не по порядку).

Этот тест не испытывает проблем с конфликтом кэша. Но написание целой строки кеша должно помочь и некоторым.

Answer 3

Я считаю, что это сложнее, чем это. Является ли один цикл быстрее, чем несколько циклов, зависит от нескольких факторов.

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

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

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

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

Answer 4

При попытке сравнительного анализа кода вам необходимо:

1. Скомпилировать с флагами оптимизации включено.
2. Запустить каждый тест несколько раз, чтобы набрать среднее .

Вы не делали обоих.Например, вы можете использовать -O3, а что касается среднего, я сделал это (я заставил функцию возвращать элемент из списка):

for(int i = 0; i < 100; ++i)        
    dummy = myFunc1();

Затем я получил вывод, подобный этому:

Time taken by func1 (micro s):206693

Time taken by func2 (micro s):37898

Это подтверждает то, что вы видели, но разница на порядок (что очень важно).

---

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

---

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

---

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

Answer 5

Этот код создает переменные:

    list1 = new int[n]; list2 = new int[n];
    list3 = new int[n]; list4 = new int[n];
    list5 = new int[n]; list6 = new int[n];
    list7 = new int[n]; list8 = new int[n];
    list9 = new int[n]; list10 = new int[n];

, но почти наверняка не создаст фактические физические отображения страниц , пока память фактически не будет изменена . См. Создает ли malloc ленивые страницы для размещения в Linux (и других платформах)? для примера.

То есть ваш func1() должен ждать создания реальных физических страниц ОЗУ, а ваш func2() - нет. Измените порядок, и время отображения будет отнесено к производительности func2().

Самое простое решение, если ваш код опубликован, - запустить func1() или func2() до выполнения ваших запусков по времени.

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

Answer 6

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

myFunc1() по существу выполняет запись в память 10e8 в режиме произвольного доступа.

myFunc2() выполняет 10-кратную последовательную запись в память 10e7 слов.

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

Answer 7

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

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

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

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