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

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

---

나는 어떤 이유로 glibc의 strlen기능 을 벤치마킹하고 싶었고 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의 컴파일러 탐색기에서 코드를 테스트 하면 다음 설명이 제공됩니다.

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

코드를 반복적으로 벤치마킹하면 한 실행에서 다른 실행으로 상당한 차이가 있지만 반복 횟수를 늘리면 다음을 확인할 수 있습니다.

• -O1코드는 훨씬 느린 C 라이브러리 구현보다 : 32240대3090
• -O2코드는 빠르게보다 -O1여전히 실질적으로 느리게 C ibrary 코드보다 : 8570대 3090.

이 동작은 gcc및 glibc. OS / X와 clangApple의 Libc 에 대한 동일한 테스트 에서는 큰 차이가 나타나지 않습니다. 이는 Godbolt 가 모든 최적화 수준에서 clangC 라이브러리 strlen에 대한 호출을 생성 한다는 것을 보여 주듯이 놀라운 일이 아닙니다 .

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

이 벤치 마크를 개선하고 다양한 문자열 길이를 테스트했습니다. Intel (R) Core (TM) i3-2100 CPU @ 3.10GHz에서 실행되는 gcc (Debian 4.7.2-5) 4.7.2를 사용하는 Linux의 벤치 마크에서 생성 된 인라인 코드는 다음 -O1과 같이 항상 느립니다. 적당히 긴 문자열 의 경우 10 의 요소에 -O2해당 하는 반면, 매우 짧은 문자열의 경우 libc strlen보다 약간 빠르며 긴 문자열의 경우 절반 정도 빠릅니다. 이 데이터에서 GNU C 라이브러리 버전은 strlen적어도 내 특정 하드웨어에서 대부분의 문자열 길이에 대해 매우 효율적입니다. 또한 캐싱은 벤치 마크 측정에 큰 영향을 미칩니다.

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

#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
평균 길이 0-> 평균 시간 : 14.000ns / byte, 14.000ns / call
평균 길이 4-> 평균 시간 : 2.364ns / byte, 13.000ns / call
평균 길이 10-> 평균 시간 : 1.238ns / byte, 13.000ns / call
평균 길이 50-> 평균 시간 : 0.317ns / byte, 16.000ns / call
평균 길이 100-> 평균 시간 : 0.169ns / byte, 17.000ns / call
평균 길이 500-> 평균 시간 : 0.074ns / 바이트, 37.000ns / 호출
평균 길이 1000-> 평균 시간 : 0.068ns / 바이트, 68.000ns / 호출
평균 길이 5000-> 평균 시간 : 0.064ns / 바이트, 318.000ns / 호출
평균 길이 10000-> 평균 시간 : 0.062ns / byte, 622.000ns / call
평균 길이 1000000-> 평균 시간 : 0.062ns / byte, 62000.000ns / call
chqrlie> gcc -std = c99 -O1 benchstrlen.c && ./a.out
평균 길이 0-> 평균 시간 : 20.000ns / byte, 20.000ns / call
평균 길이 4-> 평균 시간 : 3.818ns / byte, 21.000ns / call
평균 길이 10-> 평균 시간 : 2.190ns / 바이트, 23.000ns / 호출
평균 길이 50-> 평균 시간 : 0.990ns / byte, 50.000ns / call
평균 길이 100-> 평균 시간 : 0.816ns / byte, 82.000ns / call
평균 길이 500-> 평균 시간 : 0.679ns / byte, 340.000ns / call
평균 길이 1000-> 평균 시간 : 0.664ns / byte, 664.000ns / call
평균 길이 5000-> 평균 시간 : 0.651ns / byte, 3254.000ns / call
평균 길이 10000-> 평균 시간 : 0.649ns / byte, 6491.000ns / call
평균 길이 1000000-> 평균 시간 : 0.648ns / byte, 648000.000ns / call
chqrlie> gcc -std = c99 -O2 benchstrlen.c && ./a.out
평균 길이 0-> 평균 시간 : 10.000 ns / byte, 10.000 ns / call
평균 길이 4-> 평균 시간 : 2.000ns / byte, 11.000ns / call
평균 길이 10-> 평균 시간 : 1.048ns / byte, 11.000ns / call
평균 길이 50-> 평균 시간 : 0.337ns / byte, 17.000ns / call
평균 길이 100-> 평균 시간 : 0.299ns / byte, 30.000ns / call
평균 길이 500-> 평균 시간 : 0.202ns / byte, 101.000ns / call
평균 길이 1000-> 평균 시간 : 0.188ns / 바이트, 188.000ns / 호출
평균 길이 5000-> 평균 시간 : 0.174ns / 바이트, 868.000ns / 호출
평균 길이 10000-> 평균 시간 : 0.172ns / byte, 1716.000ns / call
평균 길이 1000000-> 평균 시간 : 0.172ns / byte, 172000.000ns / call

---

GCC의 인라인 strlen패턴은 훨씬 느린가 SSE2와 함께 무엇을 할 수 있는지보다 pcmpeqb/ pmovmskb과 bsf에서 16 바이트 정렬 주어진calloc . 이 "최적화"는 실제로 비관적입니다.

16 바이트 정렬을 활용하는 간단한 손으로 쓴 루프는 -O3큰 버퍼의 경우 gcc 인라인 보다 5 배 빠르며 짧은 문자열의 경우 ~ 2 배 빠릅니다. (짧은 문자열에 대해 strlen을 호출하는 것보다 빠릅니다). 가능한 경우 gcc가 -O2 / -O3에서 인라인해야하는 내용을 제안하기 위해 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=88809 에 주석을 추가했습니다 . (시작할 4 바이트 정렬 만 알고있는 경우 최대 16 바이트까지 증가 할 것을 제안합니다.)

---

gcc가 버퍼에 대해 4 바이트 정렬이 있음을 알게되면 (에서 보장 calloc) strlenGP 정수 레지스터 ( -O2이상)를 사용하여 한 번에 4 바이트 스칼라 비트 핵 으로 인라인하도록 선택합니다 .

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

에서 -O1gcc는 항상 (알려진 정렬이 없더라도) 인라인 strlen을 선택합니다 repnz scasb. 이는 매우 느립니다 (최신 Intel CPU에서 클럭주기 당 약 1 바이트). "빠른 문자열"은 rep stos및 에만 적용되며 / 지침에는 적용 rep movs되지 않습니다 . 마이크로 코드는 한 번에 1 바이트에 불과하지만 여전히 약간의 시작 오버 헤드가 있습니다. ( https://agner.org/optimize/ )repzrepnz

( 예를 들어 s를 저장 / 다시로드하여 컴파일러에서 포인터를 "숨겨서"테스트 할 수 있습니다 volatile void *tmp. gcc는에서 다시 읽은 포인터 값에 대해 0으로 가정하여 volatile정렬 정보를 파괴해야합니다.)

---

GCC에는 일반적으로 인라인 문자열 작업에 대한 vs. vs. 와 같은 몇 가지 x86 튜닝 옵션이 있습니다 (strlen뿐만 아니라 rep 또는 루프로 수행 할 수있는 또 다른 주요 옵션). 나는 이것이 여기에서 어떤 영향을 미치는지 확인하지 않았습니다.-mstringop-strategy=libcallunrolled_looprep_bytememcmp

다른 옵션에 대한 문서도 현재 동작을 설명합니다. 정렬되지 않은 포인터에서 원하는 경우에도이 인라인 (정렬 처리를위한 추가 코드 포함)을 얻을 수 있습니다. (이것은 기계가 할 수있는 것에 비해 인라인 루프가 쓰레기가 아닌 대상에서 특히 작은 문자열의 경우 실제 성능 승리였습니다.)

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

GCC는 또한 이것을 제어하기 위해 분명히 사용할 수있는 기능별 속성 을 __attribute__((no-inline-all-stringops)) void foo() { ... }가지고 있지만, 나는 그것을 가지고 놀지 않았습니다. (즉, 인라인 모두의 반대입니다. 그것은 하지 않습니다 평균 인라인 것도, 그냥 단지 4 바이트 정렬이 알고있을 때 인라인으로 돌아 간다.)

---

gcc의 두 인라인 strlen전략 은 모두 16 바이트 정렬을 활용하지 못하며 x86-64에 매우 좋지 않습니다.

작은 문자열 케이스가 매우 일반적이지 않는 한, 4 바이트 청크 하나를 수행하면 정렬 된 8 바이트 청크가 4 바이트보다 약 두 배 빠릅니다.

그리고 4 바이트 전략은 0 바이트를 포함하는 dword 내에서 바이트를 찾는 데 필요한 것보다 훨씬 느린 정리를 제공합니다. 높은 비트 세트가있는 바이트를 찾아이를 감지하므로 다른 비트를 마스킹하고 bsf(비트 스캔 포워드)를 사용해야 합니다. 최신 CPU (Intel 및 Ryzen)에서 3주기 지연이 있습니다. 또는 컴파일러는 AMD에서 더 효율적인 BMI1을 지원하는 CPU에서 rep bsf실행되도록 사용할 수 있습니다 tzcnt. bsf및 tzcnt비 - 제로 입력에 대해 동일한 결과를 제공한다.

GCC의 4 바이트 루프는 순수 C 또는 일부 타겟 독립적 논리에서 컴파일 된 것처럼 보이지만 bitscan을 활용하지 않습니다. gcc는 andnBMI1로 x86 용으로 컴파일 할 때이를 최적화하는 데 사용 하지만 여전히 사이클 당 4 바이트 미만입니다.

SSE2 pcmpeqb+ bsf는 짧은 입력과 긴 입력 모두에 훨씬 좋습니다 . SSE2이 가능하고, x86-64에 시스템 V는있다 x86-64를 보장 것을 alignof(maxalign_t) = 16때문에 calloc항상 적어도 16 바이트 정렬 된 포인터를 반환합니다.

---

strlen성능을 테스트 하기 위해 블록을 대체했습니다.

예상대로 Skylake에서는 한 번에 4 바이트가 아닌 16 바이트로 약 4 배 더 빠릅니다.

(원래 소스를 asm로 컴파일 한 -O3다음 asm을 편집하여 인라인 확장을위한이 전략의 성능을 확인 strlen했습니다. 또한 C 소스 내부의 인라인 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 바이트 루프를 인라인합니다.

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

AVX와 제로화 레지스터를 파괴하지 않고 하나의 명령에 비교 + 부하가 전체 루프 인텔 AMD 모두 하나 UOP 아래로 5 (시험 / JZ 매크로 퓨즈에서, 단지 4 개의 마이크로 연산 인 있도록. vpcmpeqb로 인덱싱되지 않은 메모리 -소스는 전체 파이프 라인을 통해 마이크로 융합 상태를 유지할 수 있으므로 프런트 엔드에 대해 하나의 융합 도메인 uop입니다.)

(128 비트 AVX를 SSE와 혼합 해도 Haswell에서도 중단이 발생 하지 않습니다 . 처음부터 깔끔한 상태에있는 한. 그래서 다른 명령어를 AVX로 변경하는 것에 대해 신경 쓰지 않았습니다. AVX 루프 바디의 경우 pxor실제로 내 데스크톱 보다 약간 더 나은 약간의 효과가있는 vpxor것처럼 보였습니다. 다소 반복 할 수있는 것처럼 보였지만 코드 크기 차이가 없으므로 정렬 차이가 없기 때문에 이상합니다.)

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

매우 작은 문자열 케이스 (예 : 0 ~ 3 바이트)의 경우 순수 스칼라 (특히 Bulldozer 제품군)를 사용하여 해당 케이스에 대해 약간 더 낮은 지연 시간을 달성 할 수 있지만 0 ~ 15 바이트의 모든 문자열을 사용하면 동일한 분기 경로 (루프 분기를 사용하지 않음)는 대부분의 짧은 문자열 사용 사례에 매우 좋습니다 .

16 바이트 정렬이 있다는 것을 알고있을 때 최대 15 바이트의 모든 문자열에 대해 매우 좋은 것은 좋은 선택처럼 보입니다. 더 예측 가능한 분기는 매우 좋습니다. (루핑 할 때 pmovmskb지연 시간은 루프에서 벗어나는 분기 예측 오류를 얼마나 빨리 감지 할 수 있는지에 만 영향을줍니다. 분기 예측 + 추측 실행은 각 반복에서 독립적 인 pmovmskb의 지연 시간을 숨 깁니다.

더 긴 문자열이 일반적으로 사용되기를 기대했다면 조금 풀 수 있지만 그 시점에서 libc 함수를 호출하여 런타임에 사용 가능한 경우 AVX2로 전달할 수 있습니다. 두 개 이상의 벡터로 펼치면 정리가 복잡해져 단순한 케이스가 손상됩니다.

---

내 컴퓨터 i7-6700k Skylake, 4.2GHz 최대 터보 (및 energy_performance_preference= 성능)에서 Arch Linux의 gcc8.2를 사용하면 memset 중에 CPU 클럭 속도가 증가하기 때문에 다소 일관된 벤치 마크 타이밍을 얻습니다. 하지만 항상 최대 터보는 아닙니다. Skylake의 hw 전원 관리는 메모리 바인딩시 다운 클럭됩니다. perf statstdout 출력을 평균화하고 stderr에서 성능 요약을보기 위해 이것을 실행할 때 일반적으로 약 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시간 단위 : -O1rep scas : ( clock()조금 구식이지만 변경하지 않았습니다.)
• ~ 15900 clock_t시간 단위 : -O3gcc 4 바이트 루프 전략 : 평균 100 회 실행 =. (와 아니면 ~ 15800 -march=native에 대한 andn)
• ~ 1880 clock_t시간 단위 : -O3glibc strlen함수 호출 사용, AVX2 사용
• ~ 3190 clock_t시간 단위 : (AVX1 128 비트 벡터, 4 uop 루프) gcc가 인라인 할 수 있거나 인라인해야하는 손으로 쓴 인라인 asm.
• ~ 3230 clock_t시간 단위 : (SSE2 5 uop 루프) gcc가 인라인 할 수 있거나 인라인해야하는 손으로 쓴 인라인 asm.

내 손으로 쓴 asm은 특별히 분기 할 필요가 없기 때문에 짧은 문자열에도 매우 좋습니다. 알려진 정렬은 strlen에 매우 유용하며 libc는이를 활용할 수 없습니다.

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

그러나 L3 캐시 대역폭은 4-uop 버전이 클록 당 1 회 반복 실행되는 것을 막는 병목 현상 일 수 있으므로 AVX의 이점이 적어 루프에서 uop를 절약 할 수 있습니다. L1d 캐시에서 핫 데이터를 사용하면 반복 당 1.25 사이클이 1 회가됩니다.

그러나 좋은 AVX2 구현은 vpminub0을 확인하기 전에 쌍을 결합 하는 데 사용하여 사이클 당 최대 64 바이트 (2x 32 바이트로드)를 읽을 수 있으며 원래 위치로 돌아갑니다. 이것과 libc 사이의 간격은 ~ 2k ~ ~ 30kiB 크기 또는 L1d에서 뜨겁게 유지 될 때 더 넓어집니다.

length = 1000 인 일부 읽기 전용 테스트는 glibc strlen가 L1d 캐시에서 핫한 중간 크기 문자열에 대한 루프보다 실제로 약 4 배 빠르다는 것을 나타냅니다 . 그것은 AVX2가 큰 풀린 루프로 올라갈만큼 충분히 크지 만 여전히 L1d 캐시에 쉽게 맞습니다. (읽기 전용은 상점 전달 중단을 방지하므로 여러 번 반복 할 수 있습니다.)

당신의 캐릭터가 큰 경우에, 당신은 명시 적 길이 문자열을 사용하는 대신에 필요해야 strlen하므로 간단한 루프 여전히 그것이 사실이다로서, 합리적인 전략처럼 보인다 인라인, 모두에서 좋은 매체에 대한 짧은 문자열이 아니라 전체 쓰레기를 ( 300 바이트와 같음) 및 매우 긴 (> 캐시 크기) 문자열.

---

다음과 같이 작은 문자열을 벤치마킹합니다.

예상 한 결과를 얻으려고 시도하는 동안 몇 가지 이상한 점이 있습니다.

s[31] = 0매 반복 전에 문자열을 자르 려고 했습니다 (짧은 상수 길이 허용). 하지만 내 SSE2 버전은 GCC 버전과 거의 같은 속도였습니다. 점포 포장 마차가 병목이었습니다! 더 넓은로드가 뒤 따르는 바이트 저장소는 저장소 전달이 저장소 버퍼의 바이트를 L1d 캐시의 바이트와 병합하는 느린 경로를 취하게합니다. 이 추가 대기 시간은 다음 반복에 대한 저장소 인덱스를 계산하기 위해 문자열의 마지막 4 바이트 또는 16 바이트 청크를 통한 루프 전달 dep 체인의 일부입니다.

GCC의 느린 한 번에 4 바이트 코드는 해당 지연 시간의 그림자에서 이전 4 바이트 청크를 처리하여 따라 잡을 수 있습니다. (비 순차적 실행은 매우 환상적입니다. 느린 코드는 때때로 프로그램의 전체 속도에 영향을주지 않습니다.)

나는 결국 읽기 전용 버전을 만들고 인라인 asm을 사용하여 컴파일러 strlen가 루프 에서 벗어나는 것을 막음으로써 그것을 해결했습니다 .

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

준비가되기 전에 끝까지 도달하지 못하도록 느리게 실행하는 것은 일반적으로 좋지 않으므로 여기에는 훌륭한 솔루션이 없습니다. 저는 대부분 의 경우 방금 작성한 버퍼를 훔치지 않을 것이라고 생각합니다 . 일반적으로 strlen읽기만하는 입력으로 이동 하므로 상점 전달 매점은 문제가되지 않습니다 . 다른 것이 방금 작성했다면 효율적인 코드는 길이를 버리지 않았을 것이며 재 계산이 필요한 함수를 호출하지 않았을 것입니다.

---

내가 완전히 알아 내지 못한 다른 이상한 점 :

Code alignment is making a factor of 2 difference for read-only, size=1000 (s[1000] = 0;). But the inner-most asm loop itself is aligned with .p2align 4 or .p2align 5. Increasing the loop alignment can slow it down by a factor of 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

Note branch misses definitely non-zero, vs. almost exactly zero for the fast version. And uops issued is much higher than the fast version: it may be speculating down the wrong path for a long time on each of those branch misses.

Probably the inner and outer loop-branches are aliasing each other, or not.

Instruction count is nearly identical, just different by some NOPs in the outer loop ahead of the inner loop. But IPC is vastly different: without problems, the fast version runs an average of 4.82 instructions per clock for the whole program. (Most of that is in the inner-most loop running 5 instructions per cycle, thanks to a test/jz that macro-fuses 2 instructions into 1 uop.) And note that uops_executed is much higher than uops_issued: that means micro-fusion is working well to get more uops through the front-end bottleneck.

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

I think it's just the branch prediction, not other front-end stuff that's a problem. The test/branch instructions aren't getting split across a boundary that would prevent macro-fusion.

Changing .p2align 5 to .p2align 4 reverses them: -UHIDE_ALIGNMENT becomes slow.

This Godbolt binary link reproduces the same padding I'm seeing with gcc8.2.1 on Arch Linux for both cases: 2x 11-byte nopw + a 3-byte nop inside the outer loop for the fast case. It also has the exact source I was using locally.

---

short strlen read-only micro-benchmarks:

Tested with stuff chosen so it doesn't suffer from branch mispredicts or store-forwarding, and can test the same short length repeatedly for enough iterations to get meaningful data.

strlen=33, so the terminator is near the start of the 3rd 16-byte vector. (Makes my version look as bad as possible vs. the 4-byte version.) -DREAD_ONLY, and i<1280000 as an outer-loop repeat loop.

• 1933 clock_t: my asm: nice and consistent best-case time (not noisy / bouncing around when re-running the average.) Equal perf with/without -DHIDE_ALIGNMENT, unlike for the longer strlen. The loop branch is much more easily predictable with that much shorter pattern. (strlen=33, not 1000).
• 3220 clock_t: gcc -O3 strlen. (-DHIDE_ALIGNMENT)
• 6100 clock_t: gcc -O3 4-byte loop
• 37200 clock_t: gcc -O1 repz scasb

So for short strings, my simple inline loop beats a library function call to strlen that has to go through the PLT (call + jmp [mem]), then run strlen's startup overhead that can't depend on alignment.

There were negligible branch-mispredicts, like 0.05% for all the versions with strlen(s)=33. The repz scasb version had 0.46%, but that's out of fewer total branches. No inner loop to rack up many correctly predicted branches.

With branch predictors and code-cache hot, repz scasb is more than 10x worse than calling glibc strlen for a 33-byte string. It would be less bad in real use cases where strlen could branch miss or even miss in code-cache and stall, but straight-line repz scasb wouldn't. But 10x is huge, and that's for a fairly short string.

참고URL : https://stackoverflow.com/questions/55563598/why-is-this-code-6-5x-slower-with-optimizations-enabled