为什么 static_cast 转换会加速我的整数除法函数的未优化构建？

Question

... 或者更确切地说，为什么没有 static_cast-ing 减慢我的功能？

考虑下面的函数，它执行整数除法：

int Divide(int x, int y) {
  int ret = 0, i = 32;
  long j = static_cast<long>(y) << i;
  while (x >= y) {
    while (x < j) --i, j >>= 1;
    ret += 1 << i, x -= j;
  }
  return ret;
}

这表现得相当不错，正如人们所期望的那样。但是，如果我们删除第 3 行的 static_cast，如下所示：

int Divide(int x, int y) {
  int ret = 0, i = 32;
  long j = y << i;
  while (x >= y) {
    while (x < j) --i, j >>= 1;
    ret += 1 << i, x -= j;
  }
  return ret;
}

对于 x 较大且 y 较大的病态输入，此版本的执行速度明显较慢，有时会慢数百倍（我没有严格测量，但应该相差不远）小的。我很好奇并想研究原因，并尝试深入研究汇编代码。然而，除了第 3 行的转换差异之外，我得到了完全相同的输出。这是第 3 行的输出供参考 (source):

与static_cast:

movsxd  rax, dword ptr [rbp - 8]
mov     ecx, dword ptr [rbp - 16]
shl     rax, cl
mov     qword ptr [rbp - 24], rax

没有static_cast:

mov     eax, dword ptr [rbp - 8]
mov     ecx, dword ptr [rbp - 16]
shl     eax, cl
cdqe
mov     qword ptr [rbp - 24], rax

其余相同

我真的很好奇开销在哪里发生。

编辑：我进一步测试了一下，看起来 while 循环是花费大部分时间的地方，而不是 y 初始化时.额外的 cdqe 指令似乎不足以保证墙上时间的总增加。

一些免责声明，因为我收到了很多与实际问题无关的评论：

我知道将 int 移动超过 32 位是 UB。
我假设只有正输入。
long 在我的平台上是 8 个字节长，所以它不会溢出。

我想知道可能导致运行时间增加的原因，批评上述内容的评论实际上并未解决。

Answer 1

我暂时保留这个答案，因为评论很有用。

Answer 2

int Divide(int x, int y) {
  int ret = 0, i = 32;
  long j = y << i;

在大多数系统上，int 的大小为 32 位或更少。 Left-shifting 一个带符号的整数，其位数等于或大于其大小会导致未定义的行为。不要这样做。既然程序坏了，慢点快点都无所谓

_{旁注：将带符号的 32 位整数左移 31 位或更少位也可能是未定义的，如果该移位导致最左边的位由于算术溢出而改变。}

Answer 3

移位后加宽将您的循环减少到简单的重复减法

这与 cdqe 或 movsxd 与 mov 的 run-time 无关，这是循环的不同起始值，导致不同的迭代次数，特别是对于病理病例。

没有优化的 Clang 完全按照编写的方式编译您的源代码，对 int 进行移位，然后 sign-extending 结果为 long。 shift-count UB 对于禁用优化的编译器是不可见的，因为 for consistent debugging, it assumes variable values can change between statements，因此行为取决于目标机器通过 operand-size 对 shift-count 执行的操作。

为 x86-64 编译时，结果是 long j = (long)(y<<0);，即 long j = y;，而不是将这些位放在 64 位值的顶部。

x86 scalar shifts like shl eax, cl 用 &31 屏蔽计数（64 位操作数大小除外），因此移位使用了 32 % 32 == 0 的计数。我认为 AArch64 会使移位计数饱和，即让您移出所有位。

请注意，它使用 operand-size shl eax, cl 和然后 sign-extends 结果 cdqe，而不是sign-extending 重新加载 y 然后是 64 位 operand-size shl rax,cl.

您的循环有 data-dependent 次迭代计数

如果您 single-step 使用调试器，您可以准确地看到局部变量值。（这是 un-optimized 调试构建的主要好处，即 not what you should be benchmarking。）您可以计算迭代次数。

  while (x >= y) {
    while (x < j) --i, j >>= 1;
    ret += 1 << i, x -= j;
  }

使用j = y，如果我们完全进入外循环，那么内循环条件永远为假。
所以它永远不会运行s，j 始终保持不变，并且 i 保持不变在 32.

1<<32 再次编译为具有 32 位 operand-size 的 variable-count 移位，因为 1 的类型为 int。（1LL 的类型为 long long，并且可以安全地 left-shifted 到 32）。在 x86-64 上，这只是一种执行 ret += 1;.

的缓慢方法

x -= j; 当然只是 x -= y;，所以我们计算要进行多少次减法 x < y。

well-known 对于大商，通过重复减法进行除法非常慢，因为运行时间与商成线性关系。

不过你碰巧得到了正确的结果。耶。

顺便说一句，long 在某些目标上仅是 32 位的，例如 Windows x64 和 32 位平台；如果您想要 int 宽度两倍的类型，请使用 long long 或 int64_t。也许 static_assert 以确保 int 没有那么宽。

启用优化后，我认为同样的事情仍然适用：clang 看起来就像是在没有 store/reload 的情况下编译成类似的 asm。所以它有效地 / de-facto 定义了 1<<32 的行为只编译为 x86 移位指令。

但我没有测试，只是快速浏览了 asm https://godbolt.org/z/M33vqGj5P 并注意到 mov r8d, 1 之类的东西； shl r8d, cl（32 位 operand-size）； add eax, r8d

为什么 static_cast 转换会加速我的整数除法函数的未优化构建？

Why does static_cast conversion speed up an un-optimized build of my integer division function?

c++

assembly

x86-64

type-conversion

undefined-behavior

移位后加宽将您的循环减少到简单的重复减法

您的循环有 data-dependent 次迭代计数