/queue

Primary LanguageRust

内存泄露

最初的实现中dequeue方法以及队列结构Drop时会出现内存泄露的问题。因为 Rust 本身没有 GC,无法回收dequeue操作后无用的空结点,必须手动处理,此处采用的解决方案是利用Box::frow_raw方法把无用结点的裸指针转换为智能指针, Rust 的所有权系统就可以在这个BoxDrop时释放内存,队列本身被Drop时要将剩余节点全部dequeue,然后主动释放空队列的 dummy_node,才能保证内存不会泄露。

Benchmark 时出现 OOM 问题

做基准测试时本来想单独测试enqueue操作,但运行时发现测试可能卡死或报错,检查后发现是因为测试框架对同一个队列结构进行了太多的入队操作,最终导致内存不够产生 OOM 问题。因此我将测试部分修改成enqueuedequeue的一组操作,就不会产生 OOM 问题。

AtomicPtr 原始值为 null 指针时的 CAS 操作

在尝试解决 ABA 问题的过程中,发现在原始值为空指针时的 CAS 操作无需处理,因为这个AtomicPtr中保存着一个空指针,那么也就不存在这部分内存被释放在重用的可能,因此也不会发生 ABA 问题。

多线程 Benchmark

在编写多线程 Benchmark 代码时,测试框架会卡死,尝试修复但没有解决,该框架官方文档中也没有提及多线程环境测试方法,因此我使用一个单独的可执行程序测试多线程下的性能表现。

Benchmark 结果

各种实现在多线程环境下每秒执行的enqueue操作数量。

lock_free_queue lock_free_queue_no_aba lock_free_queue_by_epoch lock_based_queue
4063920 2346813 1293374 1074467