SEAL库中reverse_bits索引为何能实现合并内存访问？

位反转索引优化内存访问的核心逻辑 #

位反转索引的优化目标是匹配NTT迭代计算阶段的高频访存模式，你观测到的连续输入i对应输出分散的现象只出现在常数数组的一次性初始化阶段，二者场景完全不同，具体逻辑如下：

• 首先明确开销对比：inv_root_powers是预计算的根幂常数数组，整个程序运行周期内仅会初始化一次，哪怕写入时地址分散，产生的开销也可以完全忽略；而NTT计算是同态加密运算中的核心热点路径，会被反复调用数万到数百万次，访存性能的提升会被指数级放大。
• Cooley-Tukey迭代式NTT的原生访存缺陷：如果根幂数组按自然顺序存储，每一层蝶形运算需要访问的两个元素地址间隔为2^k（k为当前迭代层数），高层迭代时间隔可达到数KB甚至更大，完全无法命中CPU缓存，也不支持SIMD指令的连续内存加载，访存效率极低。
• 位反转重排后的访存收益：将根幂数组按reverse_bits重排后，每一层蝶形运算需要访问的所有元素都会对应连续的内存块，刚好适配CPU的缓存预取策略，连续的地址也支持CPU将多个零散访存请求合并为单个缓存行访问，同时可以直接用AVX2/AVX512等SIMD指令一次性加载多个连续存储的根幂数据，访存吞吐量可以提升数倍。

你可以用8点NTT的极简场景验证：8个元素的位反转索引为[0,4,2,6,1,5,3,7]，原生顺序存储时第一层蝶形需要访问(0,4)、(1,5)、(2,6)、(3,7)，地址间隔为4；重排后第一层蝶形访问的是(0,1)、(2,3)、(4,5)、(6,7)，所有地址完全连续，直接实现合并访问。

内容的提问来源于stack exchange，提问作者Poperton