預取示例？

Question

任何人都可以舉一個例子或者鏈接到一個在GCC中使用__builtin_prefetch的例子（或者只是一般的asm指令prefetcht0）來獲得實質性的性能優勢嗎？特別是，我希望該示例符合以下條件：

1. 這是一個簡單的小型自包含示例。
2. 刪除__builtin_prefetch指令會導致性能下降。
3. 用相應的存儲器訪問替換__builtin_prefetch指令會導致性能下降。

也就是說，我想要最短的例子顯示__builtin_prefetch執行優化，沒有它就無法管理。

Answer 1

這裏是代碼的實際塊，我掏出一個大項目。 （對不起，這是我能找到的最短的一個，它有一個明顯的預取提速。） 此代碼執行非常大的數據轉置。

本示例使用SSE預取指令，該指令可能與GCC發出的指令相同。

要運行這個例子，你需要爲x64編譯這個，並且有超過4GB的內存。您可以使用較小的數據大小運行它，但速度太快而無法使用。

#include <iostream> 
using std::cout; 
using std::endl; 

#include <emmintrin.h> 
#include <malloc.h> 
#include <time.h> 
#include <string.h> 

#define ENABLE_PREFETCH 


#define f_vector __m128d 
#define i_ptr  size_t 
inline void swap_block(f_vector *A,f_vector *B,i_ptr L){ 
    // To be super-optimized later. 

    f_vector *stop = A + L; 

    do{ 
     f_vector tmpA = *A; 
     f_vector tmpB = *B; 
     *A++ = tmpB; 
     *B++ = tmpA; 
    }while (A < stop); 
} 
void transpose_even(f_vector *T,i_ptr block,i_ptr x){ 
    // Transposes T. 
    // T contains x columns and x rows. 
    // Each unit is of size (block * sizeof(f_vector)) bytes. 

    //Conditions: 
    // - 0 < block 
    // - 1 < x 

    i_ptr row_size = block * x; 
    i_ptr iter_size = row_size + block; 

    // End of entire matrix. 
    f_vector *stop_T = T + row_size * x; 
    f_vector *end = stop_T - row_size; 

    // Iterate each row. 
    f_vector *y_iter = T; 
    do{ 
     // Iterate each column. 
     f_vector *ptr_x = y_iter + block; 
     f_vector *ptr_y = y_iter + row_size; 

     do{ 

#ifdef ENABLE_PREFETCH 
      _mm_prefetch((char*)(ptr_y + row_size),_MM_HINT_T0); 
#endif 

      swap_block(ptr_x,ptr_y,block); 

      ptr_x += block; 
      ptr_y += row_size; 
     }while (ptr_y < stop_T); 

     y_iter += iter_size; 
    }while (y_iter < end); 
} 
int main(){ 

    i_ptr dimension = 4096; 
    i_ptr block = 16; 

    i_ptr words = block * dimension * dimension; 
    i_ptr bytes = words * sizeof(f_vector); 

    cout << "bytes = " << bytes << endl; 
// system("pause"); 

    f_vector *T = (f_vector*)_mm_malloc(bytes,16); 
    if (T == NULL){ 
     cout << "Memory Allocation Failure" << endl; 
     system("pause"); 
     exit(1); 
    } 
    memset(T,0,bytes); 

    // Perform in-place data transpose 
    cout << "Starting Data Transpose... "; 
    clock_t start = clock(); 
    transpose_even(T,block,dimension); 
    clock_t end = clock(); 

    cout << "Done" << endl; 
    cout << "Time: " << (double)(end - start)/CLOCKS_PER_SEC << " seconds" << endl; 

    _mm_free(T); 
    system("pause"); 
} 

當我啓用ENABLE_PREFETCH運行它，這是輸出：

bytes = 4294967296 
Starting Data Transpose... Done 
Time: 0.725 seconds 
Press any key to continue . . . 

當我與ENABLE_PREFETCH禁用運行它，這是輸出：

bytes = 4294967296 
Starting Data Transpose... Done 
Time: 0.822 seconds 
Press any key to continue . . . 

所以有預取速度提高13％。

編輯：

這裏的一些結果：

Operating System: Windows 7 Professional/Ultimate 
Compiler: Visual Studio 2010 SP1 
Compile Mode: x64 Release 

Intel Core i7 860 @ 2.8 GHz, 8 GB DDR3 @ 1333 MHz 
Prefetch : 0.868 
No Prefetch: 0.960 

Intel Core i7 920 @ 3.5 GHz, 12 GB DDR3 @ 1333 MHz 
Prefetch : 0.725 
No Prefetch: 0.822 

Intel Core i7 2600K @ 4.6 GHz, 16 GB DDR3 @ 1333 MHz 
Prefetch : 0.718 
No Prefetch: 0.796 

2 x Intel Xeon X5482 @ 3.2 GHz, 64 GB DDR2 @ 800 MHz 
Prefetch : 2.273 
No Prefetch: 2.666 

Answer 2

從the documentation：

 for (i = 0; i < n; i++) 
     { 
      a[i] = a[i] + b[i]; 
      __builtin_prefetch (&a[i+j], 1, 1); 
      __builtin_prefetch (&b[i+j], 0, 1); 
      /* ... */ 
     } 

Answer 3

二進制搜索是一個簡單的例子，可以從明確的預取中受益。二進制搜索中的訪問模式對硬件預取器來說幾乎是隨機的，所以它很少有機會準確預測要獲取的內容。

在這個例子中，我預取了當前迭代中下一個循環迭代的兩個可能的「中間」位置。其中一個預取可能永遠不會被使用，但另一個會（除非這是最後一次迭代）。

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

int binarySearch(int *array, int number_of_elements, int key) { 
     int low = 0, high = number_of_elements-1, mid; 
     while(low <= high) { 
       mid = (low + high)/2; 
      #ifdef DO_PREFETCH 
      // low path 
      __builtin_prefetch (&array[(mid + 1 + high)/2], 0, 1); 
      // high path 
      __builtin_prefetch (&array[(low + mid - 1)/2], 0, 1); 
      #endif 

       if(array[mid] < key) 
         low = mid + 1; 
       else if(array[mid] == key) 
         return mid; 
       else if(array[mid] > key) 
         high = mid-1; 
     } 
     return -1; 
} 
int main() { 
    int SIZE = 1024*1024*512; 
    int *array = malloc(SIZE*sizeof(int)); 
    for (int i=0;i<SIZE;i++){ 
     array[i] = i; 
    } 
    int NUM_LOOKUPS = 1024*1024*8; 
    srand(time(NULL)); 
    int *lookups = malloc(NUM_LOOKUPS * sizeof(int)); 
    for (int i=0;i<NUM_LOOKUPS;i++){ 
     lookups[i] = rand() % SIZE; 
    } 
    for (int i=0;i<NUM_LOOKUPS;i++){ 
     int result = binarySearch(array, SIZE, lookups[i]); 
    } 
    free(array); 
    free(lookups); 
} 

當我編譯和運行這個例子啓用DO_PREFETCH，我看到在運行時減少了20％：

$ gcc c-binarysearch.c -DDO_PREFETCH -o with-prefetch -std=c11 -O3 
$ gcc c-binarysearch.c -o no-prefetch -std=c11 -O3 

$ perf stat -e L1-dcache-load-misses,L1-dcache-loads ./with-prefetch 

    Performance counter stats for './with-prefetch': 

    356,675,702  L1-dcache-load-misses  # 41.39% of all L1-dcache hits 
    861,807,382  L1-dcache-loads            

    8.787467487 seconds time elapsed 

$ perf stat -e L1-dcache-load-misses,L1-dcache-loads ./no-prefetch 

Performance counter stats for './no-prefetch': 

    382,423,177  L1-dcache-load-misses  # 97.36% of all L1-dcache hits 
    392,799,791  L1-dcache-loads            

    11.376439030 seconds time elapsed 

注意，我們在預取版本數量的L1高速緩存負載做兩次。實際上，我們正在做更多的工作，但內存訪問模式對管道更加友好。這也顯示了權衡。雖然這段代碼的運行速度很快，但我們已經將很多垃圾加載到緩存中，這可能會給應用程序的其他部分帶來更大的壓力。