Sepa ja otsi, mis tõestab end ära
Vana trikiga seotud probleem
Igas tõsises tarkvarasüsteemis on mõni koodijupp, mis mõjutab asju palju rohkem, kui tema suurus lubaks arvata. Silmus, mis jookseb miljoneid kordi. Bititehe tihendustee sees. Väike maatriksirutiin. Modulaararitmeetika tuum. Selline asi, mis koodiülevaatusel kahjutu välja näeb ja siis vaikselt otsustab energiarve, latentsusaja eelarve või selle, mitu masinat sul osta tuleb. Väga demokraatlik asi, see tarkvara. Üks pisike funktsioon võib kõigi koosoleku ära rikkuda.
Ajalooliselt on neid tuumi täiustanud inimesed. Vanem insener mäletab nippi mõnest artiklist. Keegi kaevab üles vana foorumipostituse. Kirjutatakse benchmark-komplekt. Proovitakse mõnda kandidaati. Kiireim võidab, kui ta ikka õige tundub. Siis organisatsioon selle külmutab, sest uuesti puudutamine tundub nagu magava trafo torkamine kahvliga.
Forge on uurimistöö selle protsessi parema versiooni kallal. See on programmisünteesi mootor väikeste, kriitiliste implementatsioonide jaoks: anna talle tüübitud spetsifikatsioon ja omadused, lase tal otsida kandidaatprogramme, mõõda ja võrdle kompromisse, kontrolli samaväärsust, seejärel alanda leitud implementatsioon sihtmärkidele, mis olulised on. Oluline sõna ei ole otsimine. Oluline sõna on ikkagi. See peab ikkagi õige olema.
Sellepärast elabki Forge uurimistöös. See ei ole avalik tootenupp, kus keegi kirjutab tee kiiremaks ja saab ime. See on sünteesitööpink partnerkatsete, tuumi avastamise ja uurimistöö jaoks selle kohta, kui kaugele automatiseeritud otsing võib minna, kui see on seotud kontrollimisega, mitte benchmark-teatriga.
Spetsifikatsioon on lähtejoon
Optimeerimine ilma spetsifikatsioonita on lihtsalt hasartmäng ilusamate muutujanimedega. Kui nutikas kandidaat ilmub, peab meeskond teadma, mida see peaks säilitama. Kas see töötleb iga sisendit või ainult sõbralikke benchmarki omi? Kas see austab ületäitumise käitumist? Kas algebraline identiteet kehtib tegelikult kasutatava esituse all? Kas see hoiab sama semantikat, kui see alandatakse teisele backendile?
Forge alustab tüübitud avaldistest ja omadustest, sest otsing vajab piiri. Piir ütleb, mis loeb samaväärseks. Ilma selleta võib mootor leida midagi uskumatult kiiresti, kustutades poole tööst. Arvutid on suurepärased pahatahtlikus vastavuses, kui leping on ähmane.
Otsingu pool on teadlikult mitmuses. Loendav otsing on kasulik, kui ruum on piisavalt väike, et see katta. CEGIS on kasulik, kui vastunäited saavad täpsustamist juhtida. Geneetiline programmeerimine ja MCTS uurivad erinevalt. ML-juhitud otsing saab õppida kulumudeleid ja seada prioriteediks paljutõotavad piirkonnad. Ükski neist pole universaalselt parim. See ei ole nõrkus. Nii käitub otsing päris maailmas. Kui üks haamer lahendaks iga tuuma, oleksid tööriistakastid väga igavad ja riistvaramüüjad töötud.
Uurimisküsimus on, kuidas neid mootoreid kombineerida piisava tõestussurvega, et tulemus poleks lihtsalt nutikas. Sünteesitud tuum peab üle elama nii õnneliku tee benchmarki kui ka õnnetu tee kontrollija. Muidu pole täiustus inseneritöö. See on mustkunstitrikk hoolduskuluga.
Kontrollija on täiskasvanu ruumis
Forge kasutab kontrollimiseks mitmekihilist süsteemi, sest ühest kontrollist ei piisa kõigi valdkondade jaoks. Kiired näited on odavad ja kasulikud. Ominaduspõhised testid leiavad laia valiku vigu ja vähendavad vastunäited loetavaks. SMT-lahendurid, nagu Z3 ja CVC5, suudavad tõestada samaväärsust seal, kus kodeering on jälgitav. Ammendav kontroll on väikeste valdkondade puhul praktiline. E-graafi võrdsuse küllastumine pakub veel ühe tee algebralise samaväärsuse juurde.
Süsteem on oluline, sest tuumad ebaõnnestuvad tüütutel viisidel. Kandidaat võib läbida kõik tavalised testid ja olla siiski vale äärejuhtumi puhul. See võib olla õige märgita sisendite puhul ja vale märgiga sisendite puhul. See võib olla õige matemaatilises väljas ja vale pärast seda, kui valitud esitus ületab piiri. See võib olla õige enne madaldamist ja kavalalt vale pärast käskude valiku otsust. Kontrollija on olemas, sest optimism ei ole testimisstrateegia. Me kontrollisime. Korduvalt. See jääb tõeks.
On ka praktiline põhjus hoida mitu tõestusrada. Formaalsed meetodid on võimsad, kuid mitte tasuta. Mõned kodeeringud aeguvad. Mõned valdkonnad on ammendava kontrolli jaoks liiga suured. Mõnda omadust on lihtsam kõigepealt tõenäosuslikult testida ja hiljem tõestada. Forge käsitleb kontrollimist lehtrina, mitte puhtusetseremooniana. Odavad kontrollid lükkavad tagasi ilmselge jama. Tugevamad kontrollid kaitsevad lõplikku kandidaati.
Kiirus ei ole üks number
Jõudluse kallal töötamine muutub naeruväärseks, kui ühel mõõdikul lubatakse domineerida igas vestluses. Latentsus on oluline. Tehete arv on oluline. Mälu kasutus on oluline. Registrisurve on oluline. Kompileerimisaeg on mõnikord oluline. Teisaldatavus on oluline, kui sama tuum peab elama rohkem kui ühel tagarakendusel. Kandidaat, kes võidab latentsuses, põletades registreid nagu väike lõke, võib olla vale tegeliku sihtmärgi jaoks. Kandidaat, kes on väike, kuid aeglane, võib olla kasulik kusagil mujal. Kontekst jääb alistamatuks.
Seetõttu raamib Forge optimeerimist Pareto-probleemina. Mootor saab otsida üle eesmärkide, selle asemel et teeselda, et on olemas üks universaalne skoor, mille on andnud väga enesekindel tabel. Kasulik väljund ei ole alati kõige kiirem kandidaat. Mõnikord on see kandidaatide perekond nähtavate kompromissidega, et insener saaks valida selle, mis sobib juurutamise piirangutega.
See on ka põhjus, miks mulle ei meeldi alasti kiirendusväited ajaveebipostitustes. Teadusleht võib kirjeldada sisemisi ootusi ja eksperimentaalseid eesmärke, kuid avalikud väited vajavad värskeid käivitusi, praegust riistvara, praeguseid kompilaatori lipukesi ja täpset töökoormuse konteksti. Muidu muutub number suveniiriks. Suveniirid on toredad. Need ei ole arhitektuur.
Aus väide on niikuinii tugevam: Forge seisneb selles, et muuta otsing korratavaks, võrreldavaks ja kontrollitavaks. Kui kandidaat võidab, peaksime teadma, millise eesmärgi see võitis, milliseid kandidaate see võitis, milline kontrollija selle vastu võttis ja millisele tagarakendusele see on suunatud. See on palju kasulikum kui number, mis hõljub läbi slaidikomplekti kallilt välja nähes.
Madaldamine on koht, kus tõestusi proovile pannakse
Avastatud implementatsioon on kasulik ainult siis, kui see jõuab tervena päris sihtmärkideni. Forge'i uurimistöö hõlmab allalaskmist sellistele tagaotsadele nagu x86-64, RISC-V, WASM, Vulkani GPU-rajad, C ja Verilog. See sihtmärkide loend pole lihtsalt kaunistus. Igal tagaotsal on oma piirangud, käskude kujud, mälukäitumine ja rikkerežiimid. Sama spetsifikatsioon peab säilitama oma tähenduse, samal ajal kui implementatsioon muutub millekski, mida sihtmärk suudab tegelikult käivitada.
Siin ühendub süntees ülejäänud Dweve'i virnaga. Core soovib tõhusaid sisemisi silmuseid. Numerus hoolib deterministlikest numbrilistest tuumadest. BitWeave soovib binaarseid vektor- ja maatriksoperatsioone, mis ei raiska protsessorit. Kera hoolib arvutusgraafide allalaskmisest päris riistvarale. Forge saab neid kihte toita ainult siis, kui loodud implementatsioon on enam kui lihtsalt kiire. See peab olema samaväärne, piisavalt kaasaskantav valitud sihtmärgi jaoks ja kontrollitav, kui midagi muutub.
Mida see meeskondade jaoks muudab
Meeskonna jaoks pole huvitav nihe see, et masin võib avastada kiirema tuuma. See on see, et tuumatöö muutub vähem sõltuvaks rahvapärimusest. Selle asemel, et üks ekspert mäletab õiget nippi, muutub protsess järgmiseks: sõnasta leping, otsi ruum, mõõda kandidaate, tõesta samaväärsus, salvesta kompromiss ja genereeri sihtmärgikood. Inimesed otsustavad ikka. Nad lihtsalt lõpetavad kogu avastamise käsitsi tegemise.
See on oluline operatsioonide jaoks, sest jõudlusvõlg on kallis viisil, mida organisatsioonid sageli varjavad. Aeglane tuum muutub rohkemateks serveriteks. Rohkem servereid tähendab rohkem kulusid, rohkem energiat, rohkem juurutamise keerukust ja rohkem müra planeerimisel. Vale optimeerimine muutub intsidentideks. Õige, kuid dokumenteerimata nipp muutub tulevaseks migratsiooniriskiks. Forge on uurimistöö selle välditava jama hunniku vähendamiseks.
Toimub ka kultuuriline muutus. Käsitsi jõudlustöö premeerib sageli kangelaslikkust. Keegi kaob koopasse ja naaseb nutika bitinipiga. Kõik aplodeerivad, keegi ei mõista seda täielikult ja ettevõte on omandanud väikese püha eseme. Forge lükkab protsessi tõendite suunas: siin on spetsifikatsioon, siin on otsingutee, siin on tagasilükatud kandidaadid, siin on verifitseerija, siin on valitud tagao ts. Vähem mütoloogiat. Rohkem tõendeid.
Kus töö on endiselt raske
Miski sellest ei muuda sünteesi lihtsaks. Spetsifikatsioonid on rasked. Kui spetsifikatsioon on vale, saab mootor ustavalt avastada vale asja. Otsinguruumid võivad plahvatada. Lahendajad võivad aeguda. Kul mudelid võivad eksitada. Tagao tsad võivad paljastada üksikasju, millest abstraktne avaldis ei hoolinud. Kontrollimine võib olla tugev ühes valdkonnas ja kohmakas teises. Igaüks, kes müüb programmisünteesi kui müügiautomaati optimaalse koodi jaoks, kas jätab rasked osad vahele või küsib pettumuse eest lisatasu.
Forge on huvitav just seetõttu, et see seisab nende raskete osadega otse silmitsi. See ühendab mitu otsingustrateegiat. See hoiab kontrollimise lähedal. See käsitleb eesmärke kompromissidena. See sihib päris tagao tsu. See jääb uurimisprogrammiks, sest me õpime ikka veel, kus on piir automatiseeritud avastamise, inimese otsustuse, lahendajate piirangute ja juurutamise tegelikkuse vahel.
Seda piiri tasub uurida. Tarkvaratööstuses on liiga palju väikeseid kuumi silmuseid, liiga palju dubleeritud jõudlusrahvapärimust ja liiga palju optimeerimisi, mida keegi ei taha enam puudutada. Kui Forge suudab muuta kas või osa sellest tööst korratavaks tõendusprotsessiks, pole tulemuseks lihtsalt kiirem kood. See on rahulikum kood. Rahulikku koodi alahinnatakse, enamasti inimeste poolt, keda pole kell 02:17 välja kutsutud.
Mida hea Forge'i käitamine vajab
Tõsine Forge'i eksperiment algab enne mootori käivitamist. Meeskond peab kaasa tooma päris tuuma, mitte ebamäärase kaebuse jõudluse üle. Vaja on esinduslikke sisendeid, teadaolevaid äärejuhtumeid, sihtriistvara, praeguseid võrdlusnäitajaid ja ärilist põhjust, miks see tuum oluline on. Vastasel juhul võib sünteesimootor kulutada palju aega probleemi lahendamisele, mida kellelgi tegelikult pole. Uurimistööriistad pole immuunsed halva sisendi suhtes. Nad muudavad halva sisendi lihtsalt kallimaks uurida.
Kõige kasulikum sisend on väike ja täpne spetsifikatsioon. Mida funktsioon peaks arvutama? Millised algebralised seadused on olulised? Milline ületäitumise käitumine on tahtlik? Millised vahemikud on konstruktsiooni poolest võimatud ja millised lihtsalt ei esinenud viimases testikäitus? Millised väljundid taluvad lähendamist ja millised mitte? Meeskond, kes ei suuda neile küsimustele vastata, ei pruugi veel omada optimeerimisprobleemi. Tal on toote selgitamise probleem, mis kannab kompilaatori mütsi.
Hea käitamine vajab ka sihtasendit. x86-64 ja RISC-V pole samad. WASM-il on erinevad piirangud. Vulkani GPU-rajad hoolivad kujudest ja mälu liikumisest. Verilog tõstatab riistvaraküsimusi, mida tavalised rakendusmeeskonnad enne kohvi harva naudivad. Forge saab uurida sihtalandamist, kuid ta ei saa otsustada organisatsiooniliste prioriteetide üle. Kui teisaldatavus on olulisem kui ühe sihtkoha kiirus, öelge seda. Kui latentsus on olulisem kui mälu, öelge seda. Kui registrisurve on praktiline piir, öelge ka seda. Mootor on võimas, mitte selgeltnägija.
Väljundit tuleks käsitleda nagu tõendite paketti. Kandidaat, eesmärk, tõestustee, tagasilükatud vastunäited, tagarakendus, võrdlusnäitajate kontekst ja avatud hoiatused. See pakett on see, mis laseb inimestel teha mõistliku otsuse. Mõnikord on võidukäik kandidaadi kasutuselevõtt. Mõnikord on see vana tuuma säilitamine, sest teisaldatavuse kompromiss pole seda väärt. Mõnikord on avastus see, et spetsifikatsioon oli liiga lõtv. Kõik kolm tulemust on kasulikud. Ainult üks neist näeb demos põnev välja, mistõttu on demode halb aseaine inseneritööle.
Õppetund
Forge'i õppetund on lihtne: jõudlus ei tohiks tõestusest ette joosta. Otsing on võimas, kuid otsingumootor ilma kontrollita on lihtsalt väga energiline viis vigade loomiseks. Kontroll on võimas, kuid ilma otsinguta ootab see, et inimesed toovad talle kandidaate. Forge paneb need kaks kokku ja küsib, milliseid tuumasid saame avastada, kui masinal lubatakse uurida, kuid ei lubata valetada.
See on uurimistöö, mida tasub teha. Tüübitud spetsifikatsioonid, kandidaadiotsing, tõestuslehtrid, Pareto-eesmärgid ja tagarakendus. Mitte maagia. Mitte toote otsetee. Viis teha paremat väikest koodi koos lisatud tõenditega.