本文为原创,转载请注明:http://www.cnblogs.com/gistao/
背景
上一篇只是细致的把源码分析了一遍,而源码背后的设计思想并没有写,设计思想往往是最重要的,没有它,基本无法做整体性的优化或正确的使用,
但是根据结果反推原因是困难的,也极容易不到位,这里‘磕磕绊绊’写下自己的理解,另外对源码里的‘问题’也写出来。
简单
调试一个多线程程序是比较头疼的,而使用atomic来编写一个正确的多线程数据结构更是困难的,出了问题一般都是随机问题,且等着复现看log吧,
所以简单这个特性在设计里应是第一位的。
AtomicHashmap的key只支持int,为什么不像tbb的concurrent_hash_map一样也支持自定义类型的key呢?它完全可以通过把现有的key定位为
纯的状态机,再设置一个字段来保存自定义的key,我想就是为了简单,因为使用者可以自行通过hash算法将自定义的key转换为int来解决。这样还
节省了一个指针空间占用,够用够简单。
28原则
这里说的28原则是指80%的cpu在执行20%的代码。rehash是hashmap必不可失的功能,但它明显不在20%代码之内的范畴。
所以,AtomicHashmap可以不支持传统的rehash,一方面是atomic的能力限制,另一方面是rehash够复杂效率够低,但Facebook的工程师选择了
让80%的cpu执行要够快,而剩余的20%cpu稍低点也可以接受的思路。
AtomicHashmap的rehash类似于dequue的扩充策略,这会有两个结论
- 当容量未满时,这属于80%的概率事件,依然可以O(1)
- 当容量满时,这属于20%的概率事件,依然可以O(2),O(3),O(4...)
简单+28原则
AtomicHashmap的冲突解决策略是线性探测,线性探测会因为本次冲突而影响其他key的插入,而拉链法没有这个问题。为什么Facebook的工程师
选择这个呢,我想首先冲突也是属于20%概率事件,那么代码效率稍差也是可以接受的,其次这个拉链其实就是个多生产者多消费者模式下的队列,
参见boost的一个无锁实现,比线性探测复杂多了,而线性探测也有个优点就是局部性好。
O(1)变成O(N)
看个场景
step1:100个并发,每个并发做100次的随机插入,AtomicHashmap的size设置为10w,总共插入14w数据。
step2:2个并发查询,查询的key不存在
step3:cpu idle降为0
如何解决
通过上一篇的源码分析,得出有三个怀疑点
- 要查的key发生过冲突,那么查找最好的情况是往后遍历一个或者几个(取决于hash算法和容量大小)找到元素,
或者发现空元素,然后结束查找;而最坏的情况(map里空间全部被占用)是遍历查找一遍,
当然这种可能性很小,取决于填充因子和插入的并发度 - 要查的key没有插入过,那么最好的情况是遇到第一个空元素结束查找,最坏的情况是遍历查找一遍
- 要查的key已经被删除了,这种情况同上
总结就是空间上空元素的分布很重要,而分布情况有三种
- 所有元素都被使用,没有空元素
- 被使用元素集中分布,相应的空元素也集中分布
- 被使用元素和空元素相隔/均匀分布
后两种分布主要取决于hash算法,好的hash算法能尽量保证每一bit变化的输入反映在输出上。
测试场景使用的hash算法是通用的Murmurhash,此算法效果是比较好的,在实际使用中并不会发生这两种情况,
那么问题就只有第一种分布:没有空元素
insertInternal(KeyT key_in, T&& value) {
......
if (isFull_.load(std::memory_order_acquire))
return false; //满了,不让再插入这个map了 ++numEntries_; //已插入的数量
if (numEntries_.readFast() >= maxEntries_) {
isFull_.store(true, std::memory_order_relaxed); //isfull设置为true
......
}
这是AtomicHashmap的插入逻辑:当插满时,不允许插入。那应该不会出现没有空元素的情况吧?no
maxEntries_为10w,填充因子为0.8,那么元素的容量=12.5w(10/0.8),那么空元素的容量为2.5w(12.5w-10w)。
可是为什么空元素的容量为0呢?
numEntries_为thread_cache_int类型,这个类的大致思想是可以配置一个cache_size,那么访问这个numEntries_对象
的所有线程的局部变量++到cache_size后才会同步给其他线程(即readFast可以获取到)。
比如cache_size配置为1000,线程数为100,那么理论上readFast的最大延迟同步为100*1000=10w。
10w远大于空元素的容量2.5w,即有可能发生实际插入元素已经满了(空元素容量为0),而isFull_依然为false。
遇到这种问题,解决思路是把容量调大。