c++ - 高效的函数调用匹配的数据结构

Question

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

为了完成该任务，我实现了一个探查器，该探查器会在调用函数或返回函数时进行跟踪，并就此通知我。首先，我将输出转储到文件中以了解将要使用的数据，以下大致是它们的样子:

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

为了更好地直观了解此数据的外观，以下是前10000个函数调用的图形:(x轴:时间，y轴:深度/嵌套):
( http://img444.imageshack.us/img444/4710/proflog.gif)

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

总结起来，我将要对这些数据执行的操作是:

插入一个带有当前时间戳的新函数调用标记。

查找特定ID的最新函数调用，并存储返回时间戳。

查看从某个函数中调用了哪些其他函数(并查看其花费时间)-例如，如果我在上一个示例中查看Function＃2，我想知道它调用了Function＃3，Function ＃4，Function＃5和Function＃5调用Function＃6，然后返回(已标记所有调用/返回时间戳记)。

现在，我对数据结构有一些想法，这可能适合这种情况:

一种自动平衡的树(即AVL)，其中每个节点的键将是功能标识符，而每个节点中的值将是一堆时间戳对。当标记函数时间戳以及每个节点都是堆栈的事实时，这种方法将为我提供快速的插入和查找，它还将照顾到将正确的返回时间戳与起始时间戳进行匹配-始终(我假设)为a的最新返回时间戳某些函数应与最嵌套/最近的函数调用匹配。
在这种方法中，使用不同的标识符维护嵌套函数调用会有些麻烦，因为我将不得不遍历树并根据其时间戳匹配它们，以找出它们的嵌套-不理想。

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

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

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

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

更新:

那这个呢:

具有一棵树，该树将具有函数调用及其嵌套调用，并且有一个单独的堆栈用于未返回的函数。

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

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

您认为我的想法有什么重大缺陷吗？

更新2:

我的方法非常有效。我将等待2天，然后回答我的问题。

Answer 1

从一个线程的角度来看，我认为最有效的方法是拥有一个严肃的介入式数据结构-您结合调用堆栈和AVL树，如下所示:

// 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;

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