最初的实现中dequeue
方法以及队列结构Drop
时会出现内存泄露的问题。因为 Rust 本身没有 GC,无法回收dequeue
操作后无用的空结点,必须手动处理,此处采用的解决方案是利用Box::frow_raw
方法把无用结点的裸指针转换为智能指针, Rust 的所有权系统就可以在这个Box
被Drop
时释放内存,队列本身被Drop
时要将剩余节点全部dequeue
,然后主动释放空队列的 dummy_node,才能保证内存不会泄露。
做基准测试时本来想单独测试enqueue
操作,但运行时发现测试可能卡死或报错,检查后发现是因为测试框架对同一个队列结构进行了太多的入队操作,最终导致内存不够产生 OOM 问题。因此我将测试部分修改成enqueue
和dequeue
的一组操作,就不会产生 OOM 问题。
在尝试解决 ABA 问题的过程中,发现在原始值为空指针时的 CAS 操作无需处理,因为这个AtomicPtr
中保存着一个空指针,那么也就不存在这部分内存被释放在重用的可能,因此也不会发生 ABA 问题。
在编写多线程 Benchmark 代码时,测试框架会卡死,尝试修复但没有解决,该框架官方文档中也没有提及多线程环境测试方法,因此我使用一个单独的可执行程序测试多线程下的性能表现。
各种实现在多线程环境下每秒执行的enqueue
操作数量。
lock_free_queue | lock_free_queue_no_aba | lock_free_queue_by_epoch | lock_based_queue |
---|---|---|---|
4063920 | 2346813 | 1293374 | 1074467 |