C++代码执行缓慢

Question

我最近一周花时间将一个递归Branch&Cut算法从Matlab转换到C++，希望能显著减少解决方案所需的时间，但令人难以置信的是，恰恰相反。 我并不是C++的专家，因此我下载了Sleepy Profiler并试图找到潜在的瓶颈。我想问一下，我从这个结果中得出的结论是否正确，或者我正在完全错误的方向上寻找。

代码运行了137秒，以下是Profiler显示的内容（还有其他很多条目，但不重要）：

所以如果我理解正确的话，98秒用于创建新对象，34秒用于释放内存（即删除对象）。

我会检查我的代码并看看我能否做得更好，但我也想问一下，你有没有关于常见错误或产生这种行为的坏习惯的提示。我想到的一件事是，在我的代码中使用了许多临时std::vectors来计算一些东西，所以可能会很慢。

为了避免你变瞎，我不会在我自己检查之前发布我的代码，但如果我自己无法解决这个问题，我会回来的。

- Christoph

---

我在C++方面还有点新，但我认为在堆栈上分配临时空间会很有帮助。 - ChaosPandion

你是如何在函数之间传递向量（特别是大向量）的？通过值传递：void function(vector a)，通过引用传递：void function(vector &a)，或者通过指针传递：void function(vector *a) 或 void function(shared_ptr<vector> a)？ - us2012

按引用传递对我来说似乎最容易。通过引用传递和通过指针传递之间有很大的区别吗？ - Christoph

不，我猜你是按值传递。按引用应该没问题。你检查过你的代码是否正确，即使它很慢吗？也就是说，你的代码在小整数LP问题上能完成并给出正确的答案吗？ - us2012

1. 尝试随机暂停方法。
2. 在调试器下使用调试版本。某些助理教授在告诉人们，你只应该在打开优化的情况下进行分析，这是学术玩具程序的无稽之谈。
3. 看起来你的第一个大问题是太多的 new 和 free 操作。最初的几个暂停样本将告诉你哪些语句负责，然后你可以将它们移出内部循环或池化已使用的对象。

- Mike Dunlavey

Answer 1

是的，如果使用不当，std::vector可能会很昂贵。最大的性能损失可能是重新分配 - 因为大小需要动态调整，并且您必须满足元素必须在连续内存中的约束条件，因此每当添加新元素超出已分配的元素时，就会发生重新分配。

这就是为什么您应该事先声明大小。如果您知道您将需要容纳n个元素，请将其声明为

 std::vector<MyClass> x(n);

或者

 std::vector<MyClass> x;
 x.reserve(n);

改为仅仅

 std::vector<MyClass> x;

接着是 n 次 push_back 操作。

如果仍然速度较慢，您可以为 std::vector 提供自定义分配器。但愿您不会走到这一步。

- Luchian Grigore

---

我提前声明了大小，这样就避免了一些陷阱 :) - Christoph

如果自动调整大小总是将容量加倍，则在向量大小M处，最多执行2M次复制（并且最多进行log2（M）次重新分配），在任何合理的初始容量下都会执行较少的操作。在任何乘数B下，任何向量大小的复制/元素都不超过B / {B-1}，因此在1.5x时最多为3，在1.25x时最多为5。除非复制非常昂贵，否则这只是噪音，不值得担心。 - jthill

Answer 2

在Matlab中，一切都是对象的引用。因此，当你传递它们时，你所做的相当于复制一个指针（大约是int大小，取决于一些因素），而不是复制整个矩阵，后者可能大一个数量级。

如果没有看到任何代码，我不能确定，但我怀疑你正在复制大量的对象，而不是复制对它们的引用。我建议你研究“智能指针”，例如std::shared_ptr。

你没有说明清楚，但你应该使用优化编译。（g++ -O3。）一些昂贵的复制和其他操作可以被优化掉，但不是全部。

此外，如果你是C++新手，你不应该使用new。它是为专家准备的，只有在与同事讨论并喝足一杯咖啡后才能使用。（当然，某些容器，如std::vector，可以代表你使用new。）

- Alex Chamberlain

---

你过于夸张了，声称只有专家才应该使用new。经过一点思考，人们可以轻松地以安全和高效的方式使用new。 - ChaosPandion

我很幸运自己没有在使用new。我还将向函数传递向量的引用，这是我已经发现的一件事 :) - Christoph

@Christoph 是的，会的。将它放在循环体外面... - Alex Chamberlain

@Christoph 或者使用 std::array。 - Alex Chamberlain

我的例子中的10只是一个魔法数字，在我的代码中，大小不幸来自一个变量。但我会看看能否稍微改变一下，并在某些点引入数组，感谢您的建议。不幸的是，我现在必须离开，但我会尽力改进我的代码，并在有所改变时报告回来！ - Christoph

Answer 3

正如Luchian Grigore所说，std::vector是昂贵的。但不仅如此，您的代码中不断创建对象、移动数据、重新分配内存甚至删除它的任何部分都可能耗费时间。如果Alex Chamberlain所说的是真的，那么这就是一个巨大的瓶颈。如果不是，我会提醒您（或者告诉您，如果您不知道）几乎每件事情都可以使您的软件在内存消耗方面更便宜，但代价是性能下降。反之亦然，更多的内存消耗意味着CPU需要计算的内容更少，因为您已经缓存了以前计算过的所有内容。这很基础，但有时我们会忘记它。

- Adrián Pérez

Answer 4

避免在时间关键的代码中调用new和delete。 这很慢。 或者使用快速内存管理器（例如SmartHeap）。

- Tobias Langner