循环展开技术

循环展开技术
转载：

循环一直令我们头疼，因为循环体内总是隐藏着热点！请读者回顾上一小节中的示例代码。

for(i = 0; i < 10; i++){
        temp = temp * (array[i]);
}

以上循环体的汇编代码如图9-7所示。观察其汇编代码，我们很容易发现，由于循环体的内容相对简单，以至于这个循环实际执行过程中差不多一半的指令 都在为检查循环执行的条件而服务。如果计算循环索引和测试循环条件的循环开销部分所占比重过大，这时就可以考虑使用一种被称作"循环展开"的方式来优化代 码。所谓循环展开就是通过在每次迭代中执行更多的数据操作来减小循环开销的影响。其基本思想是设法把操作对象线性化，并且在一次迭代中访问线性数据中的一 小组而非单独的某个。这样得到的程序将执行更少的迭代次数，于是循环开销就被有效地降低了。

为了便于读者理解，下面先来举一个实际中的例子。笔者在另外一本讲解数字图像处理编程的书中曾经介绍过对彩色图像取反色的方法。假设有一幅24位真 色彩的数字图像为待处理对象，那么常识告诉我们该图像的每一个像素都由三个分量组成，即R分量、B分量和G分量，且每个分量占8位。如果将R、G和B三个 分量的实际值定量地看作整数，那么它们的取值范围是0～255之间的整数。图像取反色处理，简单说来，就是将整幅彩色图像的每个像素的每个分量都被255 减。下面这个函数实现了图像的取反色处理功能。其中，参数int width表示图像的宽（以像素计），参数int height表示图像的高（以像素计），参数BYTE * pixel是待处理的像素数组，而参数BYTE * tempPixel用来存储结果图像。

void Negative(BYTE * pixel, BYTE * tempPixel, int width, int height)
{
        int i = 0;
        int sum = width * height * 4;
        memcpy(pixel, tempPixel, sum);

        for(i = 0; i < sum; i++)
        {
            tempPixel[i] = 255 - tempPixel[i];
        }
}

易见，上面的函数中循环体部分过于简单，这显然是相当不划算的。于是更加明智的方法是采用循环展开的方式来改写上面的函数，改写结果如下：

void Negative(BYTE * pixel, BYTE * tempPixel, int width, int height)
{
        int i = 0;
        int sum = width * height * 4;
        memcpy(pixel, tempPixel, sum);

        for(i = 0; i < sum; i+=3)
        {
            tempPixel[i] = 255 - tempPixel[i];
            tempPixel[i+1] = 255 - tempPixel[i+1];
            tempPixel[i+2] = 255 - tempPixel[i+2];
        }
}

上面这个例子在实际应用中是非常典型的，优化结果将循环次数变为了原来的三分之一。但这也是一个特例，只所以认为它是特例，那是因为我们设定的图像 是24位真色彩的，因此图像中的每个像素都只包括三个分量，所以用于表示图像的色彩分量数组就刚好可以被3整除。但是实际中更多的情况是，待处理的数组不 一定能被3整除。如果这时还是希望能够对循环进行3次展开，那么该如何处理呢。可以从两个方面来解决这个需求。首先，要确保第一次循环不会超过数组的界 限。这并不难做到，对于长度为n的数组，可以将循环限制设为n-2。然后，保证只有当循环索引i

#include

void function(int array[], int *dest)
{
        int i;

        int temp = 1;
        int limit = 10 -2;

        for(i = 0; i < limit; i+=3){
            temp = temp * (array[i])* (array[i+1])* (array[i+2]);
        }

        for(; i < 10; i++){
            temp = temp * array[i];
        }
        *dest = temp;
}

void main()
{
        int array[10] = {1, 1, 1, 2, 2, 3, 3, 3, 4, 1};

        int number = 1;
        int * dest = &number;

        function(array, dest);

        printf("%d\n", *dest);
}

将这种方法推广到更加通用的层面上，如果循环展开k次，就可以把上限设为n-k+1，那么最大循环索引i+k-1将会比n小。然后，再加上第二个循环，以每次处理一个元素的方式处理数组的最后几个元素。

循环展开技术的好处在于它能减小循环开销的影响。但它也不是没有缺点的，天下没有免费的午餐！首先，循环展开增加了生成的目标代码的数量，这很容易 理解，因为循环体在源代码级别就已经变得庞大。读者可以试想它们被翻译成目标代码时的情况。为了验证这一点，读者可以使用Visual C++来对比使用循环展开前后循环体的汇编代码的长度，验证结果将表明循环展开对目标代码的长度的确有很大的影响。当然，在我们所举的例子中，循环展开所 要付出的代价都是比较小的。当然这并不能概括其他所有的情况，因此这个空间换时间的折中最优位置还需要针对具体问题来做具体的分析。

还有一个规律应当是被普遍认同的，那就是循环展开的程度越高，循环执行开销所占的比例就会越小。例如，对一幅24位真色彩图像进行取反色处理，假设 该图像由16个像素组成，也就是说，图像的像素分量数组中应该有16×3=48个元素。当进行1次循环展开时，循环需要执行48次；如果进行3次循环展 开，那么循环将需要执行16次；如果进行8次循环展开，那么循环就只需要进行6次。这是一个最基本、最普遍的认识。但仍然要说明，效率提升的效果还和循环 体内执行的操作类型有着很大的关系，并不是所有计算都会取得理想中的效果。这与CPU的功能单元设计有着密切的关系，因为这是一个比较复杂的话题，这里将 不对其进行深入研究。但是一个客观的规律是如果数组比较长，那么执行循环展开的效果将较为明显，此时性能通常会随着展开度的增加而得到显著的改进，例如， 我们所举的图像取反色操作的例子。但是如果数组较短，那么增加展开度并不会得到线性的性能改进，例如，实验表明当数组长度为31时，展开度为3将可以得到 最好的性能。

使用循环展开时一方面要考虑实际待处理数组的长度，并由此选择一个较好的展开度；另一方面要综合考虑这个展开度对时空开销比例的影响，在尽量不会使 目标代码空间消耗激增的前提下获得最高的时间收益。另外，也可以让编译器为我们完成这些工作。通常，编译器可以很容易地执行循环展开，但这需要设定其优化 级别足够高，所以程序员也可以选择让编译器来完成这个工作。当然，我们曾经提醒过读者，在开发阶段并不适合将优化级别设置得过高，因此如果你希望让编译器 执行循环展开，那么最好等到软件开发完成之后。