A-A+

LockFree数据结构的内存回收性能测试 阅读笔记

2017年02月04日 并发并行编程 暂无评论 阅读 205 次
摘要:

最近在搞性能优化,读了一篇挺有意思的相关论文。
Performance of memory reclamation for lockless synchronization
这篇论文测试了几种LockFree数据结构的内存回收性能和简单的分析。

最近在搞性能优化,读了一篇挺有意思的相关论文。

Performance of memory reclamation for lockless synchronization

几种Memory Reclaimation Scheme

评测了几种回收机制的性能:

1. QSBR  quiescent-state-based reclaimation

2. EBR   epoch-based reclaimation

3. HPBR  hazard-pointer-based reclaimation

4. LFRC  lock-free reference counting

结论:没有一个各个场景都胜出的机制。数据结构算法本身、负载、执行环境都会影响选型。

回收机制简介

a grace period:有时间段[a,b],如果在b之后,所有在a之前删除的元素都可以被释放,那么[a,b]被称为a grace period。

QSBR简介

QSBR是通过quiescent state来检测grace period。如果线程T在某时刻不再持有共享对象的引用,那么该线程T在此时就处于quiescent state。如果一个时间区间内,所有线程都曾处于quiescent state,那么这个区间就是一个grace period。QSBR需要实现时明确手动指明在算法某一步处于quiescent state。

具体实现时,可以在时间轴上划分出interval,每个interval内,每一个线程至少有一次quiescent state。那么当前interval删除的对象的内存可以在下一个interval结束时释放掉。

需要注意的是,QSBR是个blocking的算法。如果某个线程卡死了,那么就等不到grace period了,最终导致内存都无法释放。

EBR简介

EBR将所有的线程的操作都归到某个epoch,通过有条件地增大epoch值来限制只使用连续三个epoch值,使得每个线程本地的epoch最多只落后全局epoch一个,线程在epoch维度上基本上是齐步走的。

具体实现时,设置一个全局的global_epoch,每个线程操作前将线程本地的local_epoch设置为global_epoch。

当线程尝试周期性更新global_epoch时,如果发现每一个在临界区内的线程的local_epoch都等于global_epoch,则递增global_epoch,否则放弃递增保持原来的值(有线程还在更旧的epoch)。如果更新成功,表明global_epoch-2时期下被删除的对象都可以回收。因为只需要三个连续epoch,所以可以用模3的方式修改epoch。

HPBR简介

Hazard Pointer思路比较简单,线程在使用一个共享对象时,为了避免该共享对象被释放,将其指针放在本线程局部声明成风险指针保护起来。如果某个线程想释放一个对象对象时,先看看有没有其他线程保护该对象,没有线程保护时才释放。

Hazard Pointer适合lock free的queue或者stack之类的简单数据结构,这种数据结构要保护的指针只有一两个。如果是hash或者tree等基本不实用。

LFRC简介

不太实用。略。

 

影响回收性能的因素

Memory Consistency

通常lock free代码假设内存模型是sequentially consistent。但是实际实现的时候可以放松,以避免不必要的fence。

Workload,contention,scheduling

workload: queue通常是更新操作,而hash往往读多写少。

contention: 算法是否受多线程竞争影响,例如HPBR在double check以确保将正确的指针保护起来的时候,double check可能失败。

scheduling: 基于grace period的算法会有不利的影响,HPBR不受影响。

Memory constraint

使用的内存大小限制。这个因素需要考虑,是因为不同的回收算法对内存使用是否bounded是不一样的。

测试结果 & Summary

详见原始论文。测试用的数据结构是linked-list和queue。

在单线程测试下,主要耗时在原子操作,扫描hazard pointer并不大(注,HPBR中扫描操作的频率可以通过参数控制)。

在需要遍历的list比较长时,HPBR需要更多的原子操作,开销较大(注,HPBR方式下的lockfree list search需要逐个保护所查找过程中访问到的节点,不过没看懂为什么一次search保护了所有访问的节点,按我的理解应该只需要保护现在正在访问到的节点)。

QSBR和EBR本身就要依赖grace period足够频繁。如果因为线程抢占或者写操作太多,grace period被停顿了,内存就可能爆了。这个问题可以缓解:通过如果发现操作时内存不足就放弃CPU,让其他拖后腿的线程尽快完成操作。

 

给我留言