c++ - (速度)优化影响代码的意外部分

Question

Closed. This question does not meet Stack Overflow guidelines。它当前不接受答案。












想改善这个问题吗？更新问题，以便将其作为 on-topic用于堆栈溢出。

7年前关闭。



Improve this question




我正在对自己的代码进行速度优化。伪代码是这样的:

1. myStructure = constructStructure (param1)
2. processStructure(myStructure)
3. myStructure = constructStructure (param2)
4. processStructure(myStructure)

我一直专注于优化 constructStructure(param)函数，因为对该函数的两次调用占用了大约75％的时间。我没有触摸功能 processStructure(structure)。

我确实获得了不错的加速(现在整个过程大约花费了原始时间的75％)，但是当我测量 1.-4.的各个操作时间时，我得到了意外的结果:

      before        after
1.   75.10ms      56.88ms
2.   23.12ms      19.32ms
3.   70.72ms      53.22ms
4.   20.81ms      14.45ms

我在未更改的 2.和 4.部分中获得了(很小，但是)显着的加速!在 1000运行时对其进行测量，然后取平均值。 (我没有计算标准偏差，但是我确实对每种变体进行了运行并显示了20 ish次，这似乎与平均值相符)。

据我所知，优化前后所产生的结构是相同的，并且两种情况下程序的最终输出都是相同的。

据我所知，没有(大量)内存泄漏-我在测试运行期间正在监视系统内存，并且使用的内存没有持续增加。 (我知道这不是测试它的好方法，而深入研究潜在的内存泄漏是我的下一站。此外，我确实会在不需要时立即释放/删除所有保留的内存) 。

并不是说我对速度不满意，但是我什至无法开始理解发生了什么!因为这是我将要完成的代码，所以我将在相当长的一段时间内使用它，所以在代码中包含一个神秘之处并不是一个吸引人的选择。

有人对和 发生了什么有任何想法，我如何才能验证您所建议的情况是否如此？ PS。我正在使用C++。

由于实际的代码太大而不能在此处放置(用于生产结构的100行+用于处理结构的300行)，因此我可以对其进行一些描述，并描述更改:

constructStructure

它是一种构建树结构(不是二叉树)(基于灰度图像像素)的函数，其中为每个节点分配了int属性。
constructStructure函数的参数是Comparator，它指示像素强度的顺序(第一次是less<int>()，第二次是greater<int>())。

在优化过程中，仅更改中的更改是使用std::priority_queue而不是std::multimap来实现堆结构(如this question of mine中所述-除非它不与std::pair<int,int>一起使用，而是在std::pair<int,myData>上使用)

在某种意义上，我已经验证了生成的myStructure是等效树(通过检查生成的树以获取10种不同的图像):

产生的树具有相同数量的节点

节点中包含的数据与

相同

但使用std::multimap时，节点内子级的顺序与使用std::priority_queue时(子级仍然是拥有相同数据的节点)不同。

结论:这些树与其所保存的数据及其结构相同，直到其在任何单个父节点中的子节点的顺序为止

processStructure

该功能以DFS(自下而上)的方式检查构造的树。复杂度仅取决于树中节点的数量，并且仅检查分配给每个节点的属性(不检查节点中包含的数据，该数据可用于此处未使用的进一步处理)。

最后，经过进一步测试和我指出的节点顺序之间的差异之后，问题将是:是否有可能树中节点的顺序会产生这种显着的性能变化，即使(当遍历树时， DFS方法)不检查节点内的数据，而是仅检查每个节点的单个整数属性？

最佳答案

可能的情况:

内联:也许，processStructure()和constructStructure()位于包含文件中，或者位于您将这些函数称为文件的文件中。如果是这样，编译器可以内联代码本身，以节省proc调用。因此，这仅仅是组合函数调用的宏优化的效果。

缓存效果:也许您使用更少的代码或更少的内存，并且在优化后某些内容可以放入L1 / L2缓存中。

我建议您为两个程序变体(gcc的-S选项)生成汇编文件，并比较汇编器代码。

关于c++ - (速度)优化影响代码的意外部分，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18919060/

上一篇：c++ - 在 C++ 中存储大矩阵 (Armadillo)

下一篇：C++ 使用 std::pair 模板特化定义树节点数据结构

相关文章：

c++ - 忽略了 OpenMP 任务依赖性？

适用于 UWP 和经典桌面的 C++ 通用 Windows DLL

php - PHP 中首先发生什么，包含还是解析？

mysql - 为什么当有几个索引时，MySQL InnoDB 对大表的插入/更新会变得非常慢？

java - 失败 : Build failed with an exception(Could not resolve all files for configuration ':app:lintClassPath' . )

css - 在 CSS 中使用非常具体的选择器有优势吗？

c++ - 有什么理由应该将 C++ 11+ std::mutex 声明为全局变量而不是作为函数参数传递给 std::thread 吗？

swift - 如何在非标准库 Swift 框架中为容器启用高级 SIL 优化？

javascript - next.js:是否可以只为 google bot 和其他爬虫而不为用户做 SSR？

c++ - 指向普通变量的常量指针

Answer 1

可能的情况:

内联:也许，processStructure()和constructStructure()位于包含文件中，或者位于您将这些函数称为文件的文件中。如果是这样，编译器可以内联代码本身，以节省proc调用。因此，这仅仅是组合函数调用的宏优化的效果。

缓存效果:也许您使用更少的代码或更少的内存，并且在优化后某些内容可以放入L1 / L2缓存中。

我建议您为两个程序变体(gcc的-S选项)生成汇编文件，并比较汇编器代码。