c++ - 附加条件语句使程序更快

Question

看完Why is it faster to process a sorted array than an unsorted array? ，我在主循环中添加了一个额外的测试。似乎这个额外的测试使程序更快。

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
         data[c] = std::rand() % 256;

    //Don't sort the array
    //std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];

            //With this additional test, execution becomes faster
            if (data[c] < 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

通过附加测试我得到了大约 4.2 秒，在没有附加测试的情况下我得到了 18 秒。额外的测试不应该让程序变慢而不是变快吗？

Answer 1

因为那个特别的额外的测试，这个的等效代码:

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
       if (data[c] >= 128)
            sum += data[c];

        //With this additional test, execution becomes faster
        if (data[c] < 128)
            sum += data[c];
     }
}

变成这样:

for (unsigned i = 0; i < 100000; ++i)
{
  // Primary loop
  for (unsigned c = 0; c < arraySize; ++c)
  {
    sum += data[c];//because exactly one condition is guaranteed to be
                   //true in each iteration (in your code)!
                   //the equivalent is as if there is no condition at all!
  }
}

这就是它变得更快的原因。

这是因为不寻常额外的测试和相同主体，编译器能够优化代码，删除if条件.当你有一个 if 时，编译器就不能这样做。

尝试这样写:

sum -= data[c]; //the body is not identical anymore!

在 if 条件之一中。我确信编译器不会能够优化代码。它现在应该发出较慢的机器代码。

---

请注意，外部循环可以完全省略，尽管它不太依赖于额外的测试::

// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
    sum += 100000 * data[c];
}

或者，这个:

// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
    sum += data[c];
} 
sum = 100000 * sum; //multiple once!