哪些购物网站用php做的,140平米装修全包费用,高端网站建设成都,wordpress 附件id杀手锏SwissTable 0.导语 最近在研究HashJoin的性能#xff0c;发现SwissTable的性能真牛逼#xff0c;对于原生的哈希表采用STL的unordered_multimap#xff0c;其性能一般#xff0c;为了加速这个查找#xff0c;Arrow提供了SwissJoin#xff0c;其实现原理为SwissTabl… 杀手锏SwissTable 0.导语 最近在研究HashJoin的性能发现SwissTable的性能真牛逼对于原生的哈希表采用STL的unordered_multimap其性能一般为了加速这个查找Arrow提供了SwissJoin其实现原理为SwissTable但是其细节部分还是有很多不一样的地方本节先来个开篇以经典的abseil库的代码为例先聊聊abseil库里面的SwissTable原理。 SwissTable在性能上远超于std::unordered_map的哈希表。 通常哈希表会面临几个问题其中最重要的便是哈希碰撞。 比较经典的算法有拉链法、线性探测法。 拉链法 像std::unordered_map的哈希表采用拉链法实现对于CPU 需要读写内存地址会检测缓存是否存在由于链表的随机访问性质会导致缓存查询失败性能会骤降。 线性探测法 对于拉链法缓存问题我们可以使用线性探测法解决对cache来说比较友好。由于是顺序访问元素当这些连续的内存正好是cache line的一部分时省下了CPU指令周期但是当元素越来越多连续的序列也会变长查询缓存失败率也会加大。 因此我们需要解决几个问题 CPU cache比内存快n倍如何有效利用cache来加速哈希表的查找如何解决hash冲突 为了解决这些问题于是有了缓存友好、内存与CPU效率比较高的SwissTable。 1.abseil SwissTable SwissTable的伪代码 int8_t* ctrl_;
char* slots_; SwissTable划分为control byte结构与slots结构如下图所示 对于每个key的hash值拆分成两部分 H1: hash最左边57位找到第几个group。 H2: hash最右边7位 假设每个group有16个slot同时有16个控制字节。 控制字节Carol byte为8位有三个状态 空 10000000 删除 11111110 在使用 当有数据时ctro byte长这个样子00010100最高位为0。 哨兵 只是个dummy 当执行查询时先通过h1计算出对应group的起始位置然后扫描当前group中的控制字节(通过h2)搜索出对应的slot。 其中根据group的其实位置扫描key是否存在这一步骤如果进行“线性探测”可就太慢了。 于是SwissTable怎么做了 一组的控制字节为 128 位可以放入 L1 的cache line像SSE2这类的指令可以直接使用128位快速搜索出对应的slot。 所以可以一次比较一整个group的control bytes信息从而确定这个key在不在当前group中如下图所示一次可以比较16个值。如果当前group没有找到继续查找下一个group。当然涉及的好的话一次可以通过simd算n个group。 插入过程 查找到目标的key如果存在更新目标key完毕。当前hash值可以计算出哪个group这个group如果满了就下一个group找空位然后插入对应slot。 当然插入过程还涉及扩容操作。 本节简单讲解了SwissTable的原理下一节详细讲讲Arrow的SwissTable。 更多资料欢迎加入与我一起探讨。
