在C#、C和OCaml中的模运算

Question

在C#、C和OCaml中的模运算

4

我想确认取模运算是否是一项昂贵的操作，因此我测试了这段代码，用于检查给定数字是否为偶数：

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

那么下面这个：

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

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

然而，正如我的一个朋友在C语言中发现的那样，使用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的编译代码是相同的。

更有趣的是，我的另一个朋友尝试使用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

看起来在运行字节码时，模数版本更快，但在本机代码中较慢！也许有人可以解释这个谜题？

然后我开始想知道为什么它在C#中不表现出这样的行为（两个函数之间存在明显的性能差距），以及为什么JIT编译器不像gcc一样应用相同的优化。我不知道是否有一种方法可以拦截JIT编译器的输出，也许这可以帮助理解？

额外问题：我猜取模是基于除法的，由于除法的时间复杂度为O(n²)（n是数字的位数），我们可以说取模具有二次时间复杂度吗？

- Max

我们可以说取模具有二次时间复杂度吗？不可以。 - H H

你肯定在计时一个发布版本，对吧？ - Matthew Watson

@MatthewWatson：我并不是，只是好奇一下 :) - Max

@HenkHolterman，您能详细说明一下吗？ - Max

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- autistic · Accepted Answer

首先，在“可移植”的意义下，这些操作没有“速度”的概念。你的说法可能对“你的系统”是正确的，但对“所有系统”来说是无效的。因此，纯粹地推测微小优化是毫无意义的。你可以通过编写解决实际问题的程序，对其进行分析以找出占用大部分执行时间的代码部分，并为这些部分引入更快的算法来找到更重要的优化。所谓“更快的算法”，指的是“更好的数据结构”（或“更少的操作”），而不是“不同的运算符”。停止关注微小优化！

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

似乎你所看到的差异可能是由于你的系统上使用了有符号整数表示。考虑如果-1使用补码11111111...11111110来表示。你期望 -1 % 2 的结果为 -1，而不是0，对吗？（编辑：…但如果-1表示为11111111...11111110，你希望-1 & 1的结果是什么？） 需要一些额外的开销来处理使用补码作为有符号整数表示的实现。

也许你的C编译器已经注意到你使用的%表达式和&表达式在你的系统上是等价的，并因此进行了优化，但由于某种原因，C#或OCaml编译器没有执行这个优化。

奖励问题：我猜取模是基于除法的，而且由于除法的时间复杂度为O(n²)（n为数字的位数），我们可以说取模具有二次时间复杂度吗？

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