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# を使用していましたが、実際、logical を使用するコード&は他のコードよりも高速で、3 倍高速になることもあります。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# でそのように動作しないのか (2​​ つの関数の間に明らかなパフォーマンスのギャップがある場合)、なぜ JIT コンパイラが と同じ最適化を適用しないのか疑問に思い始めましたgcc。JITコンパイラの出力をインターセプトする方法があるかどうかはわかりませんが、理解に役立つでしょうか?

おまけの質問: モジュロは除算に基づいていると思いますが、除算は O(n²) 時間 (n は桁数) で行われるため、モジュロは 2 次時間複雑度を持つと言えますか?