这个数组索引器如何帮助合并内存访问？

Question

在这里，定义了这个函数：

        template <typename T, typename = std::enable_if_t<is_uint32_v<T> || is_uint64_v<T>>>
        inline T reverse_bits(T operand, int bit_count)
        {
            // Just return zero if bit_count is zero
            return (bit_count == 0) ? T(0)
                                    : reverse_bits(operand) >> (sizeof(T) * static_cast<std::size_t>(bits_per_byte) -
                                                                static_cast<std::size_t>(bit_count));
        }

稍后，该函数用于将元素以打乱的方式存储到数组中：

inv_root_powers_[reverse_bits(i - 1, coeff_count_power_) + 1].set(power, modulus_);

这样做的理由是为了合并内存访问。但是，我不知道为什么这样的随机值会使内存访问更容易。例如，以下是一些值：

reverse_bits(3661, 12) +1 = 2856
reverse_bits(3662, 12) +1 = 1832
reverse_bits(3663, 12) +1 = 3880
reverse_bits(3664, 12) +1 = 168
reverse_bits(3665, 12) +1 = 2216
reverse_bits(3666, 12) +1 = 1192
reverse_bits(3667, 12) +1 = 3240
reverse_bits(3668, 12) +1 = 680
reverse_bits(3669, 12) +1 = 2728

看起来东西都存放得很远。

Answer 1

你是对的 - 你看到的访问NTTTables::initialize是随机访问而不是串行访问。由于这种“争夺”，它变得更慢。然而，大部分工作仅在稍后DWTHandler::transform_to_rev应用变换本身时发生。

在那里，他们需要通过相反的位顺序访问根。数组被预加扰意味着对该数组的所有访问现在都是串行的：您可以在行中看到这一点r = *++roots;。

反向位访问模式有一个很好的、真正的原因 - 这是因为他们正在执行有限傅立叶变换 (FFT) 的变体。这些算法中使用的内存访问模式（有时称为蝴蝶）是按位逆序完成的。