빈 루프가 C에서 비어 있지 않은 루프보다 느립니다.

빈 루프가 C에서 비어 있지 않은 루프보다 느립니다.

C코드의 행이 얼마나 오래 실행되었는지 알아보려고 하다가 이상한 것을 발견했습니다.

int main (char argc, char * argv[]) {
    time_t begin, end;
    uint64_t i;
    double total_time, free_time;
    int A = 1;
    int B = 1;

    begin = clock();
    for (i = 0; i<(1<<31)-1; i++);
    end = clock();
    free_time = (double)(end-begin)/CLOCKS_PER_SEC;
    printf("%f\n", free_time);

    begin = clock();
    for (i = 0; i<(1<<31)-1; i++) {
        A += B%2;
    }
    end = clock();
    free_time = (double)(end-begin)/CLOCKS_PER_SEC;
    printf("%f\n", free_time);

    return(0);
}

실행 시 다음과 같이 표시됩니다.

5.873425
4.826874

빈 루프는 왜 명령어가 포함된 두 번째 루프보다 더 많은 시간을 사용하는가? 물론 나는 많은 변형을 시도했지만, 매번 빈 루프는 하나의 명령이 포함된 것보다 더 많은 시간이 걸린다.

루프 오더를 교환하고 웜업 코드를 추가해도 문제는 전혀 변하지 않습니다.

코드 블록을 GNU gcc 컴파일러, Linux ubuntu 14.04에서 IDE로 사용하고 있으며 쿼드코어 인텔 i5는 2.3입니다.GHz(단일 코어로 프로그램을 실행해 봤지만 결과는 바뀌지 않습니다).

정수를 합니다.int입력(시스템에서 실행)하면 코드에서 아무것도 판별할 수 없습니다.대신 정의되지 않은 동작을 나타냅니다.

foo.c:5:5: error: first parameter of 'main' (argument count) must be of type 'int'
int main (char argc, char * argv[]) {
    ^
foo.c:13:26: warning: overflow in expression; result is 2147483647 with type 'int' [-Winteger-overflow]
    for (i = 0; i<(1<<31)-1; i++);
                         ^
foo.c:19:26: warning: overflow in expression; result is 2147483647 with type 'int' [-Winteger-overflow]
    for (i = 0; i<(1<<31)-1; i++) {
                         ^

이 문제를 해결합시다.

#include <stdint.h>
#include <stdio.h>
#include <time.h>
#include <limits.h>

int main (int argc, char * argv[]) {
    time_t begin, end;
    uint64_t i;
    double total_time, free_time;
    int A = 1;
    int B = 1;

    begin = clock();
    for (i = 0; i<INT_MAX; i++);
    end = clock();
    free_time = (double)(end-begin)/CLOCKS_PER_SEC;
    printf("%f\n", free_time);

    begin = clock();
    for (i = 0; i<INT_MAX; i++) {
        A += B%2;
    }
    end = clock();
    free_time = (double)(end-begin)/CLOCKS_PER_SEC;
    printf("%f\n", free_time);

    return(0);
}

이제 이 코드의 어셈블리 출력을 보겠습니다.개인적으로 LLVM의 내부 어셈블리는 매우 읽기 쉽기 때문에 이를 보여 드리겠습니다.실행함으로써 생산합니다.

clang -O3 foo.c -S -emit-llvm -std=gnu99

출력의 관련 부분(주기능)은 다음과 같습니다.

define i32 @main(i32 %argc, i8** nocapture readnone %argv) #0 {
  %1 = tail call i64 @"\01_clock"() #3
  %2 = tail call i64 @"\01_clock"() #3
  %3 = sub nsw i64 %2, %1
  %4 = sitofp i64 %3 to double
  %5 = fdiv double %4, 1.000000e+06
  %6 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i64 0, i64 0), double %5) #3
  %7 = tail call i64 @"\01_clock"() #3
  %8 = tail call i64 @"\01_clock"() #3
  %9 = sub nsw i64 %8, %7
  %10 = sitofp i64 %9 to double
  %11 = fdiv double %10, 1.000000e+06
  %12 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i64 0, i64 0), double %11) #3
  ret i32 0
}

에의 콜간에는, 조작은 행해지지 않는 것에 주의해 주세요.clock()어느 경우든.그래서 둘 다 정확히 같은 것으로 컴파일 되어 있습니다.

사실 최신 프로세서는 복잡합니다.실행되는 모든 명령은 복잡하고 흥미로운 방식으로 상호 작용합니다.코드를 게시해줘서 "다른 사람"에게 고마워.

OP와 "that other guy" 둘 다 짧은 루프는 11 사이클이 걸리고 긴 루프는 9 사이클이 걸린다는 것을 알아냈습니다.긴 루프의 경우, 조작이 많아도 9 사이클이면 충분합니다.루프의 스톨이 '', '스톨', '스톨'을 붙이면 됩니다.nop스톨을 회피할 수 있을 정도로 루프가 길어집니다.

코드를 보면 다음과 같은 일이 발생합니다.

0x00000000004005af <+50>:    addq   $0x1,-0x20(%rbp)
0x00000000004005b4 <+55>:    cmpq   $0x7fffffff,-0x20(%rbp)
0x00000000004005bc <+63>:    jb     0x4005af <main+50>

읽습니다.i해 주세요반신해 주세요.addq 한 번 cmpq 후 를 루프합니다.이치노 그 때, 그 때.addq되면 프로세서가 수 없습니다.i(일본어: ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★」

.i는 읽기를 i을 사용법에서는 우리가 에입니다.i, 「어느 쪽인가 하면」이라고 하는 .i , . . . . . . . .cmpqinstruction 스토어에서 .이 에서는 '아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, 아, .i제실로일일어일!그래서 여기에 노점을 도입할 수 있습니다.

'점프addq저장소로 .cmpq어디서 데이터를 얻을 수 있을지 확실하지 않지만, 모두 매우 밀접하게 연결되어 있습니다.그들은 유별나게 친하다. 경우 는 이 에서 이 두 매우 에 이 시점에서 이 방법을 할 수 .i저장 지침에서 읽거나 메모리에서 읽습니다.그리고 메모리에서 읽는데, 저장소가 끝날 때까지 기다려야 하기 때문에 속도가 느립니다. 딱 1개만 .nop프로세서에 충분한 시간을 줍니다.

보통 RAM과 캐시가 있다고 생각합니다.최신 인텔 프로세서에서 읽기 메모리는 (최저 속도부터 고속 속도까지)에서 읽을 수 있습니다.

1. 메모리(RAM)
2. L3 캐시(옵션)
3. L2 캐시
4. L1 캐시
5. L1 캐시에 아직 기록되지 않은 이전 저장소 명령입니다.

짧은 슬로우 루프에서 프로세서가 내부적으로 수행하는 작업은 다음과 같습니다.

1. ★★★★★★★★★를 읽어 주세요.i 에서
2. .i
3. i 에의
4. i 에 .
5. ★★★★★★★★★를 읽어 주세요.i 에서
6. i
7. 작으면 (1)로 분기합니다.

길고 빠른 루프에서는 프로세서는 다음과 같은 기능을 합니다.

1. 많은 재료들.
2. ★★★★★★★★★를 읽어 주세요.i 에서
3. .i
4. 는 '가게' 지시는 '가게' 지시는 '가게' 지시는 '로 됩니다.i 에의
5. ★★★★★★★★★를 읽어 주세요.i 을 터치하지 "store" 전송
6. i
7. 작으면 (1)로 분기합니다.

이 답변은 당신이 이미 그의 답변에서 Sharth의 정의되지 않은 행동에 대한 훌륭한 요점을 이해하고 대처했다고 가정합니다.또, 컴파일러가 코드로 재생할 가능성이 있는 트릭도 지적합니다.컴파일러가 루프 전체를 쓸모없는 것으로 인식하지 않도록 해야 합니다.예를 들어, 반복자 선언 변경volatile uint64_t i;되지 않도록 「루프 삭제」가 방지됩니다.volatile int A;두 번째 루프가 첫 번째 루프보다 더 많은 작업을 수행합니다.그러나 이 모든 것을 실행하더라도 다음과 같은 사실을 발견할 수 있습니다.

프로그램의 후반 코드는 이전 코드보다 더 빨리 실행될 수 있습니다.

clock()라이브러리 기능으로 인해 타이머를 읽은 후 반환하기 전에 ICache Miss가 발생할 수 있습니다.이것에 의해, 최초로 측정된 인터벌에 약간의 시간이 걸립니다(나중의 콜의 경우, 코드는 이미 캐시에 있습니다). 이 이며, 작을 것이다.clock()디스크까지의 페이지 폴트라도 측정할 수 있습니다.랜덤 콘텍스트스위치는 어느 시간 간격에도 추가할 수 있습니다.

더 중요한 것은 i5 CPU가 있다는 것입니다.이 CPU는 다이내믹 클로킹 기능을 갖추고 있습니다.프로그램 실행이 시작되면 CPU가 유휴 상태이기 때문에 클럭 속도는 대부분 낮습니다.프로그램을 실행하는 것만으로 CPU가 아이돌 상태가 되지 않기 때문에 약간의 지연이 있으면 클럭 속도가 빨라집니다.유휴 CPU와 TurboBoosted CPU 클럭 주파수의 비율은 매우 높을 수 있습니다(울트라북의 Haswell i5-4200U에서는 이전 승수가 8이고 후자가 26이므로 부팅 코드가 나중에 실행되는 코드보다 30% 미만입니다.최신 컴퓨터에서는 지연을 구현하기 위한 "교정된" 루프는 끔찍한 아이디어입니다.)

보다 정확한 타이밍을 위해 워밍업 단계(벤치마크 반복 실행 및 첫 번째 결과 포기)를 포함하는 것은 JIT 컴파일러를 사용하는 관리 프레임워크에만 해당되지 않습니다.

최적화 없이 GCC 4.8.2-19ubuntu1을 사용하여 이를 재현할 수 있습니다.

$ ./a.out 
4.780179
3.762356

빈 루프를 다음에 나타냅니다.

0x00000000004005af <+50>:    addq   $0x1,-0x20(%rbp)
0x00000000004005b4 <+55>:    cmpq   $0x7fffffff,-0x20(%rbp)
0x00000000004005bc <+63>:    jb     0x4005af <main+50>

그리고 여기 비어있지 않은 것이 있습니다.

0x000000000040061a <+157>:   mov    -0x24(%rbp),%eax
0x000000000040061d <+160>:   cltd   
0x000000000040061e <+161>:   shr    $0x1f,%edx
0x0000000000400621 <+164>:   add    %edx,%eax
0x0000000000400623 <+166>:   and    $0x1,%eax
0x0000000000400626 <+169>:   sub    %edx,%eax
0x0000000000400628 <+171>:   add    %eax,-0x28(%rbp)
0x000000000040062b <+174>:   addq   $0x1,-0x20(%rbp)
0x0000000000400630 <+179>:   cmpq   $0x7fffffff,-0x20(%rbp)
0x0000000000400638 <+187>:   jb     0x40061a <main+157>

a를 요?nop loop empty: empty:

0x00000000004005af <+50>:    nop
0x00000000004005b0 <+51>:    addq   $0x1,-0x20(%rbp)
0x00000000004005b5 <+56>:    cmpq   $0x7fffffff,-0x20(%rbp)
0x00000000004005bd <+64>:    jb     0x4005af <main+50>

이제 동일한 속도로 작동합니다.

$ ./a.out 
3.846031
3.705035

이것은 얼라인먼트의 중요성을 나타내고 있다고 생각합니다만, 그 방법에 대해서는 구체적으로 말씀드릴 수 없습니다.|

언급URL : https://stackoverflow.com/questions/25068032/empty-loop-is-slower-than-a-non-empty-one-in-c