想象一下我需要遍历一棵树。据我了解,如果我以递归的方式进行操作,则每个递归函数调用都需要将其本地参数保存在堆栈帧中。堆栈帧驻留在堆栈存储器中,并且每个帧都由堆栈指针指向。

堆栈存储器什么时候加载到CPU缓存中?每次函数返回?例如,如果我要进行很多递归函数调用,会“破坏”我的CPU缓存吗?

遍历树时,递归地完成很多操作(由于函数正在处理的数据结构受到约束),仅凭堆栈,我是否会遭受大量的高速缓存未命中?

目标是在遍历树时尝试尽可能减少高速缓存未中。

最佳答案

(是的,我知道。TLDR;)

在我曾经研究过的PPC(我认为是860)上,有两个
缓存,数据和代码。 (我认为它们不在CPU中,但我
假设他们住在哪里都没关系。)

对于函数调用,该特定的GCC编译器(您的编译器
结果可能有所不同)生成的代码

a)将函数参数压入调用函数的堆栈中(即参数加载)

然后

b)将栈(指针,通常是cpu寄存器)“操纵”到
为所有外部范围自动建立空间
变量(堆栈变量)。 (通常只需添加一个简单的
指向堆栈指针的字节数。)

注意:这两个步骤都已完成,然后才进入
功能/方法代码。

推送功能参数将导致某些数据缓存被
标记为“已触摸”(还是仍然称为“脏”?),但是要等多久
触摸的数据实际到达堆栈存储器的时间取决于
硬件缓存处理程序。

功能/方法“输入”(跳转到新的PC位置)
没有什么可以初始化自动变量的,这就是
程序员的责任。因此,数据缓存不受影响
为他们。



修改堆栈数据项时。涉及数据缓存
当代码将数据写入堆栈时。



没有。



我认为函数调用顺序比自动调用更多
在函数开始运行之前,变量已安装在堆栈存储器中的固定编译器计算出的与堆栈指针的偏移量处。因此,当递归(或调用任何其他函数)时,“本地”参数已经在堆栈中,因此已经“保存”。作为函数调用(或返回)的一部分,不会有其他保存。

也许您将“函数调用”与“上下文”混淆了
切换”?(cpu寄存器也必须推出以用于ram)
函数调用比上下文快2到3个数量级
由于此sudo'register swap'和其他os操作而切换。



不确定“破坏”缓存的含义。 (另请参阅下面的最后一段)我猜您正在考虑缓存块的大小并可能触发
额外的缓存块以某种方式写入。既然你提到
递归,也许您担心递归算法会
更容易发生这种事情。

各种缓存复杂性和缓存块大小意味着您只有
方法是测试。

但是,对我而言,这种担忧有一些过早的优化。
如果递归足够快,如果满足要求,为什么
你会调查吗

例如,我有一些代码,其中递归方法是
比循环实现更快(以及更多)
可读)。当您可以实现尾递归时,您不需要
麻烦手动重新编码和重新测试。 “-O3”优化具有
完全删除了堆栈使用。 (易于测试。)



就个人而言,我喜欢递归。如果您的问题“比较容易”
阅读并理解使用递归,而不是应该使用它。一世
最重视可读性。您还能如何确定正确性。

在我之前提到的嵌入式PPC上,我可以从命令行启用/禁用数据缓存和指令缓存。

我希望指令缓存可以提供良好的性能提升,
我并没有失望

我对数据缓存的期望值较低,感到非常惊讶
在规模上。我当时正在处理的代码
几乎没有递归,没有树,没有大文件系统。

您可能会发现我的一些测量结果很有趣
在预加载的参数完成从数据缓存到ram的旅程之前,小型函数可以从调用中返回。
该数据缓存以0个等待状态运行。函数“参数负载”为
就缓存而言便宜。

关于c++ - 递归,堆栈和缓存未命中,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/28611220/

10-14 18:51
查看更多