65.9K
CodeProject 正在变化。 阅读更多。
Home

代码优化教程 - 第一部分

Razvan Aguridan
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.78/5 (59投票s)

2012年5月27日

CPOL

8分钟阅读

viewsIcon

152204

downloadIcon

758

新手优化教程。

引言

本文旨在向软件开发者介绍优化技术。为此，将探讨不同的优化技术。

作为第一步，我选择了一个易于理解的算法，并应用了各种优化技术：

我们将解决的问题是3n+1问题（详情）：对于1到1000000之间的每个数字n，应用以下函数

直到数字变为1，计算应用函数的次数。

该算法将针对1到1000000之间的所有数字执行。不会从键盘读取输入数字，程序将打印结果，以及计算结果所需的执行时间（以毫秒为单位）。

测试机器是一台笔记本电脑，配置如下：AMD Athlon 2 P340 双核 2.20 GHz，4 GB RAM，Windows 7 Ultimate x64。

实现使用的语言：C# 和 C++（Visual Studio 2010）。

先决条件

不适用 

同一问题的不同实现

初始实现版本：对于1到1000000之间的每个数字，将应用上述算法，生成一个数字序列，直到n变为1。将计算达到1所需的步数，并确定最大步数。

C++ 代码

for (int i = nFirstNumber; i < nSecondNumber; ++i)
{
    int nCurrentCycleCount = 1;
    long long nNumberToTest = i;
    while (nNumberToTest != 1)
    {
        if ((nNumberToTest % 2) == 1)
        {
            nNumberToTest = nNumberToTest * 3 + 1;
        }
        else
        {
            nNumberToTest = nNumberToTest / 2;
        }
        nCurrentCycleCount++;
    }
    if (nCurrentCycleCount > nMaxCycleCount)
    {
        nMaxCycleCount = nCurrentCycleCount;
    } 
}

C# 代码

for (int i = FirstNumber; i < SecondNumber; ++i)
{
    int iCurrentCycleCount = 1;
    long iNumberToTest = i;
    while (iNumberToTest != 1)
    {
        if ((iNumberToTest % 2) == 1)
        {
            iNumberToTest = iNumberToTest * 3 + 1;
        }
        else
        {
            iNumberToTest = iNumberToTest / 2;
        }
        iCurrentCycleCount++;
    }
    if (iCurrentCycleCount > MaxCycleCount)
    {
        MaxCycleCount = iCurrentCycleCount;
    }
}

我编译了Debug和Release版本，以及32位和64位版本。然后我运行了每个可执行文件100次，并计算了计算所需时间的平均值（毫秒）。

这是结果：

C++ DebugC++ ReleaseC# DebugC# Release
x86版本6882.91 6374.50 6358.41 5109.90
x64版本1020.78 812.71 1890.36 742.28

表中首先值得注意的是，32位程序版本比64位版本慢5到7倍。这是因为在x64架构上，一个寄存器可以容纳一个long long变量，而在x86上我们需要2个寄存器。这意味着在x86上，long long值的操作速度较慢。因此，本文不再讨论32位版本。

第二个值得注意的地方是Release和Debug版本之间的差异，并且对于C#来说，这种差异比C++更大。

另一个观察结果是C# Release版本和C++ Release版本之间的差异。这与之前的观察结果相结合，让我相信C#编译器比C++编译器执行的优化更好（甚至可能采用了我们稍后将要讨论的一些优化技术）。

我将应用的第一个优化与通过替换常规方法以非传统方式执行数学运算以使其更快相关。

如果我们查看上面的代码，我们会发现只有3个复杂的数学运算：模2运算（%）、乘以3（*）和除以2（/）。

我将优化的第一个操作是模2。我们知道所有数字在内存中都表示为一系列位。我们也知道，奇数的表示总是以最后一位为1（5=101，13=1101，等等），偶数的表示总是以最后一位为0（6=110，22=10110）。因此，如果我们能够获取一个数字的最后一位并将其与0进行比较，我们就知道该数字是奇数还是偶数。为了获取一个数字的最后一位，我使用了按位AND运算符（&）。

在C++中，替换

if ((nNumberToTest % 2) == 1)

用

if ((nNumberToTest & 0x1) == 1)

在C#中，替换

if ((iNumberToTest % 2) == 1)

用

if ((iNumberToTest & 0x1) == 1)

这是结果：

C++ DebugC++ ReleaseC# Debug C# Release
922.46 560.86 1641.41 714.10

C++ Release版本从这次优化中获益最多。C++ Release和Debug版本之间的改进差异让我相信，编译器在新优化算法中能够移除更多指令。

C#似乎并未从这次优化中获益太多。

下一个我将尝试优化的操作是除以2。如果我们再次查看数字的二进制表示，我们可以观察到，当我们将数字除以2时，我们会丢弃数字的最后一位，并在剩余位的前面添加一个0位。例如，5（=101）/ 2 = 2（=010），13（=1101）/ 2 = 6（=0110），6（=110）/ 2 = 3（=011），等等。我将用产生相同结果的按位右移操作来替换此操作。

在C++中，替换

nNumberToTest = nNumberToTest / 2;

用

nNumberToTest = nNumberToTest >> 1;

在C#中，替换

iNumberToTest = iNumberToTest / 2;

用

iNumberToTest = iNumberToTest >> 1;

这是结果：

C++ DebugC++ ReleaseC# Debug C# Release
821.58 555.96 1432.01 652.11

C++ Debug、C# Debug、C# Release版本从这次优化中获得了65到200毫秒的提升。

C++ Release版本由于编译器已经执行了此优化，因此几乎没有获得任何收益。

最后一个耗时较多的数学运算是乘以3。对此操作我们唯一能做的就是将其替换为加法。

在C++中，替换

 nNumberToTest = nNumberToTest * 3 + 1;

用

 nNumberToTest = nNumberToTest + nNumberToTest + nNumberToTest + 1;

在C#中，替换

 iNumberToTest = iNumberToTest * 3 + 1;

用

 iNumberToTest = iNumberToTest + iNumberToTest  + iNumberToTest  + 1;

这是结果：

C++ DebugC++ ReleaseC# Debug C# Release
820.84 548.93 1535.28 629.89

最大的性能提升可以在C# Release版本中观察到，其次是C++ Release版本。

C# Debug版本性能下降，因为当前软件版本执行的指令比以前多，并且编译器无法优化这些指令（因为我们可能需要在任何一条指令上设置断点，所以无法将其替换为其他内容）。

基于处理器实现的一些特殊指令，我们可以进行最后一种数学优化。这些指令称为条件移动指令。为了让编译器生成条件移动指令，我将IF语句（检查数字是奇数还是偶数）替换为三元运算符（?:）。

为了实现上述优化，我们需要修改问题陈述。如果数字是偶数，则将其除以2（按问题要求）。如果数字是奇数，则可以表示为2 * n + 1。将这些修改应用于函数初始形式，我们将得到

 

从上面的等式可以看出，我们可以将算法的2步合并为1步。我们将重写算法，以便计算下一个要测试的数字的值，假设当前值是偶数。然后，我们将保存当前要测试数字的最后一位的值。如果该值为真，我们将增加当前周期计数，并将当前数字+1添加到要测试的下一个数字的值。（注意：此优化将在接下来的文章中，当谈论SSE时，变得非常重要。）

在C++中，替换：

if ((nNumberToTest % 2) == 1)
{
 nNumberToTest = nNumberToTest * 3 + 1;
}
else
{
 nNumberToTest = nNumberToTest / 2;
}
nCurrentCycleCount++;

用

int nOddBit = nNumberToTest & 0x1;
long long nTempNumber = nNumberToTest >> 1; 
nTempNumber += nOddBit?nNumberToTest + 1:0;
nCurrentCycleCount += nOddBit?2:1;
nNumberToTest = nTempNumber;

在C#中，替换

if ((iNumberToTest % 2) == 1)
{
    iNumberToTest = iNumberToTest * 3 + 1;
}
else
{
    iNumberToTest = iNumberToTest / 2;
}
iCurrentCycleCount++;

用

bool bOddBit = (iNumberToTest & 0x1) == 0x1;
long iTempNumber = iNumberToTest >> 1;
iTempNumber += bOddBit ? iNumberToTest + 1 : 0;
iCurrentCycleCount += bOddBit ? 2 : 1;
iNumberToTest = iTempNumber;

这是结果：

C++ Debug C++ Release C# Debug  C# Release 
1195.38 462.21 1565.01 752.92 

两个Debug版本都显示出性能下降，因为与之前的代码版本相比，我们现在执行了更多的指令，并且编译器无法优化它们。

C# Release版本之所以显示性能下降，是因为C#中没有条件移动指令。

C++ Release版本速度的提升证明了这类指令的强大威力。

可以注意到我用递归解决了这个问题。对于这个问题，递归算法会非常慢：最大周期长度为525，假设大多数数字的周期长度约为150（只是猜测，并未实际验证），如果我们有150次递归调用来处理1到1000000之间的每个数字，我们将执行150000000次调用。这显然不是一个小数字，而且由于调用函数需要大量时间，递归肯定不是解决这个问题的最佳方案。

关注点

是时候得出结论了。

  1. 模运算和除法运算耗时很长，应该用其他方法替换。
  2. 尝试分析问题并获得问题的替代表示。
  3. 尝试从代码中消除IF语句，如果它们的唯一目的是根据条件设置某些值。

下一次的主题将是关于如何使用C#和C++中的线程来提高程序速度。

历史

  • 2012年5月27日 - 首次发布。
  • 2012年5月28日 - 我想感谢anlarke指出了文章中可以改进的地方，并提交了他的代码（C++ Debug时间：546.76毫秒，C++ Release时间：386.35毫秒）。我还想感谢Reonekot对WoW话题的澄清。他是对的，性能问题是由于寄存器是32位（x86）和64位（x64）造成的。
© . All rights reserved.