队列实现基准

对于单线程应用程序,您通常只需在进入下一个项目时处理它,就可以绕过使用任何类型的队列,但在许多应用程序中,情况并非如此(例如,将数据排队等待输出)。

无需锁定队列(无需担心其他线程),简单的循环缓冲区在性能上很难击败。如果出于某种原因,队列在创建之后需要增长,这会稍微困难一点,但是您不应该很难找到循环缓冲队列实现(或者构建自己的队列)。如果插入或提取是在信号处理程序(或中断服务例程)中完成的,那么您可能实际上需要保护读和/或写位置索引,但是如果您对目标很了解,那么您可能能够确定情况并非如此(但在有疑问时,请保护)。保护措施可能是暂时阻塞信号或中断,这些信号或中断可能会将事情放入队列中。(如果需要调整队列的大小,则需要阻止此操作)

如果您要放入队列中的任何内容都必须动态分配,那么您可能只需要附加一个指针,并将其转换为一个列表节点。一种单链表,其中列表主控形状保存一个指向头部的指针,最后一个节点就足够了。从头部取出并插入尾部。在这里,保护插入和提取不受竞争条件的影响是非常独立的,当列表的长度非常低时,您只需要担心一些事情。如果你真的有一个单线程的应用程序,那么你就不必担心它了。

我没有任何实际的基准,也不能对任何库实现提出任何建议,但是这两种方法对于插入和提取都是O(1)。第一个更适合缓存(和内存寻呼机),除非您的队列大小比需要的要大得多。第二种方法对缓存不太友好,因为队列的每个成员都可以位于RAM的不同区域。

希望这能帮助您评估或创建自己的队列。