바쁜 루프는 대기 시간이 중요한 계산

Question

내 코드는 다음 않습니다 속도가 느려집니다 :

1. 일부 장기 실행 강렬한 계산을 수행합니다 (아래라고 쓸모)
2. 작은 대기 시간이 중요한 작업을 수행

대기 시간이 중요한 작업을 실행하는 데 걸리는 시간이 오래 걸리는 계산을 사용하는 경우보다 빠르다는 것을 알게되었습니다. 여기

이 효과를 재현하는 일부 독립 실행 형 C++ 코드 : 1 억 USELESS 세트 -O3로 컴파일 할 때

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

    #define LEN 128 
    #define USELESS 1000000000 
    //#define USELESS 0 

    // Read timestamp counter 
    static inline long long get_cycles() 
    { 
      unsigned low, high; 
      unsigned long long val; 
      asm volatile ("rdtsc" : "=a" (low), "=d" (high)); 
      val = high; 
      val = (val << 32) | low; 
      return val; 
    } 

    // Compute a simple hash 
    static inline uint32_t hash(uint32_t *arr, int n) 
    { 
      uint32_t ret = 0; 
      for(int i = 0; i < n; i++) { 
        ret = (ret + (324723947 + arr[i]))^93485734985; 
      } 
      return ret; 
    } 

    int main() 
    { 
      uint32_t sum = 0;  // For adding dependencies 
      uint32_t arr[LEN];  // We'll compute the hash of this array 

      for(int iter = 0; iter < 3; iter++) { 
        // Create a new array to hash for this iteration 
        for(int i = 0; i < LEN; i++) { 
          arr[i] = (iter + i); 
        } 

        // Do intense computation 
        for(int useless = 0; useless < USELESS; useless++) { 
          sum += (sum + useless) * (sum + useless); 
        } 

        // Do the latency-critical task 
        long long start_cycles = get_cycles() + (sum & 1); 
        sum += hash(arr, LEN); 
        long long end_cycles = get_cycles() + (sum & 1); 

        printf("Iteration %d cycles: %lld\n", iter, end_cycles - start_cycles); 
      } 
    } 

을 세 번 반복은 각각 588, 4184, 536 사이클을했다. USELESS을 0으로 설정하면 컴파일은 각각 394, 358 및 362 사이클이 소요되었습니다.

왜 이것이 (특히 4184주기) 일어날 수 있습니까? 강렬한 계산으로 인해 캐시 미스 또는 분기 오 예측이 의심됩니다. 그러나 강렬한 계산이 없으면 대기 시간이 긴 태스크의 반복 횟수가 매우 빠르기 때문에 차가운 캐시/분기 예측자가 원인이라고 생각하지 않습니다.

Answer 1

대답에 내 투기 코멘트를 이동 :

바쁜 루프가 실행되는 동안, 서버에서 다른 작업은 L1 캐시 아웃 캐시 arr 데이터를 밀고 가능성이 최초의 메모리 액세스 있도록 hash에서 하위 수준 캐시에서 다시로드해야합니다. 계산 루프가 없으면 이런 일이 일어나지 않을 것입니다. arr 초기화를 계산 루프 다음으로 이동하여 효과가 무엇인지 확인할 수 있습니다.