优化速度：向量队列与向量指针队列

Question

我正在尝试将向量（实际上是管理向量的对象）存储到队列中，以便稍后处理它们。

这是我当前的实现：

// in constructor:  
q = new boost::lockfree::spsc_queue<MyObject>(num_elements_in_q);
// ...
bool Push(const MyObject& push_me) { return q->push(push_me); }
//  ...  
// in Pop() (i.e., this is how I pop stuff off of the queue)  
MyObject temp;  
q->pop(&temp);

我想知道存储指针而不是对象是否有意义。新代码如下所示：

// in constructor:  
q = new boost::lockfree::spsc_queue<MyObject*>(num_elements_in_q);
// ...
bool Push(const MyObject& push_me) {
  MyObject* ptr = new MyObject(push_me);
  return q->push(push_me);  
}
//  ...  
// in Pop() (i.e., this is how I pop stuff off of the queue)  
MyObject* ptr;  
q->pop(&ptr);
//  do stuff with ptr
delete ptr;

就最小化推送操作所花费的时间而言，哪种方法最好？一般来说，最好是存储整个 MyObject 还是只存储指针（并动态分配内存）？我意识到通过存储整个 MyObject，仍然涉及动态内存，因为 MyObject 中的向量需要调整大小。

我的最终目标是以内存使用量和 Pop() 执行时间为代价（顶部version 需要 Pop() 中的一个副本，这可以通过使用指针来避免）。

感谢您的帮助。另外，我目前无法访问此系统上的分析器，否则我可能已经有了答案。

Answer 1

如果不实际测试，我会说使用 new 的内存分配比复制整个 MyObject 的成本更高。当然要看MyObject是怎么实现的。

另一件需要考虑的事情是，假设 boost::lock_free 将数据存储在连续内存中，存储对象本身可能会给您带来更高的缓存命中率。因为你所有的对象都可以被 cpu 批量读取，因此一起存储在 L1 缓存中。使用指针将导致 CPU 从指针指向的内存中加载内容，并可能将队列中的其他元素踢出缓存。

当然，要 100% 确定您必须测量它。

Answer 2

同意在几乎所有情况下，存储指针必须比存储比指针更大的东西更便宜。

在每种情况下，似乎都存在 MyObject 的复制构造。通过让调用者负责对象的生命周期，就有机会移除这个构造：

提供右值接口将允许使用移动构造，这可能会轻得多，具体取决于为 MyObject 选择的表示形式。
或者，您可以传递 std::unique_ptr<MyObject> 智能指针并将其排队，强制调用者显式管理对象的构造和生命周期保证。

Answer 3

如果速度是最终目标，请考虑使用某种侵入式模式。侵入式，我的意思是，为每个对象添加链接指针，并使用这些指针来构建队列。最大的优点是将对象添加到队列时内存分配为零。而且，如果您将所有对象分配到一个大块中（例如使用向量），您的对象将保持靠近。这意味着遍历列表将不太可能导致缓存未命中。

这确实意味着您可能需要在队列上实现自己的锁定，但请记住，正确实现的无竞争互斥量应该或多或少与用于无锁编程的原子操作一样便宜。

查看：Boost Intrusive 以了解模板化 boost 实现的详细信息。

Answer 4

鉴于弄清楚发生了什么的唯一真正方法是测量，我使用了一种粗略的方法来计算我的执行时间（对于两种实现都是）。

以下是运行向队列中插入 2500 次的结果。时间以秒为单位，基于函数调用周围的 boost::timer。请注意，这些是每次通话的平均时间。

用于存储整个对象：
运行 1: 0.000343423
运行 2: 0.000338752
运行 3: 0.000339651
运行 4: 0.000320011
运行 5: 0.00034017

用于存储指针：
运行 1: 0.00033717
运行 2: 0.00033645
运行 3: 0.000336106
运行 4: 0.00033674
运行 5: 0.000336841

然后我开始制作并将测试增加到 25,000 次插入，因为我想知道最初是否有缓存未命中等问题。结果如下：

用于存储整个对象：
运行 1: 0.00023566
运行 2: 0.000255699
运行 3: 0.000250765
运行 4: 0.000239108
运行 5: 0.000264594

用于存储指针：
运行 1: 0.000317314
运行 2: 0.000316985
运行 3: 0.000414893
运行 4: 0.000334542
运行 5: 0.00033179

所以看起来（这只是我的理论）在最初的 Push() 调用中，在对象中找到的向量被适当地调整了大小。从那里开始，复制构造函数不再需要支付每次调整向量大小的代价，它成为一个更高效的过程。

优化速度：向量队列与向量指针队列

Optimizing for Speed: Queue of Vectors vs. Queue of Pointers to Vectors

c++

stl

vector