Kovanje i pretraga koja dokazuje svoju vrijednost
Problem starog trika
Svaki ozbiljan softverski sustav ima nekoliko dijelova koda koji su važniji nego što njihova veličina sugerira. Petlja koja se izvodi milijune puta. Bitna operacija u putanji kompresije. Mala matrična rutina. Jezgra modularne aritmetike. Takve stvari izgledaju bezazleno u pregledu koda, a onda tiho odlučuju o računu za struju, proračunu latencije ili broju strojeva koje treba kupiti. Vrlo demokratski, taj softver. Jedna sićušna funkcija može upropastiti sastanak svima.
Povijesno, te jezgre poboljšavaju ljudi. Viši inženjer sjeti se trika iz nekog rada. Netko kopa po staroj forumskoj objavi. Napiše se skup mjerila. Isproba se nekoliko kandidata. Najbrži pobjeđuje ako i dalje izgleda ispravno. Zatim ga organizacija zamrzne, jer dirati ga ponovno osjeća se kao bockanje usnulog transformatora vilicom.
Forge je istraživanje bolje verzije tog procesa. To je motor sinteze programa za male, kritične implementacije: dajte mu tipiziranu specifikaciju i svojstva, neka pretražuje kandidatske programe, mjeri i uspoređuje kompromise, verificira ekvivalenciju, zatim spusti otkrivenu implementaciju na ciljeve koji su važni. Važna riječ nije pretraživanje. Važna riječ je još uvijek. Još uvijek mora biti ispravan.
Zato Forge živi u istraživanju. To nije javni proizvodni gumb gdje netko upiše napravi brže i dobije čudo. To je radni stol za sintezu za partnerske eksperimente, otkrivanje jezgri i istraživanje koliko daleko automatizirano pretraživanje može ići kada je vezano uz verifikaciju umjesto uz kazalište mjerila.
Specifikacija je startna crta
Optimizacija bez specifikacije samo je kockanje s ljepšim imenima varijabli. Čim se pojavi pametan kandidat, tim mora znati što bi trebao sačuvati. Radi li s ulazima ili samo s onim prijateljskim iz mjerila? Poštuje li ponašanje preljeva? Je li algebarski identitet valjan pod reprezentacijom koja se stvarno koristi? Zadržava li istu semantiku kada se spusti na drugi backend?
Forge kreće od tipiziranih izraza i svojstava jer pretraživanje treba granicu. Granica kaže što se smatra ekvivalentnim. Bez nje, motor može pronaći nešto zapanjujuće brzo brisanjem pola posla. Računala su izvrsna u zlonamjernoj usklađenosti kada je ugovor nejasan.
Strana pretraživanja namjerno je pluralna. Enumerativno pretraživanje korisno je kada je prostor dovoljno mali da se pokrije. CEGIS je koristan kada protuprimjeri mogu usmjeriti poboljšanje. Genetsko programiranje i MCTS istražuju drugačije. Pretraživanje vođeno strojnim učenjem može naučiti modele troškova i dati prioritet obećavajućim regijama. Nijedno od ovih nije univerzalno najbolje. To nije slabost. Tako se pretraživanje ponaša u stvarnom svijetu. Kad bi jedan čekić riješio svaku jezgru, kutije s alatom bile bi vrlo dosadne, a proizvođači hardvera bili bi nezaposleni.
Istraživačko pitanje je kako kombinirati te motore s dovoljno pritiska dokaza da rezultat nije samo pametan. Sintetizirana jezgra mora preživjeti i mjerilo sretnog puta i verifikator nesretnog puta. Inače poboljšanje nije inženjering. To je magični trik s troškom održavanja.
Verifikator je odrasla osoba u sobi
Forge koristi sloj provjere jer nijedna pojedinačna provjera nije dovoljna za svako područje. Brzi primjeri su jeftini i korisni. Testovi svojstava pronalaze široke klase pogrešaka i sažimaju protuprimjere u nešto što čovjek može pročitati. SMT rješavači poput Z3 i CVC5 mogu dokazati ekvivalentnost tamo gdje je kodiranje izvedivo. Iscrpna provjera praktična je za mala područja. E-graph saturacija jednakosti pruža još jedan put kroz algebarsku ekvivalentnost.
Sloj je važan jer jezgre otkazuju na neugodne načine. Kandidat može proći svaku uobičajenu mjeru uspješnosti, a i dalje biti pogrešan u rubnom slučaju. Može biti točan za nepredznačene ulaze, a pogrešan za predznačene. Može biti točan u matematičkom polju, a pogrešan nakon što odabrana reprezentacija prekorači. Može biti točan prije spuštanja, a suptilno pogrešan nakon odluke o odabiru instrukcija. Provjeritelj postoji jer optimizam nije strategija testiranja. Provjerili smo. Više puta. I dalje vrijedi.
Postoji i praktičan razlog za zadržavanje više putova dokazivanja. Formalne metode su moćne, ali nisu besplatne. Neka kodiranja prekorače vremensko ograničenje. Neka su područja prevelika za iscrpnu provjeru. Neka je svojstva lakše najprije testirati probabilistički, a dokazati kasnije. Forge tretira provjeru kao lijevak, a ne kao ritual čistoće. Jeftine provjere odbacuju očite besmislice. Strože provjere štite konačnog kandidata.
Brzo nije jedan broj
Rad na performansama postaje besmislen kada jedna mjera smije dominirati svakim razgovorom. Latencija je važna. Broj operacija je važan. Korištenje memorije je važno. Pritisak na registre je važan. Vrijeme kompilacije ponekad je važno. Prenosivost je važna kada ista jezgra mora živjeti na više od jednog pozadinskog sustava. Kandidat koji pobjeđuje u latenciji tako što troši registre poput malog logora može biti pogrešan za stvarnu metu. Kandidat koji je malen, ali spor, može biti koristan negdje drugdje. Kontekst ostaje nepobjediv.
Forge stoga optimizaciju oblikuje kao Pareto problem. Motor može pretraživati ciljeve umjesto da se pretvara da postoji jedna univerzalna ocjena koju je dala vrlo samouvjerena tablica. Koristan rezultat nije uvijek jedini najbrži kandidat. Ponekad je to obitelj kandidata s vidljivim kompromisima, kako bi inženjer mogao odabrati onaj koji odgovara ograničenjima implementacije.
To je također razlog zašto ne volim gole tvrdnje o ubrzanju u objavama na blogu. Stranica istraživanja može opisati unutarnja očekivanja i eksperimentalne ciljeve, ali javne tvrdnje zahtijevaju svježa izvođenja, trenutačni hardver, trenutačne zastavice prevoditelja i točan kontekst radnog opterećenja. Inače broj postaje suvenir. Suveniri su lijepi. Oni nisu arhitektura.
Poštena tvrdnja je u svakom slučaju jača: Forge se bavi time da pretraživanje bude ponovljivo, usporedivo i provjerljivo. Kada kandidat pobijedi, trebamo znati koji je cilj osvojio, koje je kandidate pobijedio, koji ga je provjeritelj prihvatio i koji pozadinski sustav cilja. To je mnogo korisnije od broja koji lebdi kroz prezentaciju i izgleda skupo.
Spuštanje je mjesto gdje se dokazi testiraju
Otkrivena implementacija korisna je samo ako preživi put do stvarnih ciljnih sustava. Forge istraživanje obuhvaća spuštanje na pozadinske sustave poput x86-64, RISC-V, WASM, Vulkan GPU putova, C i Verilog. Taj popis ciljnih sustava nije ukras. Svaki pozadinski sustav ima vlastita ograničenja, oblike instrukcija, ponašanje memorije i načine na koje zna zakazati. Ista specifikacija mora zadržati svoje značenje dok implementacija postaje nešto što ciljni sustav stvarno može izvoditi.
Ovdje se sinteza povezuje s ostatkom Dweve stoga. Core želi učinkovite unutarnje petlje. Numerus brine o determinističkim numeričkim jezgrama. BitWeave želi binarne operacije s vektorima i matricama koje ne troše CPU uzalud. Kera brine o spuštanju grafova izračuna na stvarni hardver. Forge može hraniti te slojeve samo ako je generirana implementacija više od puke brzine. Mora biti ekvivalentna, dovoljno prenosiva za odabrani ciljni sustav i pregledna kada se nešto promijeni.
Što to mijenja za timove
Za tim, zanimljiv pomak nije to što bi stroj mogao otkriti bržu jezgru. Već to što rad na jezgrama postaje manje ovisan o usmenoj predaji. Umjesto jednog stručnjaka koji pamti pravi trik, proces postaje: definiraj ugovor, pretraži prostor, izmjeri kandidate, dokaži ekvivalenciju, zabilježi kompromis i generiraj kod za ciljni sustav. Ljudi i dalje odlučuju. Samo prestaju sve otkriće raditi ručno.
To je važno za operacije jer je cijena performansnog duga skupa na način koji organizacije često skrivaju. Spora jezgra postaje više poslužitelja. Više poslužitelja postaje više troškova, više energije, više složenosti implementacije i više šuma u planiranju. Pogrešna optimizacija postaje incidenti. Točan, ali nedokumentiran trik postaje budući rizik za migraciju. Forge je istraživanje usmjereno na smanjenje te gomile izbjegljivih gluposti.
Postoji i kulturološka promjena. Ručni rad na performansama često nagrađuje junaštvo. Netko nestane u špilji i vrati se s pametnim trikom. Svi plješću, nitko ga u potpunosti ne razumije, a tvrtka je stekla mali sveti predmet. Forge gura proces prema dokazima: evo specifikacije, evo puta pretraživanja, evo odbačenih kandidata, evo verifikatora, evo odabranog pozadinskog sustava. Manje mitologije. Više dokaza.
Gdje je posao još uvijek težak
Ništa od ovoga ne čini sintezu lakom. Specifikacije su teške. Ako je specifikacija pogrešna, stroj može vjerno otkriti pogrešnu stvar. Prostori pretraživanja mogu eksplodirati. Rješavači mogu isteći s vremenom. Modeli troškova mogu zavarati. Pozadinski sustavi mogu otkriti detalje do kojih apstraktnom izrazu nije bilo stalo. Verifikacija može biti snažna u jednoj domeni, a nezgrapna u drugoj. Svatko tko prodaje programsku sintezu kao automat za optimalni kod ili preskače teške dijelove ili naplaćuje dodatno za razočaranje.
Forge je zanimljiv upravo zato što se izravno suočava s tim teškim dijelovima. Kombinira nekoliko strategija pretraživanja. Drži verifikaciju blizu. Tretira ciljeve kao kompromise. Cilja na stvarne pozadinske sustave. Ostaje istraživački program jer još uvijek učimo gdje je granica između automatiziranog otkrića, ljudske prosudbe, ograničenja rješavača i stvarnosti implementacije.
Tu granicu vrijedi istraživati. Softverska industrija ima previše malih vrućih petlji, previše duplicirane usmene predaje o performansama i previše optimizacija kojih se nitko ne želi ponovno doticati. Ako Forge može pretvoriti čak i dio tog posla u ponovljiv proces utemeljen na dokazima, rezultat nije samo brži kod. To je mirniji kod. Mirniji kod je podcijenjen, uglavnom od strane ljudi koji nisu bili pozvani u 02:17.
Što dobar Forge pokretanje zahtijeva
Ozbiljan Forge eksperiment počinje prije nego što se motor pokrene. Tim mora donijeti stvarno jezgro, a ne nejasnu pritužbu o performansama. Potrebni su reprezentativni ulazi, poznati rubni slučajevi, ciljani hardver, trenutna mjerila i poslovni razlog zašto je to jezgro važno. Inače, sintetski motor može provesti puno vremena rješavajući problem koji zapravo nitko nema. Istraživački alati nisu imuni na smeće na ulazu. Oni samo čine smeće skupljim za pregled.
Najkorisniji ulaz je mali, oštar ugovor. Što funkcija treba izračunati? Koji algebarski zakoni su važni? Koje je ponašanje prekoračenja namjerno? Koji su rasponi nemogući po konstrukciji, a koji se jednostavno nisu dogodili u zadnjem testnom pokretanju? Koji izlazi mogu tolerirati aproksimaciju, a koji ne mogu? Tim koji ne može odgovoriti na ta pitanja vjerojatno još nema problem optimizacije. Ima problem razjašnjenja proizvoda koji nosi kompilatorski šešir.
Dobro pokretanje također treba ciljanu poziciju. x86-64 i RISC-V nisu isto. WASM ima različita ograničenja. Vulkan GPU putanje brinu o oblicima i kretanju memorije. Verilog postavlja hardverska pitanja koja normalni aplikacijski timovi rijetko uživaju prije kave. Forge može istraživati spuštanje na ciljnu arhitekturu, ali ne može odlučivati o organizacijskim prioritetima. Ako je prenosivost važnija od brzine na jednoj arhitekturi, recite to. Ako je latencija važnija od memorije, recite to. Ako je pritisak na registre praktično ograničenje, recite i to. Motor je moćan, nije vidovit.
Izlaz bi trebalo tretirati kao paket dokaza. Kandidat, cilj, put dokaza, odbačeni protuprimjeri, pozadinski sustav, kontekst mjerila i otvorene napomene. Taj paket je ono što ljudima omogućuje donošenje razumne odluke. Ponekad je pobjednički potez usvojiti kandidata. Ponekad je zadržati staro jezgro jer kompromis oko prenosivosti nije vrijedan toga. Ponekad je otkriće da je specifikacija bila previše labava. Sva tri ishoda su korisna. Samo jedan od njih izgleda uzbudljivo u demonstraciji, zbog čega su demonstracije loša zamjena za inženjering.
Pouka
Pouka Forgea je jednostavna: performanse ne bi smjele prestići dokaz. Pretraživanje je moćno, ali tražilica bez provjere samo je vrlo energičan način stvaranja grešaka. Provjera je moćna, ali bez pretraživanja čeka da joj ljudi donesu kandidate. Forge spaja to dvoje i pita koja jezgra možemo otkriti kada je stroju dopušteno istraživati, ali mu nije dopušteno lagati.
To je istraživanje vrijedno rada. Tipizirane specifikacije, pretraživanje kandidata, lijevci dokaza, Pareto ciljevi i spuštanje na pozadinski sustav. Ne magija. Ne prečac za proizvod. Način da se napravi bolji mali kod s priloženim dokazima.