前言
 
  循环是程序中最常见结构，针对循环已有众多的优化技术。循环的优化分为源码上的修改和编译器的优化，编译器能自动执行许多循环优化技术，但对源代码的修改可辅助编译器就行优化处理。
 
1. 源码上的优化
 
1. 多重循环的“外小内大”
 
  在多重循环中，采用迭代次数较小的循环驱动内层迭代次数较大的循环能减少内存的消耗，如下示例：
 
for (int i = 0; i < 10000; i++) {
    for (int j = 0; j < 200; j++) {

    }
}
改为：
for (int i = 0; i <200 ; i++) {
    for (int j = 0; j < 10000; j++) {

    }
}
 
2. 循环变量实例化放在循环外
 
如下示例：
 
int i,j;
for (i = 0; i <200 ; i++) {
    for (j = 0; j < 10000; j++) {

    }
}
 
3. 循环无关的表达式放到循环外
 
如下示例：
 
int i,j;
for (i = 0; i <200 ; i++) {
    for (j = 0; j < 10000; j++) {
          j = i*j*x/(y-1);
    }
}
改为：
int i,j,tmp;
tmp = x/(y-1);
for (i = 0; i <200 ; i++) {
    for (j = 0; j < 10000; j++) {
          j = i*j*tmp;
    }
}
 
4. 消除循环终止时的方法调用
 
如下示例：
 
for (int i = 0; i < vec.size(); i++) {

}
改为：
int size = vec.size();
for (int i = 0; i < size; i++) {

}
 
5. 循环外部捕获异常
 
  在循环外部捕获异常能有效减少内层消耗。一般而言，foreach 循环优先于传统的 for 循环。
 
6. 循环的 i++ 改为 ++i
 
  效率上来说++i 比 i++来的更有效率（后置操作符必须先保存操作数原来的值），但现代编译器上这个影响会很小。
 
 
2. 编译器角度的优化
 
1. 循环展开（loop Unrolling）
 
  重组循环，以便每次迭代多次使用加载的值，让一拍流水线上尽可能满。在流水线中，会因为指令顺序安排不合理而导致CPU等待空转，影响流水线效率。循环展开为编译器进行指令调度带来了更大的空间。
 如下示例：
 
do j = 1,2*n
    do i = 1,m
        A(j) = A(j) + B(i)
    enddo
enddo

Unrolling之后：
do j = 1,2*n by 2
    do i = 1,m
        A(j) = A(j) + B(i)
        A(j+1) = A(j+1) + B(i)
    enddo
enddo
 
2. 循环分块（loop tiling）
 
  由于内存空间有限，代码访问的数据量过大时，无法一次性将所需要的数据加载到设备内存，循环分块能有效提高处理器 cache 上的访存效率，改善数据局部性。（分块应用于外部循环，它会增加计算的空间和时间局部性；分块应与缓存块一起使用，因为这样可以提高最内部软件流水线的效率）。示意如图：
 
 
如下示例：
 
do j = 1,2*n
    do i = 1,m
        A(j)= A(j) + B(i)
    enddo
enddo

Tiling之后：
do jj = 1,2*n by 2
    do i = 1,m
        do j = jj, jj+2-1
            A(j)= A(j)+B(i)
        enddo
    enddo
enddo

Unroll and Jam之后：
do jj = 1,2*n by 2
    do i = 1,m
        A(j)= A(j)+B(i)
        A(j+1)= A(j+1)+B(i)
    enddo
enddo
 
更多关于 loop tiling 的优化方法可参见论文：《Augmenting Loop Tiling with data Alignment for Improved Cache Performance》、《Automatic Tiling of Iterative Stencil Loops》、《面向局部性和并行优化的循环分块技术》
 
3. 循环交换（loop interchange）
 
  内外层循环交换，改善空间局部性，并最大限度地利用引入缓存的数据。对循环进行重新排序，以最大程度地减少跨步并将访问模式与内存中的数据存储模式对齐。
 如下示例：
 
do i=1,n
    do j=1,n
        A(i,j)=B(i,j)*C(i,j)
    enddo
enddo

interchange之后：
do j=1,n
    do i=1,n
        A(i,j)=B(i,j)*C(i,j)
    enddo
enddo
 
4. 循环融合（loop fusion）
 
  将相邻或紧密间隔的循环融合在一起，减少的循环开销和增加的计算密度可改善软件流水线，数据结构的缓存局部性增加，编译器在某些情况下未执行融合，需要手动完成。
 如下示例：
 
for(i = 0; i < size; ++i){
    A(i) = a(i) + b(i);
    c(i) = 2*a(i);
}
for(i = 1; i < size-1; ++i){
    D(i) = c(i) + a(i);
}

fusion之后：
A(0) = a(0) + b(0);
c(0) = 2*a(0);
A(size-1) = a(size-1) + b(size-1);
c(size-1) = 2*a(size-1);
for(i = 1; i < size-1; ++i){
    A(i) = a(i) + b(i);
    c(i) = 2*a(i);
    D(i) = c(i) + a(i);
}
 
5. 循环分裂（loop fission）
 
  将循环分成多个循环，可以在有条件的循环中使用，分为无条件循环和含条件循环。
 如下示例：
 
for(i = 0; i < size; ++i){
    A(i) = a(i) + b(i);
    c(i) = 2*a(i);
    if(temp[i] > data)
        d(i) = a(i);
}

fission之后：
for(i = 0; i < size; ++i){
    A(i) = a(i) + b(i);
    c(i) = 2*a(i);
}
for(i = 0; i < size; ++i){
    if(temp[i] > data)
        d(i) = a(i);
}
 
6. 循环剥离（loop peeling）
 
  剥离 k 次迭代意味着从循环主体中删除这些迭代并将其放置在循环主体之前或之后。
 如下示例：
 
do i=1,n
    Y(i,n) = (1.0 - x(i,1))*y(1,n) + x(i,1)*y(n,n)
enddo

peeling之后：
t2 = y(n,n)
t1 = y(1,n)
y(1,n) = (1.0 - x(1,1))*t1 + x(1,1)*t2
do i=2,n-1
    Y(i,n) = (1.0 - x(i,1))*t1 + x(i,1)*t2
enddo
y(n,n) = (1.0 - x(n,1))*t1 + x(n,1)*t2
 
7. 循环强度减弱（Strength reduction in loops）
 
  使用简单的表达式来替换复杂的表达式。
 例如，除法替换，如下示例：
 
z(i) = x(i)/y(i)
w(i) = u(i)/v(i)

Strength reduction之后：
tmp = 1.0/(y(i)*v(i))
z(i) = x(i)*v(i)*tmp
w(i) = u(i)*y(i)*tmp
 
 
References:
 
https://blog.csdn.net/qq_37436998/article/details/100055770
https://www.cs.colostate.edu/~mstrout/CS553Fall07/Slides/lecture27-tiling.pdf
http://users.cecs.anu.edu.au/~Alistair.Rendell/sc02/module2b.pdf

 
文章目录
 
循环优化概述.
计算必经节点集.
循环查找算法.
1.查找回边.
2.查找循环.
  
  
代码外提.
强度削弱.
删除归纳变量.

 
循环优化概述.
 
什么叫做循环？循环就是程序中那些可能反复执行的代码序列。也正是由于这部分代码序列可能会被反复执行，所以在进行中间代码优化时应着重考虑循环优化，这对提高目标代码的效率起到很大的作用。为了进行循环优化，首先需要确定的是程序流图中哪些基本块构成一个循环。按照结构程序设计思想，程序员在编程时应使用高级语言所提供的结构性的循环语句来编写循环。而由高级语言的循环语句所形成的循环，是不难找出的。对于循环中的代码，可以实行代码外提、强度削弱和删除归纳变量等优化操作。一个中间代码序列的程序流图如下所示：
 
 我们不难看出，其中B${}_2$和B${}_3$分别构成一个循环，{B${}_2$,B${}_3$,B${}_4$,B${}_5$}构成一个范围更大的循环。而我们要进行循环优化，首先需要知道循环在哪里，接下来，我们就一步步给出，整个循环优化的过程。
 
计算必经节点集.
 
 
 
【定义】：若从首结点出发到达结点N${}_j$的每一条通路都必须经过结点N${}_i$，那么我们称N${}_i$是N${}_j$的必经节点，记为N${}_i$ dom N${}_j$，其中dom是dominate的简写。那么N${}_j$所有必经节点的集合，就是N${}_j$的必经节点集，记为D(N${}_j$).
 
 
计算程序流图中必经节点集的算法也是一个不动点算法，通过每一次的迭代来计算一个结点的必经节点集。当程序流图中所有结点的迭代计算结果都不发生改变时，说明已经获得了最终的结果，算法宣布结束。下面我们给出计算必经节点集的算法：
 
 这里我们也给出一个例题，作为计算必经节点集算法的收尾：
 
 【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】
 
 需要注意的是，该算法并不像图中那样，一次迭代计算就可以确定结果，而是需要再一次迭代确认了所有的结点都没有发生变化，才能确定最终结果的。
 
循环查找算法.
 
1.查找回边.
 
 
 
【定义】如果一个程序流图中存在有向边<N${}_i$→N${}_j$>，并且N${}_j$∈D(N${}_i$)，那么我们称有向边<N${}_i$→N${}_j$>是一条回边。
 
 
依旧是我们前一部分给出的实例，考察其中的回边：
 
 【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】
 
 
2.查找循环.
 
求出了程序流图中的回边之后，我们就可以基于回边来查找循环。具体的方法是，若<N${}_i$→N${}_j$>是一条回边，那么该回边构成的循环中的结点包括：N${}_i$和N${}_j$以及所有不经过N${}_i$能够到达N${}_j$的结点。我们以上图中求出的三条回边为例，6→6确定的循环中只包括结点6；7→4确定的循环中包括结点有{4，7，5，6}；4→2确定的循环中包括的结点有{2，4，3，5，6，7}。
 
 【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】
 
 
代码外提.
 
至此我们已经完成了查找循环包含结点的工作，接下来就是要对循环体中的中间代码进行优化了。循环中的某些代码虽然随着循环反复地执行，但其中某些运算的结果并没有发生改变，例如循环中有形如A:=B op C的代码，并且如果B和C都是常数，或者到达它们的定值点都在循环外，那么不管循环多少次，每次计算出来得到的B op C的结果都是不变的，对于这样的不变运算，我们完全可以将其外提到循环以外，避免其随着循环多次计算。如此一来，程序的结果没有发生变化，但程序的运行速率却得到了一定程度的提高，这就是代码外提。
 
 
 
【定义】所谓变量A在程序中某一点d的定值到达了另一点u，或者说变量A的定值点d达到另一点u，指的是程序流图中从d有一条通路到达u，并且通路上没有A的其它定值点。
 
 
实行代码外提时，我们在循环的入口结点之前建立一个新结点(基本块)，称为循环的前置结点，该前置结点以循环的入口结点为其唯一后继。并且原来流图中从循环外引到循环入口结点的有向边，都改为引到该前置结点。如下图所示：
 
 我们考虑的循环结构，其入口结点都是唯一的，从而其前置结点也是唯一的，我们后续进行代码外提时所有外提的代码都将提到前置结点中。下面一段Pascal源程序，是我们叙述代码外提的第一个例子：
 
for I:=1 to 10 do
	A[I,2*J]:=A[I,2*J]+1
 
它对应的中间代码序列如下：
 
 【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】
 
 
考察序号为3和7的语句，因为循环中并没有J的定值点，所以其中J所有引用的定值点都在循环外，从而3和7都是循环不变运算；
考察序号为6和10的语句，分配给数组A的首地址addr(A)的值并不会随着循环的一次次执行而改变，所以6和10也都是循环不变运算。
 
所以我们可以做出这样的判断：3与7、6与10都可以外提到该循环的前置节点中，进行了代码外提之后的中间代码序列如下所示：
 
 【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】
 
 那么问题又来了，是不是在任何情况下，都可以将循环不变运算进行外提呢？我们看第二个例子：
 
 从程序流图中我们不难看出，{B${}_2$,B${}_3$,B${}_4$}构成了一个循环，并且B${}_2$是入口结点，B${}_4$是出口结点。
 
 
 
【定义】出口结点是指循环中具有如下性质的结点：从该结点有一条有向边引到循环外的某结点。
 
 
图中我们也不难看出，基本块B${}_3$中的I:=2语句是循环不变语句，那么我们是否可以直接将这一语句外提到循环以外的前置结点B${}_2^{\prime }$呢？我们暂且认为可以这样做，外提之后的程序流图如下所示：
 
 我们看外提了I:=2这一语句的程序流图，执行到基本块B${}_5$时，变量I的值总会是2，从而J的值也会是2.但我们需要注意的是，在原始的、没有进行I:=2外提的程序流图中，B${}_3$并不是B${}_4$的必经结点。我们在原始流图中考虑X=30、Y=25的情况，这样的情况下B${}_3$是不会被执行的，所以执行到B${}_5$时变量I的值应该是1，从而J的值也应该是1而非2.那么很显然，我们进行了I:=2外提的程序已经改变了程序运行的结果，这必然是不允许的。问题到底出在什么地方呢？其实前面已经点出，B${}_3$并不是循环出口结点B${}_4$的必经节点，再直白一点说，B${}_3$中的代码并不一定会对B${}_4$中的代码起到作用，但如果我们将其外提到循环的前置结点，那么该外提的语句必然是会对B${}_4$产生影响的，这就导致了程序运行结果被改变的风险，我们并不允许这样的风险存在。
 所以从这个例子中我们可以看到，当一个循环不变运算要外提到循环的前置结点时，要求该循环不变运算的语句所在的结点是循环的所有出口结点的必经结点。
 另外，我们注意到，如果循环中变量I的所有引用点都是B${}_3$中I的定值点所能到达的，I在循环中不再有其它的定值点，并且出循环之后也不会再引用变量I的值(即在循环外的循环后继结点入口，变量I不是活跃的)，那么即使B${}_3$不是B${}_4$的必经结点，还是可以将I:=2外提到循环的前置结点，因为这样做并不会改变程序的结果。
 再一个例子，如果我们将上述程序流图中的基本块B${}_2$改为：
 
I:=3
if X<Y goto B3
 
考虑B${}_2$中I:=3外提的问题。
 通过计算必经结点集可以发现，B${}_2$确实是循环出口结点B${}_4$的必经结点，那么我们是否可以将I:=3进行代码外提呢？同样的论述过程，我们姑且认为可以，那么如果程序的执行过程是2-3-4-2-4-5，则执行B${}_5$时的变量I值为2，从而J的值也是2；而如果不进行外提操作，那么同样的执行过程下，I和J的值都应该是3，而非2.这一错误的原因在于，循环中除了B${}_2$以外，B${}_3$也对同一个变量进行了定值。
 所以从这个例子中我们可以看到，当我们将循环不变运算A:=B op C外提时，要求循环中的其它地方不再有A的定值点。
 第三个例子，也是最后一个例子，我们看下面一个程序流图：
 
 考察基本块B${}_4$中循环不变运算I:=2这一语句的外提操作。首先，B${}_4$结点就是整个循环的出口结点，并且B${}_4$结点也是其本身的必经结点；其次整个循环{B${}_2$,B${}_3$,B${}_4$}中也没有第二个对于变量I定值的语句。那么我们是否可以将这一语句外提呢？同样的方法，我们还是暂且认为这一语句可以外提，再比较对于同一个执行过程，外提前后的执行结果。我们考虑X=0、Y=2的情况，循环的执行流程是2-3-4-2-4-5，代码外提前，程序的执行结果为J=2；而代码外提后，程序的执行结果为J=3.
 通过这个例子，我们看到，当将循环不变语句A:=B op C进行代码外提时，要求循环中所有对于A的引用点都是并且仅仅是这一定值语句所能到达的。上述的例子中，能够到达A:=I+1这一对于I的引用的定值语句，不仅有B${}_4$中的I:=2，还有B${}_1$中的I:=1.
 最后我们给出查找循环L中不变运算的算法：
 
 以及代码外提算法：
 
 
强度削弱.
 
我们要介绍的第二种循环优化技术叫做强度削弱。强度削弱是将程序中执行时间较长的运算替换为执行时间较短的运算。例如，最常见的就是将循环中的乘法运算用递归的加法运算来代替。我们考察前面经过了代码外提的示例流图：
 
 【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】
 
 不难看出{B${}_2$,B${}_5$}是一个循环，并且B${}_2$是循环的入口结点。我们注意序号为13的语句，这里的变量I是一个递归赋值的变量，每循环一次，它增加一个常量1。另外，序号为4和8的语句在计算T${}_2$和T${}_6$时，都会使用I的值，并且T${}_2$和T${}_6$都是I的线性函数，每循环一次，它们都增加一个常量10.因此，如果把4和8外提到循环的前置结点中，并且在13号语句之后添加上为T${}_2$和T${}_6$增加常量10的语句，程序的运行结果依然不变。
 
 【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】
 
 经过上述变换，循环中原来的乘法运算4和8被替换为了在前置结点中进行一次初始化的乘法运算(计算初值)以及在循环中递归赋值的加法运算(4’)和(8’).不仅加法运算一般来说比乘法运算快，而且这种在循环前计算初值，再于循环末尾进行常量递增的运算，可以利用变址器提高运算速度，从而使运算的强度得到削弱。所以我们称这种优化技术为强度削弱。
 强度削弱不仅对于乘法可以实行，对于加法也可以实行。例如上图中序号为5和9的语句，T${}_3$与T${}_7$的计算中引用到了T${}_2$和T${}_6$，并且T${}_2$和T${}_6$也是递归赋值的变量，每循环一次，它们的值就增加一个常量10.而T${}_3$与T${}_7$的另一个运算对象都是循环不变量，所以每循环一次，T${}_3$与T${}_7$的值就增加一个常量10.很自然地，我们会想到对它们进行强度削弱，即外提一个初始化语句，在循环的末尾添加常量递增语句，得到的优化结果如下所示：
 
 【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】
 
 从上面的例子中我们可以看到：
 
如果循环中有A的递归赋值A:=A±b${}_1$，并且循环中另一个变量B的赋值运算可以写为B:=k*A±b${}_2$的形式，那么对于B的赋值运算，我们可以进行强度削弱；
进行强度削弱之后，循环中可能会出现一些新的无用赋值，例如上图中的(4’)和(8’)，因为循环中不再使用T${}_2$和T${}_6$，那么如果循环出口之后它们也不是活跃变量，是完全可以删除的；
循环中下标变量的地址计算是相当耗费时间的，这里介绍的方法对削弱下标变量地址计算的强度是非常有效的。前面的例子中，数组是二维的，如果我们考察一个更高维度的数组，将会进一步看到强度削弱的作用。对于下标变量地址计算来说，强度削弱实际上就是实现下标变量地址的递归计算。
 
删除归纳变量.
 
我们要介绍的最后一种循环赋值技术叫做删除归纳变量。讲述具体的流程之前，首先给出基本归纳变量以及归纳变量的定义：
 
 
 
【定义】基本归纳变量：循环中对于变量A的赋值只有唯一的、形如A:=A±b${}_1$的赋值，那么称A为循环中的基本归纳变量；
 【定义】归纳变量：如果A是一个基本归纳变量，循环中对于B的赋值总是可以化归为A的同一个线性函数，即B:=k*A±b${}_2$，那么我们称B是一个归纳变量。
 
 
考察进行了代码外提之后的示例程序流图：
 
 【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】
 
 不难发现变量I是循环{B${}_2$,B${}_3$}的基本归纳变量，T${}_2$和T${}_6$是循环中与I同族的归纳变量，再继续发掘，T${}_3$和T${}_7$也是与I同族的归纳变量。
 一个基本归纳变量除了用于自身的递归赋值以外，往往只在循环中用于计算其他的归纳变量和控制循环的进行。经过了强度削弱之后的示例程序流图如下所示：
 
 【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】
 
 关注基本块B${}_3$可以发现变量I除了用于自身的递归赋值以外，只用于控制循环的进行。这时，我们可以使用与I同族的某一个归纳变量来代替I控制循环的进行，从而删除变量I.例如，我们选取T${}_3$(T${}_7$与T${}_3$都在循环中被引用，所以是一样的，而T${}_2$和T${}_6$在循环中没有被引用)来代替I， 由于T${}_3$可以写为10*I+T1，并且循环的控制条件为I>10，所以用T${}_3$代替了I之后，控制条件变为了T3>100+T1.为了不在每一次进行判断时都计算100+T${}_1$的值，我们引入新的临时变量R:=100+T${}_1$，所以序号为2的if语句改写为：
 
R:=100+T1
if T3>R goto (15)
 
然后我们就可以删去变量I了，这一优化技术称为删除归纳变量，也叫变换循环控制条件。如果我们假定T${}_2$和T${}_6$在循环出口之后也不是活跃的，那么我们完全可以删去这两个临时变量(因为它们在循环中也没有被使用)。但如果我们在选择代替I的变量时选择了T${}_2$或T${}_6$，那么(4’)或(8’)就不能删除了，最后完成删除归纳变量的中间代码如下：
 
 【下图引用自中南大学徐德智老师的编译原理2020年授课PPT】
 
 删除归纳变量是在强度削弱之后进行的。我们在下面统一给出强度削弱和删除归纳变量的算法：
 

循环是我们在写代码时经常用到的一种结构，而往往在考虑性能优化时，循环的优化能带来很大的收益，特别是当我们不得不循环多次时，如果没对性能进行优化，那毫无疑问会带来性能的负担。
 
循环的类型
 

1.for循环
 
for循环可能是我们最常用的循环，相对于其他种循环来说，for循环将初始化，判断终止条件，判断值的改变明显地写在了括号内，更为直观。
 
for(var i=0;i<sum;i++){
    //...
}
 
2.while循环
 
var i=0;
while(i<sum){
    // ...
    i++;
}
 
3.do...while循环
 
var i=0;
do{
    // ...
    i++;
}while(i<sum)
 
4.for-in
 
for-in循环一般用于遍历对象中的key，一般不会使用for-in，因为for-in循环会对性能有更多消耗，会在下文提及原因
 
for(var prop in object){
    // ...
}
 
5.for-of
 
for-of循环也可用于一个有Iterator的对象，如数组，具体可见ES6学习笔记（六）Iterator接口，与for-in不同的是，for-of可以使用break和return语句来跳出循环。然而，虽然其性能消耗比for-in少，但是其性能消耗相对于前三种来说还是更多的，将在下文提及原因
 
for(var val of arr){
    // ...
}
 
循环类型的性能
 

在对上面的几种循环遍历数组进行测试后，可以发现for-in循环和for-of循环的速度明显慢于其它三种，对于for-in来说，需要同时遍历实例和原型链，在遍历上的消耗更多，而对于for-of来说，需要去调用Symbol.iterator函数来构建一个迭代器，自动调用next()，且不向next()传入任何值，在接收到done:true之后停止，自然回比前三种方法慢。
 
（这里的性能测试我使用了console.time()和console.timeEnd()之间的时间差距来比对，因为会受浏览器等各种因素影响，上面的结论是我测试了多组数据后得出的结论）
 
let arr = [];
arr.length = 10000;
arr.fill(1);

(function() {
    console.time('for循环');
    for (var i = 0; i < arr.length; i++) {
        // ... 相同操作
    }
    console.timeEnd('for循环')
})();

(function() {
    console.time('while循环')
    var i = 0;
    while (i < arr.length) {
        // ...相同操作
        i++;
    }
    console.timeEnd('while循环')
})();

(function() {
    console.time('do-while');
    var i = 0;
    do {
        // ...相同操作
        i++;
    } while (i < arr.length)
    console.timeEnd('do-while');
})();

(function() {
    console.time('for-in');
    for (var i of arr) {
        // ...相同操作
    }
    console.timeEnd('for-in');
})();

(function() {
    console.time('for-of');
    for (var i of arr) {
        // ...相同操作
    }
    console.timeEnd('for-of');
})();
 
下面是其中一次的执行结果
 
 
性能优化
 

要对循环的性能进行优化，只能减少其每次循环的工作量，或者减少循环的次数
 
减少每次循环工作量
 
首先看看for遍历一个数组每次循环的工作量
 
for(var i=0;i<arr.length;i++){
    //...操作
}
 
1.查找一次arr的长度
 
2.比较一次i和arr.length的值
 
3.判断比较结果为true或false
 
4.执行for循环内的自增
 
5.i变量的自增（如果步骤3中判断结果为true的话）
 
存储arr.length的值
 
每次我们都要去查找一次length的值，那么我们为什么不先在设置初始条件时使用一个变量来存储arr的length值呢。
 
for(var i=0,len=arr.length;i<len;i++){
    //...操作
}
 
这样做的好处是，arr至少是在当前作用域链的下一个位置，如果我们把arr.length放在当前一个局部变量中，在查找该值时在作用域链上查找的步数就会减少，所以能有效地减少性能的消耗。这样上面的步骤就变为
 
1.比较一次i和len的值
 
2.判断比较结果为true或false
 
3.执行for循环内的自增
 
4.i变量的自增（如果步骤3中判断结果为true的话）
 
倒序循环
 
倒序循环是一种通用的循环优化方法，我们通过代码来理解
 
for(var i=arr.length;i--;){
    //...操作
}
 
此时每次循环的步骤变为
 
1.i==true的判断（i为0时等式即成立）
 
2.i变量的自减
 
3.执行循环内的操作
 
可以看到，倒序操作实际上就是将i和数组长度的比较和判断为true或false这两步合并，以此来得到性能上的优化。
 
减少循环次数
 
达夫设备
 
达夫设备实际上就是在一次循环中完成多次循环的事情，以达到减少循环次数的作用，看看下面的代码（代码源自《高性能JavaScript》）
 
// items为要遍历的数组，process为对数组内成员的操作方法

var i=items.length%8;
while(i){
    process(items[i--]);
}

i=Math.floor(items.length/8);

while(i){
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
}
 
这里通过取长度除以8的余数，先进行这个余数次数的循环，然后之后每次循环执行8次自减操作，相当于一次循环中完成八次循环的操作，以此来达到减少循环的次数的目的
 
基于函数的迭代
 

很多框架中都封装了迭代循环的方法，包括JavaScript本身也有原生的数组迭代方法，看看下列实例（代码原则《高性能JavaScript》）
 
// 原生数组方法
items.forEach(function(value, index, array) {
    process(value);
});

// YUI 3
Y.Array.each(item, function(value, index, array) {
    process(value);
});

// jQuery
jQuery.each(items, function(index, value) {
    process(value);
});

// Dojo
dojo.forEach(items, function(value, index, array) {
    process(values);
});

// prototype
items.each(function(value, index) {
    process(value);
});

// MooTools
$each(items, function(value, index) {
    process(value);
});
 
虽然函数迭代的方法较为方便，但从性能上来说，函数迭代需要去调用函数，性能上的消耗会比普通的循环更多，所以在追求性能的情况下不适合使用函数迭代的方法。
 

参考自《高性能JavaScript》

循环通常是数据并行应用的最密集计算段，因此循环优化直接影响性能。当面对嵌套循环时，分配给线程的计算粒度将直接影响性能。循环转换如Fission（循环裂变）与Fusion（循环融合）的嵌套式循环可促使并行化，并提高工作效率。
 
本文就几种循环优化的方法与多面体模型的调度进行简要阐述（因为LZ已经被这些循环优化搞得痛不欲生了）。
 
 
Loop fusion
 
顾名思义，该变换令循环进行了融合。如图所示，原始代码是两个for循环，变化之后，对两个循环中 i、j 相同的范围进行了融合。
 
 我们为了把该变换映射或者说调度到多面体模型中去，需要产生调度树。
 
举例如下：
 
 有这样一段用TC写的代码，语句S、T分别为循环语句。其融合操作表述如下：
 
 Band 操作将S、T所对应的迭代向量进行了融合。
 
 
Loop tiling
 
Loop tiling/blocking 的意思是分块，可以将循环的迭代空间划分为更小的块，以帮助确保循环中使用的数据在重用之前一直保存在缓存中。循环迭代空间的划分导致将大数组划分为更小的块，从而将被访问的数组元素匹配到缓存大小中，增强缓存重用，消除缓存大小需求。
 
平常的循环：
 
for(i=0; i<N; ++i){
  ...
}
 
变换后的循环，拥有一个全新的 block 大小B：
 
for(j=0; j<N; j+=B){
  for(i=j; i<min(N, j+B); ++i){
    ....
  }
}
 
更具体的例子：
 
 下面是一个矩阵向量乘法的例子。有三个数组，每个数组有100个元素。代码没有将数组划分为更小的大小。
 
  int i, j, a[100][100], b[100], c[100];
  int n = 100;
  for (i = 0; i < n; i++) {
    c[i] = 0;
    for (j = 0; j < n; j++) {
      c[i] = c[i] + a[i][j] * b[j];
    }
  }
 
当我们应用循环分块，使用2 * 2块，代码变为：
 
  int i, j, x, y, a[100][100], b[100], c[100];
  int n = 100;
  for (i = 0; i < n; i += 2) {
    c[i] = 0;
    c[i + 1] = 0;
    for (j = 0; j < n; j += 2) {
      for (x = i; x < min(i + 2, n); x++) {
        for (y = j; y < min(j + 2, n); y++) {
          c[x] = c[x] + a[x][y] * b[y];
        }
      }
    }
  }
 
原来的循环迭代空间n×n。数组的访问块(i, j)也是n×n。当n过大和机器的缓存容量太小,访问数组元素的循环迭代(例如,i = 1, j = 1到n)可能交叉的高速缓存线路,导致缓存丢失。