任何人都可以给出一个示例或链接到一个__builtin_prefetch在 GCC 中使用的示例（或通常只是 asm 指令 prefetcht0）以获得实质性的性能优势吗？特别是，我希望该示例满足以下条件：
- 这是一个简单、小型、独立的示例。
- 删除
__builtin_prefetch指令会导致性能下降。 - 用相应的内存访问替换
__builtin_prefetch指令会导致性能下降。
也就是说，我想要一个最短的例子来展示__builtin_prefetch一个没有它就无法管理的优化。
问问题
34706 次
5 回答
68
这是我从一个更大的项目中提取的一段实际代码。（抱歉，它是我能找到的最短的一个，它从预取中得到了显着的加速。）这段代码执行了一个非常大的数据转置。
此示例使用 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
于 2011-09-07T02:13:30.963 回答
40
二进制搜索是一个可以从显式预取中受益的简单示例。二进制搜索中的访问模式对于硬件预取器来说看起来非常随机，因此它几乎不可能准确预测要获取的内容。
在这个例子中，我预取了当前迭代中下一个循环迭代的两个可能的“中间”位置。其中一个预取可能永远不会被使用，但另一个会（除非这是最后一次迭代）。
#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 缓存加载。我们实际上做了很多工作，但内存访问模式对管道更友好。这也显示了权衡。虽然这段代码单独运行得更快，但我们已经将大量垃圾加载到缓存中，这可能会给应用程序的其他部分带来更大的压力。
于 2015-07-28T22:18:14.837 回答
5
我从@JamesScriven 和@Mystical 提供的出色答案中学到了很多东西。但是，他们的示例仅提供了适度的提升-此答案的目的是提出一个（我必须承认有些人为的）示例，其中预取的影响更大（在我的机器上大约为 4 倍）。
现代架构存在三个可能的瓶颈：CPU 速度、内存带宽和内存延迟。预取就是减少内存访问的延迟。
在一个完美的场景中，延迟对应于 X 个计算步骤，我们将有一个预言机，它会告诉我们在 X 个计算步骤中我们将访问哪些内存，这些数据的预取将被启动并且它会在 -时间 X 计算步骤后。
对于很多算法，我们（几乎）处于这个完美的世界中。对于一个简单的 for 循环，很容易预测 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
}
}
一些备注：
- 数据以这样一种方式准备，即预言机总是正确的。
- 也许令人惊讶的是，CPU 绑定的任务越少，加速就越大：我们能够几乎完全隐藏延迟，因此加速是
CPU-time+original-latency-time/CPU-time.
编译和执行线索：
>>> 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";
}
}
于 2018-05-10T19:21:01.340 回答
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);
/* ... */
}
于 2011-09-07T01:47:15.993 回答
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 字节向量可能会带来相同的性能改进。在我的具有 100 万次迭代循环的应用程序中，仅通过这样做就可以将性能提高 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%。
于 2018-09-23T21:37:16.013 回答