优化C循环以获得数组的对角线

Question

对于一些循环优化问题的解释,Google并没有向我提出大神.所以,在悲伤中我没有Google-fu,我转向你StackOverflow.

我正在优化一个C程序来解决一个特定的微分方程系统.在找到数值解的过程中,我称之为一个函数,它建立一个线性方程组,然后是一个解决它的函数.

解决方案函数最初在访问定义线性系统的阵列对角线上的元素时存在瓶颈.所以我包含了一个在系统初始化期间设置的一维数组,它保存了数组对角线的值.

为了好玩,我继续使用初始化对角元素的代码,测量所花费的时间并尝试不断改进代码.我试过的版本引出了一些问题:

注意:我将我尝试过的所有版本放入一个函数中,并对此函数进行了分析,以查看花费的时间.我将报告一个版本的执行时间占功能总时间的百分比.该功能评估了数百万次.数字越小越好.

代码中使用的相关数据声明:

/* quick definitions of the relevant variables, data is a struct */

static const int sp_diag_ind[98] = {2,12,23,76,120,129,137,142,.../* long list */};

double *spJ = &(data->spJ[0]);
/* data has double spJ[908] that represents a sparse matrix stored in triplet
*  form, I grab the pointer because I've found it to be more 
*  efficient than referencing data->spJ[x] each time I need it
*/

int iter,jter;
double *diag_data = NV_DATA_S(data->J_diag);
/* data->J_diag has a content field that has an array double diag_data[150]
*  NV_DATA_S is a macro to return the pointer to the relevant data
*/

我初始化diag_data的原始循环.时间是评估的16.1%(见注释).

/* try 1 */
for (iter = 0; iter<3; iter++) {
    diag_data[iter] = 0; 
}
jter = 0;
for (iter = 3; iter<101; iter++) { // unaligned loop start
    diag_data[iter] = spJ[sp_diag_ind[jter]];
    jter++; // heavy line for loop
}

for (iter = 101; iter<150; iter++) {
    diag_data[iter] = 0; 
}

总而言之,我们抓住指向对角线的指针,将一些组件设置为零(根据我正在使用的算法,这不是可选的),然后获取驻留在稀疏形式的"数组"对角线上的值通过spJ.由于spJ是一个(大部分为零)150x150阵列的908个非零的一维数组,我们必须使用查找来查找spJ中对角元素的位置.此查找由98元素数组sp_diag_ind定义.

我试图删除使用jter,因为它显示为不能自由增加.我的第二次尝试的中间循环:

for (iter = 0; iter<98; iter++) { // unaligned loop start
    diag_data[iter+3] = spJ[sp_diag_ind[iter]];
}

这改善了一点.此版本的时间为15.6%.但是,当我查看Shark对此代码的分析(Mac上的XCode附带的工具)时,它警告我这是一个未对齐的循环.

改进的第三个尝试是删除"归零"循环并使用memset将零diag_data:

memset(diag_data, '\0', sizeof(diag_data));

for (iter = 0; iter<98; iter++) { // unaligned loop start
    diag_data[iter+3] = spJ[sp_diag_ind[iter]];
}

时间为14.9%.不确定一个未对齐的循环是什么,我继续小提琴.我发现了一个改进的第四个实现,用指针执行 diag_data和spJ [crazy index]之间的对齐偏移:

realtype * diag_mask = &diag_data[3];
for (iter = 0; iter<98; iter++) { // unaligned loop start
    diag_mask[iter] = spJ[sp_diag_ind[iter]];
}

使用diag_mask可以提高速度.它的比例为13.1%.

编辑:事实证明这部分比我原先想象的更愚蠢.iter的使用未定义.支持@caf和@rlibby的道具.

最后,我接着尝试了一些我觉得很傻的东西:

memset(diag_data, '\0', sizeof(diag_data));

for (iter = 0; iter<98;) {
    diag_mask[iter] = spJ[sp_diag_ind[iter++]];
}

这个时间定在10.9%.此外,当我查看带注释的源代码时,Shark不会发出未对齐的循环警告. 结束愚蠢的部分

所以,我的问题:

1. 什么是未对齐的循环？
2. 为什么第五个实现是对齐的而第四个实现不对齐？
3. 是否有一个对齐的循环负责提高我的第四个和第五个实现之间的执行速度,或者是在sp_diag_ind的值的查找中嵌入增量步骤负责？
4. 你看到我能做出的其他任何改进吗？

谢谢您的帮助.

- 安德鲁

Answer 1

未对齐循环是指第一条指令不在特定边界（16 或 32 的倍数）上开始的循环。应该有一个编译器标志来对齐循环；它可能会也可能不会帮助性能。没有标志的循环是否对齐取决于其之前的指令，因此它是不可预测的。您可以尝试的另一种优化是将diag_mask、spJ和标记sp_diag_ind为restrict（C99 功能）。这表明它们没有别名，可能有助于编译器更好地优化循环。不过，98 的计数可能太小，看不到任何效果。