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

Ответ 1

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

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

• fill(1) - это простой 128-битный цикл хранения векторов movaps. Только одно хранилище может выполняться на каждый тактовый такт независимо от ширины, до 256b AVX. Таким образом, магазины 128b могут заполнять только половину пропускной способности кэша кэша Haswell L1D. Вот почему fill(0) примерно в 2 раза быстрее для буферов до ~ 32kiB. Скомпилируйте с -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 работает быстро. См. @BeeOnRope отличный ответ ERMSB для получения обновлений об этом.

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

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

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

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

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

Ваш movntps результат в вашем обновленном ответе вызывает удивление.
Для одного потока с большими буферами ваши результаты movnt → regular RFO > ERMSB. Так что действительно странно, что два метода non-RFO находятся на противоположных сторонах обычных старых магазинов и что ERMSB пока что не оптимален. В настоящее время у меня нет объяснений. (редактирование приветствуется с объяснением + хорошие доказательства).

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

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

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

• Руководство по оптимизации AgM Fog asm, таблицы инструкций и руководство по микрочипу: 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 теги wiki.

Ответ 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 для типов байтов, но в этом случае оптимизация компилятора преобразует фактический цикл. Как ни странно, при a std::vector<char> gcc начинает оптимизировать также fill(1). Компилятор Intel не работает, несмотря на спецификацию memset.

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

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

Update:

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

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

Для <= 6 thread vmovnt имеет преимущество 2x перед 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

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