C++：优化列表

Question

我的代码进行了大量的分析，发现它花费了很多时间为向量分配空间。
对于这些向量中的大多数，大小是事先已知的，因此我调用reserve()来预先分配空间。
对于这些向量，其大小几乎总是非常小的，例如4或5个元素，但在极少数情况下，它可能非常大。
我考虑到的另一个优化是创建自己的容器OptimizedList<T,N>。该对象的实例包含N个T实例作为普通数组，并且如果用户尝试添加多于N个项目，则会开始使用动态分配来获取额外的项。

是否有已知的实现？

- shoosh

---

你尝试过用deque替换vector吗？如果您知道大小，也可以提前保留已知大小，这适用于vector的情况。 - Dmitry Ledentsov

为什么不使用 std::deque？ - Galimov Albert

std::vectorжњ‰дёЂдёҒжһ„йЂ е‡Ңж•°пәЊеЏҮд»Өдә е…Өе€қ始元зө ж•°й‡ЏгЂ‚ - nvoigt

@NeilKirk，答案的保留部分是为了可能的向量优化（或者使用构造函数，正如其他人建议的那样）。Deque不需要连续的内存，因此在您的问题中可能不需要保留大块内存。 - Dmitry Ledentsov

@NeilKirk 我认为瓶颈不在于重新分配内存，而是在于复制/销毁其中的一部分。因此，在这种情况下，最好的优化方法是完全删除向量重新分配（以及随后的对象复制）。请参见我的答案以获取详细信息。 - Galimov Albert

Answer 1

Qt的基于堆栈的变长数组怎么样？

看起来非常适合您的用例，主要是小数组，这些数组将在堆栈上分配（最快的分配方式，只需要一对指针的add/sub指令），对于大数组则在堆上分配。

但它会浪费空间。

- Bgie

Answer 2

我认为使用优化了4-5个元素的自定义分配器（从池中取出这些元素）的std::vector是最简单且最可行的解决方案，这也是唯一一个我期望能够真正带来净收益的解决方案。

使用std::deque可能并没有帮助，虽然从教科书的角度看似乎会有所帮助。它实际上可能会产生负面影响。双端队列可以将数据复制的开销从O(n)降低到O(1)，但它们并不是神奇的无需分配内存。相反，它们可能比使用向量更多地引起分配。
双端队列通常被实现为向量的向量或循环缓冲区。在后一种情况下，您与使用std::vector完全相同的重新分配开销，除了您不能通过调用reserve()来缓解它，而在前一种情况下，您需要进行两次分配，而在其他情况下，您只需要进行一次分配。

将前几个对象直接嵌入到自定义向量类或堆栈变量数组中，就像Bgie的答案中一样，这非常诱人，并且对于不太多而且不太大的向量确实是一个很好的解决方案。
但是，由于您创建这些向量时存在性能问题，因此可以得出结论，您不仅使用了5个或10个向量，而且使用了许多向量（否则它并不重要，也无法衡量！） 这意味着将数据放在堆栈上可能会导致最终堆栈溢出。
然而，如果您的所有向量都是在堆上分配的，则可以是一个很好的解决方案。在分配容器本身时分配几百个字节更没有什么区别，并且没有溢出堆栈的风险。因此，在这种情况下，您将有效地节省一个分配。

- Damon

Answer 3

由于大多数容器都很小，而稀有容器却有许多元素，我更喜欢使用std::deque。这可以帮助您以较低的代价避免不必要的重新分配。它没有reserve()方法，但由于大多数容器都很小，我认为这没关系。

更重要的是，您应该检查包含在这些容器中的对象类型。我认为瓶颈不是重新分配本身，而是复制/销毁其中的一部分。我怀疑“容器值”的复制构造函数和/或析构函数足够“沉重”。当构造函数/析构函数过于复杂时，复制N个元素然后销毁旧的N个元素非常耗时。

作为最后的优化，我建议使用内存池/分配器来减少底层malloc/realloc/free调用。

- Galimov Albert

---

我不同意deque通常比正确保留的vector更快。 - Neil Kirk

@NeilKirk 我们不知道他是如何进行预留并且预留的精确度如何。可能他会预留100，然后有时插入100k。在我看来，保持vector的高效使用更加复杂（并且可以讨论很长时间）。因此，可能OP只需切换容器类型就可以解决问题。 - Galimov Albert

有太多的假设和可能性。如果他正确地保留了向量，那么切换到deque会导致更多的分配。 - Neil Kirk

@NeilKirk 是的，需要更多的分配，但是减少了“重新分配”的次数。所谓重新分配是指分配和随后的“复制+销毁”调用。 - Galimov Albert

@NeilKirk认为“大部分时间都被分配消耗了”，但我认为这是错误的想法，并提出了自己的建议。 - Galimov Albert