c# - C#、C 和 OCaml 中的模运算

Question

我想确认模运算是一项昂贵的操作，所以我测试了这段代码来检查给定数字是否为偶数:

bool is_even(int n) {
    return (n & 1) == 0;
}

然后这个:

bool is_even_bis(int n) {
    return (n % 2) == 0;
}

我一开始用的是C#，确实，使用逻辑&的代码比其他的快，有时甚至快三倍。使用 ILSpy 我看到编译为 MSIL 时没有进行任何优化，代码完全相同。

然而，正如我的一个使用 C 语言的 friend 所发现的那样，使用 gcc -O3 代码被编译为:

is_even:
    mov     eax, DWORD PTR [esp+4]  # tmp63, n
    and     eax, 1  # tmp63,
    xor     eax, 1  # tmp63,
    ret

和:

is_even_bis:
    mov     eax, DWORD PTR [esp+4]  # tmp63, n
    and     eax, 1  # tmp63,
    xor     eax, 1  # tmp63,
    ret

所以基本上完​​全一样。即使在使用 -O0 优化时，操作也不会出现:

is_even:
    push    ebp     #
    mov     ebp, esp        #,
    mov     eax, DWORD PTR [ebp+8]  # tmp63, n
    and     eax, 1  # D.1837,
    test    eax, eax        # D.1837
    sete    al      #, D.1838
    movzx   eax, al # D.1836, D.1838
    pop     ebp     #
    ret

不用说-O0中is_even和is_even_bis的编译代码也是一样的。

更有趣的是，我的另一个 friend 使用 OCaml 进行了同样的尝试:

let is_even x = ((x land 1) == 0)

let _ = 
  let i = ref 100000000 in
  while !i > 0 do
    ignore (is_even !i);
    decr i
  done

和:

let is_even_bis x = ((x mod 2) == 0)

let _ = 
  let i = ref 100000000 in
  while !i > 0 do
    ignore (is_even_bis !i);
    decr i
  done

而且看起来模数版本在运行字节码时速度更快，但在 native 代码中速度较慢!也许有人可以解释这个谜团？

然后我开始想知道为什么它在 C# 中的行为不同(这两个函数之间存在明显的性能差距)以及为什么 JIT 编译器不应用与 gcc 相同的优化.不知道有没有办法拦截JIT编译器的输出，或许能帮助理解？

奖金问题:我猜模是基于除法的，因为除法是在 O(n²) 时间内完成的(n 是数字的数量)，我们可以说模具有二次时间复杂度吗？

Answer 1

首先，在可移植的意义上，这些操作没有速度的概念。您的断言可能对您的系统 是正确的，但它们对所有系统 都是无效的。出于这个原因，推测微优化是毫无意义的。您可以通过生成一个解决有意义的问题的程序，对其进行分析以找到占用最多执行时间的代码部分并为这些时间引入更快的算法，从而找到更重要的优化。我所说的更快的算法，是指更好的数据结构(或更少的操作)，而不是不同的运算符。不要再专注于微优化!

is_even 的 C 版本定义不明确。它可能会产生负零或陷阱表示，特别是对于负数。使用陷阱表示是未定义的行为。

您可能看到的差异似乎是由 signed integer representation 引起的在你的系统上。考虑是否要使用补码 11111111...11111110 来表示 -1。您希望 -1 % 2 的结果是 -1，而不是 0，对吗？ (编辑:...但是如果 -1 表示为 11111111...11111110，您希望 -1 & 1 产生什么结果？) 需要一些开销来处理使用补码作为有符号整数表示的实现。

也许您的 C 编译器已经注意到您使用的 % 表达式和您使用的 & 表达式在您的系统上 是等价的，并且作为结果进行了优化，但 C# 或 OCaml 编译器出于某种原因并未执行优化。

Bonus question : I guess the modulo is based on division and since the division is done in O(n²) time (n being the number of digits) can we say that the modulo has quadratic time complexity?

没有必要考虑这两个基本操作的时间复杂度，因为它们会因系统而异。我在第一段中介绍了这一点。