【译文】40 亿条 if 语句

编程| 2024-01-02

最近，我在火车上浏览论坛帖子时偶然发现了这张截图。当然，这张图随之而后的是一连串的吐槽，批评这位新程序员试图解决计算机科学中的一个经典问题——模运算的方式。

现在，人工智能正在分分钟取代程序员，抢走他们的饭碗，并彻底改变了我们对代码的思考方式，也许我们应该对行业新鲜血液的想法持更开放的态度？事实上，上述代码就是时间与内存权衡的完美范例。你在交换自己的时间的同时，也在交换计算机的内存和时间！真是一种神奇的算法！

于是，我开始探索这种只使用比较来检查一个数字是奇数还是偶数的想法，看看它在现实世界中的效果如何。由于我是高性能代码的忠实拥护者，我决定用 C 编程语言来实现它，因为它是迄今为止地球上速度最快的编程语言（这要感谢具有远见卓识的天才Dennis Richie）。

于是我开始编写

/* 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

没有输出！看来程序只对 11 以下的数字有效！回到代码，我们可以发现问题出在最后一个 if 语句之后，我们需要更多的 if 语句！

现在，这需要在时间和内存之间做出权衡，但我在这个世界上的时间有限，所以我决定使用不同编程语言对 if 语句进行元编程。为了弥补这种作弊行为，我决定使用地球上最慢的语言 Python（这要感谢罗斯-范德古索姆（Ross van der Gussom）的远见卓识）。

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 位整数的偶偶数问题！

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

你看看这个！效果完美无瑕！现在，让我们把它放大到 16 位！

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

这样就得到了一个约 13 万行的厚厚的 c 文件。回顾一下我多年来工作过的一些代码库，这其实不算什么。开始编译

PS > python programmer.py > program.c
PS > cl.exe /Od program.c
PS > .\program.exe 21000
even
PS > .\program.exe 3475 
odd
PS > .\program.exe 3   
odd
PS > .\program.exe 65001
odd
PS > .\program.exe 65532
even

真漂亮！我们的算法似乎与数据同步！可执行文件约为 2 MB，但这与我拥有高达 31.8 GB 内存的强大游戏设备相比，简直不值一提。

现在，16 位是一个非常酷的位宽，但众所周知，32 位才是计算的圣杯，也是我们解决所有实际工程和科学问题所需的最终位宽。毕竟，在 IPv4 因所谓的 “地址耗尽 “而被认为已被淘汰的 60 年后，它依然屹立不倒。

话不多说，让我们来看看最终的规模。32 位的数字是 16 位的 65536 倍，还会有什么问题呢？

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

于是，我让强大的 “蛇 “开始工作。48 小时后，我喝了一杯咖啡，然后回来检查程序，结果发现了一个漂亮的 c 文件，大小接近 330 GB！几乎可以肯定，这是历史上最大的 c 文件之一。当我输入下一条命令时，我的手指都在颤抖，MSVC 肯定从未遇到过如此强大的源代码。在我那台可怜而强大的电脑的分页文件中滥用了半个小时后，吐出了下面这个文件：

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

真可悲！

不仅编译器让我们失望，在研究 Windows 便携式可执行文件格式（.exe）的限制时，我发现它无法处理超过 4 GB 的文件！由于需要将 40 多亿次比较编码到可执行文件中，这是实现我们算法的一大障碍。即使每次比较使用的字节数少于一个，我们的工作量也会过大。

不过，糟糕的编译器和文件格式不应该阻止我们实现梦想。毕竟，编译器所做的只是将一些花哨的机器代码写入文件，而文件格式只是告诉操作系统如何将二进制代码放入内存的一些结构。真的，我们自己就能做到。

让我们先用 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

这并不是真正正确的 asm，但这并不重要，因为我们将手动把它编译成机器代码。

我是怎么做到的？我上网查阅了 x86(-64) 体系结构手册，利用我早期编写仿真器和黑客的经验，找出了每条指令的正确操作码和格式。

开个玩笑，这太可怕了。我问 ChatGPT 每条指令的正确操作码是什么，幸运的是它并没有演化出 x86-64 的任何新扩展。

所以我们现在只需编写一个 “编译器 “来输出这些代码。请注意，我们将直接写入从人工智能中获得的指令操作码。下面是用我们的朋友 python 编写的代码：

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

虽然我们在一定程度上偏离了论坛帖子的最初构想，但本质并没有改变。我们创建了一长串、一长串、一长串的 if 语句，以确定任何数字是偶数还是奇数，而忽略了任何可以提供帮助的算术运算。

这样运行后，我们就得到了一个 40 GB 的文件，其中包含了确定 32 位数字是偶数还是奇数所需的全部 42 亿次比较！现在，我们只需编写能够加载和使用这些指令的主程序。为了提高性能（这一点非常重要），我决定将文件映射到地址空间，而不是读取全部文件。这样，我们就可以假装整个文件已经在内存中，让可怜的操作系统来处理将一个 40 GB 的 Blob 装入虚拟内存的问题。用 READ 和 EXECUTE 权限映射文件后，我们就可以使用函数指针调用代码了。它看起来像这样

#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);
}

就是这样！现在我们已经具备了检查任何 32 位数字是偶数还是奇数的所有功能。让我们试一试：

PS >.\program.exe 300
even
PS >.\program.exe 0
even
PS >.\program.exe 1000000
even
PS >.\program.exe 100000007
odd
PS >.\program.exe 400000000
even
PS >.\program.exe 400000001
odd
PS >.\program.exe 400000006
even
PS >.\program.exe 4200000000
odd <---- WRONG!

差不多了！似乎算法在符号性方面有问题，任何超过 2^31 的值似乎都会产生随机结果。可悲啊

让我们修复最后一个错误吧。

事实证明 atoi 无法处理无符号值，所以无法解析我们的大数字。用 strtoul 代替它就能解决所有问题。

uint32_t number = strtoul(argv[1], NULL, 10);// No problems here

PS >.\program.exe 4200000000
even
PS >.\program.exe 4200000001
odd

顺便提一句，该程序的性能令人惊叹。对于小数，结果是即时的，而对于接近 2^32 极限的大数，结果仍能在 10 秒左右返回。考虑到计算机必须从磁盘读取 40 GB 的数据，将其映射到物理内存，然后让 CPU 在没有缓存的情况下对其进行处理，老实说这是非常令人震惊的。作为参考，电脑的配置为酷睿 i5 12600K，32 GB 内存，文件存储在 M.2 固态硬盘上。在计算过程中，我看到固态硬盘的峰值读取速度约为 800 MB/s（这并不合理，因为执行速度应该在 40 秒以上，但电脑是神奇的，谁知道是怎么回事呢）。

就是这样！事实再次证明互联网上一些公知是错误的，你不仅可以按照这篇帖子的方式编写一个功能齐全、性能良好的程序，而且还非常有趣。

本文文字及图片出自 4 billion if statements