c – 有效函数调用匹配的数据结构

发布时间：2020-12-16 07:00:09 所属栏目：百科来源：网络整理

导读：我正在构建一个工具,除其他外必须衡量产品变化对性能的影响. 为了完成这项工作,我实现了一个探测器,无论何时调用函数或返回函数都会跟踪并通知我.首先,我将输出转储到一个文件中以了解我将要使用的数据,这里看起来像或多或少： FuncCall1 FuncCall2 FuncCall

我正在构建一个工具,除其他外必须衡量产品变化对性能的影响.

为了完成这项工作,我实现了一个探测器,无论何时调用函数或返回函数都会跟踪并通知我.首先,我将输出转储到一个文件中以了解我将要使用的数据,这里看起来像或多或少：

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

为了更好地直观地了解这些数据的外观,下面是前10000个函数调用的图表：(x轴：时间,y轴：深度/嵌套)：
Function Call/Return graph http://img444.imageshack.us/img444/4710/proflog.gif(http://img444.imageshack.us/img444/4710/proflog.gif)

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

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

>插入带有当前时间戳的新函数调用标记.
>查找特定ID的最新函数调用并存储返回时间戳.
>查看在某个函数中调用了哪些其他函数(并查看其花费时间的位置) – 例如,如果我在上一个示例中查看函数#2,我想知道它调用函数#3,函数#4,功能#5和功能#5调用功能#6然后返回(标记所有呼叫/返回时间戳).

现在,我对数据结构有几个想法可能对这种情况有好处：

>自动平衡树(即AVL),其中每个节点的密钥将是功能标识符,每个节点中的值将是一堆时间戳对.这种方法在标记函数时间戳和每个节点都是堆栈这一事实时会给我快速插入和查找,它还会处理正确的返回时间戳与开始时间戳的匹配 – 总是(我假设)a的最新返回时间戳某些函数应该匹配最嵌套/最近的函数调用.
在这种方法中,使用不同的标识符维护嵌套函数调用会有点麻烦,因为我必须遍历树并根据它们的时间戳匹配它们以找出它们的嵌套 – 不理想.
>维护一个尚未返回的函数列表(将保留调用堆栈信息)并使用skip-list,其中每个级别将等于函数调用嵌套级别.这种方法会使操作#3更容易,但查找会更慢,我可能需要维护非常长的未返回函数列表 – 例如main(),这些函数必须在我的应用程序的整个生命周期内维护.在这里,我还可以使用散列表来提高查找速度,从而牺牲更多的内存使用量.内存使用率至关重要 – 此分析器可轻松生成约20 MB / s.

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

我已经查看了区间树,范围??树和其他类型的数据结构,我知道,但我找不到任何能够有效满足我的所有3个要求的数据结构.

也许有一个数据结构会满足他们所有我不知道的东西？有任何想法吗？

更新：

那这个呢：

拥有一个将具有函数调用的树以及它们的嵌套调用,以及一个单独的堆栈用于未返回的函数.

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

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

你觉得我的想法有什么重大缺陷吗？

更新2：

我的方法很完美.我将等待2天并回答我的问题.

解决方法

从一个线程的角度来看,我认为最有效的是拥有一个严重的侵入式数据结构 – 你将调用堆栈和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;

我没有完全解决这个问题,但我认为这是要走的路.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!