cad.net 最快的字典SwissTable

你有种再说一遍

其实世界上大部分软件很多都没有发挥真正的硬件速度.
起码2-48倍提速是大部分软件都可以做到的,
大部分人是因为写得方便而不考虑运行速度,
这也无可厚非,不过不学习别人怎么加速的话,
就会像个别群友一样觉得行业顶尖软件就是最好最快,
从而小看了大公司惰性,因为一句工程实现简单就很容易断送了后续.

例如
SimdJson代替了已有方案.
ZLinq代替了Linq.
只要有个是API层面兼容的,基本上没有什么理由不去换包.

软件开发三部曲:先做出来,再把它做好,最后是做快.
我在思考怎么把扫描线算法逼近5ms


谷歌推出SwissTable巧妙的利用了
开放寻址法+元数据数组+分片扩容+对齐数组+SIMD+渐进扩容.
它构建了两个hash,h1检索分片,h2检索槽.
主要加速其实是SIMD微并行,
因为分支预测失败一次回退15-20时钟周期,4核并行就相当于30-80条指令.
也就是宁愿写多30-80条指令进行处理,也不要触发一次失败,
这说明分类和SIMD真的好重要哦.
难怪字节跳动都提议Go语言map换成它.
https://www.cnblogs.com/apocelipes/p/17562468.html

众所周知,编程拉到极限总是要处理分支预测失败.
它没有利用多核并行+SIMD(我最下面会说为什么)
只是在查询时候用一次SIMD来代替多次跳跃检查.
并且hash命中末尾的话,没有采用绕回,而是会写入到下一个分片.
在当前h1命中分片上面找不到:
SIMD对比执行了一次+遍历结果集进行EQ,
如果仍然找不到,会去下一个分片继续.

它的缩容也很有趣,它不是没有删除元素,而是标记槽为墓碑,来实现延迟处理,并且是meta元数组进行标记,不是槽数组.
分离设计就是SOA (Structure of Arrays)数组的结构体.

其实耗尽CPU算力岂不是导致其他进程短时间饥饿导致QPS下降,所以我觉得SIMD在服务器上面用处应该很少.
CK数据库真的那么干之后,发现QPS真的很少.
不过这次看到了一个微并行的SIMD场景.

在OLTP或高QPS场景中,
这种资源竞争可能导致整体吞吐量下降.
ClickHouse（CK）作为OLAP系统,
更注重单查询性能而非高并发,所以这种取舍是合理的


对了AVX512引发降频,还不如不用.

https://mp.weixin.qq.com/s?__biz ... 1&app_lang=zh-CN#rd

scnc001

不明觉厉。