logo标签列表

预取示例？

gccoptimizationassemblyprefetch
72

有没有人能给出一个使用__builtin_prefetch在GCC（或者一般情况下的汇编指令prefetcht0）的实例或链接，以获得显著的性能优势？特别是，我希望这个示例符合以下条件：

  1. 它是一个简单、小巧、自包含的示例。
  2. 删除__builtin_prefetch指令会导致性能降低。
  3. 将__builtin_prefetch指令替换为相应的内存访问会导致性能降低。

也就是说，我想要展示__builtin_prefetch执行一项优化的最短示例，这是在没有它的情况下无法实现的。

5个回答
71
这是一个从大型项目中提取出来的实际代码片段。（抱歉，这是我能找到的最短的一个，因为在使用预取技术后有明显的加速效果。）此代码执行了一个非常大的数据转换操作。
此示例使用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
1
有趣。不幸的是，在我测试的两台机器上（一台带有“Core 2 Duo”的Macbook Pro和一台带有“Quad-Core AMD Opteron Processor 2376”的Linux机器）两个版本之间没有显着差异。我怀疑这与缓存大小有关--看起来你的机器比这两台更好。你觉得呢？ - Shaun Harker
2
我的机器是一台Core i7 920 @ 3.5 GHz，8MB L3缓存。这个10%的加速大致上在我测试过的其他三台机器上也是一致的：Core i7 2600K @ 4.6 GHz和2 x Xeon X5482 @ 3.2 GHz。但我承认我从未在笔记本电脑或AMD机器上测试过它。 - Mysticial
1
我刚刚编辑了我的答案，并附上了我测试过的所有4台机器的基准测试结果。它们都是英特尔台式机/工作站。所以这可能是原因。我没有测试你的第三个观点是否成立。用内存访问替换它可能会产生相同的结果。 - Mysticial
第三点由于乱序执行而难以测试。为了满足第三点，您需要在加载和实际使用之间有大约100-200条指令。当重新排序缓冲区填满后，停顿的加载将阻塞流水线。但是预取不会。只有当您实际拥有足够的指令来溢出重新排序缓冲区时，才会看到停顿加载的惩罚...如果您只是用普通加载替换我的预取，则编译器可能会将加载优化为死代码...(这满足了您的最后一点，哈哈) - Mysticial
1
仅供记录：在我的系统上，使用1833 MHz内存的时间为0.59/0.67秒。 - Gunther Piez
显示剩余3条评论
43

二分查找是一个简单的示例，可以从明确的预取中受益。在二分查找中，访问模式对于硬件预取程序来说看起来几乎是随机的，因此它很少有机会准确地预测要获取什么。

在这个示例中，我预取了下一个循环迭代中当前迭代的两个可能的“中间”位置。其中一个预取可能永远不会被使用，但另一个会被使用（除非这是最后一次迭代）。

 #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缓存加载。实际上我们执行了更多的工作，但是内存访问模式对流水线更加友好。这也展示了权衡之处。虽然这个代码块独立运行速度更快，但是我们已经将大量垃圾加载到缓存中, 这可能会给应用程序的其他部分带来更大的压力。

如果数据对齐，是否可以将内置预取与AVX指令结合使用？预取的结果可以加载到AVX寄存器中进行比较吗？ - gansub
我使用这段代码进行了一些测试，发现编译器优化实际上使缓存命中率指标变差，并且生成的二进制文件更慢。为了查看，请编译并运行没有任何优化标志的代码。 - Mah35h
当我运行你的程序时，我得到了类似缩放的结果，但是当我运行谷歌基准测试来隔离搜索时，我发现预取比较差，降低了50%。 - kolbe
8
我从@JamesScriven和@Mystical提供的出色答案中学到了很多。然而，他们的例子只能带来一点小的改善 - 这篇答案的目标是提供一个（我必须承认有些人为的）示例，在这个示例中，预取对性能有更大的影响（在我的计算机上约为4倍）。
现代架构有三种可能的瓶颈：CPU速度、内存带宽和内存延迟。预取就是为了减少内存访问的延迟。
在一个完美的场景中，其中延迟对应于X个计算步骤，我们将拥有一个神谕，告诉我们X个计算步骤后我们将访问哪些内存数据，预取这些数据将会在X个计算步骤后及时到达。
对于很多算法来说，我们（几乎）处于这个完美世界中。对于一个简单的for-loop，很容易预测X步之后需要哪些数据。乱序执行和其他硬件技巧在这里做得非常好，几乎完全隐藏了延迟。
这就是为什么对于@Mystical的例子只有如此温和的改进的原因：预取器已经非常好了 - 没有太多的改进空间。任务也是内存绑定的，所以可能没有太多的带宽剩余 - 它可能成为限制因素。在我的计算机上，我最多能看到8%的改进。
@JamesScriven示例的关键见解：我们和CPU都不知道下一个访问地址是什么，在当前数据从内存中获取之前存在此依赖关系 - 这个依赖关系非常重要，否则乱序执行会导致向前查找，硬件将能够预取数据。然而，由于我们只能推测一步，所以潜力并不大。在我的计算机上，我无法获得超过40％的改进。
因此，让我们篡改比赛，并以这样一种方式准备数据，使我们知道在X步中访问哪个地址，但由于依赖于尚未访问的数据，硬件无法找到它（请参见答案末尾的整个程序）。
//making random accesses to memory:
unsigned int next(unsigned int current){
   return (current*10001+328)%SIZE;
}

//the actual work is happening here
void operator()(){

    //set up the oracle - let see it in the future oracle_offset steps
    unsigned int prefetch_index=0;
    for(int i=0;i<oracle_offset;i++)
        prefetch_index=next(prefetch_index);

    unsigned int index=0;
    for(int i=0;i<STEP_CNT;i++){
        //use oracle and prefetch memory block used in a future iteration
        if(prefetch){
            __builtin_prefetch(mem.data()+prefetch_index,0,1);    
        }

        //actual work, the less the better
        result+=mem[index];

        //prepare next iteration
        prefetch_index=next(prefetch_index);  #update oracle
        index=next(mem[index]);               #dependency on `mem[index]` is VERY important to prevent hardware from predicting future
    }
}

一些注释：

  1. 数据的准备方式始终使得Oracle是正确的。
  2. 也许令人惊讶的是，CPU绑定任务越少，速度提升就越大：我们几乎可以完全隐藏延迟，因此速度提升为CPU时间+原始延迟时间/CPU时间。

编译和执行结果如下：

>>> g++ -std=c++11 prefetch_demo.cpp -O3 -o prefetch_demo
>>> ./prefetch_demo
#preloops   time no prefetch    time prefetch   factor
...
7   1.0711102260000001  0.230566831 4.6455521002498408
8   1.0511602149999999  0.22651144600000001 4.6406494398521474
9   1.049024333 0.22841439299999999 4.5926367389641687
....

将速度提高到4到5倍。

prefetch_demp.cpp清单:

//prefetch_demo.cpp

#include <vector>
#include <iostream>
#include <iomanip>
#include <chrono>

const int SIZE=1024*1024*1;
const int STEP_CNT=1024*1024*10;

unsigned int next(unsigned int current){
   return (current*10001+328)%SIZE;
}


template<bool prefetch>
struct Worker{
   std::vector<int> mem;

   double result;
   int oracle_offset;

   void operator()(){
        unsigned int prefetch_index=0;
        for(int i=0;i<oracle_offset;i++)
            prefetch_index=next(prefetch_index);

        unsigned int index=0;
        for(int i=0;i<STEP_CNT;i++){
            //prefetch memory block used in a future iteration
            if(prefetch){
                __builtin_prefetch(mem.data()+prefetch_index,0,1);    
            }
            //actual work:
            result+=mem[index];

            //prepare next iteration
            prefetch_index=next(prefetch_index);
            index=next(mem[index]);
        }
   }

   Worker(std::vector<int> &mem_):
       mem(mem_), result(0.0), oracle_offset(0)
   {}
};

template <typename Worker>
    double timeit(Worker &worker){
    auto begin = std::chrono::high_resolution_clock::now();
    worker();
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::nanoseconds>(end-begin).count()/1e9;
}


 int main() {
     //set up the data in special way!
     std::vector<int> keys(SIZE);
     for (int i=0;i<SIZE;i++){
       keys[i] = i;
     }

     Worker<false> without_prefetch(keys);
     Worker<true> with_prefetch(keys);

     std::cout<<"#preloops\ttime no prefetch\ttime prefetch\tfactor\n";
     std::cout<<std::setprecision(17);

     for(int i=0;i<20;i++){
         //let oracle see i steps in the future:
         without_prefetch.oracle_offset=i;
         with_prefetch.oracle_offset=i;

         //calculate:
         double time_with_prefetch=timeit(with_prefetch);
         double time_no_prefetch=timeit(without_prefetch);

         std::cout<<i<<"\t"
                  <<time_no_prefetch<<"\t"
                  <<time_with_prefetch<<"\t"
                  <<(time_no_prefetch/time_with_prefetch)<<"\n";
     }

 }
尝试使用MSVC 19.33，实际上我似乎获得了大约7.5倍的加速，几乎适用于所有的oracle_offset值。即使对于0，看起来编译器也会展开循环，并一次性进行10次迭代，同时将预取指令偏移1（大致如此：prefetch(a); read(x); prefetch(b); read(a);）。感谢这个很好的例子。 - Jake1234
0

预取数据可以通过优化缓存行大小进行优化，对于大多数现代64位处理器而言，缓存行大小为64字节，例如可以使用一条指令预加载uint32_t [16]。

例如，在ArmV8上，通过实验发现将内存指针转换为uint32_t 4x4矩阵向量（大小为64字节）可以将所需的指令数量减半，因为之前必须增加8来加载一半数据，尽管我理解它会获取完整的缓存行。

预取一个uint32_t [32]原始代码示例...

int addrindex = &B[0];
    __builtin_prefetch(&V[addrindex]);
    __builtin_prefetch(&V[addrindex + 8]);
    __builtin_prefetch(&V[addrindex + 16]);
    __builtin_prefetch(&V[addrindex + 24]);

之后...

int addrindex = &B[0];
__builtin_prefetch((uint32x4x4_t *) &V[addrindex]);
__builtin_prefetch((uint32x4x4_t *) &V[addrindex + 16]);

由于某种原因，地址索引/偏移的int数据类型表现更佳。在Cortex-a53上使用GCC 8进行测试。如果您发现它没有像我这样预取所有数据，则在其他架构上使用等效的64字节向量可能会带来相同的性能提升。在我的应用程序中，通过这样做，对于一百万次迭代循环，它将性能提高了5％。还有进一步的改进要求。

128兆字节的“V”内存分配必须对齐到64字节。

uint32_t *V __attribute__((__aligned__(64))) = (uint32_t *)(((uintptr_t)(__builtin_assume_aligned((unsigned char*)aligned_alloc(64,size), 64)) + 63) & ~ (uintptr_t)(63));

此外，我不得不使用C运算符而不是Neon Intrinsics，因为它们需要常规数据类型指针（在我的情况下是uint32_t *），否则新的内置预取方法会导致性能回归。

我的真实世界示例可以在https://github.com/rollmeister/veriumMiner/blob/main/algo/scrypt.c中找到，其中包括scrypt_core()及其内部函数，这些都很容易阅读。GCC8完成了大部分的工作。总体性能提升了25%。

0

从文档中：

      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);
          /* ... */
        }
18
我预计CPU的硬件预取器本来应该已经预取了这个内容。通常人们发现“预取无效”的原因是，访问模式需要是一个相对简单的模式，而分析访问模式的合理逻辑不能预测到这个模式。 - Crowley9
1
@Crowley9 我不同意这是一个糟糕的答案。原帖想要一个简单的例子（可能是为了知道如何使用它），这个回答就解决了这个问题。 - a3mlord
1
旧CPU的智能硬件预取受益于更多的软件预取。我认为即使是P4也足够聪明，以硬件方式预取连续数据的顺序访问。但是，这是一个糟糕的例子，因为在这种情况下，额外的预取指令只会减慢速度。@a3mlord：OP想要获得性能提升，不仅仅是语法。 - Peter Cordes
这个例子太简短了，无法回答这个问题。 - rookiepig
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接