为什么 ARM 上的 gcc 或 clang 不使用 "Division by Invariant Integers using Multiplication" 技巧？

Question

有一个众所周知的技巧，可以执行除以不变整数实际上根本不做除法，而是做乘法。这已在 Stack Overflow 以及 and in Why does GCC use multiplication by a strange number in implementing integer division?

中进行了讨论

不过，我最近在 AMD64 和 ARM（Raspberry Pi 3 模型 B）上测试了以下代码：

#include <sys/time.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int main(int argc, char **argv)
{
  volatile uint64_t x = 123456789;
  volatile uint64_t y = 0;
  struct timeval tv1, tv2;
  int i;
  gettimeofday(&tv1, NULL);
  for (i = 0; i < 1000*1000*1000; i++)
  {
    y = (x + 999) / 1000;
  }
  gettimeofday(&tv2, NULL);
  printf("%g MPPS\n", 1e3 / ( tv2.tv_sec - tv1.tv_sec +
                             (tv2.tv_usec - tv1.tv_usec) / 1e6));
  return 0;
}

代码在 ARM 架构上非常慢。相比之下，在 AMD64 上它非常快。我注意到在 ARM 上，它调用 __aeabi_uldivmod，而在 AMD64 上它实际上根本不除法而是执行以下操作：

.L2:
        movq    (%rsp), %rdx
        addq    9, %rdx
        shrq    , %rdx
        movq    %rdx, %rax
        mulq    %rsi
        shrq    , %rdx
        subl    , %ecx
        movq    %rdx, 8(%rsp)
        jne     .L2

问题是，为什么？ ARM 体系结构是否有某些特定功能使此优化不可行？还是仅仅因为ARM架构的稀缺性，没有实现这样的优化？

在人们开始在他们的评论中提出建议之前，我会说我尝试了 gcc 和 clang，还尝试了 -O2 和 -O3 优化级别。

在我的 AMD64 笔记本电脑上，它提供 1181.35 MPPS，而在 Raspberry Pi 上它提供 5.50628 MPPS。这相差超过2个数量级！

Answer 1

gcc 仅使用乘法逆来除以寄存器宽度或更窄。您正在针对 ARM32 测试 x86-64，因此 uint64_t 在这种情况下为 x86-64 提供了巨大优势。

扩展精度乘法在具有高吞吐量乘法的 32 位 CPU 上可能是值得的，例如现代 x86，如果您的 Cortex-A7 ARM 具有更好的乘法器，也可能是值得的流水线比它的分隔线。

仅使用 32x32 => 64b 作为构建块，需要多个 mul 指令才能获得 64b x 64b => 128b 完整乘法结果的高半部分。（IIRC ARM32 有这个。）

然而，这不是 gcc 或 clang 在任何优化级别选择做的事情。

如果您想限制 x86 CPU，请使用 -m32 编译 32 位代码。 x86 gcc -O3 -m32 will use __udivdi3。不过，我不会称其为 "fair"，因为 64 位 CPU 在 64 位算法上要快得多，而 Cortex-A7 没有可用的 64 位模式。

OTOH，仅 32 位的 x86 CPU 在 32 位模式下不会比当前的 x86 CPUs 快多少；在 32 位模式下未使用的额外晶体管的主要成本是管芯面积和功耗，而不是高端时钟速度。如果某些低功耗预算 CPUs（如 ULV 笔记本电脑芯片）在设计时不支持长模式 (x86-64)，则它们可能会维持更长时间的最大涡轮增压，但这非常小。

因此，对 32 位 x86 与 32 位 ARM 进行基准测试可能很有趣，也许只是为了了解一些有关微体系结构的知识。但是如果你关心 64 位整数的性能，绝对编译 x86-64 而不是 x86-32。

为什么 ARM 上的 gcc 或 clang 不使用 "Division by Invariant Integers using Multiplication" 技巧？

Why doesn't gcc or clang on ARM use "Division by Invariant Integers using Multiplication" trick?

optimization

performance

assembly

multiplication

division