Просматривая недавно соцсети, я наткнулся на этот скриншот. Разумеется, его сопровождало множество злобных комментариев, критикующих попытку этого новичка в программировании решить классическую задачу computer science: операцию деления с остатком.
В современном мире, где ИИ постепенно заменяет программистов, отнимая у них работу и совершая переворот в том, как мы подходим к рассуждениям о коде, нам, возможно, следует быть более открытыми к мыслям людей, недавно пришедших в нашу отрасль? На самом деле, показанный выше код — идеальный пример компромисса между временем и задействованной памятью. Мы жертвуем временем и в то же время памятью и временем компьютера! Поистине чудесный алгоритм!
Поэтому я решил изучить эту идею проверки чётности числа при помощи одних сравнений, чтобы понять, насколько хорошо она работает в реальных ситуациях. Я сторонник высокопроизводительного кода, поэтому решил реализовать это на языке программирования C, потому что он и сегодня остаётся самым быстрым языком в мире с большим отрывом от других (благодаря гению Денниса Ричи).
Итак, я приступил к кодингу.
/* Copyright 2023. Любое неавторизованное распространение этого исходного кода
будет преследоваться по всей строгости закона */
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
int main(int argc, char* argv[])
{
uint8_t number = atoi(argv[1]); // Здесь никаких проблем
if (number == 0)
printf("evenn");
if (number == 1)
printf("oddn");
if (number == 2)
printf("evenn");
if (number == 3)
printf("oddn");
if (number == 4)
printf("evenn");
if (number == 5)
printf("oddn");
if (number == 6)
printf("evenn");
if (number == 7)
printf("oddn");
if (number == 8)
printf("evenn");
if (number == 9)
printf("oddn");
if (number == 10)
printf("evenn");
}Красота! Давайте скомпилируем код, отключив оптимизации при помощи /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 <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]); // Здесь никаких проблем")
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"x31xC0") # XOR EAX, EAX
for i in range(2**32):
ib = struct.pack("<I", i) # Кодируем i как 32-битное целое в little endian
file.write(b"x81xF9" + ib) # CMP ECX, i
if i%2 == 0:
file.write(b"x75x03") # JNE +3
file.write(b"xFFxC0") # INC EAX
file.write(b"xC3") # RET
else:
file.write(b"x75x01") # JNE +1
file.write(b"xC3") # RET
file.write(b"xC3") # Аварийный RET Хотя мы отошли от изначального поста в TikTok, суть остаётся той же. Мы создали о-о-очень длинный список операторов if для определения чётности любого числа, игнорируя любые арифметические операции, которые могли бы нам помочь.
Мы получаем милый файл на 40 ГБ, содержащий все 4,2 миллиарда сравнений, необходимых для определения чётности любого 32-битного числа! Теперь нам просто нужно написать хост-программу, которая сможет загружать и использовать эти команды. Для повышения производительности (в нашем случае это очень важно) я решил отобразить файл в адресное пространство, а не читать его целиком. Сделав так, мы притворимся, что весь файл уже находится в памяти, и позволим бедной операционной системе разбираться с размещением блоба на 40 ГБ в виртуальной памяти. Отобразив файл с разрешениями READ и EXECUTE, мы можем вызывать код при помощи указателя функции. Это выглядит так:
#include <stdio.h>
#include <Windows.h>
#include <stdint.h>
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("evenn");
else
printf("oddn");
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 <---- ОШИБКА!Почти! Похоже, у алгоритма есть какие-то проблемы со знаками: любое значение более 2^31 выдаёт произвольные результаты. Печально!
Давайте устраним последний баг.
Оказалось, функция atoi не может работать с чистой беззнаковостью, поэтому ей не удаётся распарсить наши крупные числа. Всё это можно исправить заменой её на strtoul.
uint32_t number = strtoul(argv[1], NULL, 10);// Здесь никаких проблемPS >.program.exe 4200000000
even
PS >.program.exe 4200000001
oddСтоит также отметить, что программа на удивление производительна. Для небольших чисел результат возвращается мгновенно, а для больших чисел, близких к 2^32, результат всё равно возвращается примерно за 10 секунд. Учитывая, что компьютеру приходится считывать 40 ГБ с диска, отображать их на физическую память, а затем обрабатывать их CPU без особых шансов на кэширование, это потрясающий результат. Для справки — в моём компьютере установлен Core i5 12600K с 32 ГБ памяти, а файлы хранятся на SSD-диске M.2. При вычислениях я наблюдал пиковую скорость чтения с SSD примерно в 800 МБ/с (что совершенно нелогично, ведь при этом скорость исполнения была бы больше сорока секунд, но компьютеры — это магия, так что кто знает, что там происходит).
И на этом мы закончили! Мы снова доказали, что в Интернете кто-то не прав — не только можно написать полнофункциональную и высокопроизводительную программу в стиле поста в TikTok, но это ещё и очень захватывающе.
Автор:
PatientZero
