Почему std::fill(0) медленнее, чем std::fill(1)?

Question

Я наблюдал за системой, которая std::fill на большом std::vector<int> был значительно и последовательно медленнее при установке постоянного значения 0 по сравнению с постоянной величиной 1 или динамическое значение:

5,8 ГБ / с против 7,5 ГБ / с

Тем не менее, результаты отличаются для меньших размеров данных, где fill(0) быстрее:

С более чем одним потоком, с размером данных 4 ГиБ, fill(1) показывает более высокий уклон, но достигает гораздо более низкого пика, чем fill(0) (51 ГиБ / с против 90 ГиБ / с):

Это поднимает вторичный вопрос, почему максимальная пропускная способность fill(1) намного ниже.

Тестовой системой для этого был двухпроцессорный процессор Intel Xeon E5-2680 v3 с тактовой частотой 2,5 ГГц (через /sys/cpufreq) с 8x16 ГиБ DDR4-2133. Я тестировал с GCC 6.1.0 (-O3) и компилятор Intel 17.0.1 (-fast), оба получают идентичные результаты. GOMP_CPU_AFFINITY=0,12,1,13,2,14,3,15,4,16,5,17,6,18,7,19,8,20,9,21,10,22,11,23 был установлен. Strem/add/24 потоков получает 85 ГБ / с в системе.

Мне удалось воспроизвести этот эффект на другой системе серверов с двумя сокетами Haswell, но не на любой другой архитектуре. Например, в Sandy Bridge EP производительность памяти идентична, тогда как в кеше fill(0) намного быстрее

Вот код для воспроизведения:

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <omp.h>
#include <vector>

using value = int;
using vector = std::vector<value>;

constexpr size_t write_size = 8ll * 1024 * 1024 * 1024;
constexpr size_t max_data_size = 4ll * 1024 * 1024 * 1024;

void __attribute__((noinline)) fill0(vector& v) {
    std::fill(v.begin(), v.end(), 0);
}

void __attribute__((noinline)) fill1(vector& v) {
    std::fill(v.begin(), v.end(), 1);
}

void bench(size_t data_size, int nthreads) {
#pragma omp parallel num_threads(nthreads)
    {
        vector v(data_size / (sizeof(value) * nthreads));
        auto repeat = write_size / data_size;
#pragma omp barrier
        auto t0 = omp_get_wtime();
        for (auto r = 0; r < repeat; r++)
            fill0(v);
#pragma omp barrier
        auto t1 = omp_get_wtime();
        for (auto r = 0; r < repeat; r++)
            fill1(v);
#pragma omp barrier
        auto t2 = omp_get_wtime();
#pragma omp master
        std::cout << data_size << ", " << nthreads << ", " << write_size / (t1 - t0) << ", "
                  << write_size / (t2 - t1) << "\n";
    }
}

int main(int argc, const char* argv[]) {
    std::cout << "size,nthreads,fill0,fill1\n";
    for (size_t bytes = 1024; bytes <= max_data_size; bytes *= 2) {
        bench(bytes, 1);
    }
    for (size_t bytes = 1024; bytes <= max_data_size; bytes *= 2) {
        bench(bytes, omp_get_max_threads());
    }
    for (int nthreads = 1; nthreads <= omp_get_max_threads(); nthreads++) {
        bench(max_data_size, nthreads);
    }
}

Представленные результаты составлены с g++ fillbench.cpp -O3 -o fillbench_gcc -fopenmp,

Answer 1

От вашего вопроса + сгенерированный компилятором asm из вашего ответа:

• fill(0) это ERMSB rep stosb который будет использовать 256b магазинов в оптимизированном микрокодированном цикле. (Лучше всего работает, если буфер выровнен, возможно, по крайней мере, до 32B или, может быть, 64B).

• fill(1) это простой 128-битный movaps векторный магазин петли. Только одно хранилище может выполняться за такт ядра независимо от ширины, до 256b AVX. Таким образом, хранилища 128b могут заполнять только половину пропускной способности записи в кэш-память Haswell L1D. Вот почему fill(0) примерно в 2 раза быстрее для буферов до ~32 кБ. Компилировать с -march=haswell или же -march=native чтобы исправить это.

  Haswell едва справляется с накладными расходами цикла, но он все равно может запускать 1 хранилище за такт, даже если он вообще не развернут. Но с 4 мопами слитых доменов за такт, это много наполнителя, занимающего место в окне "не в порядке". Некоторое развертывание может позволить ошибкам TLB начать разрешать дальше, чем происходит в хранилищах, поскольку пропускная способность для адресов хранилища выше, чем для данных хранилища. Развертывание может помочь компенсировать разницу между ERMSB и этим векторным циклом для буферов, которые соответствуют L1D. (Комментарий к вопросу говорит, что -march=native только помог fill(1) для L1.)

Обратите внимание, что rep movsd (который может быть использован для реализации fill(1) за int элементы), вероятно, будет выполнять так же, как rep stosb на Haswell. Хотя только официальная документация только гарантирует, что ERMSB дает быстро rep stosb (но нет rep stosd), фактические процессоры, которые поддерживают ERMSB, используют аналогичный эффективный микрокод для rep stosd, Есть некоторые сомнения по поводу IvyBridge, где, возможно, только b это быстро. См. Отличный ответ ERMSB @ BeeOnRope для получения обновлений по этому вопросу.

У gcc есть несколько вариантов настройки x86 для строковых операций ( например, -mstringop-strategy= и -mmemset-strategy=strategy), но IDK, если кто-нибудь из них получит его на самом деле rep movsd за fill(1), Наверное, нет, так как я предполагаю, что код начинается с цикла, а не memset,

---

При более чем одном потоке с размером данных 4 ГиБ, fill(1) показывает более высокий наклон, но достигает гораздо более низкого пика, чем fill(0) (51 ГиБ / с против 90 ГиБ / с):

Нормальный movaps Сохранение в холодной строке кэша запускает Read For Ownership (RFO). Большая часть реальной пропускной способности DRAM тратится на чтение строк кэша из памяти, когда movaps пишет первые 16 байтов. Хранилища ERMSB используют протокол без RFO для своих хранилищ, поэтому контроллеры памяти только записывают. (За исключением разных операций чтения, таких как таблицы страниц, если какие-либо обходы страниц пропускаются даже в кеше L3, и, возможно, некоторые пропуски загрузки в обработчиках прерываний или что-то еще).

@BeeOnRope объясняет в комментариях, что различие между обычными хранилищами RFO и протоколом избегания RFO, используемым ERMSB, имеет недостатки для некоторых диапазонов размеров буфера на ЦП сервера, где существует большая задержка в кеше uncore/L3. См. Также связанный ответ ERMSB для получения дополнительной информации о RFO по сравнению с non-RFO, а высокая задержка uncore (L3/memory) во многоядерных процессорах Intel является проблемой для одноядерной полосы пропускания.

---

movntps ( _mm_stream_ps() ) хранилища имеют слабую упорядоченность, поэтому они могут обходить кеш и сразу направлять в память целую строку кеша, даже не считывая строку кеша в L1D. movntps избегает RFO, как rep stos делает. (rep stos Магазины могут переупорядочиваться друг с другом, но не за пределами инструкции.)

Ваш movntps результаты в вашем обновленном ответе удивительны.
Для одного потока с большими буферами ваши результаты movnt >> Обычная РФО> ЕРМСБ. Так что это действительно странно, что два не-RFO метода находятся на противоположных сторонах старых старых магазинов, и что ERMSB так далек от оптимального. В настоящее время у меня нет объяснения этому. (исправления приветствуются с объяснениями + веские доказательства).

Как мы и ожидали, movnt позволяет нескольким потокам достигать высокой суммарной пропускной способности хранилища, как ERMSB. movnt всегда идет прямо в буферы заполнения строки, а затем в память, так что это намного медленнее для размеров буфера, которые помещаются в кэш. Одного 128-битного вектора на такт достаточно для того, чтобы легко перевести пропускную способность без ядра RFO в DRAM. Наверное vmovntps ymm (256b) является лишь измеримым преимуществом перед vmovntps xmm (128b) при сохранении результатов векторизованных вычислений AVX 256b с привязкой к ЦП (т. Е. Только тогда, когда это избавляет от необходимости распаковки в 128b).

movnti Пропускная способность низкая, потому что при хранении в узких местах блоков 4B по 1 хранилищу в тактах добавляются данные в буферы заполнения строк, а не при отправке этих буферов заполнения строк в DRAM (пока у вас не будет достаточно потоков для насыщения пропускной способности памяти).

---

@osgx опубликовал несколько интересных ссылок в комментариях:

• Руководство по оптимизации asm, таблицы инструкций и руководство по микроархам Agner Fog: http://agner.org/optimize/

• Руководство по оптимизации Intel: http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf.

• NUMA snooping: http://frankdenneman.nl/2016/07/11/numa-deep-dive-part-3-cache-coherency/

• https://software.intel.com/en-us/articles/intelr-memory-latency-checker
• Протокол согласования кэша и производительность памяти архитектуры Intel Haswell-EP

Смотрите также другие вещи в теге x86 вики.

Answer 2

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

Компилятор оптимизирует fill(0) к внутреннему memset, Это не может сделать то же самое для fill(1), поскольку memset работает только на байтах.

В частности, оба glibcs __memset_avx2 а также __intel_avx_rep_memset реализуются с помощью одной горячей инструкции:

rep    stos %al,%es:(%rdi)

Когда ручной цикл компилируется в настоящую 128-битную инструкцию:

add    $0x1,%rax                                                                                                       
add    $0x10,%rdx                                                                                                      
movaps %xmm0,-0x10(%rdx)                                                                                               
cmp    %rax,%r8                                                                                                        
ja     400f41

Интересно пока есть оптимизация шаблона / заголовка для реализации std::fill с помощью memset для байтовых типов, но в этом случае это оптимизация компилятора для преобразования фактического цикла. Странно, для std::vector<char>GCC начинает также оптимизировать fill(1), Компилятор Intel нет, несмотря на memset спецификация шаблона.

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

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

Обновить:

Вот результат по сравнению с

• заполните (1), который использует -march=native (AVX2 vmovdq %ymm0) - в L1 работает лучше, но похоже на movaps %xmm0 версия для других уровней памяти.
• Варианты 32, 128 и 256-битных невременных хранилищ. Они работают с одинаковой производительностью независимо от размера данных. Все превосходят другие варианты в памяти, особенно для небольшого количества потоков. 128 бит и 256 бит работают точно так же, для небольших потоков 32 бит работает значительно хуже.

Для потока <= 6, vmovntимеет двукратное преимущество передrep stos при работе в памяти.

Однопоточная полоса пропускания:

Общая пропускная способность в памяти:

Вот код, используемый для дополнительных тестов с соответствующими горячими циклами:

void __attribute__ ((noinline)) fill1(vector& v) {
    std::fill(v.begin(), v.end(), 1);
}
┌─→add    $0x1,%rax
│  vmovdq %ymm0,(%rdx)
│  add    $0x20,%rdx
│  cmp    %rdi,%rax
└──jb     e0


void __attribute__ ((noinline)) fill1_nt_si32(vector& v) {
    for (auto& elem : v) {
       _mm_stream_si32(&elem, 1);
    }
}
┌─→movnti %ecx,(%rax)
│  add    $0x4,%rax
│  cmp    %rdx,%rax
└──jne    18


void __attribute__ ((noinline)) fill1_nt_si128(vector& v) {
    assert((long)v.data() % 32 == 0); // alignment
    const __m128i buf = _mm_set1_epi32(1);
    size_t i;
    int* data;
    int* end4 = &v[v.size() - (v.size() % 4)];
    int* end = &v[v.size()];
    for (data = v.data(); data < end4; data += 4) {
        _mm_stream_si128((__m128i*)data, buf);
    }
    for (; data < end; data++) {
        *data = 1;
    }
}
┌─→vmovnt %xmm0,(%rdx)
│  add    $0x10,%rdx
│  cmp    %rcx,%rdx
└──jb     40


void __attribute__ ((noinline)) fill1_nt_si256(vector& v) {
    assert((long)v.data() % 32 == 0); // alignment
    const __m256i buf = _mm256_set1_epi32(1);
    size_t i;
    int* data;
    int* end8 = &v[v.size() - (v.size() % 8)];
    int* end = &v[v.size()];
    for (data = v.data(); data < end8; data += 8) {
        _mm256_stream_si256((__m256i*)data, buf);
    }
    for (; data < end; data++) {
        *data = 1;
    }
}
┌─→vmovnt %ymm0,(%rdx)
│  add    $0x20,%rdx
│  cmp    %rcx,%rdx
└──jb     40

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