跳表+Intel TSX事务内存

你有种再说一遍

索引分布不均:
由于跳表生成的索引是随机的,
搜索时候定位到最下层之后,还有一个线性扫描,
这个线性扫描会随着跳表不断插入而增加,尤其是到了后段.

方案一:
通过动态晋升概率来优化.

方案二:
利用SIMD提速这个线性扫描.

需要利用节点固定大小到SIMD长度,从而降低这种索引分布不均的代价.
那么可以利用SIMD要求的定长,随机把生成索引定位在128/256位置,
此时在上百亿个key就可以充分利用SIMD了.

你可以发现这些方式下,除非特别长的跳表,
否则速度仍然是取决于随机跳跃.

由于块内是连续的,竞争插入同一个块的多线程仍然耗时,
因为插入块内需要锁块.
此时定制硬件就显得重要了,
如果有一个原子性的话...

然后我就去找资料,发现嘿嘿,还真有.
若硬件支持原子性操作SIMD数组(如Intel TSX事务内存)
可进一步减少锁开销.
然后发现了AMD居然没这个,看来通用性不大,
难怪没有成为跳表的基础

gzxl

很深的研究咯