给定相同的输入，某些代码怎么可能花费更多时间运行似乎只是因为它处于循环中？

Question

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

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

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

下面的代码，以防这是一个我不太熟悉的新语言的简单编码错误。我正在使用具有所有默认设置的 Visual Studio 2017 社区版，除了我正在使用 "release" 构建以加快代码执行速度。注释掉 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

不幸的是，我还不能 post 评论，所以我会 post 在这里，即使它可能不是一个完整的答案。

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

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

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

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

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

给定相同的输入，某些代码怎么可能花费更多时间运行似乎只是因为它处于循环中？

How is it possible for some code to take more time to run given the same inputs seemingly just because it's in a loop?

c++

benchmarking

loops

给定相同的输入，某些代码怎么可能花费更多时间 运行 似乎只是因为它处于循环中？

How is it possible for some code to take more time to run given the same inputs seemingly just because it's in a loop?

c++

benchmarking

loops

给定相同的输入，某些代码怎么可能花费更多时间运行似乎只是因为它处于循环中？