c++ - 为什么需要模运算符？

Question

我在一个文档中读到，您可以用逻辑替换 mod 操作，如下所示：

反而：

int Limit = Value % Range;

你做：

int Limit = Value & (Range-1);

但是编译器仍然会生成 mod 指令，我的问题基本上是：如果编译器工作相同，为什么编译器不使用最有效的方法？

Answer 1

嗯，不……只有当Range是 2 的幂时才有效。

对于所有其他值，您仍然需要模数%运算符。

使用负数时也有一些细微的（可能是实现定义的）差异。

---

附带说明：使用%运算符也可能更具可读性。

Answer 2

只有当它是 2 的幂时，你才能用它替换模数。使用初等数学来替换它而不用模数

a = b % c;

可以用

x = b % c;
a = b / (x*c);

让我们用一个例子来检查一下

25 % 7 = 
25 / 7 = 3 (integer math)
25 - (3 * 7) =
25 - 21 = 4

因为我没有模运算符，所以无论如何我必须在我的计算器上这样做。

注意

25 & (7-6) = 
0x19 & 0x6 = 0x0

所以你的替换不起作用。

不仅大多数处理器没有模数，许多处理器也没有除法。查看黑客喜悦书。

为什么要取模？如果您已经烧毁了硬件以进行划分，那么您可能也愿意加倍努力来添加模数。大多数处理器将您的问题提升到一个新的水平，当它可以在软件中完成时，您为什么要在硬件中实现它。您的问题的答案是大多数处理器系列没有模数，并且许多没有分频器，因为与软件解决方案相比，它不值得芯片空间、功耗等。软件解决方案的痛苦/成本/风险较小。

现在我假设你的问题不是获奖海报的答案。对于 Range 是 2 的幂并且恒等式确实有效的情况...首先，如果在编译时不知道范围，那么您必须执行减法和一个与，两个操作，也许还有一个中间变量，即比模更昂贵，编译器将错误地优化为减法和而不是模数。如果范围是 2 的幂并且在编译时已知，那么您更好/更高级的编译器将进行优化。有时，尤其是具有可变字长指令集的情况下，较小的指令可以在较大的指令上使用，加载 Range 并进行模运算可能比加载大量非零位（值与您的身份匹配的范围在值中设置了一个位，其他位为零，0x100、0x40、0x8000 等）并进行取模。load immediate plus modulo 可能比 load immediate plus and 便宜，或者 modulo immediate 可能比 and immediate 便宜。您必须检查指令集以及编译器如何实现解决方案。

我建议您发布一些未进行优化的示例，并且我假设我们可以发布许多示例，说明编译器在何处进行了您所期望的优化。

Answer 3

正如其他人所说，范围必须是 2^n-1，即使这样，如果它是在运行时完成的，你也会遇到问题。

在最近的架构上（比方说，P4 时代之后的任何东西）整数除法指令的延迟在最坏情况下在 26 到 50 个周期之间。相比之下，乘法可以是 1-3 个周期，并且通常可以更好地并行完成。

DIV 指令返回 EAX 中的商和 EDX 中的余数。“余数”是自由的（模数是余数）。

如果你在运行时实现范围可变的东西，如果你想使用 &，你必须：

a) 检查范围是否为 2^n-1，如果是，请使用您的 & 代码路径：这是一个分支，可能的缓存未命中等。增加了巨大的潜在延迟 b) 如果不是 2^n-1，则使用DIV 指令

使用 DIV 而不是在等式中添加分支（在缓存驱逐不佳的情况下，这可能会花费数百甚至数千个周期）使 DIV 成为明显的最佳选择。最重要的是，如果您将 & 与带符号的数据类型一起使用，则需要进行转换（对于混合数据类型没有 &，但对于 DIV 有）。此外，如果 DIV 仅用于从模数中进行分支，而不使用其余结果，则推测执行可以很好地执行；可以并行执行指令的多个管道也进一步减轻了性能损失。

您必须记住，如果您使用的是真实代码，您的大量缓存将被您正在处理的数据以及您将很快使用或刚刚处理的其他代码和数据填充。您真的不想因为分支预测错误而驱逐缓存页面并等待它们调入页面。在大多数模数情况下，你不只是去 i = 7; d = 我 % 4; 您正在使用较大的代码，该代码通常调用一个子程序，该子程序本身就是一个（预测和缓存的）子程序调用。此外，您可能正在循环中执行此操作，该循环本身也使用分支预测；带有循环的嵌套分支预测在现代微处理器中得到了很好的处理，但它最终只是简单地添加到它试图做的预测中。

总而言之，对于一般用例，在现代处理器上使用 DIV 更有意义；由于缓存考虑和其他因素，编译器生成 2^n-1 并不是真正的“优化”。如果您真的需要微调整数除法，并且您的整个程序都依赖于它，那么您最终会将除数硬编码为 2^n-1 并自己进行按位和逻辑。

最后，这有点啰嗦——用于整数除法的专用 ALU 单元确实可以将延迟减少到大约 6-8 个周期，它只是占用了相对较大的芯片区域，因为数据路径最终大约为 128 位宽，并且当整数 DIV 工作得很好时，没有人拥有它的空间。