2

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

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 次，它似乎与平均值一致）。

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

据我所知，没有（大量）内存泄漏——我在测试运行期间监控我的系统内存，并且使用的内存没有持续增加。（我知道这不是一个很好的测试方法，挖掘潜在的内存泄漏是我的下一站。另外，我确实会在不需要时立即释放/删除所有保留的内存） .

并不是说我对加速不满意，但我什至无法开始理解发生了什么！由于这是我在完成工作后将使用相当长一段时间的代码，因此在代码中包含一个谜团并不是一个吸引人的选择。

是否有人对发生的事情以及我如何验证您的建议是否属实有任何想法？PS。我在C++中工作。

由于实际代码太大而无法放在这里（100 行用于生成结构 + 300 行用于处理它），我可以稍微描述一下，同时描述一下变化：

constructStructure

它是一个构建树结构（不是二叉树）（基于灰度图像像素）的函数，其中每个节点都分配有一个int属性。

该constructStructure函数的参数是Comparator指示像素强度的顺序（第一次是less<int>()，第二次greater<int>()）。

优化过程中的唯一变化是使用std::priority_queue而不是std::multimap实现堆结构（如我的这个问题中所述- 除了它不使用 withstd::pair<int,int>而是使用 on std::pair<int,myData>）

从某种意义上说，我已经验证了生成myStructure的是一棵等效的树（通过检查生成的树是否有10 个不同的图像）：

  • 生成的树具有相同数量的节点
  • 节点中包含的数据相同
  • 但是使用时节点内子节点的顺序与使用时不同（子节点再次是持有相同数据的节点）std::multimapstd::priority_queue
  • 结论：树就其拥有的数据及其结构而言等价于任何单个父节点中的子节点的顺序

processStructure

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

最后，在进一步测试和我指出的节点顺序之间的差异之后，问题是： 树中节点的顺序是否有可能在性能上产生这种显着变化，即使（使用 DFS 遍历树时）方法）不检查节点内的数据，而只检查每个节点的单个整数属性？

4

2 回答 2

3

什么是可能的：

  1. 内联：也许，processStructure() 和constructStructure() 位于包含文件中，或者在您调用这些函数的文件中。如果是这样，编译器可以内联代码本身，以节省 proc-call。所以，这只是组合函数调用的宏观优化的效果。

  2. 缓存效果：也许，你使用更少的代码，或者更少的内存，优化后可以放入缓存 L1/L2。

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

于 2013-09-20T14:30:38.897 回答
1

这有点猜测，因为我们没有要查看的代码，并且需要仔细研究来验证，即使使用代码，即使这样，它在不同的系统上也可能完全不同。但是，缓存和引用的局部性以及虚拟内存转换可能会产生这里看到的那种显着的性能影响。

仔细查看您的处理阶段访问节点的顺序（即按顺序、预排序、后排序、随机等）。然后考虑相对于将按顺序处理的其他节点，这些节点中的每一个可能已被分配到哪里。如果在访问一个节点之后，下一个节点恰好在内存中非常靠近（尤其是在同一个缓存行内，但也可能在同一个虚拟内存页面内，因为 TLB 资源有限），它可能比访问一个节点更快。也就是说，从缓存的角度来看，节点位于一个相当随机的位置。缓存的作用类似于预取，这意味着如果以主要线性方式访问内存，缓存可以隐藏访问主内存的大量延迟。最坏的情况是如果每个节点都在一个完全不同的缓存行中，在与前一个节点没有明显关系的位置。关于缓存层次结构和虚拟内存性能还有很多可以说的——整本书都在讨论这个主题。

我猜想您用于构建树的两种不同方法会导致在树中分配节点的顺序明显不同，结果是稍后遍历树具有完全不同的内存访问模式，这可能会导致显着的性能变化。我不知道你会怎么做，但是如果你可以安排你的所有节点在内存中是连续的，按照你在处理过程中访问它们的顺序，那几乎是最好的安排，而且你可能会看到比您现在更多的加速。但是，通常，您必须满足于“足够好”，尤其是在不同的输入导致显着不同的数据集的情况下。

valgrind有一个cachegrind模块可以帮助模拟某个缓存层次结构如何与您的程序一起工作的近似值 - 找到其中一些类型的差异很有用，尽管它不应被视为严重的性能保证，因为它必然是一个更简单的模型缓存比真实的缓存，并且不能考虑多任务，内核用户上下文切换等。

于 2013-09-20T22:01:27.100 回答