4

我正在构建一个工具，除其他外，它必须衡量我们产品更改对性能相关的影响。

为了做到这一点，我实现了一个分析器，它跟踪函数何时被调用或返回并通知我。首先，我将输出转储到一个文件中，以了解我将使用的数据，这里或多或少是它们的样子：

FuncCall1
   FuncCall2
      FuncCall3
      FuncRet3
      FuncCall4
      FuncRet4
      FuncCall5
        FuncCall6
        FuncRet6
      FuncRet5
    FuncRet2
FuncRet1

为了更好地了解这些数据的外观，这里是前 10000 个函数调用的图表：（x 轴：时间，y 轴：深度/嵌套）： 函数调用/返回图（http://img444.imageshack.us /img444/4710/proflog.gif )

当一个函数开始执行时，我将记录它的名称/标识符和当前的高精度时间戳，当它返回时，我需要查找我存储开始时间的条目并添加一个新的时间戳来标记它返回。

总而言之，我将对这些数据执行的操作是：

  1. 插入具有当前时间戳的新函数调用标记。
  2. 查找某个 ID 的最近一次函数调用并存储返回时间戳。
  3. 查看从某个函数中调用了哪些其他函数（并查看它在哪里花费时间） - 例如，如果我在前面的示例中查看 Function#2，我想知道它调用 Function#3、Function# 4、Function#5 和 Function#5 调用 Function#6 然后返回（标记所有调用/返回时间戳）。

现在，我对可能适用于这种情况的数据结构有几个想法：

  1. 一个自动平衡树（即 AVL），其中每个节点的键是函数标识符，每个节点中的值是时间戳对的堆栈。这种方法将在标记函数时间戳时为我提供快速插入和查找，并且每个节点都是一个堆栈这一事实，它还将负责将正确的返回时间戳与开始时间戳相匹配 - 始终（我假设）a 的最新返回时间戳某些函数应该匹配最近的嵌套/最近的函数调用。在这种方法中，维护具有不同标识符的嵌套函数调用会有点麻烦，因为我必须遍历树并根据它们的时间戳匹配它们以找出它们的嵌套 - 这并不理想。

  2. 维护一个尚未返回的函数列表（这将保留调用堆栈信息）并使用跳过列表，其中每个级别都等于函数调用嵌套级别。这种方法会使操作 #3 更容易，但查找速度会变慢，而且我可能必须维护很长的未返回函数列表 - 例如 main()，这将必须在我的应用程序的整个生命周期中维护。在这里，我还可以使用哈希表，以牺牲更多内存使用来提高查找速度。内存使用很关键——这个分析器很容易生成大约 20 MB / s。

我不使用简单堆栈来跟踪这些数据的原因是，我需要定期将部分结果同步到不同的机器，并且在一切返回之前至少有部分结果可用。

我查看了区间树、范围树和其他我知道的数据结构，但我找不到任何能有效满足我所有 3 个要求的数据结构。

也许有一种数据结构可以满足我不知道的所有需求？有任何想法吗？

更新：

那这个呢：

拥有一棵树，其中包含函数调用及其嵌套调用以及未返回的函数的单独堆栈。

现在堆栈上的每个元素都有一个指向它在树中的副本的指针，当一个新的函数调用到达时，我将查看堆栈上的顶部元素，跟踪它指向它在树中的表示的指针，添加新的函数调用作为该调用的子节点，并使用指向新创建的树节点的指针将其副本推送到堆栈上。

对于函数返回，它是类似的，对于每个函数返回，堆栈上的最新条目将始终是它的调用 - 跟踪调用指针，将返回时间保存在树中并弹出调用。

你看到我的想法有什么重大缺陷吗？

更新 2：

我的方法效果很好。我将等待 2 天并回答我的问题。

4

3 回答 3

1

您可以使用跟踪类。缺点：您必须在必须记录/测量的每个函数的开头声明此跟踪器的实例。它还为您的测量增加了大量的周期，因此只能使用这种方法正确跟踪巨大的函数。

实现这一目标的另一种方法是编写一个真正的分析器，但这样的工具已经存在（ gprof ），并为它编写一个解析器。您仍然可以编写自己的...一个非常长的任务。

我建议您在单元测试中分别测试每个功能或组，这是我们通常有效的方式。然后弹出一个分析器并尝试优化你在 90% 的时间内运行的 10% 的代码。你把注意力放在远处的小细节上。

这是我的一个工具的输出：

2010 年 7 月 9 日星期五 00:49:12 - [ 3799946229640 ] - D:\Code Project\include/design/BTL/algorithm/dispatch_policy.h::operator() # |...operator() ( ) {

2010 年 7 月 9 日星期五 00:49:12 - [ 3799946246830 ] - D:\Code Project\include/design/BTL/algorithm/dispatch_policy.h::operator() # |...shape *, shape *

2010 年 7 月 9 日星期五 00:49:12 - [ 3799946265738 ] - D:\Code Project\include/design/BTL/algorithm/dispatch_policy.h::operator() # |...} operator() : 46027 cpu_cycles

正如您在上面所说的，输出量很大，因此对于深度分析来说是不切实际的，由于 20Mb/s 的输出流，您既不能监视程序太长时间。只有当您已经知道在哪里进行调查时，它才有用。由于此类工具所需的理论带宽的另一个问题，您必须使用缓冲的 ostreams ... 使该工具对真实软件更具侵入性。我已经经历了 10 倍的减速！

于 2012-05-28T22:54:15.980 回答
1

从一个线程的角度来看，我认为最有效的是拥有一个严重的侵入性数据结构——你将调用堆栈和 AVL-tree 结合起来，如下所示：

// one of these per call
struct {
    function *func; // func in the tree (or ID)
    timestamp time; // timestamp of call
    call *prev_call; // previous function call
    call *next_call; // next function call
} call;

// one of these per function
struct {
    call *last_call; // last call of this function
    your_type id; // identifier

    // insert tree-specifics here
} function;

我还没有完全解决这个问题，但我认为这是要走的路。

于 2012-05-28T22:37:42.950 回答
-1

一棵树的想法似乎……很浪费。

您正在做的事情需要一个简单的堆栈。

  • 记录 ID/条目时间戳对
  • 执行子调用
  • 使用退出时间戳修改栈顶条目

此外，所有子调用实际上都是同一父级的子级...

在你的位置，我会简单地使用：

  • 用于自动退出时间戳记录的 RAII
  • deque用于快速记录追加的类似结构

记录结构如下：

struct Record {
    unsigned level;
    unsigned id;
    unsigned entry;
    unsigned exit;
};

然后，您保留两个线程局部结构：

extern thread_local unsigned CurrentLevel;
extern thread_local std::deque<Record> CallRecords;

最后，您实现了一个简单的 RAII 类：

class CallRecorder: boost::noncopyable() {
public:
    CallRecord(unsigned id):
        record(*CallRecords.insert(CallRecords.end(),
                                   Record{CurrentLevel++, id, time(), 0}))
    {
    }

    ~CallRecord() { record.exit = time(); --CurrentLevel; }

private:
    Record& record;
};

您可以潜在地将父 ID 传递给每个子调用，但这似乎不值得。这是您在利用流时可以重建的信息（在旁边保留一个单独的堆栈）。

我只有两个笔记：

  • 您可能希望创建自己的实现deque来分配更大的块（例如 4K 页面）并真正优化附加。
  • 使用 RAII，我们可以处理常规退货和异常情况。只有abort不记录，因为程序终止。它可以被检测到，因为它留下了不完整的痕迹。
于 2012-05-29T07:39:00.980 回答