优化C循环以获得数组的对角线
伟大的神谷歌并没有向我提供一些循环优化问题的解释。 所以，在悲伤中我没有足够的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％。 但是当我看着这个代码的鲨鱼分析（Mac上的XCode附带的工具）时，它警告我这是一个未对齐的循环。
第三个改进的尝试是通过删除“调零”循环并使用memset将零diag_data设置为零：
memset(diag_data, ' ', 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, ' ', sizeof(diag_data));
for (iter = 0; iter<98;) {
diag_mask[iter] = spJ[sp_diag_ind[iter++]];
}
这个时间是10.9％。 此外，当我查看带注释的源代码时，Shark不会发出未对齐的循环警告。 结束愚蠢的部分
所以，我的问题是：
谢谢您的帮助。
- 安德鲁
未对齐的循环是第一条指令不在特定边界上开始的位置（16或32的倍数）。 应该有一个编译器标志来对齐循环; 它可能会或可能不会帮助性能。 无论标志是否对齐，回路是否对齐，都是基于哪些指令到达之前，因此不可预测。 您可以尝试的另一个优化是将diag_mask ， spJ和sp_diag_ind为restrict （C99功能）。 这表明它们没有别名，可能会帮助编译器更好地优化循环。 尽管如此，98的计数可能太小而不能产生任何效果。
你的第五个版本是不正确的 - 它有未定义的行为，因为它既修改iter并且引用它的值，除了计算新值之外，没有中间顺序点。
您是否尝试在计算sp_diag_ind[]的位置存储对角线的实际值，而不是spJ内的索引？ 然后，您可以直接将它们复制到diag_data （或者，更好地，直接使用对角线矢量）。
C标准的相关部分是§6.5表达式：
“2。 在前一个和下一个序列点之间，一个对象应该通过评估一个表达式最多修改其存储值一次。 此外，先验值只能读取以确定要存储的值。
这适用于表达式中的对象iter 。 违反“应”约束是未定义的行为。
海湾合作委员会（测试版本4.4.5）甚至警告你的表达：
x.c:16: warning: operation on ‘iter’ may be undefined
你看到我可以做的其他改进吗？
您正在调整大约11％的时间使用的日光。 其他89％可以优化吗？
链接地址: http://www.djcxy.com/p/51203.html