为什么 std::chrono 说我的函数执行时间为零纳秒？

Question

我正在做一个项目，我在这个项目中用 C++ 实现了两种流行的 MST 算法，然后打印出每个算法的执行时间。请忽略实际的算法，我已经测试过它们并且只对准确测量它们需要多长时间感兴趣。

void Graph::krushkalMST(bool e){
    size_t s2 = size * size;
    typedef struct{uint loc; uint val;} wcType; //struct used for storing a copy of the weights values to be sorted, with original locations
    wcType* weightsCopy = new wcType[s2];       //copy of the weights which will be sorted.
    for(int i = 0; i < s2; i++){
        weightsCopy[i].loc = i;
        weightsCopy[i].val = weights[i];
    }
    std::vector<uint> T(0);                                     //List of edges in the MST
    auto start = std::chrono::high_resolution_clock::now();     //time the program was started
    typedef int (*cmpType)(const void*, const void*);           //comparison function type
    static cmpType cmp = [](const void* ua, const void* ub){    //Compare function used by the sort as a C++ lambda
        uint a = ((wcType*)ua)->val, b = ((wcType*)ub)->val;
        return (a == b) ? 0 : (a == NULLEDGE) ? 1 : (b == NULLEDGE) ? -1 : (a < b) ? -1 : 1;
    };
    std::qsort((void*)weightsCopy, s2, sizeof(wcType), cmp);    //sort edges into ascending order using a quick sort (supposedly quick sort)
    uint* componentRefs = new uint[size];                       //maps nodes to what component they currently belong to
    std::vector<std::vector<uint>> components(size);            //vector of components, each component is a vector of nodes;
    for(int i = 0; i < size; i++){
        //unOptimize(components);
        components[i] = std::vector<uint>({(uint)i});
        componentRefs[i] = i;
    }
    for(int wcIndex = 0; components.size() >= 2 ; wcIndex++){
        uint i = getI(weightsCopy[wcIndex].loc), j = getJ(weightsCopy[wcIndex].loc); //get pair of nodes with the smallest edge
        uint ci = componentRefs[i], cj = componentRefs[j];      //locations of nodes i and j
        if(ci != cj){
            T.push_back(weightsCopy[wcIndex].loc);              //push the edge into T
            for(int k = 0; k < components[cj].size(); k++)      //move each member in j's component to i's component
                components[ci].push_back(components[cj][k]);
            for(int k = 0; k < components[cj].size(); k++)      //copy this change into the reference locations
                componentRefs[components[cj][k]] = ci;
            components.erase(components.begin() + cj);          //delete j's component
            for(int k = 0; k < size; k++)                                   
                if(componentRefs[k] >= cj)
                    componentRefs[k]--;
        }
    }
    auto end = std::chrono::high_resolution_clock::now();
    uint time = std::chrono::duration_cast<std::chrono::nanoseconds>(end-start).count();
    std::cout<<"\nMST found my krushkal's Algorithm:\n";
    printData(time, T, e);
    delete[] weightsCopy;
    delete[] componentRefs;
}

void Graph::primMST(bool e){
    std::vector<uint> T(0);                                     //List of edges in the MST
    auto start = std::chrono::high_resolution_clock::now();     //Start calculating the time the algorithm takes
    bool* visited = new bool[size];                             //Maps each node to a visited value
    visited[0] = true;
    for(int i = 1; i < size; i++)
        visited[i] = false;
    for(uint numVisited = 1; numVisited < size; numVisited++){
        uint index = 0;                                         //index of the smallest cost edge to unvisited node
        uint minCost = std::numeric_limits<uint>::max();                //cost of the smallest edge filling those conditions
        for(int i = 0; i < size; i++){
            if(visited[i]){
                for(int j = 0; j < size; j++){
                    if(!visited[j]){
                        uint curIndex = i * size + j, weight = dweights[curIndex];
                        if(weight != NULLEDGE && weight < minCost){
                            index = curIndex;
                            minCost = weight;
                        }
                    }
                }
            }
        }
        T.push_back(index);
        visited[getI(index)] = true;
    }
    auto end = std::chrono::high_resolution_clock::now();
    uint time = std::chrono::duration_cast<std::chrono::microseconds>(end-start).count();
    std::cout<<"\nMST found my Prim's Algorithm:\n";
    printData(time, T, e);
    delete[] visited;
}

我最初使用 <ctime> 中的 clock() 来尝试准确测量这需要多长时间，我最大的测试文件有一个包含 40 个节点和 780 条边的图表（足够大以保证一些计算时间），即使在使用 g++ 和 -O0 的慢速计算机上，我也会得到 0 或 1 毫秒。在我的桌面上，我只能得到 0 毫秒，但是因为我需要一种更准确的方法来区分测试用例之间的时间，所以我决定尝试使用 <chrono> 库提供的 high_resolution_clock。

这才是真正的麻烦开始的地方，我会（并且仍然）始终如一地得到程序执行时间为 0 纳秒。在寻找解决方案的过程中，我遇到了多个处理类似问题的问题，其中大部分都指出 <chrono> 是系统相关的，您实际上不太可能获得纳秒甚至微秒的值。尽管如此，我尝试使用 std::chrono::microsecond 仍然始终如一地得到 0。最终我发现我认为有人和我有同样的问题：

然而，这显然是一个过度活跃的优化器的问题，它删除了一段不必要的代码，而在我的情况下，最终结果总是取决于必须完全执行的一系列复杂循环的结果。我在 Windows 10，使用 -O0 通过 GCC 进行编译。

我最好的假设是我做错了什么，或者 windows 不支持任何小于毫秒的东西，而使用 std::chrono 和 std::chrono::nanoseconds 实际上只是用 0 填充的毫秒最后（正如我在算法中放入 system("pause") 并在任意时间取消暂停时观察到的那样）。如果您发现了这个问题，或者是否有任何其他方法可以实现更高分辨率，请告诉我。

应@Ulrich Eckhardt 的要求，我提供了最小的可重现示例以及我使用它进行的测试的结果，我必须说它非常有见地。

#include<iostream>
#include<chrono>
#include<cmath>

int main()
{
    double c = 1; 

    for(int itter = 1; itter < 10000000; itter *= 10){
        auto start = std::chrono::high_resolution_clock::now();
        for(int i = 0; i < itter; i++)
            c += sqrt(c) + log(c);
        auto end = std::chrono::high_resolution_clock::now();
        int time = std::chrono::duration_cast<std::chrono::nanoseconds>(end-start).count();
        std::cout<<"calculated: "<<c<<". "<<itter<<" iterations took "<<time<<"ns\n";
    }
    system("pause");
}

对于我的循环，我选择了一个随机的任意数学公式，并确保使用循环的结果，这样它就不会被优化到不存在的地步。在我的桌面上用各种迭代测试它会产生：
这似乎意味着在它开始计算时间之前需要一个特定的阈值，因为将产生非零时间的第一个结果所花费的时间除以 10，我们得到另一个非零时间，这不是结果所说的尽管假设整个循环需要 O(n) 时间和 n 次迭代，这就是它应该如何工作。如果说这个小例子有什么让我更加困惑的话。

Answer 1

切换到 steady_clock，您将获得 MSVC 和 MinGW GCC 的正确结果。

您应该避免使用 high_resolution_clock，因为它只是 steady_clock 或 system_clock 的别名。要像时尚一样用秒表测量经过的时间，您总是想要 steady_clock。 high_resolution_clock 是一件不幸的事情，应该避免。

我刚刚查了一下，MSVC 有以下内容：

using high_resolution_clock = steady_clock;

而 MinGW GCC 有：

/**
 *  @brief Highest-resolution clock
 *
 *  This is the clock "with the shortest tick period." Alias to
 *  std::system_clock until higher-than-nanosecond definitions
 *  become feasible.
*/
using high_resolution_clock = system_clock;

为什么 std::chrono 说我的函数执行时间为零纳秒？

Why does std::chrono say my function took zero nanoseconds to execute?

c++

performance-testing

chrono