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

不用说编译后的代码在两者之间也是is_even一样的。is_even_bis-O0

如果我可以说，更有趣的是，我的另一个朋友使用 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 是位数），我们可以说模具有二次时间复杂度吗？

4

1 回答 1

2

首先，在便携的意义上，这些操作没有速度的概念。你的断言可能对你的系统是正确的，但它们对所有系统都是无效的。因此，对微优化进行推测是毫无意义的。您可以通过生成解决有意义问题的程序、对其进行分析以找到占用最多执行时间的代码部分并针对这些时间引入更快的算法来找到更重要的优化。通过更快的算法，我的意思是更好的数据结构（或更少的操作），而不是不同的操作符。停止关注微优化！

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

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

也许您的 C 编译器已经注意到%您使用的表达式和您使用的表达式在您的系统上&是等效的，因此进行了优化，但无论出于何种原因，C# 或 OCaml 编译器都没有执行优化。

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

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

于 2013-04-25T11:15:09.523 回答