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

Question

在here处定义了这个函数：

        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));
        }

在later point，这个函数用于将元素以乱码的方式存储到数组中：

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) 的变体。这些算法中使用的内存访问模式（有时称为蝴蝶）是按位反转顺序完成的。

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

How does this array indexer helps coalesced memory access?

c++

memory

arrays

ram