c - 파이썬 for 문 빠르게




이 코드가 최적화가 활성화 된 상태에서 6.5 배 더 느린 이유는 무엇입니까? (2)

어떤 이유로 glibcstrlen 함수를 벤치 마크하고 싶었고 GCC에서 최적화가 가능할 때 훨씬 느린 속도를 보이는 것으로 나타났습니다. 그 이유는 모르겠습니다.

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

#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

int main() {
    char *s = calloc(1 << 20, 1);
    memset(s, 65, 1000000);
    clock_t start = clock();
    for (int i = 0; i < 128; ++i) {
        s[strlen(s)] = 'A';
    }
    clock_t end = clock();
    printf("%lld\n", (long long)(end-start));
    return 0;
}

내 컴퓨터에서 다음과 같이 출력됩니다.

$ gcc test.c && ./a.out
13336
$ gcc -O1 test.c && ./a.out
199004
$ gcc -O2 test.c && ./a.out
83415
$ gcc -O3 test.c && ./a.out
83415

어떻게 든, 최적화를 가능하게하면 더 오래 실행됩니다.


Godbolt의 Compiler Explorer에서 코드를 테스트하면 다음과 같은 설명이 제공됩니다.

  • -O0 또는 최적화없이, 생성 된 코드는 C 라이브러리 함수 strlen 호출합니다
  • -O1 에서 생성 된 코드는 rep scasb 명령어를 사용하여 간단한 인라인 확장을 사용합니다.
  • -O2 이상에서는 생성 된 코드가보다 정교한 인라인 확장을 사용합니다.

코드를 반복적으로 벤치마킹하면 실행 간 차이가 상당하지만 반복 횟수를 늘리면 다음과 같이 표시됩니다.

  • -O1 코드는 C 라이브러리 구현보다 훨씬 느립니다. 32240 3090
  • -O2 코드는 -O1 보다 빠르지 만 C 라이브러리 코드 인 85703090 보다 훨씬 느립니다.

이 동작은 gccglibc 합니다. clang 과 Apple의 Libc를 사용하는 OS / X에 대한 동일한 테스트는 큰 차이점을 나타내지 않습니다. Godbolt는 clang 모든 최적화 수준에서 C 라이브러리 strlen 을 호출한다는 사실을 보여주기 때문에 놀랄 일이 아닙니다.

이것은 gcc / glibc의 버그로 간주 될 수 있지만보다 광범위한 벤치마킹은 strlen 을 호출하는 오버 헤드가 작은 문자열에 대한 인라인 코드의 성능 부족보다 더 중요한 영향을 strlen 보여줍니다. 벤치마킹하는 문자열이 너무 많아서 매우 긴 문자열에 벤치 마크를 집중 시키면 의미있는 결과를 얻을 수 없습니다.

이 벤치 마크를 개선하고 다양한 문자열 길이를 테스트했습니다. -O1 생성 한 인라인 코드가 항상 느린 인텔 ® 코어 ™ i3-2100 CPU @ 3.10GHz에서 실행되는 gcc (Debian 4.7.2-5) 4.7.2의 Linux 벤치 마크에서 나타납니다. 중간 정도 긴 문자열의 경우 10 배까지, -O2 는 매우 짧은 문자열의 경우 libc strlen보다 길고 긴 문자열의 경우 절반 정도입니다. 이 데이터에서, strlen 의 GNU C 라이브러리 버전은 적어도 특정 하드웨어에서 대부분의 문자열 길이에 대해 매우 효율적입니다. 또한 캐싱은 벤치 마크 측정에 중요한 영향을 미친다는 것을 명심하십시오.

다음은 업데이트 된 코드입니다.

#include <stdlib.h>
#include <string.h>
#include <time.h>

void benchmark(int repeat, int minlen, int maxlen) {
    char *s = malloc(maxlen + 1);
    memset(s, 'A', minlen);
    long long bytes = 0, calls = 0;
    clock_t clk = clock();
    for (int n = 0; n < repeat; n++) {
        for (int i = minlen; i < maxlen; ++i) {
            bytes += i + 1;
            calls += 1;
            s[i] = '\0';
            s[strlen(s)] = 'A';
        }
    }
    clk = clock() - clk;
    free(s);
    double avglen = (minlen + maxlen - 1) / 2.0;
    double ns = (double)clk * 1e9 / CLOCKS_PER_SEC;
    printf("average length %7.0f -> avg time: %7.3f ns/byte, %7.3f ns/call\n",
           avglen, ns / bytes, ns / calls);
}

int main() {
    benchmark(10000000, 0, 1);
    benchmark(1000000, 0, 10);
    benchmark(1000000, 5, 15);
    benchmark(100000, 0, 100);
    benchmark(100000, 50, 150);
    benchmark(10000, 0, 1000);
    benchmark(10000, 500, 1500);
    benchmark(1000, 0, 10000);
    benchmark(1000, 5000, 15000);
    benchmark(100, 1000000 - 50, 1000000 + 50);
    return 0;
}

출력은 다음과 같습니다.

chqrlie> gcc -std=c99 -O0 benchstrlen.c && ./a.out
average length       0 -> avg time:  14.000 ns/byte,  14.000 ns/call
average length       4 -> avg time:   2.364 ns/byte,  13.000 ns/call
average length      10 -> avg time:   1.238 ns/byte,  13.000 ns/call
average length      50 -> avg time:   0.317 ns/byte,  16.000 ns/call
average length     100 -> avg time:   0.169 ns/byte,  17.000 ns/call
average length     500 -> avg time:   0.074 ns/byte,  37.000 ns/call
average length    1000 -> avg time:   0.068 ns/byte,  68.000 ns/call
average length    5000 -> avg time:   0.064 ns/byte, 318.000 ns/call
average length   10000 -> avg time:   0.062 ns/byte, 622.000 ns/call
average length 1000000 -> avg time:   0.062 ns/byte, 62000.000 ns/call
chqrlie> gcc -std=c99 -O1 benchstrlen.c && ./a.out
average length       0 -> avg time:  20.000 ns/byte,  20.000 ns/call
average length       4 -> avg time:   3.818 ns/byte,  21.000 ns/call
average length      10 -> avg time:   2.190 ns/byte,  23.000 ns/call
average length      50 -> avg time:   0.990 ns/byte,  50.000 ns/call
average length     100 -> avg time:   0.816 ns/byte,  82.000 ns/call
average length     500 -> avg time:   0.679 ns/byte, 340.000 ns/call
average length    1000 -> avg time:   0.664 ns/byte, 664.000 ns/call
average length    5000 -> avg time:   0.651 ns/byte, 3254.000 ns/call
average length   10000 -> avg time:   0.649 ns/byte, 6491.000 ns/call
average length 1000000 -> avg time:   0.648 ns/byte, 648000.000 ns/call
chqrlie> gcc -std=c99 -O2 benchstrlen.c && ./a.out
average length       0 -> avg time:  10.000 ns/byte,  10.000 ns/call
average length       4 -> avg time:   2.000 ns/byte,  11.000 ns/call
average length      10 -> avg time:   1.048 ns/byte,  11.000 ns/call
average length      50 -> avg time:   0.337 ns/byte,  17.000 ns/call
average length     100 -> avg time:   0.299 ns/byte,  30.000 ns/call
average length     500 -> avg time:   0.202 ns/byte, 101.000 ns/call
average length    1000 -> avg time:   0.188 ns/byte, 188.000 ns/call
average length    5000 -> avg time:   0.174 ns/byte, 868.000 ns/call
average length   10000 -> avg time:   0.172 ns/byte, 1716.000 ns/call
average length 1000000 -> avg time:   0.172 ns/byte, 172000.000 ns/call

GCC의 인라인 strlen 패턴은 SSE2 pcmpeqb / pmovmskbbsf calloc 의 16 바이트 정렬을 사용)보다 훨씬 느립니다 . 이 "최적화"는 실제로는 비관입니다.

16 바이트 정렬을 이용하는 필자의 손으로 직접 작성한 간단한 루프는 큰 버퍼의 경우 gcc -O3 인라인보다 5 배 빠르며 짧은 문자열의 경우 2 배 빠릅니다. (그리고 짧은 문자열의 경우 strlen을 호출하는 것보다 빠릅니다.) gcc.gnu.org/bugzilla/show_bug.cgi?id=88809 에 주석을 추가하여 gcc가 -O2 / -O3에서 인라인해야 할 것을 제안합니다. (우리는 4 바이트 정렬 만 알고 있다면 16 바이트까지 램핑을 제안합니다.)

gcc는 ( calloc 의해 보증 된) 버퍼에 대해 4 바이트 정렬 가지고있을 때 , GP 정수 레지스터 ( -O2 이상)를 사용하여 4 바이트 단위의 스칼라 bithack으로 strlen 을 인라인하는 것을 선택합니다.

(한 번에 4 바이트를 읽는 것은 문자열 바이트를 포함하지 않는 페이지를 넘을 수 없다는 것을 알면 매핑이 해제 될 수 있습니다. 동일한 버퍼 내의 끝까지 읽는 것이 안전합니까? x86 및 x64 페이지 (TL : DR 예, asm입니다. 따라서 컴파일러는 C 소스에서 UB를 사용하더라도 코드를 내보낼 수 있습니다.) libc strlen 구현도이를 활용합니다. glibc strlen 에 대한 링크 및 큰 문자열에 대해 매우 빠르게 실행되는 방법에 대한 요약.)

-O1 에서 gcc는 항상 ( repnz scasb 정렬 없이도) 매우 느린 repnz scasbstrlen 을 인라인으로 선택합니다 (최신 Intel CPU에서는 클럭 사이클 당 약 1 바이트). "빠른 문자열"은 rep stos / repnz 명령이 아닌 rep stosrep movs 에만 적용됩니다. 그들의 마이크로 코드는 한 번에 단순한 1 바이트이지만 여전히 시작시 오버 헤드가 있습니다. ( https://agner.org/optimize/ )

(예를 들어 volatile void *tmp s 를 저장 / 재로드하여 컴파일러에서 포인터를 "숨기는"방법으로 테스트 할 수 있습니다 .gcc는 volatile 에서 다시 읽은 포인터 값에 대한 가정을 없애야합니다. .)

GCC는 -mstringop-strategy=libcallunrolled_loop-mstringop-strategy=libcall 와 같은 일부 x86 튜닝 옵션 을 일반적으로 사용합니다 (strlen뿐만 아니라 rep 또는 loop로 수행 할 수있는 또 다른 주요 작업이 될 수 있습니다). 나는 이것들이 어떤 영향을 미치는지 여기에서 확인하지 않았다.

또 다른 옵션을위한 문서는 현재의 행동을 기술한다. 정렬되지 않은 포인터를 원할 경우에도이 인라이닝 (정렬 처리를위한 추가 코드 사용)을 얻을 수 있습니다. (인라인 루프가 기계가 수행 할 수있는 것과 비교할 때 쓰레기가 아니었던 대상의 경우, 특히 작은 문자열의 경우 실제 우승하는 경우가 많았습니다.)

-minline-all-stringops
기본적으로 GCC는 대상이 4 바이트 경계 이상으로 정렬되어있는 경우에만 문자열 연산을 인라인합니다. 이것은 더 많은 인라이닝을 가능하게하고 코드 크기를 증가 시키지만 짧은 memcpy, strlen 및 memset에 의존하는 코드의 성능을 향상시킬 수 있습니다.

GCC에는 __attribute__((no-inline-all-stringops)) void foo() { ... } 처럼 이것을 제어하는 ​​데 분명히 사용할 수있는 함수 별 특성 이 있지만이 함수를 사용하지 않았습니다. (인라인의 반대입니다. 인라인을 의미 하지는 않습니다 . 4 바이트 정렬이 알려진 경우 인라인에만 돌아갑니다.)

gcc의 인라인 strlen 전략은 16 바이트 정렬을 이용하지 못하고 x86-64의 경우 꽤 나쁘다.

소문자의 경우가 매우 일반적이지 않은 한, 4 바이트 덩어리를 1 개하고, 정렬 한 8 바이트 덩어리는 4 바이트의 약 2 배가됩니다.

그리고 4 바이트 전략은 0 바이트를 포함하는 dword 내에서 바이트를 찾는 데 필요한 것보다 훨씬 느린 정리를합니다. 이것은 상위 비트가 설정된 바이트를 찾음으로써이를 감지하므로 다른 비트를 마스크하여 bsf (비트 스캔 앞으로)를 사용해야합니다. 이는 최신 CPU (Intel 및 Ryzen)에서 3 사이클 대기 시간을가집니다. 또는 컴파일러는 rep bsf 를 사용할 수 있으므로 AMD에서보다 효율적으로 BMI1을 지원하는 CPU에서 tzcnt 실행됩니다. bsftzcnt 는 0이 아닌 입력에 대해 동일한 결과를 제공합니다.

GCC의 4 바이트 루프는 비트 스캔 (bitcan)을 이용하지 않고 순수 C 나 타겟 독립적 로직으로 컴파일 된 것처럼 보입니다. gcc는 BMI1을 사용하여 x86 용으로 컴파일 할 때 ANDn을 사용하지만 바이트 당 사이클 수가 4 바이트보다 작습니다.

SSE2 pcmpeqb + bsf 는 짧은 입력과 긴 입력 모두에 훨씬 좋습니다 . x86-64는 SSE2를 사용할 수 있고 x86-64 System V는 alignof(maxalign_t) = 16 하므로 calloc 은 항상 16 바이트 이상의 포인터를 반환합니다.

성능을 테스트하기 위해 strlen 블록 대신에 썼습니다.

예상대로 Skylake가 4 바이트가 아닌 16 바이트로 4 배 빠릅니다.

(원본 소스를 -O3 과 함께 asm으로 컴파일 한 다음 -O3 을 편집하여 strlen 인라인 확장을 위해이 전략을 사용하여 어떤 성능을 가져 왔는지 확인했습니다. 또한 C 소스 내에서 asm을 asm으로 이식했으며 Godbolt에서 해당 버전을 참조하십시오 . )

    # at this point gcc has `s` in RDX, `i` in ECX

    pxor       %xmm0, %xmm0         # zeroed vector to compare against
    .p2align 4
.Lstrlen16:                         # do {
#ifdef __AVX__
    vpcmpeqb   (%rdx), %xmm0, %xmm1
#else
    movdqa     (%rdx), %xmm1
    pcmpeqb    %xmm0, %xmm1           # xmm1 = -1 where there was a 0 in memory
#endif

    add         $16, %rdx             # ptr++
    pmovmskb  %xmm1, %eax             # extract high bit of each byte to a 16-bit mask
    test       %eax, %eax
    jz        .Lstrlen16            # }while(mask==0);
    # RDX points at the 16-byte chunk *after* the one containing the terminator
    # EAX = bit-mask of the 0 bytes, and is known to be non-zero
    bsf        %eax, %eax           # EAX = bit-index of the lowest set bit

    movb       $'A', -16(%rdx, %rax)

strlen 정리의 일부를 저장소 주소 지정 모드에 최적화했음을 유의하십시오. -16 변위를 사용하여 오버 슛을 수정하고, 실제로 길이를 계산하지 않고 문자열의 끝을 찾은 다음 GCC처럼 색인을 생성합니다 4-byte-at-a-time 루프를 인라이닝 한 후에 수행합니다.

실제 문자열 길이 (끝에 대한 포인터 대신)를 얻으려면 rdx-start를 뺀 다음 rax-16 을 추가합니다 (LEA를 사용하여 2 개의 레지스터 + 상수를 추가 할 수도 있지만 3 구성 요소 LEA는 지연 시간이 더 길 것입니다).

AVX로 제로 레지스터를 손상시키지 않으면 서 하나의 명령으로 load + compare를 할 수 있습니다. 전체 루프는 5에서 4 uops입니다 (테스트 / jz 매크로 - 퓨즈가 인텔과 AMD 모두에서 하나의 uop로됩니다.) vpcmpeqb 인덱싱되지 않습니다 메모리 소스는 전체 파이프 라인을 통해 마이크로 융합을 유지할 수 있기 때문에 프론트 엔드에 대해 하나의 융합 된 도메인 만 사용할 수 있습니다.

(128 비트 AVX와 SSE를 함께 사용하면 Haswell에서도 스톨이 발생하지 않는다는 것을 기억하십시오. 다른 명령을 AVX로 변경하는 것에 신경 쓰지 않고, AVX 루프 본문에서 pxor 가 실제로 데스크탑에서 vpxor 보다 약간 더 나은 경우 약간의 효과가있는 것으로 보였습니다. 다소 반복적 인 것처럼 보였지만 코드 크기 차이가 없으므로 얼라인먼트 차이가 없으므로 이상합니다. .)

pmovmskb 는 single-uop 명령입니다. Intel 및 Ryzen에는 3 사이클 대기 시간이 있습니다 (불도저 제품군에서는 더 나쁩니다). 짧은 문자열의 경우 SIMD 유닛을 통과하여 다시 정수로 이동하는 것은 입력 메모리 바이트에서 준비중인 저장소 주소까지 대기 시간의 중요한 경로 종속성 체인에서 중요한 부분입니다. 그러나 SIMD만이 정수를 비교하므로 스칼라는 더 많은 작업을해야합니다.

매우 작은 문자열의 경우 (0에서 3 바이트까지) 순수한 스칼라 (특히 Bulldozer 계열)를 사용하여이 경우 약간 낮은 대기 시간을 달성 할 수 있지만 0에서 15 바이트의 모든 문자열은 동일한 분기 경로 (루프 분기를 수행하지 않음)는 대부분의 짧은 문자열 사용 사례에 매우 유용합니다 .

15 바이트까지의 모든 문자열을 매우 잘 처리하는 것은 좋은 선택입니다. 우리는 16 바이트 정렬을 알고 있습니다. 더 예측 가능한 분기가 매우 좋습니다. (또한 루프 할 때 pmovmskb 대기 시간은 분기 오류 예측이 루프에서 벗어나는 것을 감지 할 수있는 속도에만 영향을 미치며 분기 예측 + 추측 실행은 각 반복에서 독립적 인 pmovmskb의 대기 시간을 숨 깁니다.

더 긴 문자열이 일반화 될 것으로 예상했다면 조금 풀었지만 그 시점에서 런타임에 사용 가능하다면 AVX2에 디스패치 할 수 있도록 libc 함수를 호출해야합니다. 하나 이상의 벡터로 풀면 정리가 복잡해지며 간단한 경우가 아플 수 있습니다.

내 컴퓨터에서 i7-6700k Skylake 4.2GHz max turbo (및 energy_performance_preference = performance)에서 gcc8.2를 사용하여 아치 리눅스에서 내 CPU 클럭 속도가 memset 동안 램핑 업하기 때문에 다소 일관된 벤치 마크 타이밍을 얻습니다. 하지만 항상 터보를 최대한 활용할 수있는 것은 아닙니다. Skylake의 hw 전원 관리는 메모리가 부족할 때 다운 클럭합니다. perf stat 따르면이 기능을 실행하여 표준 출력을 평균화하고 표준보기에서 perf 요약을 볼 때 일반적으로 4.0GHz 부근에서 정상적으로 나타납니다.

perf stat -r 100 ./a.out | awk '{sum+= $1}  END{print sum/100;}'

나는 asm을 GNU C inline-asm 문으로 복사 하는 작업을 마쳤으므로 코드를 Godbolt 컴파일러 탐색기에 넣을 수있었습니다 .

큰 문자열의 경우, 질문과 길이가 같습니다 : ~ 4GHz Skylake의 시간

  • ~ 62100 clock_t 시간 단위 : -O1 rep scas : ( clock() 은 다소 쓸모가 없지만 변경하지 않았습니다.)
  • ~ 15900 clock_t 시간 단위 : -O3 gcc 4 바이트 루프 전략 : 평균 실행 횟수 = 100. (또는 아마도 ~ 15800과 -march=native for andn )
  • ~ 1880 clock_t 시간 단위 : - AVX2를 사용하는 glibc strlen 함수 호출을 사용하는 -O3
  • ~ 3190 clock_t time units : gcc가 인라인 할 수있는 인라인 asm을 직접 작성한 (AVX1 128 비트 벡터, 4 uop 루프).
  • ~ 3230 clock_t 시간 단위 : gcc가 인라인 할 수있는 손으로 쓴 인라인 asm (SSE2 5 uop 루프).

특수 문자열을 사용할 필요가 없기 때문에 필자의 손으로 작성한 asm은 짧은 문자열에도 매우 적합해야합니다. 알려진 정렬은 strlen에 매우 유용하며 libc는이를 활용할 수 없습니다.

큰 문자열이 드문 것으로 예상되면 libc보다 1.7 배 느립니다. 1M 바이트의 길이는 내 CPU에서 L2 (256k) 또는 L1d 캐시 (32k)에서 뜨겁지 않을 것임을 의미하므로 L3 캐시에서 병목 현상이 발생하더라도 libc 버전이 더 빠릅니다. (아마도 언 롤링 루프와 256 비트 벡터가 바이트 당 uops만큼 ROB를 방해하지 않으므로 OOO 임원은 특히 페이지 경계에서 더 먼 메모리 병렬 처리를 볼 수 있습니다.)

그러나 L3 캐시 대역폭은 아마도 4-uop 버전이 1 클록 당 1 반복으로 실행되는 것을 막는 병목 현상이므로 병목 현상을 줄이기 위해 AVX의 이점을 덜 보게됩니다. L1d 캐시의 데이터가 뜨거워지면 1 회 반복 당 1.25 사이클이 발생합니다.

그러나 좋은 AVX2 구현은 vpminub 를 사용하여 사이클 당 최대 64 바이트 (2x 32 바이트로드)를 vpminubvpminub 0을 확인하기 전에 쌍을 결합하고 vpminub 위치로 되돌아갑니다. 이 라이브러리와 libc 사이의 간격은 ~ 2k ~ ~ 30kiB 정도의 크기로 넓어 지므로 L1d에서 뜨거워집니다.

길이가 1000 인 일부 읽기 전용 테스트는 glibc strlen 이 L1d 캐시의 중간 크기 문자열에 대한 내 루프보다 실제로 약 4 배 빠르다는 것을 나타냅니다 . 이는 AVX2가 큰 풀린 루프까지 올라갈만큼 충분히 크지 만 여전히 L1d 캐시에 쉽게 맞습니다. (읽기 전용은 저장 전달을 피하기 때문에 많은 반복을 할 수 있습니다)

문자열이 크다면 strlen 을 필요로하지 않고 명시 적 길이의 문자열을 사용해야하므로 단순한 루프를 인라이닝하는 것이 실제로 짧은 문자열에 적합하고 매체에 대한 총 쓰레기가 아니라면 합리적인 전략처럼 보입니다 (300 바이트와 같은)와 매우 긴 (> 캐시 크기) 문자열이 있습니다.

이 작은 문자열 벤치마킹 :

예상했던 결과를 얻으려고 몇 가지 기이하게 만났습니다.

모든 반복 전에 문자열을 자르기 위해 s[31] = 0 을 시도했습니다 (짧은 일정 길이 허용). 하지만 SSE2 버전은 GCC 버전과 거의 같은 속도였습니다. 스토어 전달 포장 마차가 병목 현상이었습니다! 더 많은로드로 이어지는 바이트 저장소는 store-forwarding이 저장소 버퍼의 바이트를 L1d 캐시의 바이트와 병합하는 느린 경로를 사용하도록 만듭니다. 이 여분의 대기 시간은 문자열의 마지막 4 바이트 또는 16 바이트 청크를 통해 루프가 실행되는 지연 체인의 일부로 다음 반복의 저장소 인덱스를 계산합니다.

GCC의 느린 4 바이트 코드는 대기 시간의 그늘에서 이전 4 바이트 청크를 처리하여 계속 유지할 수 있습니다. (Out-of-order 실행은 환상적입니다. 느린 코드는 때로는 프로그램의 전체 속도에 영향을주지 않습니다.)

나는 결국 읽기 전용 버전을 만들고 inline asm을 사용하여 컴파일러가 strlen 을 루프 밖으로 strlen 올리는 것을 strlen 으로써이를 해결했다.

그러나 저장소 전달은 16 바이트로드를 사용할 때 잠재적 인 문제입니다. 다른 C 변수가 배열 끝을 지나서 저장되면 좁은 저장소보다 배열의 끝을 멀리로드하기 때문에 SF 멈춤이 발생할 수 있습니다. 최근에 복사 된 데이터의 경우 16 바이트 또는 더 많은 정렬 된 저장소로 복사 한 것이 좋지만 작은 사본의 경우 glibc memcpy는 개체의 시작과 끝에서 전체 개체를 덮는 2 배의 중복되는로드를 수행합니다. 둘 다 저장하고 다시 겹쳐서 memmove src를 처리하면 dst 케이스가 무료로 겹칩니다. 따라서 memcpyied 된 짧은 문자열의 두 번째 16 바이트 또는 8 바이트 청크는 마지막 청크를 읽는 SF 실속을 줄 수 있습니다. (출력에 대한 데이터 종속성이있는 것)

그냥 천천히 실행하면 준비가 끝나기 전에 끝나지 않으므로 일반적으로 좋지 않으므로 여기에는 훌륭한 해결책이 없습니다. 대부분 의 경우 방금 작성한 버퍼를 strlen하지 않을 것이라고 생각합니다. 일반적으로 독서 strlen 는 입력을 strlen 으로 처리하므로 상점 포워딩은 문제가되지 않습니다 . 뭔가 다른 사람이 썼다면, 효율적인 코드는 길이를 버려서 다시 계산할 필요가있는 함수를 호출하지 않았을 것입니다.

내가 완전히 알아 내지 못한 다른 기괴함 :

코드 정렬은 읽기 전용, 크기 = 1000 ( s[1000] = 0; )에 대해 2의 차이를 만듭니다. 그러나 가장 안쪽의 asm 루프 자체는 .p2align 4 또는 .p2align 5 와 정렬됩니다. 루프 정렬을 늘리면 속도가 2 배 느려질 수 있습니다!

# slow version, with *no* extra HIDE_ALIGNMENT function call before the loop.
# using my hand-written asm, AVX version.
  i<1280000 read-only at strlen(s)=1000 so strlen time dominates the total runtime (not startup overhead)
  .p2align 5 in the asm inner loop. (32-byte code alignment with NOP padding)

gcc -DUSE_ASM -DREAD_ONLY -DHIDE_ALIGNMENT -march=native -O3 -g strlen-microbench.c &&
 time taskset -c 3 perf stat -etask-clock,context-switches,cpu-migrations,page-faults,cycles,branches,branch-misses,instructions,uops_issued.any,uops_executed.thread -r 100 ./a.out |
 awk '{sum+= $1}  END{print sum/100;}'

 Performance counter stats for './a.out' (100 runs):

             40.92 msec task-clock                #    0.996 CPUs utilized            ( +-  0.20% )
                 2      context-switches          #    0.052 K/sec                    ( +-  3.31% )
                 0      cpu-migrations            #    0.000 K/sec                  
               313      page-faults               #    0.008 M/sec                    ( +-  0.05% )
       168,103,223      cycles                    #    4.108 GHz                      ( +-  0.20% )
        82,293,840      branches                  # 2011.269 M/sec                    ( +-  0.00% )
         1,845,647      branch-misses             #    2.24% of all branches          ( +-  0.74% )
       412,769,788      instructions              #    2.46  insn per cycle           ( +-  0.00% )
       466,515,986      uops_issued.any           # 11401.694 M/sec                   ( +-  0.22% )
       487,011,558      uops_executed.thread      # 11902.607 M/sec                   ( +-  0.13% )

         0.0410624 +- 0.0000837 seconds time elapsed  ( +-  0.20% )

40326.5   (clock_t)

real    0m4.301s
user    0m4.050s
sys     0m0.224s

브랜치 (branch)는 확실히 0이 아니고, 거의 정확히 0이된다. 그리고 발행 된 uops는 빠른 버전보다 훨씬 높습니다. 즉, 분기 오류가 발생할 때마다 오랜 시간 잘못된 경로를 추측 할 수 있습니다.

아마 안쪽과 바깥 쪽 루프 브랜치는 서로 별명을 짓고 있지 않을 수도 있습니다.

인스트럭션 수는 거의 동일하며, 내부 루프 앞에있는 외부 루프의 일부 NOP 만 다릅니다. 그러나 IPC는 크게 다르지 않습니다. 문제없이 빠른 버전은 전체 프로그램에 대해 평균 4.82 개의 명령을 실행합니다. (대부분은 가장 안쪽에있는 루프에서 5 개 명령을 실행합니다. 테스트 / jz 덕택에 2 개 명령어가 1 개로 통합됩니다.) 그리고 uops_executed는 uops_issued보다 훨씬 높습니다. 즉 마이크로 융합을 의미합니다. 프런트 엔드 병목 현상을 통해 더 많은 일자리를 얻을 수 있습니다.

fast version, same read-only strlen(s)=1000 repeated 1280000 times

gcc -DUSE_ASM -DREAD_ONLY -UHIDE_ALIGNMENT -march=native -O3 -g strlen-microbench.c &&
 time taskset -c 3 perf stat -etask-clock,context-switches,cpu-migrations,page-faults,cycles,branches,branch-misses,instructions,uops_issued.any,uops_executed.thread -r 100 ./a.out |
 awk '{sum+= $1}  END{print sum/100;}' 

 Performance counter stats for './a.out' (100 runs):

             21.06 msec task-clock                #    0.994 CPUs utilized            ( +-  0.10% )
                 1      context-switches          #    0.056 K/sec                    ( +-  5.30% )
                 0      cpu-migrations            #    0.000 K/sec                  
               313      page-faults               #    0.015 M/sec                    ( +-  0.04% )
        86,239,943      cycles                    #    4.094 GHz                      ( +-  0.02% )
        82,285,261      branches                  # 3906.682 M/sec                    ( +-  0.00% )
            17,645      branch-misses             #    0.02% of all branches          ( +-  0.15% )
       415,286,425      instructions              #    4.82  insn per cycle           ( +-  0.00% )
       335,057,379      uops_issued.any           # 15907.619 M/sec                   ( +-  0.00% )
       409,255,762      uops_executed.thread      # 19430.358 M/sec                   ( +-  0.00% )

         0.0211944 +- 0.0000221 seconds time elapsed  ( +-  0.10% )

20504  (clock_t)

real    0m2.309s
user    0m2.085s
sys     0m0.203s

제 생각에 그것은 분기 예측 일 뿐이며 다른 프런트 엔드 문제는 아닙니다. 테스트 / 분기 명령은 매크로 융합을 방지하는 경계를 넘어 분할되지 않습니다.

.p2align 5.p2align 4 변경하면 다음과 같이 .p2align 5 . -UHIDE_ALIGNMENT 가 느려집니다.

이 Godbolt 바이너리 링크 는 Arch Linux에서 gcc8.2.1과 동일한 패딩을 재현합니다. 두 경우 모두 : 2x 11 바이트 nopw + 빠른 케이스의 외부 루프 안의 3 바이트 nop . 그것은 또한 내가 로컬에서 사용했던 정확한 소스를 가지고 있습니다.

짧은 strlen 읽기 전용 마이크로 벤치 마크 :

선택한 항목으로 테스트하여 분기 예측 오류 또는 매장 전달 문제가 발생하지 않도록하고 의미있는 데이터를 얻기에 충분한 반복을 반복하여 동일한 짧은 길이를 반복적으로 테스트 할 수 있습니다.

strlen=33 이므로 종결자가 세 번째 16 바이트 벡터의 시작 부분에 있습니다. (내 버전을 4 바이트 버전과 비교하여 가능한 한 나쁘게 만듭니다.) -DREAD_ONLYi<1280000 을 외부 루프 반복 루프로 사용합니다.

  • 1933 clock_t : my asm : 훌륭하고 일관성있는 최상의 시간 (시끄 -DHIDE_ALIGNMENT 않고 평균을 다시 실행할 때 주변에서 튀는 것). 더 긴 strlen과 달리 -DHIDE_ALIGNMENT 있는 /없는. 훨씬 더 짧은 패턴으로 루프 분기를 훨씬 쉽게 예측할 수 있습니다. (strlen = 33, 1000이 아님).
  • 3220 clock_t : gcc -O3 strlen . ( -DHIDE_ALIGNMENT )
  • 6100 clock_t : gcc -O3 4 바이트 루프
  • 37200 clock_t : gcc -O1 repz scasb

따라서 짧은 문자열의 경우, 간단한 인라인 루프 PLT (call + jmp [mem] )를 거친 다음 strlen 라이브러리 함수 호출을 수행 한 다음 정렬에 의존 할 수없는 strlen의 시작 오버 헤드를 실행합니다.

strlen(s)=33 모든 버전에서 0.05 %와 같이 무시할 수있는 분기 오류 예측이있었습니다. repz scasb 버전은 0.46 % 였지만 전체 분기 수가 적습니다. 올바르게 예측 된 분기를 여러 개 배치하는 내부 루프가 없습니다.

분기 예측기와 코드 캐시가 뜨겁기 때문에 repz scasb 는 glibc strlen 을 33 바이트 문자열로 호출하는 것보다 10 배 이상 더 나쁩니다. strlen 이 코드 캐시와 스톨에서 실패하거나 놓칠 수있는 실제 사용 사례에서는 그다지 좋지 않지만 직선 repz scasb 는 그렇지 않습니다. 그러나 10 배는 거대하며, 이는 매우 짧은 문자열입니다.





glibc