c++ - 某些代码在给定相同输入的情况下似乎仅仅因为它处于循环中就可能花费更多时间来运行？

Question

前言/上下文:我刚刚开始学习 C++，并决定编写一些代码，将单个量子位门应用于量子寄存器，其中寄存器保存在一个称为振幅的数组中，以及单个量子位的四个元素门是a，b，c，d。我尝试编写一个版本来避免出现在我的第一遍中的 if 语句，并且令我最初高兴的是，它似乎有轻微的性能增强(~10%)。如果我更改寄存器中的量子位数量或门的目标量子位，我会得到类似的结果。然后，我尝试制作一个循环，为各种目标量子位执行时序比较，但发生了一些非常奇怪的事情(至少对我而言)。我编写的替代函数避免了 if 语句，其执行时间加倍(从 ~0.23 秒到 0.46 秒)，而带有 if 语句的函数的执行时间不受影响(~0.25 秒)。这引出了我的问题:

如何编写代码，在两种情况下给定相同的输入时，在迭代这些输入的循环内执行更长时间？

例如，如果我运行一个给定 25 个量子位和目标量子位 1 的测试，则“否如果”函数获胜。然后，如果我编写一个 while 循环来对从 1 开始的每个目标值进行 25 个量子位的比较，“no if”函数即使在第一次迭代中接收到与先前情况相同的输入时也会花费双倍的时间来执行.有趣的是，如果我只包含 while 循环并通过在 while 语句中放置“True”或通过注释掉增量语句 target+=1 使其成为无限 while 循环，则该函数不再需要双倍时间。据我所知，这种现象需要循环和增量。

下面的代码，以防这是一个我不太熟悉的新语言的简单编码错误。我使用的是具有所有默认设置的 Visual Studio 2017 社区版，但我使用的是“发布”版本以加快代码执行速度。注释掉 while 语句和相应的右大括号会使“no if”时间加倍。

#include "stdafx.h"
#include <iostream>
#include <time.h>
#include <complex>

void matmulpnoif(std::complex<float> arr[], std::complex<float> out[], int numqbits, std::complex<float> a,
std::complex<float> b, std::complex<float> c, std::complex<float> d, int target)
{
    long length = 1 << (numqbits);
    long offset = 1 << (target - 1);
    long state = 0;
    while (state < length)
    {
        out[state] = arr[state] * a + arr[state + offset] * b;
        out[state + offset] = arr[state] * c + arr[state + offset] * d;
        state += 1 + offset * (((state%offset) + 1) / offset);
    }
}

void matmulpsingle(std::complex<float> arr[], std::complex<float> out[], int numqbits, std::complex<float> a,
std::complex<float> b, std::complex<float> c, std::complex<float> d, int target)
{
    long length = 1 << (numqbits);
    int shift = target - 1;
    long offset = 1 << shift;
    for (long state = 0; state < length; ++state)
    {
        if ((state >> shift) & 1)
        {
            out[state] = arr[state - offset] * c + arr[state] * d;
        }
        else
        {
            out[state] = arr[state] * a + arr[state + offset] * b;
        }
    }
}

int main()
{
    using namespace std;
    int numqbits = 25;
    long arraylength = 1 << numqbits;
    complex<float>* amplitudes = new complex<float>[arraylength];
    for (long i = 0; i < arraylength; ++i)
    {
        amplitudes[i] = complex<float>(0., 0.);
    }
    amplitudes[0] = complex<float>(1., 0.);
    complex<float> a(0., 0.);
    complex<float> b(1., 0.);
    complex<float> c(0., 0.);
    complex<float> d(1., 0.);
    int target = 1;
    int repititions = 10;
    clock_t startTime;
    //while (target <= numqbits) {
        startTime = clock();
        for (int j = 0; j < repititions; ++j) {
            complex<float>* outputs = new complex<float>[arraylength];
            matmulpsingle(amplitudes, outputs, numqbits, a, b, c, d, target);
            delete[] outputs;
        }
        cout << float(clock() - startTime) / (float)(CLOCKS_PER_SEC*repititions) << " seconds." << endl;
        startTime = clock();
        for (int k = 0; k < repititions; ++k) {
            complex<float>* outputs = new complex<float>[arraylength];
            matmulpnoif(amplitudes, outputs, numqbits, a, b, c, d, target);
            delete[] outputs;
        }
        cout << float(clock() - startTime) / (float)(CLOCKS_PER_SEC*repititions) << " seconds." << endl;
        target+=1;
    //}
    delete[] amplitudes;
    return 0;
}

Answer 1

不幸的是，我还不能发表评论，所以我会在这里发表这个，尽管它可能不是一个完整的答案。

总的来说，你提出的问题很难。编译器执行优化，这两种情况是不同的代码，因此它们得到不同的优化。

在我的机器上，例如(Linux，GCC 7.3.1)，只启用了 -O3，matmulpnoif总是更快(4.8s vs 2.4s 或 4.8s vs 4.2s - 这些时间不是用 clock() 测量的，取决于循环是否存在)。如果我不得不猜测在这种情况下会发生什么，编译器可能会意识到 offset始终为一，并优化余数操作(除法是迄今为止您在那里进行的最昂贵的操作)。但是，它也可能是其他事物的组合。

还有一点要注意，clock()不应用于测量时间。它计算时钟滴答的数量，例如，如果您将代码并行化到 2 个线程，则该数字将是时间的两倍(假设您的代码不会在任何地方等待 - 这在我的机器上似乎不是这种情况)。如果你想测量时间，我建议你看看<chrono> , high_resolution_clock应该做的伎俩。

另一方面，不需要一直分配和释放输出数组，你可以简单地使用一个，这样你会浪费更少的时间。但最重要的是，如果你使用的是 C++，我建议你将所有这些都放在一个类中，因为你将许多参数传递给每个函数，如果你传递了很多数据(因为它被复制)。

第二个注意事项，由于您正在使用移位，因此使用无符号变量作为右移可能更安全 >>对于它用带符号的变量填充的内容没有严格的定义。至少要记住这一点，它可能在那一侧填充 1。