[Перевод] 4 миллиардов операторов if28.12.2023 13:00

Просматривая недавно соцсети, я наткнулся на этот скриншот. Разумеется, его сопровождало множество злобных комментариев, критикующих попытку этого новичка в программировании решить классическую задачу computer science: операцию деления с остатком.

В современном мире, где ИИ постепенно заменяет программистов, отнимая у них работу и совершая переворот в том, как мы подходим к рассуждениям о коде, нам, возможно, следует быть более открытыми к мыслям людей, недавно пришедших в нашу отрасль? На самом деле, показанный выше код — идеальный пример компромисса между временем и задействованной памятью. Мы жертвуем временем и в то же время памятью и временем компьютера! Поистине чудесный алгоритм!

Поэтому я решил изучить эту идею проверки чётности числа при помощи одних сравнений, чтобы понять, насколько хорошо она работает в реальных ситуациях. Я сторонник высокопроизводительного кода, поэтому решил реализовать это на языке программирования C, потому что он и сегодня остаётся самым быстрым языком в мире с большим отрывом от других (благодаря гению Денниса Ричи).

Итак, я приступил к кодингу.

/* Copyright 2023. Любое неавторизованное распространение этого исходного кода 
   будет преследоваться по всей строгости закона */
#include 
#include 
#include 
int main(int argc, char* argv[])
{
    uint8_t number = atoi(argv[1]); // Здесь никаких проблем
    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.

print("/* Copyright 2023. Любое неавторизованное распространение этого исходного кода
print("   будет преследоваться по всей строгости закона */")

print("#include ")
print("#include ")
print("#include ")

print("int main(int argc, char* argv[])")
print("{")
print("    uint8_t number = atoi(argv[1]); // Здесь никаких проблем")

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]); // Здесь никаких проблем")
…
for i in range(2**16):

Мы получаем красивый жирный файл .c примерно из 130 тысяч строк. На самом деле, это ничто по сравнению с некоторыми кодовыми базами, с которыми я сталкивался за годы работы. Давайте его скомпилируем!

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 МБ, но это ерунда для моего мощной игровой машины с 31,8 ГБ памяти.

Ну, 16 битов — это очень прекрасная битовая ширина, но, как мы знаем, Святой Грааль вычислений — это 32 бита, и это последняя битовая ширина, которой достаточно для решения всех практических инженерных и научных задач. В конце концов, IPv4 чувствует себя как никогда хорошо, хотя его уже шестьдесят лет назад признали устаревшим из-за так называемого «исчерпания адресов».

Так что давайте без лишних церемоний увеличим масштаб до нашего последнего размера. В 32 битах всего в 65536 раз больше чисел, чем в 16 битах, что может пойти не так?

print("    uint32_t number = atoi(argv[1]); // Здесь никаких проблем")
…
for i in range(2**32):

Позволим могучей змее выполнить свою работу: выпив кофе и вернувшись к программе спустя 48 часов, я обнаружил красивый файл .c размером почти 330 ГБ! Я практически уверен, что это самый большой файл .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

Жалкое зрелище!

И нас подвёл не только компилятор: изучив ограничения формата Portable Executable (.exe) для Windows, я обнаружил, что он не может обрабатывать больше, чем жалкие 4 ГБ! Учитывая, что в исполняемом файле должно быть закодировано 4 миллиарда сравнений, это серьёзное препятствие для реализации нашего алгоритма. Даже если каждое сравнение будет использовать меньше одного байта, файл всё равно будет слишком тяжёлым.

Однако плохие компиляторы и форматы файлов не должны мешать нам в стремлении к нашей мечте. В конце концов, компилятор всего лишь записывает машинный код в файл, а формат файлов — это всего лишь некая структура, сообщающая операционной системе, как помещать двоичный код в память. На самом деле, мы и сами можем с этим справиться.

Начнём с написания функции IsEven на языке ассемблера x86–64, потому что это нативный язык моей машины с процессором Intel. Функция выглядит примерно так:

; Аргумент хранится в ECX, возвращаемое значение в EAX
XOR EAX, EAX ; Присваивам eax значение 0 (возвращаемое значение для нечётного числа)
CMP ECX, 0h ; Сравниваем аргумент с 0 
JNE 3h ; Пропускаем следующие две команды в случае неравенства
INC EAX ; Если число чётное, задаём возвращаемое значение чётного числа (1)
RET ; Возврат
CMP ECX, 1h ; Сравниваем аргумент с 1
JNE 2 ; Пропускаем следующую команду в случае неравенства
RET ; Возвращаемое значение нечётного числа уже находится в EAX, просто делаем RET
; сюда вставляем следующие 2...2^32-1 сравнений
RET ; Аварийный возврат

Не совсем корректный ассемблерный код, но это не особо важно, потому что мы собираемся компилировать его в машинный код вручную.

Как я это сделал? Я вышел в Интернет с таким вопросом. Воспользовался своим опытом написания эмуляторов и хакинга, изучил руководства по архитектуре 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("

#include 
#include 
#include 

int main(int argc, char* argv[])
{
    uint32_t number = atoi(argv[1]); // Здесь никаких проблем

    // Открываем файл с кодом
    HANDLE binFile = CreateFileA(
                        "isEven.bin",
                        GENERIC_READ | GENERIC_EXECUTE, FILE_SHARE_READ,
                        NULL,
                        OPEN_EXISTING,
                        FILE_ATTRIBUTE_NORMAL,
                        NULL);
   
    // Получаем 64-битный размер файла
    LARGE_INTEGER codeSize;
    GetFileSizeEx(binFile, &codeSize);

    // Создаём отображение файла в памяти
    HANDLE mapping = CreateFileMapping(
                        binFile,
                        NULL,
                        PAGE_EXECUTE_READ,
                        0,
                        0,
                        NULL);

    // Получаем указатель на код
    LPVOID code = MapViewOfFile(
                    mapping,FILE_MAP_EXECUTE | FILE_MAP_READ,
                    0,
                    0,
                    codeSize.QuadPart);

    // Создаём функцию, указывающую на код
    int (*isEven)(int) = (int(*)(int))code;

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

    CloseHandle(binFile);
}

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 <---- ОШИБКА!

uint32_t number = strtoul(argv[1], NULL, 10);// Здесь никаких проблем

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