对于操作数据数组的算法,在Java和C等语言中,有两个因素会显著影响性能:
以此无害示例为例,展示一个常见的滤镜(类似于模糊,但1D):
for(int i = 0; i < ndata - ncoef; ++i) {
z[i] = 0;
for(int k = 0; k < ncoef; ++k) {
z[i] += c[k] * d[i + k];
}
}
访问数组元素时,coef[k]
的操作流程如下:
- 将数组
coef
的地址加载到寄存器中;
- 将值
k
加载到一个寄存器中;
- 将这两个值相加;
- 获取该地址处的内存。
每个数组访问都可以得到提升,因为您知道索引是连续的。编译器和JIT都不知道索引是否连续,因此无法进行充分的优化(尽管它们会继续尝试)。
在C++中,您可以编写更像这样的代码:
int d[10000];
int z[10000];
int coef[10];
int* zptr;
int* dptr;
int* cptr;
dptr = &(d[0]); // Just being overly explicit here, more likely you would dptr = d;
zptr = &(z[0]); // or zptr = z;
for(int i = 0; i < (ndata - ncoef); ++i) {
*zptr = 0;
*cptr = coef;
*dptr = d + i;
for(int k = 0; k < ncoef; ++k) {
*zptr += *cptr * *dptr;
cptr++;
dptr++;
}
zptr++;
}
第一次尝试这样做时(并成功地得到正确的结果),你将惊讶于它可以更快地完成。获取索引,求和索引和基地址的所有数组地址计算都被替换为增量指令。
对于2D数组操作,例如对图像进行模糊处理,一个简单的代码data[r,c]涉及两个值的获取、一个乘法和一个求和。因此,使用指针可以消除乘法运算。
因此,该语言可真正减少CPU必须执行的操作。代价在于C++代码难以阅读和调试。指针错误和缓冲区溢出是黑客的温床。但当涉及到原始数字计算算法时,其速度提高太诱人了,不能忽视。