我正在优化一个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是一个(大部分为零)150×150阵列的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的使用未定义. Props to @caf and @rlibby for catching it.
最后,我接着尝试了一些我认为很傻的东西：
memset(diag_data,sizeof(diag_data));
for (iter = 0; iter<98;) {
diag_mask[iter] = spJ[sp_diag_ind[iter++]];
}
时间为10.9％.此外,当我查看带注释的源代码时,Shark不会发出未对齐的循环警告.
结束愚蠢的部分
所以,我的问题：
>什么是不对齐的循环？
>为什么第五个实现是对齐而第四个不是？
>是否有一个对齐的循环负责提高我的第四个和第五个实现之间的执行速度,或者在查找sp_diag_ind的值时嵌入增量步骤？
>你看到我能做出的其他任何改进吗？
谢谢您的帮助.
– 安德鲁
