作者热门文章
- r - 以节省内存的方式增长 data.frame
- ruby-on-rails - ruby/ruby on rails 内存泄漏检测
- android - 无法解析导入android.support.v7.app
- UNIX 域套接字与共享内存(映射文件)
没有裂变的代码是这样的:
int check(int * res, char * map, int n, int * keys){
int ret = 0;
for(int i = 0; i < n; ++i){
res[ret] = i;
ret += map[hash(keys[i])]
}
return ret;
}
裂变:
int check(int * res, char * map, int n, int * keys){
int ret = 0;
for(int i = 0; i < n; ++i){
tmp[i] = map[hash(keys[i])];
}
for(int i = 0; i < n; ++i){
res[ret] = i;
ret += tmp[i];
}
return ret;
}
注意事项:
瓶颈是随机访问内存的map[hash(keys[i])]
。
通常是 if(tmp[i]) res[ret++] = i;
来避免 if,我使用的是 ret += tmp[i ]
.
map[..]
始终为 0 或 1
裂变版本通常要快得多,我试图解释原因。我最好的猜测是 ret += map[..]
仍然会引入一些依赖关系,从而阻止推测执行。
我想听听是否有人有更好的解释。
最佳答案
从我的测试中,我得到融合和分离循环之间大约 2 倍的速度差异。无论我如何调整循环,这种速度差异都非常一致。
Fused: 1.096258 seconds
Split: 0.562272 seconds
(完整的测试代码见底部。)
虽然我不是 100% 确定,但我怀疑这是由于两件事的结合:
map[gethash(keys[i])]
的缓存未命中。很明显 map[gethash(keys[i])]
几乎每次都会导致缓存未命中。事实上,可能足以使整个加载存储缓冲区饱和。
现在让我们看看添加的依赖项。问题是 ret
变量:
int check_fused(int * res, char * map, int n, int * keys){
int ret = 0;
for(int i = 0; i < n; ++i){
res[ret] = i;
ret += map[gethash(keys[i])];
}
return ret;
}
ret
变量是 商店的地址解析所需要的 res[ret] = i;
.
ret
来自一个确定的缓存未命中。ret
即将到来 tmp[i]
- 这要快得多。这种融合循环情况的地址解析延迟可能会导致 res[ret] = i
与 map[gethash(keys[i ])]
.
由于加载-存储缓冲区具有固定大小,但其中的垃圾数量增加了一倍:
您只能将缓存未命中的重叠率降低到以前的一半。 因此2 倍减速。
假设如果我们将融合循环更改为:
int check_fused(int * res, char * map, int n, int * keys){
int ret = 0;
for(int i = 0; i < n; ++i){
res[i] = i; // Change "res" to "i"
ret += map[gethash(keys[i])];
}
return ret;
}
这将打破地址解析依赖性。
(注意已经不一样了,只是为了演示性能差异。)
然后我们得到类似的时间:
Fused: 0.487477 seconds
Split: 0.574585 seconds
这是完整的测试代码:
#define SIZE 67108864
unsigned gethash(int key){
return key & (SIZE - 1);
}
int check_fused(int * res, char * map, int n, int * keys){
int ret = 0;
for(int i = 0; i < n; ++i){
res[ret] = i;
ret += map[gethash(keys[i])];
}
return ret;
}
int check_split(int * res, char * map, int n, int * keys, int *tmp){
int ret = 0;
for(int i = 0; i < n; ++i){
tmp[i] = map[gethash(keys[i])];
}
for(int i = 0; i < n; ++i){
res[ret] = i;
ret += tmp[i];
}
return ret;
}
int main()
{
char *map = (char*)calloc(SIZE,sizeof(char));
int *keys = (int*)calloc(SIZE,sizeof(int));
int *res = (int*)calloc(SIZE,sizeof(int));
int *tmp = (int*)calloc(SIZE,sizeof(int));
if (map == NULL || keys == NULL || res == NULL || tmp == NULL){
printf("Memory allocation failed.\n");
system("pause");
return 1;
}
// Generate Random Data
for (int i = 0; i < SIZE; i++){
keys[i] = (rand() & 0xff) | ((rand() & 0xff) << 16);
}
printf("Start...\n");
double start = omp_get_wtime();
int ret;
ret = check_fused(res,map,SIZE,keys);
// ret = check_split(res,map,SIZE,keys,tmp);
double end = omp_get_wtime();
printf("ret = %d",ret);
printf("\n\nseconds = %f\n",end - start);
system("pause");
}
关于c - 为什么循环裂变在这种情况下有意义?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11123658/
我是一名优秀的程序员,十分优秀!