Vështirësitë e Jo-Determinizmit

Kohët e fundit, u përballa me një problem interesant - më duhej një mënyrë përcaktuese dhe ndër-platformë e "kohësimit" të kodit C++. Me përcaktues, dua të them që kodi identik duhet të marrë të njëjtin numër njësish kohore për t'u ekzekutuar. Me ndër-platformë, dua të them që i njëjti kod në Windows dhe Ubuntu duhet të marrë një numër të barabartë njësish kohore për t'u ekzekutuar.

Natyrisht, matja e kohës së CPU-së nuk do ta shkurtojë atë. Kodi i makinerisë ndryshon midis arkitekturave dhe sistemeve operative, kështu që sigurisht i njëjti kod do të kërkonte sasi të ndryshme kohe për t'u ekzekutuar. Edhe në të njëjtën makinë, faktorë si mungesa e cache-it luajnë një rol të rëndësishëm – mjaftueshëm për të anuar kohën e CPU-së përgjatë ekzekutimeve të së njëjtës pjesë të kodit. Më duhej të bëja diçka më të zgjuar…

Motivimi

Unë u përballa me këtë problem gjatë punës në projektin tim, "Karakteri i kodit". Karakteri i kodit është një sfidë në internet e inteligjencës artificiale, ku garuesit shkruajnë robotë për të kontrolluar një ushtri në një lojë strategjie të bazuar në kthesa. Doja të kufizoja sasinë e kodit që një konkurrent mund të ekzekutonte me një kthesë.

Mendimi im i parë ishte thjesht të caktoja kohën e kodit, por siç e kemi parë, ajo strategji nuk është as përcaktuese, kështu që një konkurrent që dorëzon të njëjtin kod dy herë mund të japë rezultate krejtësisht të ndryshme. Në fakt, ne u përpoqëm ta zbatonim këtë zgjidhje dhe rezultatet ndryshonin aq shumë saqë një garues mund të humbte dhe të fitonte — me të njëjtin kod! Përfundoi të ishte jashtëzakonisht i rastësishëm dhe na u desh të hiqnim dorë nga ideja e përdorimit të kohës fare.

LLVM Bytecode

Meqenëse nuk mund të masnim kohën, vendosëm të matim numrin e udhëzimeve që po ekzekutoheshin. Kjo do të thotë se na duhej një mënyrë për të instrumentuar kodin e garuesve. Nëse nuk jeni të njohur me termin, instrumentimi është shtimi i kodit në disa aplikacione në mënyrë që të monitorohet çdo komponent i atij aplikacioni, si përdorimi i CPU-së ose koha e ekzekutimit. Në këtë rast, na duhej të monitoronim numrin e udhëzimeve të ekzekutuara nga një robot i konkurrentit. Natyrisht, ne nuk mund të prisnim që garuesit të instrumentonin vetë robotët e tyre, kështu që ne duhej ta automatizonim këtë proces prapa skenave.

Ne donim të shmangnim shpenzimet e sipërme të një vegle instrumentimi në kohën e ekzekutimit pasi do të ekzekutonim ndeshjet në serverin tonë, kështu që diçka si "vegla PIN" ishte e papërshtatshme për qëllimet tona. Në vend të kësaj, ne vendosëm të instrumentonim drejtpërdrejt kodin e garuesve për të numëruar numrin e udhëzimeve që ata do të ekzekutonin. Në vend të binarëve të instrumenteve (kodi i makinës), ne vendosëm të përdorim Clang për të përpiluar kodin tonë dhe bytekodin e instrumentit LLVM.

Nëse nuk jeni të njohur me "LLVM", është "një koleksion i përpiluesve modularë dhe të ripërdorshëm dhe teknologjive të zinxhirit të veglave". Një nga projektet e tyre kryesore është LLVM IR dhe backend. Me fjalë të thjeshta, LLVM ka zhvilluar një Përfaqësim të Ndërmjetëm në të cilin një "frontend" i përpiluesit mund të përpilojë kodin. Kjo LLVM IR përpilohet më pas në kodin e makinës nga prapavija e LLVM. Kështu, nëse do të krijonit një gjuhë të re, mund të vendosni të lejoni që LLVM të merret me gjenerimin dhe optimizimin e kodit të makinës dhe të shkruani një frontend për ta kthyer gjuhën tuaj në LLVM IR.

Clang është një frontend përpiluesi që është nën projektin LLVM. Meqenëse na duhej një metodë ndër-platformë për të matur kodin, nuk mundëm të instrumentonim kodin binar. LLVM IR, megjithatë, është i pavarur nga platforma, pasi është vetëm një paraqitje e ndërmjetme e kodit. Instrumentimi i IR me ndihmën e bibliotekave LLVM është një zgjidhje e thjeshtë, ndër-platformë.

Zgjidhja

Thjesht numërimi i numrit të udhëzimeve LLVM IR në kod nuk do të mjaftojë, pasi na duhet numri i instruksioneve të ekzekutuara në të vërtetë, jo vetëm numri i instruksioneve në kod. Për këtë qëllim, ne zhvilluam një algoritëm të thjeshtë që mbështetet në konceptin e një "blloku bazë" të kodit.

Një bllok bazë kodi është një grup instruksionesh në të cilat pika e hyrjes mund të jetë vetëm instruksioni i parë dhe pika e daljes mund të jetë vetëm instruksioni i fundit. Për të marrë një intuitë për këtë, provoni të ndani çdo pjesë të kodit në grupe të njëpasnjëshme udhëzimesh në të cilat nuk ka degëzime (nëse, sythe, kthime) përveç udhëzimit të fundit në një grup dhe nuk është e mundur të futet (udhëzimet e para në një funksion , cikli ose një bllok if/else) ruaj për instruksionin e parë në një grup. Rezultati është grupi i blloqeve bazë në kod - ato janë blloqe të kodit sekuencial që thjesht mund të ekzekutohen pa pasur nevojë të merrni ndonjë vendim se çfarë instruksioni do të ekzekutohet më pas.

Pse nuk përpiqemi ta bëjmë këtë tani? Këtu është një fragment nga kodi i mostrës që u është ofruar garuesve të Karakterit të Kodit:

Duke përdorur faktin se një bllok bazë ka vetëm një pikë hyrjeje (udhëzimin e tij të parë) dhe një dalje (udhëzimin e tij të fundit), ne mund ta copëtojmë fragmentin e mësipërm në këto blloqe bazë:

Ndërsa kjo na ndihmon të kuptojmë se si funksionojnë blloqet bazë, algoritmi që kemi përdorur në Karakterin e kodit përdor LLVM IR, i cili duket si ky:

Nëse shikoni me vëmendje, do të vini re se fragmenti i mësipërm është tre blloqet e para të fragmentit tonë C++ të përpiluar në LLVM IR (çdo rresht <label> është fillimi i një blloku bazë).

LLVM ka biblioteka që na lejojnë të shkruajmë 'kalime' - kod që mund të ekzekutohet në LLVM IR. LLVM API na lejon të lexojmë dhe analizojmë lehtësisht LLVM IR duke përsëritur mbi module, funksione dhe blloqe bazë, madje të modifikojmë LLVM IR përpara se ta përpilojmë atë në kodin e makinës.

Tani që kemi këto blloqe bazë dhe API LLVM, bëhet e thjeshtë të numërosh numrin e instruksioneve që ekzekutohen duke përdorur këtë algoritëm të thjeshtë:

  1. Shkruani një funksion IncrementCount që pranon një numër të plotë dhe rrit një int statik me atë numër të plotë kur thirret. Kjo duhet të lidhet me kodin e konkurrentit.
  2. Përsëriteni nëpër të gjitha blloqet bazë në kodin e konkurrentit. Për çdo bllok bazë, bëni hapat 3 dhe 4:
  3. Vendosni n = numri i udhëzimeve në atë bllok bazë.
  4. Fusni një thirrje për funksionin IncrementCount menjëherë përpara udhëzimit përfundimtar në bllokun bazë, duke marrë n si argument.
  5. Numri i plotë statik mbi të cilin funksionon IncrementCount do të ketë numërimin përfundimtar të udhëzimeve pasi kodi i konkurrentit të ketë përfunduar. Kjo mund të ruhet diku për të inspektuar më vonë.

IR jonë e instrumentuar do të duket kështu:

Siç mund ta shihni, një telefonatë në IncrementCount bëhet në fund të çdo blloku bazë pikërisht përpara udhëzimit të fundit. Duke përdorur int-in statik me të cilin funksionon IncrementCount, mund të marrim numërimin e instruksioneve në fund të çdo kthese të garuesit. Ky numërim është gjithashtu përcaktues dhe ndër-platformë, pasi i njëjti kod është i garantuar të gjenerojë të njëjtin kod IR LLVM nëse përdorim të njëjtin version të përpiluesit dhe flamujt e përpiluesit në kodin e garuesve.

konkluzioni

Rezulton se kodi i profilizimit nuk është çështja e thjeshtë që dikur mendova marrëzisht se ishte. Në procesin e punës në detyrën mashtruese të thjeshtë të kodit të kohës, përfundova duke lexuar pak se si funksionojnë përpiluesit dhe për kalimet LLVM. Nëse jeni të interesuar për gjenerimin e kodit dhe dëshironi të shkruani lejen tuaj LLVM, vetë LLVM "ka ofruar një tutorial" se si të filloni. Ekziston edhe "ky postim i shkëlqyer në blog" që përdora kur shkruaja lejen time. Meqenëse API LLVM nuk është i përputhshëm me versionet kryesore, kini kujdes se cilin version LLVM po përdorni.

Kodi përfundimtar i kalimit LLVM i përdorur është "këtu".