4 billion if statements (2023)

以下は、元の英語テキストを日本語に訳したものです。
コードブロックはそのまま残し、不要な改行や「…」などの記号は削除しています。

ストーリー

電車でソーシャルメディアを調べているときに、偶然このスクリーンショットを見つけました。
もちろん、それに対して新人プログラマーが古典的なコンピュータサイエンスの問題「剰余演算」を解く試みを非難する悪意あるコメントが連続で寄せられました。

AI が人間の仕事を置き換え、コードへの考え方を変えている今、私たちは業界に新しい血を取り入れるべきだと感じています。実際、このコードは時間‑メモリトレードオフの典型例です。あなたは自分の時間だけでなく、コンピュータのメモリや時間も使っているのです―本当に素晴らしいアルゴリズムですね！

そこで私は「数が奇数か偶数か」を比較のみで判定するアイデアを実際に試すために、C 言語で実装しようとしました。性能重視なので、現在最も高速だと言われる C を選びました（デニス・リッチーのビジョンのおかげです）。

1. 手書きで始める

/* Copyright 2023. All unauthorized distribution of this source code 
   will be persecuted to the fullest extent of the law*/
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

int main(int argc, char* argv[])
{
    uint8_t number = atoi(argv[1]); // No problems here
    if (number == 0) printf("even\n");
    if (number == 1) printf("odd\n");
    if (number == 2) printf("even\n");
    if (number == 3) printf("odd\n");
    if (number == 4) printf("even\n");
    if (number == 5) printf("odd\n");
    if (number == 6) printf("even\n");
    if (number == 7) printf("odd\n");
    if (number == 8) printf("even\n");
    if (number == 9) printf("odd\n");
    if (number == 10) printf("even\n");
}

コンパイルして

/Od

PS > cl.exe /Od program.c
PS > .\program.exe 0 
even
PS > .\program.exe 4
even
PS > .\program.exe 3
odd
PS > .\program.exe 7
odd

しかし、さらにテストすると問題が出てきました。

PS > .\program.exe 50
PS > .\program.exe 11
PS > .\program.exe 99

何も出力されません。10 より大きい数は動作しないのです。コードを見直すと、最後の

if

if

2. メタプログラミングで拡張

そこで「if 文」を別言語で生成することにしました。最遅の言語といわれる Python を使います（ロス・ヴァン・デル・ガッソムのおかげです）。

print("/* Copyright 2023. All unauthorized distribution of this source code")
print("   will be persecuted to the fullest extent of the law*/")

print("#include <stdio.h>")
print("#include <stdint.h>")
print("#include <stdlib.h>")

print("int main(int argc, char* argv[])")
print("{")
print("    uint8_t number = atoi(argv[1]); // No problems here")

for i in range(2**8):
    print("    if (number == "+str(i)+")")
    if i % 2 == 0:
        print("        printf(\"even\\n\");")
    else:
        print("        printf(\"odd\\n\");")

print("}")

これで 8‑ビット整数全てに対して正しく判定できる C プログラムが生成されます。

PS > python programmer.py > program.c
PS > cl.exe /Od program.c
PS > .\program.exe 99
odd
PS > .\program.exe 50
even
PS > .\program.exe 240
even
PS > .\program.exe 241
odd

3. 16‑ビットへ拡張

print("    uint16_t number = atoi(argv[1]); // No problems here")
…
for i in range(2**16):

これで約 13 万行の C ファイルができ、コンパイルすると実行ファイルは約 2 MB。
私のゲーム PC では 31.8 GB のメモリがあるので問題ありません。

4. 32‑ビットへ挑戦

print("    uint32_t number = atoi(argv[1]); // No problems here")
…
for i in range(2**32):

Python に任せた結果、約 330 GB の C ファイルができました。
コンパイルすると次のようになります。

PS > cl /Od program.c
Microsoft (R) C/C++ Optimizing Compiler Version 19.32.31329 for x64
Copyright (C) Microsoft Corporation.  All rights reserved.

program.c
program.c(134397076): warning C4049: compiler limit: terminating line number emission
program.c(134397076): note: Compiler limit for line number is 16777215
program.c(41133672): fatal error C1060: compiler is out of heap space

パッチャーは失敗。さらに、PE（Portable Executable）フォーマットは 4 GB を超えることができません。32‑ビットの比較を 40 億個もエンコードするには大きすぎます。

5. 手動でアセンブリを書いてみる

それでも止まらないので、x86‑64 アセンブリで

IsEven

; Argument is stored in ECX, return value in EAX
XOR     EAX, EAX          ; Set eax to zero (return value for odd number)
CMP     ECX, 0h           ; Compare arg to 0 
JNE     3h                ; Skip next two instructions if it wasn’t equal
INC     EAX               ; It was even, set even return value (1)
RET                     ; Return
CMP     ECX, 1h            ; Compare arg to 1
JNE     2                  ; Skip next instruction if not equal
RET                     ; Odd return value already in EAX, just RET
; add the next 2…2^32‑1 comparisons here
RET                       ; Fallback return

正確ではありませんが、機械語に手書きで変換すれば実行できます。

6. バイナリ生成

import struct

with open('isEven.bin', 'wb') as file:
    file.write(b"\x31\xC0")                     # XOR EAX, EAX

    for i in range(2**32):
        ib = struct.pack("<I", i)               # Encode i as 32‑bit little endian integer
        file.write(b"\x81\xF9" + ib)            # CMP ECX, i
        if i%2 == 0:
            file.write(b"\x75\x03")             # JNE +3
            file.write(b"\xFF\xC0")             # INC EAX
            file.write(b"\xC3")                # RET
        else:
            file.write(b"\x75\x01")             # JNE +1
            file.write(b"\xC3")                # RET

    file.write(b"\xC3")                         # Fallback RET

7. 実行ファイルにマップして呼び出す

#include <stdio.h>
#include <Windows.h>
#include <stdint.h>

int main(int argc, char* argv[])
{
    uint32_t number = atoi(argv[1]); // No problems here

    /* Open code file */
    HANDLE binFile = CreateFileA(
        "isEven.bin",
        GENERIC_READ | GENERIC_EXECUTE,
        FILE_SHARE_READ,
        NULL,
        OPEN_EXISTING,
        FILE_ATTRIBUTE_NORMAL,
        NULL);

    /* Get 64‑bit size of file */
    LARGE_INTEGER codeSize;
    GetFileSizeEx(binFile, &codeSize);

    /* Create memory map of the file */
    HANDLE mapping = CreateFileMapping(
        binFile,
        NULL,
        PAGE_EXECUTE_READ,
        0,
        0,
        NULL);

    /* Get a pointer to the code */
    LPVOID code = MapViewOfFile(
        *mapping, FILE_MAP_EXECUTE | FILE_MAP_READ,
        0,
        0,
        codeSize.QuadPart);

    /* Create a function that points to the code */
    int (*isEven)(int) = (int(*)(int)code;

    if (isEven(number)) printf("even\n");
    else               printf("odd\n");

    CloseHandle(binFile);
}

これで … という状態に到達します。
（ここは自由に補完しても構いません。）