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

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

5.8 гиб / с против 7.5 гиб / с

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

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

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

тестовой системой для этого был двойной сокет Intel Xeon CPU 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 был установлен. Стрем/добавить/24 потоков, получает 85 ГБ/С на систему.

я смог воспроизвести этот эффект на другой системе Haswell dual socket server, но не на любой другой архитектуре. Например, на песчаных мостов ЕР, производительность памяти, является идентичным, в то время как в кэш 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,fill1n";
    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.

2 62
c++ performance x86 compiler-optimization memset

2 ответа:

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

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

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

    Haswell может едва поспевать за накладными расходами цикла, но он все еще может запускать 1 магазин за часы, даже если он вообще не развернут. Но с 4 плавлеными доменами uops за часы, это много наполнителя, занимающего место в окне out-of-order. Некоторые разворачивания, возможно, позволят TLB пропустить начало разрешения дальше впереди того, где происходят магазины, так как есть больше пропускной способности для uops адреса магазина, чем для данных хранилища. Разворачивание может помочь компенсировать остальную разницу между 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 для string ops (как -mstringop-strategy=alg и -mmemset-strategy=strategy), но IDK, если любой из них получит его на самом деле испускать rep movsd на fill(1). Вероятно, нет, так как я предполагаю, что код начинается как цикл, а не memset.

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

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

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

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

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

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

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

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

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

37

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

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

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

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

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

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

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

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

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

обновление:

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

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

для vmovnt имеет преимущество 2x над rep stos при работе в памяти.

однопоточная пропускная способность:

single threaded performance by data size

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

memory performance by thread count

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

void __attribute__ ((noinline)) fill1(vector& v) {
    std::fill(v.begin(), v.end(), 1);
}
┌─→add    x1,%rax
│  vmovdq %ymm0,(%rdx)
│  add    x20,%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    x4,%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    x10,%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    x20,%rdx
│  cmp    %rcx,%rdx
└──jb     40

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

28