队列实现基准

Question

我开始开发一系列图像处理算法，其中一些算法密集使用队列。你们是否知道这些数据结构的良好基准？

为了缩小范围，我用C居多，但我可以用C++，STL和任何库。 我已经得到的数据结构库的几个点击，如GLib和C-Generic-Library和STL的过程中的容器。另外，如果你们中的任何一个开发/知道比这些更快的队列，请告知:)

此外，队列将有很多入队和出队操作，所以最好有一个聪明的方式来管理内存。

Answer 1

对于单线程应用程序，你经常可以避开具有所有通过简单处理下一个项目，因为它涉及到使用任何类型的队列，但也有很多应用中，这是不是这种情况（排队数据例如输出）。

而不需要锁定队列（没有其他线程操心）一个简单的循环缓冲区将是很难被击败的性能。如果由于某种原因，队列需要在创建后增长，这有点困难，但是您不应该很难找到循环缓冲区队列实现（或者自己构建）。如果在信号处理程序（或中断服务程序）中完成插入或提取操作，那么实际上您可能需要保护读取和/或写入位置索引，但如果您了解了目标，则可以确定这不是案件（如果有疑问保护，虽然）。通过暂时阻止信号或中断将保护队列中的东西保护起来。 （如果你需要调整队列的大小，你真的需要阻止这个）

如果你在队列中的任何东西都必须动态分配，那么你可能需要粘贴一个指针，到一个列表节点。一个单链表，其中列表主控者持有指向头部和最后一个节点的指针就足够了。从头部提取并在尾部插入。在这里保护插入和提取不受竞争条件的影响非常大，您只需要担心列表长度非常短的情况。如果你真的有一个单线程的应用程序，那么你根本不必担心它。

我没有任何实际的基准，并不能对任何库实现任何建议，但是这两种方法都是O（1）两个插入和提取。首先是更多的缓存（和内存寻呼机）友好，除非你的队列大小比它需要的大得多。第二种方法缓存友好性较低，因为队列中的每个成员都可以位于RAM的不同区域。

希望这有助于你评估或创建自己的队列。