Immutable, RCU and Transnational Container
在编写并发程序的时候,经常要面对共享数据结构的保护问题。 虽然 C++ 提供的 RAII 实现的各种 guard lock 模式,早就让“忘记解锁” 导致的死锁成为历史。但是,锁带来的性能损耗依然是我们不得不面对的问题。 为了避免锁带来的开销,使用“无锁” 的数据结构似乎是个好主意。 然而事情的发展总是出乎所有人的意料。现代的多核CPU随着核数的越来越高,核与核之间的通信开销也变得越来越大。于是,所谓的“无锁” 容器,因为内部大量的“原子操作”变得越来越不适应于当前的时代。 不使用原子操作,又想大并发,又想安全,唯一能想到的,就只有“不修改” 了。 只读的数据,永远不需要锁的保护。这也是为何当下的程序员越来越青睐函数式编程。 然而,只有 const 没有 variable 的程序是根本不可能的。程序要运行,就得有变化。有变化,就不能使用只读的数据结构,不能只读,还是少不了要上锁。一锁,就离高性能大并发越来越远了。 有没有既可以修改,又可以无锁,还不需要使用原子操作的办法呢? 当然有啊,就是 RCU。但是 RCU 的局限性非常大,具体的来说就是,因为其赖以实现的原理导致了 RCU 只能是 list 容器。不能实现为更高效的 vector 和 hashmap 容器。 RCU 先修改 关联节点的 next/prev 指针,使得 后续的读者,会跳过当前要操作的节点,然后等待一段时间后, 释放节点。这样,读可以全速并发进行。无需任何锁的介入。而只有 list 容器,才能在不使用原子操作和锁的情况下,安全的 Detach 掉一个节点。map 容器,因为要对 tree 重新排序,无法实现成 RCU 操作。 即使 RCU 的读取速度再怎么好, list 就决定了,它在大元素量下注定的低性能。因此 rcu 即使在内核里,使用的也非常有限。只用在为数不多的 “读远大于写,而且容器元素不多” 的地方。 这个虽然不是 RCU 的问题,而是 list 的问题,但是 RCU 注定只能使用 list。 有没有办法让我最喜欢的 map/set/multiset/multimap/boost.multiindex 都能并发化呢? ...