有没有可靠的方法可以强制GCC(或任何编译器)在循环之外对memcpy()
中的运行时大小检查进行分解(其中该大小不是编译时常量,但在该循环内是常量),为每个相关大小范围专门化循环,而不是在其中重复检查大小?
这是从一个用于高效内存分析大型数据集的开源库中报告的性能回归缩小的测试案例(在这里)(此回归恰好是由我的提交之一引起的...)
原始代码是Cython,但我已将其缩减为以下纯C代理。
void take(double * out, double * in,
int stride_out_0, int stride_out_1,
int stride_in_0, int stride_in_1,
int * indexer, int n, int k)
{
int i, idx, j, k_local;
k_local = k; /* prevent aliasing */
for(i = 0; i < n; ++i) {
idx = indexer[i];
for(j = 0; j < k_local; ++j)
out[i * stride_out_0 + j * stride_out_1] =
in[idx * stride_in_0 + j * stride_in_1];
}
}
步长是可变的;一般来说,数组甚至不能保证是连续的(因为它们可能是更大数组的非连续切片)。然而,对于C连续的数组这个特定情况,我已经将上面的代码优化为以下形式:
void take(double * out, double * in,
int stride_out_0, int stride_out_1,
int stride_in_0, int stride_in_1,
int * indexer, int n, int k)
{
int i, idx, k_local;
assert(stride_out_0 == k);
assert(stride_out_0 == stride_in_0);
assert(stride_out_1 == 1);
assert(stride_out_1 == stride_in_1);
k_local = k; /* prevent aliasing */
for(i = 0; i < n; ++i) {
idx = indexer[i];
memcpy(&out[i * k_local], &in[idx * k_local],
k_local * sizeof(double));
}
}
(原始代码中不存在assertion; 取而代之的是检查连续性并在可能的情况下调用优化版本,否则调用未优化版本。)
这个版本在大多数情况下都能很好地进行优化,因为正常使用情况是小的n
和大的k
。然而,相反的使用情况也会发生(大的n
和小的k
),并且对于n == 10000
和k == 4
的特定情况(不能排除是虚拟工作流的重要部分的代表),memcpy()
版本比原始版本慢3.6倍。显然,这主要是由于k
不是编译时常量造成的,这一事实可以通过下一个版本的表现得到证明(在特定的k == 4
的情况下,根据优化设置的不同,该版本表现得几乎或完全与原始版本一样好,有时甚至更好。)
if (k_local == 4) {
/* this optimizes */
for(i = 0; i < n; ++i) {
idx = indexer[i];
memcpy(&out[i * k_local], &in[idx * k_local],
k_local * sizeof(double));
}
} else {
for(i = 0; i < n; ++i) {
idx = indexer[i];
memcpy(&out[i * k_local], &in[idx * k_local],
k_local * sizeof(double));
}
}
显然,为每个特定值 k
编写一个循环是不切实际的,因此我尝试了以下方法(作为第一次尝试,如果成功,则可以进一步推广):
if (k_local >= 0 && k_local <= 4) {
/* this does not not optimize */
for(i = 0; i < n; ++i) {
idx = indexer[i];
memcpy(&out[i * k_local], &in[idx * k_local],
k_local * sizeof(double));
}
} else {
for(i = 0; i < n; ++i) {
idx = indexer[i];
memcpy(&out[i * k_local], &in[idx * k_local],
k_local * sizeof(double));
}
}
遗憾的是,这个最新版本比起原始的memcpy()
版本并没有更快,这让我对GCC的优化能力失去信心。
是否有任何方法可以通过任何手段给GCC提供额外的“提示”,帮助它在这里做正确的事情?(更好的是,是否有“提示”可以可靠地适用于不同的编译器?此库已编译为多个不同的目标。)
引用的结果是针对32位Ubuntu上使用“-O2”标志的GCC 4.6.3,但我还测试了GCC 4.7.2和“-O3”版本,并获得了类似(但不完全相同)的结果。我在LiveWorkspace上发布了我的测试工具,但时间是从我的自己的机器使用time(1)
命令计算出来的(我不知道LiveWorkspace的时间计算有多可靠)。
编辑:我还考虑过只设置某些最小大小的“魔法数字”来调用memcpy()
,并且可以通过反复测试找到这样的值,但我不确定我的结果在不同的编译器/平台上是否具有普适性。我可以在这里使用什么经验法则吗?
进一步编辑:实际上,在这种情况下,k_local
变量有点无用,因为不存在别名;这是我运行某些实验后缩小的范围(k
是全局的),我忘记我更改了它。只需忽略该部分。
编辑标签:我意识到在较新版本的Cython中也可以使用C ++,因此标记为C ++,以防有任何可以从C ++中获得帮助的内容...
最终编辑:除了降级到汇编语言进行专门的memcpy()
之外,在我的本地计算机上,以下似乎是最好的经验解决方案:
int i, idx, j;
double * subout, * subin;
assert(stride_out_1 == 1);
assert(stride_out_1 == stride_in_1);
if (k < 32 /* i.e. 256 bytes: magic! */) {
for(i = 0; i < n; ++i) {
idx = indexer[i];
subout = &out[i * stride_out_0];
subin = &in[idx * stride_in_0];
for(j = 0; j < k; ++j)
subout[j] = subin[j];
}
} else {
for(i = 0; i < n; ++i) {
idx = indexer[i];
subout = &out[i * stride_out_0];
subin = &in[idx * stride_in_0];
memcpy(subout, subin, k * sizeof(double));
}
}
这里使用了一个“魔数”来判断是否调用memcpy()
,但仍然针对已知为连续的小数组优化(因此在大多数情况下比原始版本更快,因为原始版本并没有做出这样的假设)。