跳表+Intel TSX事务内存
本帖最后由 你有种再说一遍 于 2025-4-17 17:12 编辑索引分布不均:
由于跳表生成的索引是随机的,
搜索时候定位到最下层之后,还有一个线性扫描,
这个线性扫描会随着跳表不断插入而增加,尤其是到了后段.
方案一:
通过动态晋升概率来优化.
方案二:
利用SIMD提速这个线性扫描.
需要利用节点固定大小到SIMD长度,从而降低这种索引分布不均的代价.
那么可以利用SIMD要求的定长,随机把生成索引定位在128/256位置,
此时在上百亿个key就可以充分利用SIMD了.
你可以发现这些方式下,除非特别长的跳表,
否则速度仍然是取决于随机访问的跳跃速度.
并且由于块内是连续的,竞争插入同一个块的多线程仍然耗时,
因为插入块内需要锁块.
此时定制硬件就显得重要了,如果有一个原子性的话...
然后我就去找资料,发现嘿嘿,还真有.
若硬件支持原子性操作SIMD数组(如Intel TSX事务内存)
可进一步减少锁开销.
然后发现了AMD居然没这个,看来通用性不大,
难怪没有成为跳表的基础 很深的研究咯
页:
[1]