草庐IT

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

coder 2024-02-25 原文

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

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

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天，然后回答我的问题。

    最佳答案

    从一个线程的角度来看，我认为最有效的方法是拥有一个严肃的介入式数据结构-您结合调用堆栈和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;

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

    关于c++ - 高效的函数调用匹配的数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10790871/

    amp43brcall的c++algorithmdata-structuresstl-algorithm

    有关c++ - 高效的函数调用匹配的数据结构的更多相关文章

    1. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

      我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

    2. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

      我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

    3. ruby 正则表达式 - 如何替换字符串中匹配项的第 n 个实例 - 2

      在我的应用程序中，我需要能够找到所有数字子字符串，然后扫描每个子字符串，找到第一个匹配范围(例如5到15之间)的子字符串，并将该实例替换为另一个字符串“X”。我的测试字符串s="1foo100bar10gee1"我的初始模式是1个或多个数字的任何字符串，例如，re=Regexp.new(/\d+/)matches=s.scan(re)给出["1","100","10","1"]如果我想用“X”替换第N个匹配项，并且只替换第N个匹配项，我该怎么做？例如，如果我想替换第三个匹配项“10”(匹配项[2])，我不能只说s[matches[2]]="X"因为它做了两次替换“1fooX0barXg

    4. ruby - 匹配未转义的平衡定界符对 - 2

      如何匹配未被反斜杠转义的平衡定界符对(其本身未被反斜杠转义)(无需考虑嵌套)？例如对于反引号，我试过了，但是转义的反引号没有像转义那样工作。regex=/(?!$1:"how\\"#expected"how\\`are"上面的正则表达式不考虑由反斜杠转义并位于反引号前面的反斜杠，但我愿意考虑。StackOverflow如何做到这一点？这样做的目的并不复杂。我有文档文本，其中包括内联代码的反引号，就像StackOverflow一样，我想在HTML文件中显示它，内联代码用一些spanMaterial装饰。不会有嵌套，但转义反引号或转义反斜杠可能出现在任何地方。

    5. ruby - 在没有 sass 引擎的情况下使用 sass 颜色函数 - 2

      我想在一个没有Sass引擎的类中使用Sass颜色函数。我已经在项目中使用了sassgem，所以我认为搭载会像以下一样简单:classRectangleincludeSass::Script::FunctionsdefcolorSass::Script::Color.new([0x82,0x39,0x06])enddefrender#hamlengineexecutedwithcontextofself#sothatwithintemlateicouldcall#%stop{offset:'0%',stop:{color:lighten(color)}}endend更新:参见上面的#re

    6. ruby-on-rails - 在 ruby​​ 中使用 gsub 函数替换单词 - 2

      我正在尝试用ruby​​中的gsub函数替换字符串中的某些单词，但有时效果很好，在某些情况下会出现此错误？这种格式有什么问题吗NoMethodError(undefinedmethod`gsub!'fornil:NilClass):模型.rbclassTest"replacethisID1",WAY=>"replacethisID2andID3",DELTA=>"replacethisID4"}end另一个模型.rbclassCheck 最佳答案 啊，我找到了!gsub!是一个非常奇怪的方法。首先，它替换了字符串，所以它实际上修改了

    7. 使用 ACL 调用 upload_file 时出现 Ruby S3 "Access Denied"错误 - 2

      我正在尝试编写一个将文件上传到AWS并公开该文件的Ruby脚本。我做了以下事情:s3=Aws::S3::Resource.new(credentials:Aws::Credentials.new(KEY,SECRET),region:'us-west-2')obj=s3.bucket('stg-db').object('key')obj.upload_file(filename)这似乎工作正常，除了该文件不是公开可用的，而且我无法获得它的公共(public)URL。但是当我登录到S3时，我可以正常查看我的文件。为了使其公开可用，我将最后一行更改为obj.upload_file(file

    8. ruby - 在 Ruby 中有条件地定义函数 - 2

      我有一些代码在几个不同的位置之一运行:作为具有调试输出的命令行工具，作为不接受任何输出的更大程序的一部分，以及在Rails环境中。有时我需要根据代码的位置对代码进行细微的更改，我意识到以下样式似乎可行:print"Testingnestedfunctionsdefined\n"CLI=trueifCLIdeftest_printprint"CommandLineVersion\n"endelsedeftest_printprint"ReleaseVersion\n"endendtest_print()这导致:TestingnestedfunctionsdefinedCommandLin

    9. ruby - 匹配大写字母并用后续字母填充，直到一定的字符串长度 - 2

      我有一个驼峰式字符串，例如:JustAString。我想按照以下规则形成长度为4的字符串:抓取所有大写字母；如果超过4个大写字母，只保留前4个；如果少于4个大写字母，则将最后大写字母后的字母大写并添加字母，直到长度变为4。以下是可能发生的3种情况:ThisIsMyString将产生TIMS(大写字母)；ThisIsOneVeryLongString将产生TIOV(前4个大写字母)；MyString将生成MSTR(大写字母+tr大写)。我设法用这个片段解决了前两种情况:str.scan(/[A-Z]/).first(4).join但是，我不太确定如何最好地修改上面的代码片段以处理最后一种

    10. ruby - Ruby 有 `Pair` 数据类型吗？ - 2

      有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳

    随机推荐