std :: fill (0)이 std :: fill (1)보다 느린 이유는 무엇입니까?

Development Tip

std :: fill (0)이 std :: fill (1)보다 느린 이유는 무엇입니까?

yourdevel 2020. 11. 18. 21:35

std :: fill (0)이 std :: fill (1)보다 느린 이유는 무엇입니까?

나는 상수 값 이나 동적 값에 비해 상수 값을 설정할 때 std::fill큰 시스템 std::vector<int>에서 상당히 그리고 지속적으로 느리다는 것을 관찰했습니다 .01

5.8GiB / s 대 7.5GiB / s

그러나 더 작은 데이터 크기의 경우 결과가 다릅니다 fill(0).

스레드가 2 개 이상인 경우 데이터 크기가 4GiB이면 fill(1)기울기가 더 높지만 fill(0)(51GiB / s 대 90GiB / s) 보다 훨씬 낮은 피크에 도달합니다 .

이것은 왜 피크 대역폭이 fill(1)훨씬 낮은 지에 대한 두 번째 질문을 제기합니다 .

이를위한 테스트 시스템은 /sys/cpufreq8x16 GiB DDR4-2133과 함께 2.5GHz (경유 )로 설정된 듀얼 소켓 Intel Xeon CPU E5-2680 v3입니다 . 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 스레드는 시스템에서 85GiB / s를 얻습니다.

이 효과를 다른 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.

귀하의 질문 + 귀하의 답변에서 컴파일러 생성 asm에서 :

fill(0)최적화 된 마이크로 코딩 된 루프에서 256b 저장소를 사용 하는 ERMSBrep stosb 입니다. (버퍼가 정렬 된 경우 가장 잘 작동합니다 (최소 32B 또는 64B).
fill(1)간단한 128 비트 movaps벡터 저장 루프입니다. 너비에 관계없이 코어 클럭 사이클 당 최대 256b AVX의 스토어 하나만 실행할 수 있습니다. 따라서 128b 저장소는 Haswell의 L1D 캐시 쓰기 대역폭의 절반 만 채울 수 있습니다. 이것이 fill(0)최대 32kiB의 버퍼에 대해 약 2 배 빠른 이유 입니다. -march=haswell또는 -march=native로 컴파일하여 .

Haswell은 루프 오버 헤드를 간신히 따라갈 수 있지만 전혀 풀리지 않더라도 클럭 당 1 개의 스토어를 실행할 수 있습니다. 그러나 클럭 당 4 개의 융합 도메인 uop를 사용하면 비 순차적 창에서 공간을 차지하는 많은 필러가 있습니다. 일부 언 롤링은 저장소 데이터보다 저장소 주소 uop에 대한 처리량이 더 많기 때문에 TLB 미스가 저장소가 발생하는 위치보다 훨씬 앞서 해결을 시작하도록 할 수 있습니다. 언 롤링은 L1D에 맞는 버퍼에 대해 ERMSB와이 벡터 루프 간의 나머지 차이를 보완하는 데 도움이 될 수 있습니다. (질문에 대한 의견 은 L1 -march=native에게만 도움이 되었다고 말합니다 fill(1).)

그 주 rep movsd(구현하는 데 사용할 수있는 fill(1)대한 int아마 같은 수행 할 요소) rep stosb스웰합니다. 단지 공식 문서는 ERMSB 빠르게 제공한다는 보장하지만 rep stosb(하지만 rep stosd) 실제 CPU에 대한 지원 ERMSB 사용 유사 효율적인 마이크로 것을rep stosd . IvyBridge에 대해 약간의 의심이 있습니다 b. 이에 대한 업데이트는 @BeeOnRope의 우수한 ERMSB 답변 을 참조하십시오 .

GCC는 (문자열 작전에 대한 몇 가지의 x86 튜닝 옵션이 같은 -mstringop-strategy=ALG 과-mmemset-strategy=strategy ),하지만 그들 중 어떤 것이 실제로 방출 얻을 것이다 경우 IDK rep movsd위해 fill(1). 아마도 그렇지 않을 것입니다. 왜냐하면 코드가 memset.

하나 이상의 스레드에서 4GiB 데이터 크기에서 fill (1)은 더 높은 기울기를 나타내지 만 fill (0)보다 훨씬 낮은 피크에 도달합니다 (51GiB / s 대 90GiB / s).

movaps콜드 캐시 라인에 대한 일반 저장은 RFO (Read For Ownership)를 트리거합니다 . movaps처음 16 바이트를 쓸 때 메모리에서 캐시 라인을 읽는 데 많은 실제 DRAM 대역폭이 사용 됩니다. ERMSB 저장소는 저장소에 RFO가없는 프로토콜을 사용하므로 메모리 컨트롤러는 쓰기 만합니다. (L3 캐시에서도 페이지 워크가 누락되는 경우 페이지 테이블과 같은 기타 읽기를 제외하고 인터럽트 핸들러 등에서 일부로드 미스가 발생할 수 있습니다.)

@BeeOnRope 는 일반 RFO 저장소와 ERMSB에서 사용하는 RFO 방지 프로토콜의 차이가 언 코어 / L3 캐시에 높은 지연 시간이있는 서버 CPU의 일부 버퍼 크기 범위에 단점이 있다고 설명합니다. RFO 대 비 RFO에 대한 자세한 내용은 링크 된 ERMSB 답변을 참조하고 단일 코어 대역폭에 문제가되는 다중 코어 Intel CPU에서 언 코어 (L3 / 메모리)의 높은 지연 시간을 확인하십시오.

movntps( _mm_stream_ps()) 저장소 는 약하게 정렬되어 있으므로 캐시 라인을 L1D로 읽지 않고도 캐시를 우회하여 한 번에 전체 캐시 라인을 메모리로 바로 이동할 수 있습니다. movntpsRFO를 피합니다 rep stos. ( rep stos상점은 서로 재정렬 할 수 있지만 지침의 경계를 벗어나서는 안됩니다.)

movntps업데이트 된 답변 의 결과는 놀랍습니다.
큰 버퍼가있는 단일 스레드의 경우 결과는 movnt>> regular RFO> ERMSB 입니다. 두 가지 비 RFO 방법이 평범한 오래된 상점의 반대편에 있고 ERMSB가 최적과는 거리가 멀다는 것은 정말 이상합니다. 나는 현재 그것에 대한 설명이 없습니다. (설명 + 좋은 증거로 환영합니다).

예상대로 movntERMSB와 같이 여러 스레드가 높은 집계 저장소 대역폭을 달성 할 수 있습니다. movnt항상 라인 채우기 버퍼와 메모리로 곧장 이동하므로 캐시에 맞는 버퍼 크기의 경우 훨씬 느립니다. 클록 당 하나의 128b 벡터는 단일 코어의 RFO가없는 대역폭을 DRAM으로 쉽게 포화시키기에 충분합니다. 아마도 vmovntps ymm(256b)는 vmovntps xmmCPU 바운드 AVX 256b 벡터화 된 계산의 결과를 저장할 때 (128b)에 비해 측정 가능한 이점 일뿐입니다 (즉, 128b로 압축을 푸는 문제를 줄일 때만 해당).

movnti 대역폭은 낮습니다. 클럭 당 1 개의 저장소 uop에 4B 청크 병목 현상을 저장하면 라인 채우기 버퍼에 데이터를 추가하는 것이지 DRAM에 데이터를 추가하기 때문입니다 (메모리 대역폭을 포화시킬 충분한 스레드가있을 때까지).

@osgx는 댓글에 흥미로운 링크를 게시했습니다 .

Agner Fog의 asm 최적화 가이드, 지침 테이블 및 마이크로 아키텍처 가이드 : http://agner.org/optimize/
인텔 최적화 가이드 : http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf .
NUMA 스누핑 : 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 태그 위키 의 다른 내용도 참조하십시오 .

더 자세한 답변 을 장려 하기 위해 예비 조사 결과를 공유 하겠습니다 . 나는 이것이 질문 자체의 일부로 너무 많이 될 것이라고 느꼈습니다.

컴파일러는 최적화 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

흥미롭게도 for 바이트 유형을 std::fill통해 구현할 템플릿 / 헤더 최적화가 memset있지만이 경우 실제 루프를 변환하는 것은 컴파일러 최적화입니다. 이상하게도 a의 std::vector<char>경우 gcc도 최적화하기 시작합니다 fill(1). 인텔 컴파일러는 memset템플릿 사양 에도 불구하고 그렇지 않습니다 .

이것은 코드가 실제로 캐시가 아닌 메모리에서 작동 할 때만 발생하기 때문에 Haswell-EP 아키텍처가 단일 바이트 쓰기를 효율적으로 통합하지 못하는 것처럼 보입니다.

문제 및 관련 마이크로 아키텍처 세부 사항에 대한 추가 통찰력 을 높이고 싶습니다 . 특히 이것이 4 개 이상의 스레드에서 왜 그렇게 다르게 작동하는지 그리고 왜 memset캐시에서 훨씬 더 빠른지 명확하지 않습니다 .

최신 정보:

다음은 비교 결과입니다.

-march=native(avx2 )를 사용하는 fill (1) -L1 vmovdq %ymm0에서 더 잘 작동하지만 movaps %xmm0다른 메모리 수준 의 버전 과 유사 합니다.
32, 128 및 256 비트 비 임시 저장의 변형. 데이터 크기에 관계없이 동일한 성능으로 일관되게 수행됩니다. 특히 적은 수의 스레드에서 모두 메모리의 다른 변형보다 성능이 뛰어납니다. 128 비트와 256 비트는 정확히 비슷한 성능을냅니다. 스레드 수가 적기 때문에 32 비트는 훨씬 더 성능이 떨어집니다.

<= 6 스레드의 경우 메모리에서 작동 할 때보 다 vmovnt2 배의 이점이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

참고 : 루프를 매우 간결하게 만들기 위해 수동 포인터 계산을 수행해야했습니다. 그렇지 않으면 루프 내에서 벡터 인덱싱을 수행합니다. 아마도 최적화 프로그램을 혼동하는 내재적 때문일 것입니다.

참고 URL : https://stackoverflow.com/questions/42558907/why-is-stdfill0-slower-than-stdfill1

'Development Tip' 카테고리의 다른 글

Tomcat에서 레벨 로깅을 DEBUG로 설정하는 방법은 무엇입니까? (0)	2020.11.18
iOS 6.0이 설치된 Xcode 4.5에서 요청하지 않은 로그 메시지 (0)	2020.11.18
node.js 앱간에 코드를 공유하는 방법은 무엇입니까? (0)	2020.11.18
Qt 정적 연결 및 배포 (0)	2020.11.18
Covered Index 란 무엇입니까? (0)	2020.11.18

현재글std :: fill (0)이 std :: fill (1)보다 느린 이유는 무엇입니까?

yourdevel

std :: fill (0)이 std :: fill (1)보다 느린 이유는 무엇입니까?

std :: fill (0)이 std :: fill (1)보다 느린 이유는 무엇입니까?

'Development Tip' 카테고리의 다른 글

'Development Tip'의 다른글

티스토리툴바

std :: fill (0)이 std :: fill (1)보다 느린 이유는 무엇입니까?

std :: fill (0)이 std :: fill (1)보다 느린 이유는 무엇입니까?

'Development Tip' 카테고리의 다른 글

'Development Tip'의 다른글

관련글

티스토리툴바