codememo

이 memcpy 구현에서 누락된/최적의 것은 무엇입니까?

tipmemo 2023. 9. 15. 21:02

이 memcpy 구현에서 누락된/최적의 것은 무엇입니까?

나는 글 쓰는 것에 흥미를 가지게 되었습니다.memcpy()교육적인 행사로서제가 한 일과 생각하지 못한 일에 대한 전체 논문을 쓰지는 않겠지만, 여기 어떤 사람이 실행한 것이 있습니다.

__forceinline   // Since Size is usually known,
                // most useless code will be optimized out
                // if the function is inlined.

void* myMemcpy(char* Dst, const char* Src, size_t Size)
{
        void* start = Dst;
        for ( ; Size >= sizeof(__m256i); Size -= sizeof(__m256i) )
        {
                __m256i ymm = _mm256_loadu_si256(((const __m256i* &)Src)++);
                _mm256_storeu_si256(((__m256i* &)Dst)++, ymm);
        }

#define CPY_1B *((uint8_t * &)Dst)++ = *((const uint8_t * &)Src)++
#define CPY_2B *((uint16_t* &)Dst)++ = *((const uint16_t* &)Src)++
#define CPY_4B *((uint32_t* &)Dst)++ = *((const uint32_t* &)Src)++
#if defined _M_X64 || defined _M_IA64 || defined __amd64
#define CPY_8B *((uint64_t* &)Dst)++ = *((const uint64_t* &)Src)++
#else
#define CPY_8B _mm_storel_epi64((__m128i *)Dst, _mm_loadu_si128((const __m128i *)Src)), ++(const uint64_t* &)Src, ++(uint64_t* &)Dst
#endif
#define CPY16B _mm_storeu_si128((__m128i *)Dst, _mm_loadu_si128((const __m128i *)Src)), ++(const __m128i* &)Src, ++(__m128i* &)Dst

    switch (Size) {
    case 0x00:                                                      break;
    case 0x01:      CPY_1B;                                         break;
    case 0x02:              CPY_2B;                                 break;
    case 0x03:      CPY_1B; CPY_2B;                                 break;
    case 0x04:                      CPY_4B;                         break;
    case 0x05:      CPY_1B;         CPY_4B;                         break;
    case 0x06:              CPY_2B; CPY_4B;                         break;
    case 0x07:      CPY_1B; CPY_2B; CPY_4B;                         break;
    case 0x08:                              CPY_8B;                 break;
    case 0x09:      CPY_1B;                 CPY_8B;                 break;
    case 0x0A:              CPY_2B;         CPY_8B;                 break;
    case 0x0B:      CPY_1B; CPY_2B;         CPY_8B;                 break;
    case 0x0C:                      CPY_4B; CPY_8B;                 break;
    case 0x0D:      CPY_1B;         CPY_4B; CPY_8B;                 break;
    case 0x0E:              CPY_2B; CPY_4B; CPY_8B;                 break;
    case 0x0F:      CPY_1B; CPY_2B; CPY_4B; CPY_8B;                 break;
    case 0x10:                                      CPY16B;         break;
    case 0x11:      CPY_1B;                         CPY16B;         break;
    case 0x12:              CPY_2B;                 CPY16B;         break;
    case 0x13:      CPY_1B; CPY_2B;                 CPY16B;         break;
    case 0x14:                      CPY_4B;         CPY16B;         break;
    case 0x15:      CPY_1B;         CPY_4B;         CPY16B;         break;
    case 0x16:              CPY_2B; CPY_4B;         CPY16B;         break;
    case 0x17:      CPY_1B; CPY_2B; CPY_4B;         CPY16B;         break;
    case 0x18:                              CPY_8B; CPY16B;         break;
    case 0x19:      CPY_1B;                 CPY_8B; CPY16B;         break;
    case 0x1A:              CPY_2B;         CPY_8B; CPY16B;         break;
    case 0x1B:      CPY_1B; CPY_2B;         CPY_8B; CPY16B;         break;
    case 0x1C:                      CPY_4B; CPY_8B; CPY16B;         break;
    case 0x1D:      CPY_1B;         CPY_4B; CPY_8B; CPY16B;         break;
    case 0x1E:              CPY_2B; CPY_4B; CPY_8B; CPY16B;         break;
    case 0x1F:      CPY_1B; CPY_2B; CPY_4B; CPY_8B; CPY16B;         break;
    }
#undef CPY_1B
#undef CPY_2B
#undef CPY_4B
#undef CPY_8B
#undef CPY16B
        return start;
}

이 코멘트는 "크기는 보통 컴파일러가 코드 인라인 아웃을 가장 쓸모없게 최적화할 수 있기 때문에 알려져 있습니다."라고 번역됩니다.

가능하다면 이 구현을 개선하고 싶지만 개선할 점이 별로 없을 수도 있습니다.대용량 메모리 청크에 SSE/AVX를 사용하고, 마지막 32바이트를 루프 대신 수동 롤링과 약간의 조정을 수행합니다.자, 여기 제 질문이 있습니다.

마지막 몇 바이트의 루프는 롤을 풀지만 첫 번째(그리고 지금은 단일) 루프는 부분적으로 롤을 풀지 않는 이유는 무엇입니까?
정렬 문제는 어떻습니까?중요하지 않습니까?정렬 양자까지 처음 몇 바이트를 다르게 처리한 다음 정렬된 바이트 시퀀스에 대해 256비트 ops를 수행해야 합니까?그렇다면 적절한 정렬 양자를 어떻게 결정해야 합니까?
이 구현에서 누락된 가장 중요한 기능(있는 경우)은 무엇입니까?

지금까지 답변에 언급된 특징/원칙

당신은 그래야 한다.__restrict__당신의 파라미터들.(@chux)
메모리 대역폭은 제한 요소이므로 이에 대비하여 구현을 측정합니다.(@Zboson)
작은 어레이의 경우에는 메모리 대역폭에 접근할 수 있고, 큰 어레이의 경우에는 접근할 수 있습니다. (@Zboson)
메모리 대역폭을 포화시키기 위해서는 다수의 스레드(||)가 필요합니다.(@Zboson)
큰 복사 크기와 작은 복사 크기에 대해 서로 다르게 최적화하는 것이 현명할 것입니다.(@Zboson)
(정렬이 중요합니까?명시적으로 다루지 않음!)
컴파일러는 최적화를 위해 사용할 수 있는 "명백한 사실"(예: 첫 번째 루프 이후의 크기 < 32)을 보다 명확하게 인식해야 합니다.(@chux)
SSE/AVX 호출을 취소해야 한다는 주장(@BenJackson, 여기)과 반대하는 주장(@PaulR)이 있습니다.
(대상 위치를 캐시하기 위해 CPU가 필요하지 않다고 CPU에 알려주는) 비일시적 전송은 더 큰 버퍼를 복사하는 데 유용해야 합니다.(@Zboson)

저는 다양한 연산을 가진 인텔 프로세서의 메모리 대역폭을 측정하는 것을 연구해 왔습니다. 그중 하나는memcpy Bridge,. Core2, Ivy Bridge, Haswell 해봤습니다에서해봤습니다저는 대부분의 테스트를 고유성을 가진 C/C++를 사용하여 수행했습니다(아래 코드 참조). 하지만 현재 어셈블리에서 테스트를 다시 작성하고 있습니다.

만의 효율적인 를 memcpy함수는 가능한 최고의 대역폭이 무엇인지 아는 것이 중요합니다.은될의에다로른이s다로sfhfatnn이른eeeh은sd될memcpy기능은 작은 것과 큰 것(그리고 그 사이에)에 대해 서로 다른 최적화가 필요합니다.단순하게 하기 위해 8192바이트의 작은 어레이와 1GB의 큰 어레이에 최적화했습니다.

소형 어레이의 경우 각 코어의 최대 읽기 및 쓰기 대역폭은 다음과 같습니다.

Core2-Ivy Bridge             32 bytes/cycle
Haswell                      64 bytes/cycle

이것이 소규모 어레이를 지향해야 하는 벤치마크입니다.로우가어고이가다의몇고에의다f에몇reae의esies어가yo이의tee우가-4sd8*sizeof(float)*unroll_factor제입니다. 가 가 .memcpy 14 4 28192바이트(Ubuntu 14.04, GCC 4.9, EGLIBC 2.19)의 크기에 :

                             GB/s     efficiency
    Core2 (p9600@2.66 GHz)  
        builtin               35.2    41.3%
        eglibc                39.2    46.0%
        asmlib:               76.0    89.3%
        copy_unroll1:         39.1    46.0%
        copy_unroll8:         73.6    86.5%
    Ivy Bridge (E5-1620@3.6 GHz)                        
        builtin              102.2    88.7%
        eglibc:              107.0    92.9%
        asmlib:              107.6    93.4%
        copy_unroll1:        106.9    92.8%
        copy_unroll8:        111.3    96.6%
    Haswell (i5-4250U@1.3 GHz)
        builtin:              68.4    82.2%     
        eglibc:               39.7    47.7%
        asmlib:               73.2    87.6%
        copy_unroll1:         39.6    47.6%
        copy_unroll8:         81.9    98.4%

asmlib아그너 포그의 애슬립입니다copy_unroll1그리고.copy_unroll8함수는 아래에 정의됩니다.

가 Δ Δ Δ GCC Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ memcpy와 그 Core2에서 잘 .memcpyEGLIBC에서는 Core2나 Haswell에서 잘 작동하지 않습니다.최근에 GLIBC 헤드 버전을 확인해봤는데 Haswell보다 성능이 훨씬 뛰어났습니다.모든 경우에 롤링 해제가 최상의 결과를 가져옵니다.

void copy_unroll1(const float *x, float *y, const int n) {
    for(int i=0; i<n/JUMP; i++) {
        VECNF().LOAD(&x[JUMP*(i+0)]).STORE(&y[JUMP*(i+0)]);
    }
}

void copy_unroll8(const float *x, float *y, const int n) {
for(int i=0; i<n/JUMP; i+=8) {
    VECNF().LOAD(&x[JUMP*(i+0)]).STORE(&y[JUMP*(i+0)]);
    VECNF().LOAD(&x[JUMP*(i+1)]).STORE(&y[JUMP*(i+1)]);
    VECNF().LOAD(&x[JUMP*(i+2)]).STORE(&y[JUMP*(i+2)]);
    VECNF().LOAD(&x[JUMP*(i+3)]).STORE(&y[JUMP*(i+3)]);
    VECNF().LOAD(&x[JUMP*(i+4)]).STORE(&y[JUMP*(i+4)]);
    VECNF().LOAD(&x[JUMP*(i+5)]).STORE(&y[JUMP*(i+5)]);
    VECNF().LOAD(&x[JUMP*(i+6)]).STORE(&y[JUMP*(i+6)]);
    VECNF().LOAD(&x[JUMP*(i+7)]).STORE(&y[JUMP*(i+7)]);
}

}

VECNF().LOAD이다 ㅇ_mm_load_ps() 또는 SSE의 경우_mm256_load_ps()AVX, AVX의 경우.VECNF().STORE이다 ㅇ_mm_store_ps() 또는 SSE의 경우_mm256_store_ps()AVX의 경우 JUMP는 SSE의 경우 4 또는 AVX의 경우 8입니다.

큰 크기의 경우 비일시적 저장 지침을 사용하고 여러 스레드를 사용하여 최상의 결과를 얻을 수 있습니다.많은 사람들이 하나의 스레드가 일반적으로 메모리 대역폭을 포화시키지 않는다고 믿는 것과는 반대로 말입니다.

void copy_stream(const float *x, float *y, const int n) {
    #pragma omp parallel for        
    for(int i=0; i<n/JUMP; i++) {
        VECNF v = VECNF().load_a(&x[JUMP*i]);
        stream(&y[JUMP*i], v);
    }
}

stream이다 ㅇ_mm_stream_ps() 또는 SSE의 경우_mm256_stream_ps()AVXAVX의 경우

입니다.memcpy최대 주 메모리 대역폭이 51.2GB/s인 1GB에 대해 4개의 스레드를 사용하여 E5-1620@3.6GHz를 생성합니다.

                         GB/s     efficiency
    eglibc:              23.6     46%
    asmlib:              36.7     72%
    copy_stream:         36.7     72%

다시 한번 EGLIBC의 성능이 떨어집니다.비일시적 매장을 이용하지 않기 때문입니다.

를 했습니다.eglibc그리고.asmlib memcpy이와 같이 로는들와들는so

void COPY(const float * __restrict x, float * __restrict y, const int n) {
    #pragma omp parallel
    {
        size_t my_start, my_size;
        int id = omp_get_thread_num();
        int num = omp_get_num_threads();
        my_start = (id*n)/num;
        my_size = ((id+1)*n)/num - my_start;
        memcpy(y+my_start, x+my_start, sizeof(float)*my_size);
    }
}

memcpy함수는 64바이트(또는 32바이트 또는 16바이트)로 정렬되지 않고 크기가 32바이트의 배수 또는 unroll factor가 아닌 배열을 고려해야 합니다.또한 비일시 매장의 이용 시기에 대해서도 결정이 필요로 합니다.일반적인 경험의 법칙은 최대 캐시 레벨의 절반보다 큰 크기(보통 L3)에 대해서만 비일시적 저장소를 사용하는 것입니다.그러나 이는 크고 작은 이상적인 경우에 최적화한 후에 처리해야 할 "2차" 세부 사항입니다.이상적인 경우에도 성능이 좋지 않을 경우 잘못된 정렬이나 이상적이지 않은 크기 배수를 수정하는 것은 크게 걱정할 필요가 없습니다.

갱신하다

Canon을 사용하는 더 . Ivy Bridge와 Haswell은 Ivy Bridge와 Haswell을 사용합니다.rep movsbmovntdqa(비매점 사용 설명서).인텔은 이를 EMSB(enhanced repovsb)라고 부릅니다.이 내용은 ERMSB(Enhanced REP MOVSB 및 STOSB 작동) 섹션의 Intel Optimization 설명서에 설명되어 있습니다.

또한 섹션 17.9의 Agner Fog의 조립품 서브루틴 최적화 매뉴얼에서 데이터 블록 이동(모든 프로세서):

"대규모 데이터 블록을 이동하는 데는 여러 가지 방법이 있습니다.가장 일반적인 방법은 다음과 같습니다.

REP MOVS 지침.
데이터가 정렬된 경우: 사용 가능한 레지스터 크기가 가장 큰 루프에서 읽고 씁니다.
크기가 일정한 경우: 인라인 이동 지침.
데이터가 잘못 정렬된 경우:먼저 대상을 정렬하기 위해 필요한 만큼의 바이트를 이동합니다.그런 다음 정렬되지 않은 상태로 읽고 사용 가능한 레지스터 크기가 가장 큰 루프에 정렬된 상태로 씁니다.
데이터가 잘못 정렬된 경우: 정렬된 것을 읽고, 정렬되지 않은 것을 보상하기 위해 이동하고, 정렬된 것을 기록합니다.
데이터 크기가 너무 커서 캐싱할 수 없는 경우 비일시적 쓰기를 사용하여 캐시를 바이패스합니다.필요한 경우 정렬 오류를 보완하도록 시프트합니다."

memcpy각각의 점을 고려해야 합니다.또한 Ivy Bridge와 Haswell의 경우 대형 어레이의 경우 포인트 6보다 포인트 1이 더 나은 것으로 보입니다.인텔과 AMD 그리고 기술의 반복마다 다른 기술이 필요합니다.만의 일반적인 효율적인 것을 쓰는합니다.memcpy기능이 상당히 복잡할 수 있습니다. 제가 Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ ΔΔ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δmemcpy또는 EGLIBC에서 표준 라이브러리보다 더 잘 할 수 없다는 가정이 틀렸습니다.

다음과 같은 추가적인 세부 정보 없이는 질문에 정확하게 답할 수 없습니다.

대상 플랫폼(대부분 CPU 아키텍처이지만 메모리 구성도 그 역할을 함)은 무엇입니까?
복사 길이의 분포와 예측¹ 가능성(그리고 선형의 분포와 예측 가능성은 그보다 작음)은 어느 정도입니까?
복사 크기가 컴파일 타임에 정적으로 알려질 수 있습니까?

그래도, 나는 적어도 위의 매개변수들의 일부 조합에 대해 차선책이 될 가능성이 있는 몇 가지를 지적할 수 있습니다.

32-case 스위치문

32-케이스 스위치 문은 후행 0-31바이트를 매우 잘 처리하는 귀여운 방법이며 벤치마크가 될 가능성이 높습니다. 그러나 실제 환경에서는 적어도 두 가지 요인으로 인해 성능이 떨어질 수 있습니다.

코드 크기

이 스위치 문만 해도 바디에 대한 수백 바이트의 코드가 필요하며, 각 길이에 대한 올바른 위치로 점프하는 데 필요한 32 엔트리 룩업 테이블도 필요합니다.Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ ΔΔ Δ Δ Δ Δ Δ Δ ΔΔ Δ Δ Δ Δ Δ Δ Δ memcpy모든 것이 여전히 가장 빠른 캐시 레벨에 들어맞기 때문에 풀 사이즈 CPU에 있습니다. 그러나 실제 세계에서는 다른 코드도 실행하고 uop 캐시와 L1 데이터 및 명령 캐시에 대해 경합이 있습니다.

이렇게 많은 명령어가 uop³ 캐시의 유효 크기의 20%를 완전히 차지할 수 있으며 uop 캐시 미스(및 상응하는 캐시-레거시 인코더 전환 주기)는 이 정교한 스위치가 제공하는 작은 이점을 쉽게 없앨 수 있습니다.

게다가, 스위치는⁴ 점프 대상을 위한 32 엔트리, 256 바이트 룩업 테이블이 필요합니다.검색에서 DRAM을 놓치게 되면 150회 이상의 주기로 페널티를 받게 됩니다. 그런 다음 몇 번의 실수를 하지 않고 실행해야 하는 것입니다.switch기껏해야 한두 개 정도 절약할 수 있을 거라는 걸 감안하면 그럴 만한 가치가 있는 건가요?다시 말하지만, 마이크로벤치마크에는 나타나지 않을 것입니다.

가 있겠소, 이 ?memcpy이런 종류의 "사례의 집중적인 열거"는 최적화된 라이브러리에서도 흔히 볼 수 있습니다.저는 그들의 개발이 대부분 마이크로벤치마크에 의해 주도되었거나, 단점에도 불구하고 범용 코드의 큰 조각에 여전히 가치가 있다고 결론지을 수 있습니다.그렇기는 하지만 최적이 아닌 시나리오(명령어 및/또는 데이터 캐시 압력)도 분명히 존재합니다.

분기예측

스위치 문은 하나의 간접 분기에 의존하여 대안을 선택합니다.이는 분기 예측 변수가 이 간접 분기를 예측할 수 있는 정도로 효율적이며, 이는 기본적으로 관측된 길이의 순서가 예측 가능해야 함을 의미합니다.

간접 분기이기 때문에 조건부 분기보다 분기 예측 가능성에 더 많은 제약이 있습니다. BTB 항목의 수가 제한되어 있기 때문입니다.했지만,은 CPU서만다이수할과의od다f수fttesyeoss의e,면,s이utst의만eu과memcpy짧은 주기의 단순한 반복 패턴을 따르지 마십시오(이전 CPU의 경우 1 또는 2만큼 짧습니다). 각 호출마다 분기 예측 오류가 발생합니다.

에서 를 합니다 는 에 한 에서 합니다 는 에 에서 switch최고가 되기 위해서: 짧은 길이.매우 긴 길이에서 후행 31바이트의 동작은 대량 복사에 의해 지배되기 때문에 그다지 중요하지 않습니다.은에는는re은,st는rswitchall-important (즉, 31 바이트 이하의 복사본의 경우 실행되는 것이 전부입니다)!

길이에 는 Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δswitch간접 점프는 기본적으로 자유롭기 때문에.나,memcpy일련의 길이에 걸쳐 벤치마크 "스윕"을 수행하고, 각 하위 테스트마다 동일한 길이를 반복적으로 사용하여 "시간 대 길이" 그래프를 쉽게 그래프화할 수 있도록 결과를 보고합니다.switch는 이러한 테스트에서 매우 효과적이며, 종종 몇 바이트의 작은 길이에 대해 2 또는 3 사이클과 같은 결과를 보고합니다.

현실 세계에서, 당신의 길이는 작지만 예측할 수 없는 것일 수도 있습니다.이 경우, 간접 분기는 종종 잘못된⁵ 예측을 하게 되며, 최신 CPU에서는 ~20 사이클의 페널티를 받게 됩니다.몇 번의 사이클 중 가장 좋은 경우와 비교해 보면, 이는 규모가 더 큰 순서입니다.따라서 여기 유리 턱은 매우 심각할 수 있습니다. (즉, 그 행동은)switch이 전형적인 경우는 최상보다 더 나쁜 크기의 순서일 수 있지만, 긴 길이에서는 일반적으로 서로 다른 전략 간에 최대 50%의 차이를 볼 수 있습니다.

해결책

이 다 에서 입니다 에서 이 다 switch무너진다구요?

더프의 장치 사용

코드 크기 문제에 대한 한 가지 해결책은 스위치 케이스를 결합하는 것인데, 더프의 장치 스타일입니다.

예를 들어 길이 1, 3, 7의 경우에 대한 조립 코드는 다음과 같습니다.

길이 1

    movzx   edx, BYTE PTR [rsi]
    mov     BYTE PTR [rcx], dl
    ret

길이 3

    movzx   edx, BYTE PTR [rsi]
    mov     BYTE PTR [rcx], dl
    movzx   edx, WORD PTR [rsi+1]
    mov     WORD PTR [rcx+1], dx

길이 7

    movzx   edx, BYTE PTR [rsi]
    mov     BYTE PTR [rcx], dl
    movzx   edx, WORD PTR [rsi+1]
    mov     WORD PTR [rcx+1], dx
    mov     edx, DWORD PTR [rsi+3]
    mov     DWORD PTR [rcx+3], edx
    ret

이것은 다양한 점프 인과 함께 하나의 케이스로 결합될 수 있습니다.

    len7:
    mov     edx, DWORD PTR [rsi-6]
    mov     DWORD PTR [rcx-6], edx
    len3:
    movzx   edx, WORD PTR [rsi-2]
    mov     WORD PTR [rcx-2], dx
    len1:
    movzx   edx, BYTE PTR [rsi]
    mov     BYTE PTR [rcx], dl
    ret

들지 , 하여 3 ℓℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ ℓ.ret지침들.다음과 같은 근거가 있음을 유의하십시오.rsi그리고.rcx여기서 변경되었습니다. 첫 번째 바이트가 아닌 마지막 바이트를 가리킵니다.그 거스름돈은 점프 전 코드에 따라 무료이거나 매우 저렴합니다.

긴 길이(예: 위 체인에 길이 15 및 31을 부착할 수 있음)로 확장하고 누락된 길이에 대해서는 다른 체인을 사용할 수 있습니다.완전한 연습은 독자에게 맡겨져 있습니다.이 방법을 사용하면 50%의 크기만 줄일 수 있으며, 16에서 31 사이의 크기를 축소하기 위해 다른 방법과 결합하면 훨씬 더 나은 크기를 얻을 수 있습니다.

이 접근 방식은 코드 크기(및 점프 테이블 크기)에만 도움이 되며, 에 설명된 대로 크기를 줄이고 256바이트 미만이 되면 바이트 크기의 룩업 테이블을 허용할 수 있습니다.예측 가능성에는 아무런 도움이 되지 않습니다.

겹친 스토어

코드 크기와 예측 가능성 모두에 도움이 되는 한 가지 방법은 중복된 저장소를 사용하는 것입니다.그것은,memcpy8~15바이트의 경우 두 개의 8바이트 저장소를 가지 없는 방식으로 수행할 수 있으며, 두 번째 저장소는 첫 번째 저장소와 부분적으로 겹칩니다.예를 들어, 11바이트를 복사하려면 상대 위치에서 8바이트를 복사해야 합니다.0그리고.11 - 8 == 3. 중간에 있는 바이트 중 일부는 "두 번 복사"되지만 실제로는 8바이트 복사본이 1, 2, 4바이트 복사본과 속도가 동일하기 때문에 괜찮습니다.

C 코드는 다음과 같습니다.

  if (Size >= 8) {
    *((uint64_t*)Dst) = *((const uint64_t*)Src);
    size_t offset = Size & 0x7;
    *(uint64_t *)(Dst + offset) = *(const uint64_t *)(Src + offset);
  }

... 해당 어셈블리는 문제가 없습니다.

    cmp     rdx, 7
    jbe     .L8
    mov     rcx, QWORD PTR [rsi]
    and     edx, 7
    mov     QWORD PTR [rdi], rcx
    mov     rcx, QWORD PTR [rsi+rdx]
    mov     QWORD PTR [rdi+rdx], rcx

특히, 두 개의 적재물, 두 개의 저장소와 한 개의 적재물이 정확히 제공된다는 점에 유의하십시오.and(추가로cmp그리고.jmp그의 존재는 주변 코드를 어떻게 구성하느냐에 달려 있습니다.)이는 이미 대부분의 컴파일러가 생성한 8-15바이트 접근 방식보다 동일하거나 더 나은 방식으로, 최대 4개의 로드/스토어 쌍을 사용할 수 있습니다.

오래된 프로세서는 이러한 "중복된 스토어"에 대해 약간의 불이익을 겪었지만, 새로운 아키텍처(적어도 지난 10년 정도)는 아무런 불이익 없이 이를⁶ 처리하는 것으로 보입니다.여기에는 두 가지 주요 이점이 있습니다.

다양한 크기에 대해 분기가 없는 동작입니다.효과적으로 분기를 양자화하여 많은 값이 동일한 경로를 선택할 수 있습니다.8에서 15(또는 원하는 경우 8에서 16)까지의 모든 크기가 동일한 경로를 선택하고 잘못된 예측 압력을 받지 않습니다.
적어도 8~9개의 다른 경우는switch전체 코드 크기의 일부로 단일 케이스에 포함됩니다.

이 접근 방식은 다음과 결합할 수 있습니다.switch접근하지만, 몇 가지 경우만 사용하거나, 조건부 이동을 통해 더 큰 크기로 확장할 수 있습니다. 예를 들어 분기 없이 모두 8바이트에서 31바이트로 이동할 수 있습니다.

다시 가장 잘 작동하는 것은 분기 분포에 따라 다르지만, 전반적으로 이 "중복" 기법은 매우 잘 작동합니다.

얼라인먼트

기존 코드는 정렬을 다루지 않습니다.

사실, 그것은 일반적으로 합법적이거나 C 또는 C++가 아닙니다.char *포인터는 단순히 더 큰 유형에 캐스팅되고 역참조되며, 이는 합법적이지 않습니다. 그러나 실제로는 오늘날의 x86 컴파일러에서 작동하는 코드를 생성하지만, 실제로는 더 엄격한 정렬 요구 사항이 있는 플랫폼에서는 실패합니다.

그 이상으로 정렬을 구체적으로 처리하는 것이 더 나은 경우가 많습니다.크게 세 가지 경우가 있습니다.

원본과 대상이 이미 정렬되어 있습니다.여기서는 원래 알고리즘도 잘 될 겁니다.
원본과 대상이 상대적으로 정렬되어 있지만 완전히 정렬되어 있지 않습니다.즉, 가치가 있습니다.A둘 다 정렬되도록 소스와 대상 모두에 추가할 수 있습니다.
소스와 대상이 완전히 잘못 정렬되어 있습니다(즉, 실제로 정렬되어 있지 않으며 경우 (2)가 해당되지 않음).

(1)의 경우 기존 알고리즘은 정상적으로 동작합니다.작은 인트로 루프는 정렬되지 않은 복사본을 정렬된 복사본으로 바꿀 수 있기 때문에 (2)의 경우에는 큰 최적화가 누락될 수 있습니다.

또한 (3)의 경우에는 성능이 떨어질 가능성이 높습니다. 일반적으로 완전히 잘못 정렬된 경우에는 대상 또는 소스를 정렬한 다음 "반 정렬"을 진행할 수 있기 때문입니다.

정렬 패널티는 시간이 지남에 따라 점점 작아지고 있으며, 가장 최근의 칩은 범용 코드의 경우에는 미미하지만 로드와 저장소가 많은 코드의 경우 여전히 심각할 수 있습니다.대규모 복사본의 경우 DRAM 대역폭이 제한되므로 크게 문제가 되지 않을 수 있지만, 소규모 복사본의 경우 정렬 오류로 인해 처리량이 50% 이상 감소할 수 있습니다.

NT 저장소를 사용하는 경우 정렬이 중요할 수도 있는데, 이는 많은 NT 저장소 명령이 잘못 정렬된 인수로 수행되지 않기 때문입니다.

언롤링 금지

코드는 언롤되지 않으며 컴파일러는 기본적으로 다른 양만큼 언롤됩니다.분명히 다른 언롤 전략을 가진 두 컴파일러 중에서 기껏해야 한 컴파일러가 최선이기 때문에 이것은 차선책입니다.

(적어도 알려진 플랫폼 대상에 대해서는) 가장 좋은 접근법은 어떤 언롤 팩터가 가장 좋은지를 결정한 다음 코드에 적용하는 것입니다.

게다가, 언롤링은 종종 컴파일러가 할 수 있는 것보다 더 나은 작업을 수행하면서, 우리의 "outro" 코드를 "intro"와 현명한 방식으로 결합될 수 있습니다.

알려진 크기

'빌트인'을 이기기 어려운 가장 큰 이유memcpy현대 컴파일러의 루틴은 컴파일러가 단순히 라이브러리를 호출하지 않는다는 것입니다.memcpy언제든지memcpy소스에 나타납니다.그들은 계약을 알고 있습니다.memcpy그리고 적절한 시나리오에서 단일 인라인 명령 또는 심지어⁷ 그 이하의 명령으로 자유롭게 구현할 수 있습니다.

이것은 특히 알려진 길이와 함께 명백합니다.memcpy. 이 경우, 길이가 작으면 컴파일러는 복사를 효율적으로 수행하기 위해 몇 가지 명령어만 삽입합니다.이것은 함수 호출의 오버헤드를 방지할 뿐만 아니라 크기 등에 대한 모든 검사를 피할 수 있으며, 또한 큰 것과 마찬가지로 복사본에 대한 컴파일 시간에 효율적인 코드를 생성합니다.switch용나이fees나n서의net-te-te>switch.

마찬가지로 컴파일러는 호출 코드의 구조 정렬에 대해 많은 것을 알고 있으며, 정렬을 효율적으로 처리하는 코드를 만들 수 있습니다.

만약 당신이 단지 실행한다면.memcpy2도서관 기능으로는 복제하기 어렵습니다.메소드를 작은 부분과 큰 부분으로 분할하는 방법의 일부를 얻을 수 있습니다. 작은 부분은 헤더 파일에 나타나서 일부 크기를 확인하고 잠재적으로 기존의 것을 호출합니다.memcpy크기가 작으면 라이브러리 루틴을 수행합니다.인라이닝의 마법을 통해 빌트인과 같은 장소에 도달할 수 있습니다.memcpy.

마지막으로, 당신은 다음과 같이 트릭을 시도할 수도 있습니다.__builtin_constant_p또는 작고 알려진 사건을 효율적으로 처리하기 위한 등가물.

¹ 여기서는 크기의 "분포"(예를 들어, 8-24바이트 사이에 균일하게 분포되어 있다고 말할 수 있음)와 실제 크기 시퀀스의 "예측 가능성"(예를 들어, 크기가 예측 가능한 패턴을 가지고 있음)을 구별하고자 합니다.예측 가능성 문제는 위에서 설명한 특정 구현이 본질적으로 더 예측 가능하기 때문에 구현에 따라 달라지기 때문에 다소 미묘합니다.

² 특히 ~750바이트의 명령어가clang대 600트인인대트gcc 스위치 - 250의 명령에서만,치 256프업블에의 180 - 250다이한에트(다이r0의만p,한00ey )gcc그리고.clang각각).갓볼트 링크.

³ 유효 uop 캐시 크기가 1000개 인스트럭션 중 기본적으로 200개의 fused uop.최근 x86의 경우 uop 캐시 크기가 ~1500uop 정도였지만, 제한적인 코드-대-캐시 할당 규칙 때문에 코드베이스의 극도로 전용된 패딩 외에는 모두 사용할 수 없습니다.

⁴ 스위치 케이스의 컴파일 길이가 다르기 때문에 점프를 직접 계산할 수 없습니다.다른 방법으로 할 수도 있었습니다. 즉, 메모리 소스를 사용하지 않는 대신 룩업 테이블에서 16비트 값을 사용할 수도 있었습니다.jmp. 를 75% 를 .

⁵ 일반적인 최악의 경우 예측률이 ~50%(전임의 가지의 경우)인 조건부 가지 예측과는 달리, 동전을 뒤집는 것이 아니기 때문에 예측하기 어려운 간접 가지는 100%에 쉽게 접근할 수 있으므로 거의 무한한 가지 목표 집합을 선택하는 것입니다.이는 실제 세계에서 일어나는 일입니다.memcpy0 ~하게 분포된 . 즉,과 0에 30게은을는데다고된가다고데s는h을lg가y은switch코드는 97%까지 잘못 예측합니다.

⁶ 물론, 잘못 정렬된 상점에 대한 벌칙이 있을 수 있지만, 이것들 또한 일반적으로 규모가 작고 점점 작아지고 있습니다.

⁷ 예를 들면, a.memcpy스택으로 이동한 다음, 일부 조작 및 다른 곳의 복사본이 완전히 제거되어 원본 데이터를 최종 위치로 직접 이동할 수 있습니다.도 같은 malloc를 뒤에memcpy완전히 제거할 수 있습니다.

ERMSB의 이점 활용

더 큰 블록에 대해서도 REP MOVSB를 사용하는 것을 고려해주시기 바랍니다.

아시다시피 1993년 펜티엄 CPU가 처음 생산된 이후 인텔은 간단한 명령어는 더 빠르게 만들고 복잡한 명령어(REP MOVSB와 같은)는 더 느리게 만들기 시작했습니다.그래서, REP MOVSB는 매우 느려졌고, 더 이상 그것을 사용할 이유가 없었습니다.2013년 인텔은 REP MOVSB를 재검토하기로 결정했습니다.CPU에 CPUID ERMSB(Enhanced REP MOVSB) 비트가 있는 경우 REP MOVSB 명령은 이전 프로세서와는 다르게 실행되므로 빠릅니다.실제로는 256바이트 이상의 대용량 블록에서만 빠르며, 특정 조건이 충족될 경우에만 빠릅니다.

소스 주소와 대상 주소는 모두 16바이트 경계에 정렬해야 합니다.
소스 영역과 대상 영역이 겹쳐서는 안 됩니다.
길이는 64의 배수여야 더 높은 성능을 얻을 수 있습니다.
방향이 전방(CLD)이어야 합니다.

최적화에 관한 인텔 매뉴얼, 섹션 3.7.6 ERMSB 및 STOSB 작동(ERMSB) http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf 을 참조하십시오.

2048바이트보다 작은 블록의 경우 AVX를 사용하는 것이 좋습니다.큰 블록의 경우 REP MOVSB를 사용하는 것이 좋습니다.REP MOVSB(약 35주기)의 높은 초기 시작 비용 때문입니다.

속도 테스트를 해보았는데 2048바이트 이상의 블록에서는 REP MOVSB의 성능은 타의 추종을 불허합니다.그러나 256바이트보다 작은 블록의 경우 REP MOVSB는 매우 느리고, 심지어 루프의 일반 MOVE RAX보다 앞뒤로 느립니다.

ERMSB는 MOVSD(MOVSQ)가 아닌 MOVSB에만 영향을 미치므로 MOVSB가 MOVSD(MOVSQ)보다 조금 더 빠르지 않도록 부탁드립니다.

따라서 memcpy() 구현에 AVX를 사용할 수 있으며, 블록이 2048바이트보다 크고 모든 조건이 충족되면 REP MOVSB를 호출하면 memcpy() 구현은 타의 추종을 불허합니다.

고장난 실행 엔진의 이점 활용

또한 "Intel® 64 및 IA-32 Architectures Optimization Reference Manual"(http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf 섹션 2.1.2)에서 Out-of-Order Execution Engine에 대한 정보를 확인하고 이점을 활용할 수 있습니다.

예를 들어, Intel SkyLake 프로세서 시리즈(2015년 출시)에서는 다음과 같은 기능을 갖추고 있습니다.

ALU(산술 논리 장치)에 대한 실행 단위 4개(추가, cmp, 또는 테스트, xor, movzx, movsx, movdqu, (v)movdqa, (v)movdqa, (v)movap*, (v)movup),
Vector ALU ((v)pand, (v)por, (v)pxor, (v)movq, (v)movq, (v)movap*, (v)movup*, (v)p*, (v)orp*, (v)paddb/w/d/q, (v)blendv*, (v)blendp*, (v)pblendd)에 대한 실행 단위 3개

따라서 레지스터 전용 연산을 사용하면 위의 유닛(3+4)을 병렬로 점유할 수 있습니다.메모리 복사는 3+4 명령어를 병렬로 사용할 수 없습니다.메모리에서 로드할 때는 최대 32바이트 명령을 2개까지, 메모리에서 저장할 때는 32바이트 명령을 1개까지 동시에 사용할 수 있습니다. 레벨 1 캐시를 사용하는 경우에도 마찬가지입니다.

가장 빠른 memcpy 구현 방법에 대한 자세한 내용은 Intel 설명서를 다시 참조하십시오. http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf

섹션 2.2.2 (하스웰 마이크로아키텍처의 고장난 엔진):"스케줄러는 디스패치 포트에 마이크로옵스의 디스패치를 제어합니다.고장난 실행 코어를 지원하는 디스패치 포트는 8개입니다.8개의 포트 중 4개의 포트가 계산 작업을 위한 실행 리소스를 제공했습니다.나머지 4개의 포트는 한 주기로 최대 2개의 256비트 로드와 1개의 256비트 저장소 작업의 메모리 작업을 지원합니다."

섹션 2.2.4(캐시 및 메모리 서브시스템)에는 다음과 같은 참고 사항이 있습니다. "첫 번째 레벨 데이터 캐시는 각 사이클마다 로드 마이크로옵 2개를 지원합니다. 각 마이크로옵은 최대 32바이트의 데이터를 가져올 수 있습니다."

섹션 2.2.4.1(부하 및 저장 작동 개선)에는 다음과 같은 정보가 있습니다.L1 데이터 캐시는 매 주기마다 2개의 256비트(32바이트) 로드와 1개의 256비트(32바이트) 저장 작업을 처리할 수 있습니다.통합 L2는 매 주기마다 하나의 캐시 라인(64바이트)을 서비스할 수 있습니다.또한, 72개의 로드 버퍼와 42개의 저장 버퍼를 사용하여 마이크로옵스 실행을 기내에서 지원할 수 있습니다.

다른 섹션(Sandy Bridge 및 기타 마이크로아키텍처 전용 2.3 등)은 기본적으로 위의 정보를 반복합니다.

2.3.4절(실행핵심)은 추가적인 세부사항을 제공합니다.

스케줄러는 매 주기마다 각 포트에 하나씩 최대 6개의 마이크로옵을 디스패치할 수 있습니다.다음 표에는 어떤 작업을 어떤 포트에서 디스패치할 수 있는지 요약되어 있습니다.

포트 0: ALU, Shift, Mul, STTNI, Int-Div, 128b-Mov, Blend, 256b-Mov
포트 1: ALU, Fast LEA, Slow LEA, MUL, Shuf, Blend, 128bMov, Add, CVT
포트 2 & 포트 3 : 로드_애드러, 스토어_애드러
포트 4: 저장_데이터
포트 5: ALU, Shift, Branch, Fast LEA, Shuf, Blend, 128b-Mov, 256b-Mov

2.3.5.1(Load and Store Operation Overview) 섹션은 빠른 메모리 복사 방법과 2.4.4.1(Loads and Store) 섹션을 이해하는 데도 유용할 수 있습니다.

다른 프로세서 아키텍처의 경우 다시 로드 유닛 2개와 스토어 유닛 1개입니다.표 2-4(Skylake Microarchitecture의 캐시 파라미터)에는 다음과 같은 정보가 있습니다.

최대 대역폭(바이트/사이클):

1차 레벨 데이터 캐시: 96바이트(로드 2x32B + 저장소 1*32B)
세컨드 레벨 캐시: 64바이트
세 번째 레벨 캐시: 32바이트입니다.

DDR4 메모리를 탑재한 인텔 Core i5 6600 CPU(스카이레이크, 14nm, 2015년 9월 출시)에 대해서도 속도 테스트를 해본 결과 이론이 확인되었습니다.예를 들어, 테스트 결과 메모리 복사를 위해 일반 64비트 레지스터를 사용하는 경우, 심지어 많은 레지스터를 병렬로 사용하는 경우에도 성능이 저하되는 것으로 나타났습니다.또한 XMM 레지스터를 2개만 사용해도 충분합니다. 3번째를 추가해도 성능이 향상되지 않습니다.

CPU에 AVX CPUID 비트가 있는 경우 256비트(32바이트)의 대용량 YMM 레지스터를 사용하여 메모리를 복사하여 전체 로드 장치 2개를 차지할 수 있습니다.AVX 지원은 2011년 1분기에 출하된 Sandy Bridge 프로세서와 함께 Intel에 의해 처음 도입되었으며 이후 AMD에 의해 2011년 3분기에 Bulldozer 프로세서와 함께 출시되었습니다.

// first cycle  
vmovdqa ymm0, ymmword ptr [rcx+0]      // load 1st 32-byte part using first load unit
vmovdqa ymm1, ymmword ptr [rcx+20h]    // load 2nd 32-byte part using second load unit

// second cycle
vmovdqa ymmword ptr [rdx+0], ymm0      // store 1st 32-byte part using the single store unit

// third cycle
vmovdqa ymmword ptr [rdx+20h], ymm1    ; store 2nd 32-byte part - using the single store unit (this instruction will require a separate cycle since there is only one store unit, and we cannot do two stores in a single cycle)

add ecx, 40h // these instructions will be used by a different unit since they don't invoke load or store, so they won't require a new cycle
add edx, 40h

또한 이 코드를 8번 이상 루프 언롤하면 속도의 이점이 있습니다.이전에 썼던 것처럼 ymm0와 ymm1 외에 레지스터를 더 추가한다고 해서 성능이 향상되지는 않습니다. 왜냐하면 로드 유닛은 2개, 스토어 유닛은 1개뿐이기 때문입니다."dec9 jnz @@again"과 같은 루프를 추가하면 성능이 저하되지만 단순한 "addecx/edx"는 그렇지 않습니다.

마지막으로 CPU에 AVX-512 확장 기능이 있는 경우 512비트(64바이트) 레지스터를 사용하여 메모리를 복사할 수 있습니다.

vmovdqu64   zmm0, [rcx+0]           ; load 1st 64-byte part
vmovdqu64   zmm1, [rcx+40h]         ; load 2nd 64-byte part 

vmovdqu64   [rdx+0], zmm0           ; store 1st 64-byte part
vmovdqu64   [rdx+40h], zmm1         ; store 2nd 64-byte part 

add     rcx, 80h
add     rdx, 80h

AVX-512는 2016년에 출시된 Xeon Phix200, Skylake EP/EX Xeon "Purley"(Xeon E5-26xx V5) 프로세서(H2 2017), Cannonlake-X 프로세서(H2 2017), Skylake-X 프로세서 - 코어 i9-7xx, i7-7xx, i5-7xx - 2017년 6월에 출시되었습니다.

메모리는 사용 중인 레지스터의 크기에 맞춰 정렬해야 합니다.그렇지 않은 경우 "정렬되지 않은" 지침인 vmovdqu 및 move up을 사용하십시오.

먼저 주 루프는 정렬되지 않은 AVX 벡터 로드/스토어를 사용하여 한 번에 32바이트를 복사합니다.

    for ( ; Size >= sizeof(__m256i); Size -= sizeof(__m256i) )
    {
        __m256i ymm = _mm256_loadu_si256(((const __m256i* &)Src)++);
        _mm256_storeu_si256(((__m256i* &)Dst)++, ymm);
    }

그러면 최종 스위치 문은 잔차 0을 처리합니다.가능한 한 효율적인 방식으로 31바이트, 적절한 경우 8/4/2/1바이트 복사본의 조합을 사용합니다.이 루프는 롤링되지 않은 루프가 아니라 최소 로드 및 저장 수를 사용하여 잔여 바이트를 처리하는 32개의 서로 다른 최적화된 코드 경로입니다.

메인 32바이트 AVX 루프가 수동으로 언롤되지 않는 이유에 관해서는 다음과 같은 몇 가지 가능한 이유가 있습니다.

대부분의 컴파일러는 작은 루프를 자동으로 실행합니다(루프 크기 및 최적화 스위치에 따라 다름).
과도한 언롤링으로 인해 LSD 캐시 밖으로 작은 루프가 유출될 수 있습니다(일반적으로 디코딩된 µops만 28개).
현재 Core iX CPU에서는 [*]을(를) 중지하기 전에 두 개의 동시 로드/스토어만 실행할 수 있습니다.
일반적으로 이와 같이 언롤링되지 않은 AVX 루프도 가용 DRAM 대역폭을 포화시킬 수 있습니다[*].

[*] 위의 마지막 두 설명은 소스 및/또는 대상이 캐시에 없는 경우(즉, DRAM에 쓰기/읽기/읽기)에 적용되며, 따라서 로드/스토어 지연 시간이 높습니다.

언급URL : https://stackoverflow.com/questions/26246040/whats-missing-sub-optimal-in-this-memcpy-implementation

'codememo' 카테고리의 다른 글

게시물 유형별 카테고리 구분 (0)	2023.09.15
__attribute__((시공자)) VC에서 동치입니까? (0)	2023.09.15
PowerShell을 사용하여 모든 서비스의 "실행 경로"를 추출하는 방법 (0)	2023.09.15
rand() 함수 없이 난수를 생성하려면 어떻게 해야 합니까? (0)	2023.09.15
setTimeout/clearTimeout 문제 (0)	2023.09.15

현재글이 memcpy 구현에서 누락된/최적의 것은 무엇입니까?

각종 프로그래밍 정보를 다루는 블로그입니다.

ajax, Oracle, mongodb, jQuery, spring, sql-server, PYTHON, json, Angular, ReactJS, Excel, angularJS, C, PowerShell, asp.net, wordpress, bash, spring-boot, Git, MariaDB,

Today :
Yesterday :

tipmemo

이 memcpy 구현에서 누락된/최적의 것은 무엇입니까?

이 memcpy 구현에서 누락된/최적의 것은 무엇입니까?

지금까지 답변에 언급된 특징/원칙

32-case 스위치문

코드 크기

분기예측

해결책

더프의 장치 사용

겹친 스토어

얼라인먼트

언롤링 금지

알려진 크기

ERMSB의 이점 활용

고장난 실행 엔진의 이점 활용

'codememo' 카테고리의 다른 글

'codememo'의 다른글

티스토리툴바

« 2026/02 »
일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28

이 memcpy 구현에서 누락된/최적의 것은 무엇입니까?

이 memcpy 구현에서 누락된/최적의 것은 무엇입니까?

지금까지 답변에 언급된 특징/원칙

32-case 스위치문

코드 크기

분기예측

해결책

더프의 장치 사용

겹친 스토어

얼라인먼트

언롤링 금지

알려진 크기

ERMSB의 이점 활용

고장난 실행 엔진의 이점 활용

'codememo' 카테고리의 다른 글

'codememo'의 다른글

관련글

티스토리툴바