Balki sunʼiy aql asta-sekin dasturchilar oʻrnini egallab, ularning ishini olib qoʻyayotgan va kod borasidagi mulohazalarga boʻlgan yondashuvimizni oʻzgartirayotgan zamonaviy dunyoda sohamizga yaqinda kelgan kishilarning fikrlariga yanada ochiqroq boʻlishimiz kerakdir? Aslida, yuqorida koʻrsatilgan kod vaqt va foydalanilgan xotira oʻrtasidagi oʻzaro murosaning mukammal namunasidir. Biz vaqtni, shu bilan birga kompyuterning xotirasi va vaqtini qurbon qilamiz! Haqiqatan ham ajoyib algoritm!

Shuning uchun u real vaziyatlarda qanchalik yaxshi ishlashini tushunish maqsadida, sonlar juftligini faqat taqqoslash yordamida tekshirish gʻoyasini oʻrganib chiqishga qaror qildim. Men yuqori unumli kod tarafdori boʻlganim uchun uni C dasturlash tilida amalga oshirishga qaror qildim, chunki u bugungi kunda ham boshqalardan ancha oʻzib, dunyodagi eng tezkor til (daho Dennis Richi tufayli) boʻlib qolmoqda.

/* Copyright 2023. Ushbu manba kodning har qanday ruxsatsiz tarqatilishi 
qonun tomonidan qatʼiy taʼqib qilinadi */
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
int main(int argc, char* argv[])
{
uint8_t number = atoi(argv[1]); // Bu yerda hech bir muammo yoʻq 
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");
}

Juda soz! Keling, kodni bezor qiluvchi kompilyator algoritmimizga aralashavermasligi uchun /Od yordamida optimallashtirishni oʻchirib, kompilyatsiya qilamiz. Kompilyatsiyadan soʻng dasturning tezkor testini oʻtkazishimiz va ijobiy natijalarga erishishimiz mumkin:

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

Biroq keyingi testlarda baʼzi muammolarni aniqladim:

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

Dastur hech narsa chiqarmayapti! Aftidan, u faqat 11 dan kichik sonlar bilan ishlayapti! Kodga qaytib, muammoni shundoq oxirgi if operatori ortida topishimiz mumkin — bizga koʻproq if kerak!

Albatta, bu vaqt va foydalanilayotgan xotira oʻrtasidagi murosa, lekin mening bu dunyodagi vaqtim cheklangan, shuning uchun men if operatorlarini meta-dasturlash — boshqa dasturlash tilidagi dasturchidan foydalanishga qaror qildim. Bu gʻirromlikning badali sifatida dunyodagi eng sekin (daho Ross van der Gussom tufayli) Python tilidan foydalanadigan boʻldim.

print("/* Copyright 2023. Ushbu manba kodning har qanday ruxsatsiz tarqatilishi 
print("   qonun tomonidan qatʼiy taʼqib qilinadi */")

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]); // Bu yerda hech bir muammo yoʻq")

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("}")

Ajoyib! Endi barcha 8 bitli butun sonlar juftligi muammosini hal qiladigan dastur yaratishimiz mumkin!

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

Bunga qarang-a! Mukammal ishlamoqda! Keling, endi masshtablarni 16 bitgacha oshiraylik!

print("    uint16_t number = atoi(argv[1]); // Bu yerda hech bir muammo yoʻq")
…
for i in range(2**16):

Taxminan 130 ming qatordan iborat semizgina chiroyli faylga ega boʻlamiz. Aslida, bu men yillar davomida duch kelgan ayrim kodli bazalar bilan solishtirganda hech narsa emas. Keling, uni kompilyatsiya qilaylik!

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

Ajoyib! Aftidan, algoritmimiz maʼlumotlar bilan birga masshtablanayotganga oʻxshaydi! Bajarilayotgan fayl hajmi taxminan 2 MB ni tashkil qiladi, ammo bu mening 31,8 GB xotiraga ega kuchli oʻyin mashinam uchun arzimagan narsa.

Xoʻsh, 16 bit — ajoyib bit kengligi, ammo bilganimiz qadar, hisoblashlar uchun eng maqbuli 32 bit boʻlib, bu barcha amaliy muhandislik va ilmiy muammolar yechimini topish uchun yetarli boʻlgan soʻnggi bit kengligidir. Axir oltmish yil oldin “adreslar tugayotgani” sababli eskirgan deb tan olingan IPv4 oʻzini har qachongidan ham yaxshi his qilmoqda.

Shunday ekan, tortinmasdan masshtabni oxirgi oʻlchamimizga qadar kattalashtiramiz. 32 bitdagi sonlar 16 bitdagiga nisbatan atigi 65536 baravar koʻp, bu nimaga ham taʼsir qilishi mumkin?

print("    uint32_t number = atoi(argv[1]); // Bu yerda hech bir muammo yoʻq")
…
for i in range(2**32):

Qudratli ilonga oʻz ishini bajarishiga izn beramiz: qahvamni ichib, 48 soatdan keyin dasturga qaytganimda hajmi deyarli 330 GB boʻlgan yoqimli faylni topdim! Bu C tarixidagi eng katta fayl ekaniga ishonchim komil edi. Quyidagi buyruqni kiritayotganimda barmoqlarim titrardi: MSVC, katta ehtimol bilan, ilgari hech qachon bunday kuchli manba kodga duch kelmagan. Bechora kuchli kompyuterimni fayl ustidagi ishlar bilan faol tarzda yarim soat xoʻrlaganimdan soʻng men quyidagilarga ega boʻldim:

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

Achinarli manzara!

Bizga nafaqat kompilyator pand berdi: Portable Executable (.exe) formatining Windows uchun cheklovlarini oʻrganib chiqib, u hajmi arzimagan 4 GB dan ortiq narsalar bilan ishlay olmasligini aniqladim. Bajariladigan faylda 4 milliard taqqoslash ishlari kodlanishi kerakligini hisobga olsak, bu algoritmimizni amalga oshirishga katta toʻsiqdir. Hatto har bir taqqoslash bir baytdan kam foydalanganda ham fayl juda ogʻir boʻladi.

Biroq yomon kompilyator va fayl formatlari orzumizga intilishimizda bizga toʻsqinlik qilmasligi kerak. Pirovardida, kompilyator atigi mashina kodini faylga yozadi, fayl formati esa operatsion tizimga ikkilik kodni xotiraga qanday joylashtirish haqida xabar beradigan tuzilmadir. Aslida, buni oʻzimiz ham hal qila olamiz.

Ishni x86-64 assembler tilida IsEven funksiyasini yozishdan boshlaymiz, chunki bu mening Intel protsessorli mashinamning tili. Funksiya quyidagicha koʻrinishda boʻladi:

; Argument ECXʼda, qaytish qiymati EAXʼda saqlanadi
XOR EAX, EAX ; EAX uchun 0 qiymat belgilaymiz (toq son uchun qaytish qiymati)
CMP ECX, 0h ; Argumentni 0 bilan taqqoslaymiz
JNE 3h ; Tengsizlik boʻlgan holatda quyidagi ikkita buyruqni oʻtkazib yuboramiz
INC EAX ; Agar juft son boʻlsa, juft sonning qaytish qiymatini (1) oʻrnatamiz
RET ; Qaytish
CMP ECX, 1h ; Argumentni 1 bilan taqqoslaymiz
JNE 2 ; Tengsizlik boʻlgan holatda navbatdagi buyruqni oʻtkazib yuboramiz
RET ; Toq sonning qaytish qiymati allaqachon EAXʼda, shunchaki RET qilamiz
; bu yerga quyidagi 2...2^32-1 taqqoslashlarni kiritamiz
RET ; Favqulodda qaytish

Assembler kodi unchalik ham toʻgʻri emas, lekin bu muhim emas, chunki biz uni mashina kodiga qoʻlda kompilyatsiya qilmoqchimiz.

Buni qanday amalga oshirdim? Bu savol bilan internetga kirdim. Har bir buyruq uchun kerakli opkod va formatlarni topish uchun emulyatorlarni yozish, xaking borasidagi tajribamdan foydalandim, x86(-64) arxitektura qoʻllanmalarini oʻrganib chiqdim.

... Yoʻq, hazillashyapman, bu chunonam dahshat boʻlar edi. Men shunchaki ChatGPTʼdan har bir buyruq uchun toʻgʻri opkodni soʻradim; baxtimga u x86-64 uchun yangi kengaytmalarni oʻylab topmadi.

Endi bu kodni chiqarib olishimiz uchun “kompilyator” yozishimiz kifoya. Shuni yodda tutish kerakki, biz sunʼiy intellektdan bevosita buyruqlar uchun olingan opkodlarni yozamiz. Bu bizning sevimli Pythonʼda mana shunday koʻrinishga ega:

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)               # iʼni 32-bitli butun son sifatida little endianʼda kodlaymiz

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")                         # Favqulodda RET

Garchi TikTokʼdagi dastlabki postdan uzoqlashgan boʻlsak-da, mohiyat oʻzgarmaydi. Bizga yordam beradigan har qanday arifmetik amallarni eʼtiborsiz qoldirib, istalgan sonning juftligini aniqlaydigan if operatorlarining juda uzun roʻyxatini yaratdik.

Biz istalgan 32 bitli sonning juftligini aniqlashda zarur boʻlgan, barcha 4,2 milliard taqqoslashni oʻz ichiga olgan 40 GB hajmdagi ajib faylga ega boʻlamiz! Endi shunchaki bu buyruqlarni yuklab olib, ulardan foydalanadigan xost-dasturini yozishimiz kerak. Samaradorlikni oshirish uchun (bizning holatimizda bu juda muhim) men faylni toʻliq oʻqish oʻrniga, uni adres makonida aks ettirishga qaror qildim. Shu tarzda mugʻombirlik qilib, butun fayl allaqachon xotirada deb bechora operatsion tizimning 40 GB blobni virtual xotirada joylashtirishiga imkon beramiz. Faylni READ va EXECUTE kengaytmalari bilan koʻrsatib, kodni funksiya koʻrsatkichi yordamida chaqirishimiz mumkin. Bu shunday koʻrinishda boʻladi:

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

int main(int argc, char* argv[])
{
uint32_t number = atoi(argv[1]); // Bu yerda hech qanday muammo yoʻq

// Kod joylashgan faylni ochamiz
HANDLE binFile = CreateFileA(
isEven.bin,
GENERIC_READ | GENERIC_EXECUTE, FILE_SHARE_READ,
NULL,
OPEN_EXISTING,
FILE_ATTRIBUTE_NORMAL,
NULL);

// 64 bit hajmdagi faylga ega boʻlamiz
LARGE_INTEGER codeSize;
GetFileSizeEx(binFile, &codeSize);

// Faylning xotiradagi aksini yaratamiz
HANDLE mapping = CreateFileMapping(
binFile,
NULL,
PAGE_EXECUTE_READ,
0,
0,
NULL);

// Kod koʻrsatkichiga ega boʻlamiz
LPVOID code = MapViewOfFile(
mapping,FILE_MAP_EXECUTE | FILE_MAP_READ,
0,
0,
codeSize.QuadPart);

// Kodni koʻrsatadigan funksiyani yaratamiz
int (*isEven)(int) = (int(*)(int))code;

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

CloseHandle(binFile);
}

Ana shugina! Endi bizda har qanday 32 bitli sonning juftligini tekshirish uchun kerakli hamma narsa bor. Keling, tekshiramiz:

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 <---- XATO!

Deyarli! Aftidan, algoritmda belgilar bilan bogʻliq muammolar mavjud: 2^31 dan yuqori boʻlgan har qanday qiymat ixtiyoriy natijalar bermoqda. Achinarli!

Keling, oxirgi bagni bartaraf etaylik.

Maʼlum boʻlishicha, atoi funksiyasi aniq belgilarsiz ishlay olmas ekan, shuning uchun u bizning katta sonlarimizni parsing qila olmaydi. Bularning barchasini uni strtoul bilan almashtirish orqali tuzatish mumkin.

uint32_t number = strtoul(argv[1], NULL, 10);// Bu yerda hech qanday muammo yo'q
PS >.\program.exe 4200000000
even
PS >.\program.exe 4200000001
odd

Shuningdek, dastur hayratlanarli darajada samarador ekanini ham taʼkidlab oʻtish kerak. Kichik sonlarning natijasi bir zumda qaytadi, 2^32 ga yaqin boʻlgan katta sonlarniki esa baribir taxminan 10 soniyada qaytadi. Kompyuter diskdan 40 GB ni oʻqishi, uni jismoniy xotirada aks ettirishi, soʻngra ularni keshlash imkoniyati boʻlmagan holda CPUʼda qayta ishlashi kerakligini hisobga olsak, bu ajoyib natija. Malumot uchun — kompyuterimga 32 GB xotiraga ega Core i5 12600k oʻrnatilgan boʻlib, fayllar M.2 SSD-diskda saqlanadi. Hisoblashlar paytida SSDʼdan eng yuqori oʻqish tezligi taxminan 800 MB/s ekanini kuzatdim (bu mutlaqo mantiqsiz, axir bunda vazifaning bajarilish tezligi qirq soniyadan koʻproq boʻlishi kerak, ammo kompyuterlar — afsungar, shuning uchun uning ichida nima sodir boʻlayotganini kim biladi deysiz).

Shu bilan yakunlaymiz! Biz internetda kimdir nohaq ekanini, yaʼni nafaqat TikTokʼdagi post uslubida toʻliq funksional va yuqori samarali dasturni yozish mumkin, balki bu juda qiziqarli ham ekanini yana bir bor isbotladik.

Manba: 4 миллиарда операторов if