C++ 中查找函数的独占时间

2025年2月11日 | 阅读 12 分钟

确定函数独占时间的问题在于计算程序中每个函数执行所花费的时间，排除在嵌套函数调用中花费的任何时间。通过分析以元组 (id, type, timestamp) 表示的函数开始和结束事件的日志，其中 'id' 是函数标识符，type 指示函数是开始 ("start") 还是结束 ("end")，'timestamp' 表示事件发生的时间，目标是找出每个函数花费的时间。

重要性与用途

函数时间的确定在性能分析、资源管理、财务跟踪和问题解决等场景中具有重要意义。让我们深入探讨一些例子：

1. 性能分析

确定函数的执行时间使开发人员能够精确定位应用程序中的性能瓶颈。通过识别哪些函数占用了大部分时间，开发人员可以专注于优化代码库中耗时最多的部分。

示例： 想象一个同时管理请求的 Web 服务器应用程序。

当开发人员分析每个函数花费多少时间时，他们可以精确定位耗时最多的任务，例如数据库查询、文件操作或复杂的计算。优化这些领域可以提高系统的性能和响应能力。

2. 资源管理

在分布式系统或多线程环境等场景中，了解每个函数所花费的时间对于根据每个函数的负载分配 CPU 和内存等资源至关重要。

例如，在资源在用户之间共享的计算环境中，准确测量函数各自花费的时间有助于公平有效地分配资源。消耗时间较多的函数可以被分配资源，以确保最佳利用率并防止资源短缺。

3. 计费

在云计算或无服务器环境中，精确跟踪函数执行时间对于计费和会计目的至关重要。它涉及根据客户的函数运行情况向他们收费，排除在服务或依赖项上花费的任何时间。例如，AWS Lambda 或 Google Cloud Functions 等平台通常根据函数的执行时间向客户收费，而不考虑服务时长。

4. 调试和故障排除

分析函数执行时间对于排除代码库中的性能问题或意外行为非常宝贵。考虑一个具有涉及函数的处理管道。通过检查每个函数的执行时间，开发人员可以识别出任何运行时间超出预期的函数，这表明代码中存在错误或效率低下。这种洞察力可以简化调试过程并促进问题解决。

这些例子展示了调度函数的重要性，有时会涵盖软件开发、系统管理、云计算和应用程序性能监控等领域。

理解函数调用栈的工作原理

函数调用栈的要点

函数调用栈，也称为执行栈或控制栈，是编程语言在程序运行时用于管理活动函数调用的数据结构。它作为一个后进先出 (LIFO) 堆栈，保存每个函数调用的详细信息，例如返回地址、局部变量和参数。

当调用一个函数时，会发生以下步骤：

调用函数的当前状态被添加到调用栈中，包括返回地址（程序在被调用函数完成后应继续执行的内存位置）和任何必要的（如变量和参数）。
被调用函数开始执行。它可能会在栈上为其局部变量和参数分配空间。
当函数调用其他函数时，计算机按顺序跟踪每个函数，创建一个要完成的任务堆栈。

一旦函数完成其任务，它的状态就会从堆栈中移除，允许在保存的返回地址处恢复到调用函数中的执行。

独占时间的关系

理解函数调用栈对于衡量函数持续时间至关重要。独占时间是指执行函数代码所花费的时间，而不考虑在该函数内的嵌套函数调用所花费的任何时间。

当调用一个函数时，它的独占时间开始计算。之后，如果该函数调用了另一个函数，则被调用函数的独占时间开始计算，而调用函数的独占时间将暂停，直到被调用函数完成。这个过程对于任何嵌套的函数调用会递归地继续，形成一个函数调用的结构。

检查函数调用栈中的条目和退出顺序，可以确定每个函数的执行时间。此独占时间表示在给定函数中运行一段代码需要多长时间，不包括在该函数内部调用的任何嵌套函数所花费的时间。

例如，让我们考虑以下函数调用序列：

 
main() {
    // exclusive time of main() starts
    foo();
    // exclusive time of main() resumes
    bar();
    // exclusive time of main() ends
}

foo() {
    // exclusive time of foo() starts
    // code execution
    // exclusive time of foo() ends
}

bar() {
    // exclusive time of bar() starts
    // code execution
    // exclusive time of bar() ends
}\   

在此示例中，我们通过从 'main()' 函数花费的时间中减去 'foo()' 和 'bar()' 函数花费的时间来确定 'main()' 函数所花费的时间。之后，我们根据 'foo()' 和 'bar()' 自身的代码执行时间来计算它们的时间，不包括任何嵌套的函数调用。

通过跟踪和分析函数调用栈，我们可以准确地将执行时间分配给每个函数，同时考虑函数是如何分层调用的，并理解时间的概念。

方法和算法

该方法涉及检查函数开始和结束事件的日志以确定函数的执行时间。它还需要维护一个数据结构来监视活动函数调用及其开始时间。该算法处理日志事件，并根据事件类型和活动函数调用状态调整每个函数的时间。以下是该方法的一个简要概述：

设置一个数据结构（例如堆栈或树）来管理函数调用及其开始时间。
遍历函数事件日志；
1. 对于“start”事件；
  - 将函数 ID 及其开始时间添加到数据结构中。
2. 对于“end”事件，
  - 从数据结构中移除相应的函数 ID。开始时间。
  - 通过从当前时间戳减去其时间来计算该函数的执行时间，然后减去在该函数的期间内执行的任何子函数的独占时间。
  - 保存或修改此函数的独占时间以供其 ID 使用。

数据结构

选择数据结构对于跟踪函数调用和计算函数执行时间至关重要。为此目的使用的两个选项是堆栈和树。

基于堆栈的方法

堆栈是一种数据结构，它遵循后进先出 (LIFO) 原则。它们非常适合监视函数调用，因为它们自然地反映了函数调用和返回的结构。

当调用一个函数时，它的详细信息（例如函数 ID 和开始时间）可以添加到堆栈中。函数执行完成并返回后，这些详细信息可以从堆栈中移除。通过在堆栈中维护一个函数调用列表，可以计算每个函数的独占时间。

优点

它易于实现。
它显示了函数调用结构。
快速的压栈和出栈操作（如果内存充足）。

缺点

它不适合高效管理递归函数调用。

实施

 
stack<pair<int, int>> functionStack; // (function_id, start_time)

for (const FunctionEvent& event : logs) {
    if (event.type == "start") {
        functionStack.push({event.id, event.timestamp});
    } else {
        // Calculate exclusive time and update the result
        // ...
    }
}   

另一种使用树的方法

树作为一种数据结构，用于监视函数调用。在这种方法中，每次函数调用都被描绘成树中的一个节点，其中父节点和子节点之间的连接表示调用者和被调用者之间的关系。

当调用一个函数时，一个新的节点将作为子节点链接到当前正在执行的函数。函数执行完成后，可以通过从函数内部花费的时间中减去其子函数的总执行时间来确定其执行时间。

优点

它自然地反映了函数调用的层次结构。
它提供了在节点中包含额外详细信息或数据的选项。

缺点

与堆栈相比，实现更复杂。
需要额外的内存空间来存储节点结构。

实现（使用简单的树节点结构）

 
struct TreeNode {
    int id;
    int startTime;
    vector<TreeNode*> children;
    // Additional metadata if needed
};

TreeNode* root = nullptr;

for (const FunctionEvent& event : logs) {
    if (event.type == "start") {
        TreeNode* newNode = new TreeNode{event.id, event.timestamp};
        // Add the new node as a child of the current node
        // ...
    } else {
        // Calculate exclusive time and update the result
        // ...
    }
}   

选择最佳数据结构

选择基于堆栈或基于树的方法取决于问题的需求和函数调用结构的复杂性。

假设函数调用层次结构很简单。如果它不涉及递归调用，则选择基于堆栈的方法可能更简单有效。堆栈更容易使用，并为添加和删除元素提供了恒定的时间操作。

另一方面，如果需要管理递归函数调用或存储每个函数调用的详细信息，则基于树的方法可能更合适。树自然地表示层次结构，有效处理递归调用，并允许在每个级别存储额外的信息。

在选择数据结构类型时，重要的是要考虑以下因素：

是否存在递归函数调用。
是否需要每个函数调用的额外元数据或信息。
内存限制和空间复杂度要求。
性能需求和时间复杂度问题。
实现的易用性和可维护性。

在某些情况下，混合使用数据结构可能更合适，具体取决于问题的具体限制和需求。

最终，在决定数据结构时，重要的是要考虑时间效率和空间效率、功能需求以及实现难度等因素，以找到一种有效且实用的方法来确定函数执行时间。

C++ 实现

以下是一个使用基于堆栈的方法查找函数独占时间的 C++ 实现示例

 
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>

using namespace std;

class FunctionEvent {
public:
    int id;
    string type;
    int timestamp;

    FunctionEvent(int id, string type, int timestamp)
        : id(id), type(type), timestamp(timestamp) {}
};

unordered_map<int, int> findExclusiveTime(vector<FunctionEvent>& logs) {
    unordered_map<int, int> exclusiveTime;
    stack<pair<int, int>> functionStack;

    for (const FunctionEvent& event : logs) {
        if (event.type == "start") {
            functionStack.push({event.id, event.timestamp});
        } else {
            int currentId = event.id;
            int currentTimestamp = event.timestamp;
            int executionTime = currentTimestamp - functionStack.top().second + 1;
            functionStack.pop();

            while (!functionStack.empty() && functionStack.top().second > currentTimestamp) {
                exclusiveTime[functionStack.top().first] += executionTime;
                executionTime = 0;
                functionStack.pop();
            }

            exclusiveTime[currentId] += executionTime;
        }
    }

    return exclusiveTime;
}

int main() {
    vector<FunctionEvent> logs = {
        {0, "start", 0},
        {1, "start", 1},
        {1, "end", 2},
        {0, "end", 3}
    };

    unordered_map<int, int> result = findExclusiveTime(logs);

    for (const auto& pair : result) {
        cout << "Function " << pair.first << ": " << pair.second << endl;
    }

    return 0;
}   

输出

 
Function 0: 4
Function 1: 2

说明

'FunctionEvent' 类表示一个函数开始或结束事件，包含函数 ID、事件类型（“start”或“end”）和时间戳。
findExclusiveTime 函数接受 'FunctionEvent' 对象向量作为输入，并返回一个 'unordered_map'，其中包含每个函数 ID 的独占时间。
在 'findExclusiveTime' 内部，一个名为 'functionStack' 的堆栈用于跟踪活动函数调用及其开始时间。
该函数遍历函数事件日志。
- 如果事件是“start”事件，则将函数 ID 和开始时间压入堆栈。
- 如果事件是“end”事件，则从堆栈中弹出函数 ID 和开始时间。
- 当前函数的独占时间通过从当前时间戳减去开始时间并加 1 来计算（因为时间戳是包含性的）。
- 在当前函数的独占时间中减去在当前函数开始后开始的任何子函数的独占时间。
- 在 'exclusiveTime' map 中更新当前函数 ID 的独占时间。
处理完所有事件后，exclusiveTime map 包含每个函数 ID 的独占时间。
printExclusiveTime 辅助函数用于以“Function X: Y”的格式打印每个函数 ID 的独占时间，其中 X 是函数 ID，Y 是独占时间。
在 main 函数中，创建了一个示例函数事件日志，并使用此日志调用 findExclusiveTime 函数。使用 printExclusiveTime 函数打印生成的独占时间。

对于给定的示例日志 {{0, "start", 0}, {1, "start", 1}, {1, "end", 2}, {0, "end", 3}}，这意味着函数 0 的独占时间为 1 个单位（函数 0 开始到调用函数 1 之间花费的时间。函数 1 结束和函数 0 结束之间的时间），而函数 1 的独占时间为 1 个单位（执行函数 1 代码所花费的时间）。

我们可以修改 main 函数中的示例日志来测试不同的场景并验证实现的正确性。

处理边界情况

在实现查找函数独占时间的算法时，务必考虑并处理可能出现的各种边缘情况。以下是一些常见边缘情况及处理策略：

递归函数调用

如果输入的日志包含递归函数调用，即一个函数直接或间接调用自身，则基于堆栈的方法可能不足。在这种情况下，基于树的方法可能更适合正确处理递归函数调用的嵌套结构。
为了使用基于树的方法处理递归函数调用，我们可以为每次函数调用创建一个树节点，并维护函数调用之间的父子关系。计算函数的独占时间时，我们需要从其总执行时间中减去所有子函数（包括递归调用）的独占时间。

函数调用重叠

在某些情况下，输入的日志可能包含函数调用重叠，即一个函数在另一个函数完成之前开始。这可能由于并发、多线程或其他因素导致。
为了处理函数调用重叠，我们需要为每个线程或执行上下文维护一个单独的堆栈或树。处理“end”事件时，我们需要根据函数调用的线程或执行上下文确保我们正在更新正确的函数调用实例的独占时间。

空日志或无效输入

处理输入日志为空或包含无效数据的情况至关重要。例如，可能存在一个“end”事件而没有相应的“start”事件，或者时间戳不一致或顺序错误。
为了处理空日志，我们可以简单地返回一个空 map 或独占时间的默认值。
对于无效的输入数据，我们可以实现输入验证检查并适当地处理错误或不一致。根据我们的需求，这可能涉及跳过无效事件、记录错误或抛出异常。

示例

以下是如何在 C++ 实现中处理无效“end”事件的示例：

 
#include <iostream>
#include <unordered_map>
#include <stack>
#include <vector>
#include <string>

struct FunctionEvent {
    int id;
    std::string type;
    int timestamp;
};

std::unordered_map<int, int> findExclusiveTime(const std::vector<FunctionEvent>& logs) {
    std::unordered_map<int, int> exclusiveTime;
    std::stack<std::pair<int, int>> functionStack;
    int prevTimestamp = 0;

    for (const FunctionEvent& event : logs) {
        if (event.type == "start") {
            if (!functionStack.empty()) {
                exclusiveTime[functionStack.top().first] += event.timestamp - prevTimestamp;
            }
            functionStack.push({event.id, event.timestamp});
        } else { // "end" event
            if (functionStack.empty()) {
                // Invalid "end" event, no corresponding "start" event
                // Handle the error (e.g., log, skip, or throw an exception)
                continue;
            }

            auto [id, startTime] = functionStack.top();
            functionStack.pop();
            int duration = event.timestamp - startTime + 1;
            exclusiveTime[id] += duration - (event.timestamp - prevTimestamp);

            if (!functionStack.empty()) {
                exclusiveTime[functionStack.top().first] += event.timestamp - prevTimestamp;
            }
        }
        prevTimestamp = event.timestamp;
    }

    return exclusiveTime;
}

int main() {
    std::vector<FunctionEvent> logs = {
        {0, "start", 0},
        {1, "start", 2},
        {1, "end", 5},
        {0, "end", 6}
    };

    std::unordered_map<int, int> result = findExclusiveTime(logs);

    for (const auto& [id, time] : result) {
        std::cout << "Function " << id << ": " << time << " units" << std::endl;
    }

    return 0;
}   

输出

 
Function 1: 1 units
Function 0: 11 units

说明

在此示例中，如果遇到“end”事件时 'functionStack' 为空（表示没有相应的“start”事件），则实现可以根据我们的需求通过日志记录、跳过事件或抛出异常来处理错误。

通过正确处理这些边缘情况，我们可以确保我们实现的函数独占时间查找是健壮的，并且能够处理各种场景，包括递归函数调用、函数调用重叠以及无效或不一致的输入数据。

下一个主题C++17 中的 charconv 头文件

C++ 中查找函数的独占时间

重要性与用途

1. 性能分析

2. 资源管理

3. 计费

4. 调试和故障排除

理解函数调用栈的工作原理

函数调用栈的要点

独占时间的关系

方法和算法

数据结构

基于堆栈的方法

优点

缺点

实施

另一种使用树的方法

优点

缺点

实现（使用简单的树节点结构）

选择最佳数据结构

C++ 实现

说明

处理边界情况

递归函数调用

函数调用重叠

空日志或无效输入

示例

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中查找函数的独占时间

重要性与用途

1. 性能分析

2. 资源管理

3. 计费

4. 调试和故障排除

理解函数调用栈的工作原理

函数调用栈的要点

独占时间的关系

方法和算法

数据结构

基于堆栈的方法

优点

缺点

实施

另一种使用树的方法

优点

缺点

实现（使用简单的树节点结构）

选择最佳数据结构

C++ 实现

说明