c++ - 将两个 uint8_ts 视为 uint16_t 效率较低

Question

假设我创建了一个类，它的模板参数等于我想串成一个大整数的 uint8_t 数。

这样我就可以像这样创建一个巨大的整数:

SizedInt<1000> unspeakablyLargeNumber;  //A 1000 byte number

现在问题来了:我是不是通过使用 uint8_t 而不是使用更大的内置类型来降低速度。

例如:

SizedInt<2> num1;
uint16_t num2;

num1 和 num2 速度相同，还是 num2 更快？

Answer 1

毫无疑问，使用 uint8_t[2] 而不是 uint16_t 会更慢。

以加法为例。为了使 uint8_t[2] 的速度达到 uint16_t 的速度，编译器必须弄清楚如何转换您的 add-with-carry 逻辑和融合将这些多条指令合并为一条更广泛的指令。我敢肯定，有些编译器有时能够进行此类优化，但在很多情况下，这种优化不太可能或不可能进行。

在某些架构上，这甚至适用于加载/存储，因为 uint8_t[2] 通常具有与 uint16_t 不同的对齐要求。

典型的 bignum 库，例如 GMP , 处理对架构方便的最大单词。在 x64 上，这意味着使用 uint64_t 数组而不是像 uint8_t 这样更小的数组。在现代微处理器上相加两个 64 位数字的速度相当快，事实上，它通常与相加两个 8 位数字的速度相同，更不用说通过小数数组传播进位位引入的数据依赖性了。这些数据依赖性意味着您通常每个时钟周期只能添加一个数组元素，因此您希望这些元素尽可能大。 (在硬件层面，有一些特殊技巧可以让进位位在整个 64 位操作中快速移动，但这些技巧在软件中不可用。)

如果您愿意，您始终可以使用模板特化来选择合适大小的基元来制作您想要的最节省空间的 bignum。否则，使用 uint64_t 数组更为典型。

如果可以选择，通常最好只使用 GMP。 GMP 的某些部分是用汇编语言编写的，以使 bignum 操作比其他方式快得多。