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

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)的一种变体。在这些算法中使用的内存访问模式(有时称为蝴蝶)是以位反向顺序完成的。