我复制了 glibc 的二分搜索算法实现,然后对其进行了一些修改以满足我的需要。我决定测试它和我学到的关于 GCC 的其他东西(属性和内置)。代码如下所示:
int main() {
uint_fast16_t a[61] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61 };
uint64_t t1 = Time(0);
for(register uint_fast16_t i = 0; i < 10000000; ++i) {
binary_search(rand() % 62, a, 61);
}
printf("%ld\n", Time(0) - t1);
return 0;
}
现在,这个程序运行得很好。当我添加更多代码行时,问题就开始了,例如:
uint_fast16_t a[61] __attribute__ ((aligned (64) )) = /* ... */
在这种情况下,我希望代码更快,但经过多次测试(数十次测试)后性能没有改变。我还测试了 8 和 1 对齐的程序 - 没有变化。我什至预计 gcc 会抛出错误/警告,因为使用的对齐小于类型大小(在我的情况下 64 位机器,uint_fast16_t 是 8 个字节),但没有。然后是另一个更改,即添加缓存(在 GCC 9 中引入)。我在 for 循环之前添加了以下代码:
caches(a, uint_fast16_t, uint_fast16_t, 61, 0, 3);
// where "caches" is:
#define caches(x, type, data_type, size, rw, l) ({ \
for(type Q2W0 = 0; Q2W0 < size; Q2W0 += 64 / sizeof(data_type)) { \
__builtin_prefetch(x + Q2W0, rw, l); \
} \
})
性能也没有变化。我发现我的 CPU 可能会在第一次之后自动缓存数组,binary_search
所以我消除了for
循环并在有和没有缓存线的情况下再次测量了几次,但我也没有注意到性能有任何变化。
更多信息:
- 使用 CentOS8 64bit 最新内核
- 使用 GCC 9.2.1 20191120
- 编译
-O3 -Wall -pthread -lanl -Wno-missing-braces -Wmissing-field-initializers
,编译期间没有错误/警告 - 事情没有优化(检查 asm 输出)
我很确定我不知道某事/我做错了什么。
此处提供完整代码。