Kas yra talpyklos kodas?

Koks skirtumas tarp nedraugiško talpyklos kodo ir draugiško talpyklos kodo?

Kaip galiu įsitikinti, kad rašau kodą, kuris yra efektyvus talpyklai?

649
22 мая '13 в 21:37 2013-05-22 21:37 Alexas yra nustatytas gegužės 22 d. 13 val. 2013-05-22 21:37
@ 9 atsakymai

parengiamieji darbai

Šiuolaikiniuose kompiuteriuose tik vieno lygio ciklą duomenys gali perkelti tik žemiausio lygio atminties struktūras ( registrus ). Tačiau registrai yra labai brangūs, ir dauguma kompiuterių šerdų turi mažiau nei keletą dešimčių registrų (nuo kelių šimtų iki galbūt tūkstančius baitų). Kitame atminties spektro gale ( DRAM ) atmintis yra labai pigi (ty pažodžiui milijonus kartų pigiau), tačiau po duomenų užklausos užtrunka šimtus ciklų. Šį atotrūkį tarp super greito ir brangaus ir labai lėto ir pigaus, talpyklos atminties , vadinamos L1, L2, L3, siekiant sumažinti ir sumažinti. Idėja yra ta, kad dauguma vykdomojo kodo dažnai naudoja nedidelį kintamųjų rinkinį, o likę (daug didesnis kintamųjų rinkinys) retai. Jei procesorius negali rasti duomenų L1 talpykloje, jis atrodo L2 talpykloje. Jei ne, tada L3 talpyklą ir, jei ne, pagrindinę atmintį. Kiekvienas iš šių „klaidų“ yra daug laiko.

(Analogiškumas yra tas, kad talpyklos atmintis yra sistemos atmintyje, o sistemos atmintis skirta saugojimui standžiajame diske. Saugojimas kietajame diske yra labai pigus, bet labai lėtas).

„Caching“ yra vienas iš pagrindinių latentinio poveikio mažinimo būdų. Norėdami parafrazuoti Herb Sutter (žr. Žemiau esančias nuorodas): lengva padidinti talpą, tačiau negalime išpirkti išvedimo iš vėlavimo .

Duomenys visada gaunami per atminties hierarchiją (nuo mažiausio == iki greičiausios iki lėtos). Dažniausiai paspaudimas / trūkumas reiškia „hit“ / „praleidimą“, esantį didžiausiame talpyklos lygmenyje CPU - aukščiausiu lygiu aš turiu galvoje labiausiai == lėčiausiai. Spartos talpyklos prieigos dažnis yra labai svarbus, nes kiekvienas talpyklos praradimas sukelia duomenų iš RAM (arba dar blogiau ...), kuris užtrunka ilgai (šimtai RAM, dešimtis milijonų kietojo disko ciklų). Palyginimui, duomenų nuskaitymas iš (aukščiausio lygio) talpyklos paprastai trunka tik keletą ciklų.

Šiuolaikinėse kompiuterių architektūrose procesorius palieka kliūtį veiklai (pvz., Prieigą prie RAM ar aukštesnės). Tai tik pablogės su laiku. Proceso dažnumo didinimas nebėra svarbus gerinant našumą. Problema pasiekiant atmintį. Todėl šiuo metu pastangos kurti aparatinę įrangą procesoriuose yra orientuotos į talpyklų, išankstinio atsisiuntimo, vamzdynų ir lygiagretumo optimizavimą. Pavyzdžiui, šiuolaikiniai procesoriai praleidžia apie 85% kristalų talpyklose ir iki 99% duomenų saugojimo / perdavimo!

Šiuo klausimu galima pasakyti daug. Štai keletas puikių nuorodų apie talpyklas, atminties hierarchijas ir tinkamą programavimą:

Pagrindinės talpyklos sąvokos

Labai svarbus laikinojo ryšio kodo aspektas yra susijęs su vietovės principu , kuriuo siekiama, kad susiję duomenys būtų netoli atminties, kad būtų užtikrintas efektyvus talpinimas. Kalbant apie CPU talpyklą, svarbu žinoti apie talpyklų linijas, kad suprastumėte, kaip jis veikia: kaip veikia talpyklos linijos?

Toliau nurodyti konkretūs aspektai yra svarbūs optimizuojant talpyklą:

  1. Laikinas lokalizavimas: kai buvo pasiekta konkreti atminties ląstelė, tikėtina, kad artimiausioje ateityje tą pačią vietą vėl galėsite pasiekti. Geriausia, jei ši informacija bus išsaugota talpykloje.
  2. Erdvinis lokalizavimas : tai susiję su susijusių duomenų išdėstymu vienas šalia kito. Spartinimas atliekamas daugeliu lygių, ne tik procesoriuje. Pavyzdžiui, kai skaitote iš RAM, dažniausiai pasirenkama didesnė atminties dalis, nei buvo prašoma, nes labai dažnai programai artimiausiu metu reikia šių duomenų. HDD talpyklos laikosi tos pačios minties. Ypač svarbu, kad CPU talpyklose būtų laikoma talpyklų linijų sąvoka.

Naudokite tinkamus konteinerius

Paprastas „cache-friendly“ ir „cache-unfit“ pavyzdys yra „ std::vector versus std::list . std::vector elementai yra saugomi gretimoje atmintyje, todėl jų pasiekimas yra daug patogiau talpyklai, nei prieiga prie elementų std::list , kuris saugo jo turinį visur. Taip yra dėl erdvinės lokalizacijos.

Labai gerai tai parodo Bjarn Straustrup šiame „YouTube“ vaizdo įraše (dėka @Mohammad Ali Baydoun už nuorodą!).

Nepamirškite atminties duomenų struktūroje ir algoritme

Jei įmanoma, pabandykite pritaikyti savo duomenų struktūras ir skaičiavimo tvarką taip, kad maksimaliai išnaudotumėte talpyklą. Šiuo atžvilgiu bendras metodas yra talpyklos užraktas (versija Archive.org) , kuris yra labai svarbus didelės našumo skaičiavimams (žr., Pavyzdžiui, ATLAS ).

Žinoti ir naudoti netiesioginę duomenų struktūrą

Kitas paprastas pavyzdys, kad daugelis šioje srityje kartais pamiršta, yra pagrindinės stulpeliai (pvz., , ) arba pagrindinių eilučių (pvz., , ) tvarka dvimatėms matricoms saugoti. Pavyzdžiui, apsvarstykite šią matricą:

 1 2 3 4 

Organizuojant pagal pagrindines linijas, tai saugoma atmintyje kaip 1 2 3 4 ; stulpelio viršutinėje eilutėje jis bus išsaugotas kaip 1 3 2 4 . Tai lengva suprasti, kad įgyvendinimai, kurie nenaudoja šios tvarkos, greitai susidurs (lengvai vengiama!). Deja, dažnai matau tokius dalykus savo srityje (mašinų mokymas). @MatteoItalia savo atsakyme išsamiau parodė šį pavyzdį.

Kai atkuriamas tam tikras matricos elementas iš atminties, šalia jo esantys elementai bus atkurti ir saugomi talpykloje. Jei naudojate užsakymą, tai sumažins prieigą prie atminties (nes kitos kelios vertės, reikalingos vėlesniems skaičiavimams, jau yra talpykloje).

Dėl paprastumo darome prielaidą, kad talpykloje yra viena talpyklos linija, kurioje gali būti 2 matricos elementai, o kai šis elementas yra pasirinktas iš atminties, taip pat kitas. Tarkime, mes norime, kad visų pirmiau pateikto 2x2 matricos pavyzdžio elementų suma (vadiname jį M ):

Užsakymo naudojimas (pvz., Pirmiausia keičiant stulpelio indeksą ):

 M[0][0] (memory) + M[0][1] (cached) + M[1][0] (memory) + M[1][1] (cached) = 1 + 2 + 3 + 4 --> 2 cache hits, 2 memory accesses 

Nenaudokite užsakymo (pvz., Pirmiausia pakeiskite eilutės indeksą ):

 M[0][0] (memory) + M[1][0] (memory) + M[0][1] (memory) + M[1][1] (memory) = 1 + 3 + 2 + 4 --> 0 cache hits, 4 memory accesses 

Šiuo paprastu pavyzdžiu užsakymo naudojimas maždaug padvigubina vykdymo greitį (kadangi prieiga prie atminties užima daug daugiau ciklų nei skaičiuojant sumas). Praktikoje veiklos rezultatų skirtumas gali būti daug didesnis.

Venkite nenuspėjamų šakų.

Šiuolaikinės architektūros turi vamzdynus, o kompiliatoriai labai gerai pertvarko kodą, kad sumažintų vėlavimą dėl prieigos prie atminties. Kai jūsų kritiniame kode yra (nenuspėjamų) šakų, yra sunku ar neįmanoma iš anksto parsisiųsti duomenų. Tai netiesiogiai sukels daugiau talpyklų.

Tai labai gerai paaiškinta čia (dėka @ 0x90 už nuorodą): kodėl greičiau apdoroti rūšiuojamą masyvą nei nerūšiuota masyvas?

Venkite virtualių funkcijų

virtual metodų kontekste yra prieštaringa problema, susijusi su talpyklų praleidimais (yra bendra nuomonė, kad, jei įmanoma, reikėtų vengti jų rezultatų). Virtualios funkcijos gali sukelti laikinosios atminties išnykimą ieškant, tačiau tai atsitinka tik tada, kai dažnai nėra vadinama tam tikra funkcija (kitaip ji greičiausiai bus saugoma), todėl kai kurie žmonės mano, kad tai nėra problema. Jei reikia pagalbos dėl šios problemos, žr. „ Kokios yra„ C ++ “klasės virtualiojo metodo našumo išlaidos?

Dažniausios problemos

Dažniausiai pasitaiko šiuolaikinių daugiaprocesinių talpyklų architektūrų problema, kuri vadinama klaidingu skaidymu . Taip atsitinka, kai kiekvienas atskiras procesorius bando naudoti duomenis kitoje atminties srityje ir bando ją išsaugoti toje pačioje talpykloje. Tai sukelia talpyklos liniją, kurioje yra duomenų, kuriuos gali naudoti kitas procesorius, perrašyti. Tiesą sakant, skirtingi siūlai vienas kitą verčia laukti, todėl šioje situacijoje trūksta talpyklos. Taip pat žiūrėkite (dėka @Matt už nuorodą): Kaip ir kada turėtų būti suderintos talpyklos linijos?

Ypatingas prastos atminties talpyklos ženklo ženklas (kuris tikriausiai ne tai, ką jūs suprantate šiame kontekste) yra vadinamasis perkrovimas . Taip atsitinka, kai procesas nuolat generuoja puslapių gedimus (pvz., Pasiekia atmintį, kuri nėra dabartiniame puslapyje), kuriai reikalinga prieiga prie disko.

845
22 мая '13 в 21:39 2013-05-22 21:39 atsakymą pateikė Marc Claesen gegužės 13 d. 13 val. 21:39 2013-05-22 21:39

Be @Marc Claesen atsakymo, manau, kad pamokantis klasikinis nepageidaujamo kodo talpyklos pavyzdys yra kodas, kuris nuskaito dvejetainį C masyvą (pvz., Bitmap vaizdą) stulpeliais, o ne eilėmis.

Elementai, esantys greta eilutės, taip pat yra greta atminties, todėl prieigai prie jų seka reiškia prieigą prie jų didėjančia atminties tvarka; Tai yra laikinojo išsaugojimo požiūriu, nes talpyklė yra linkusi iš anksto parinkti nuolatinius atminties blokus.

Vietoj to, prieiga prie tokių elementų stulpeliu nėra saugi, nes viename stulpelyje esantys elementai yra pašalinami iš vienos atminties (ypač jų atstumas yra lygus eilutės dydžiui), todėl, kai naudojate šį prieigos modelį, šokinėjate atmintyje talpyklos pastangos atkurti netoliese esančias atmintines.

Ir viskas, kas reikalinga, norint sunaikinti našumą, yra perkelti iš

border=0
 // Cache-friendly version - processes pixels which are adjacent in memory for(unsigned int y=0; y<height; ++y) { for(unsigned int x=0; x<width; ++x) { ... image[y][x] ... } } 

į

 // Cache-unfriendly version - jumps around in memory for no good reason for(unsigned int x=0; x<width; ++x) { for(unsigned int y=0; y<height; ++y) { ... image[y][x] ... } } 

Šis efektas gali būti gana dramatiškas (kelis mastelius greičiu) sistemose su mažomis talpyklomis ir (arba) dirbti su didelėmis matricomis (pvz., 10 + megapikselių 24 bpp vaizdų dabartinėse mašinose); dėl šios priežasties, jei reikia atlikti daug vertikalių nuskaitymų, dažnai geriau pirmiausia pasukti vaizdą 90 laipsnių, o po to atlikti įvairias analizes, ribojant nedraugišką talpyklos kodą tik sukant.

127
22 мая '13 в 22:51 2013-05-22 22:51 atsakymą pateikė Matteo Italia gegužės 22 d., 13 val. 10:51 pm 2013-05-22 22:51

Optimizuoti talpyklos naudojimą iš esmės sumažinamas iki dviejų veiksnių.

Susieti vietovę

Pirmasis veiksnys (į kurį kiti jau minėjo) yra nuorodos vieta. Vietoj nuorodos yra tikrai du matmenys: erdvė ir laikas.

  • Erdvinis

Erdvinis dydis taip pat susideda iš dviejų dalykų: pirma, mes norime glaudžiai supakuoti mūsų informaciją, todėl papildoma informacija telpa į ribotą atmintį. Tai reiškia (pvz.), Kad jums reikia gerokai patobulinti skaičiavimo sudėtingumą, siekiant pateisinti duomenų struktūras, pagrįstas mažais mazgų, sujungtų rodyklėmis.

Antra, mums reikia informacijos, kuri bus apdorojama kartu ir kartu. Tipiška talpykla veikia „linijose“, o tai reiškia, kad, kai pasiekiama tam tikra informacija, kita informacija kaimyniniuose adresuose bus įkelta į talpyklą su dalimi, kuria palietėme. Pavyzdžiui, kai paliesiu vieną baitą, talpykla gali įkelti 128 arba 256 baitus. Norėdami pasinaudoti šia galimybe, dažniausiai norite, kad duomenys būtų užsakomi, kad maksimaliai padidintumėte tikimybę, kad jūs taip pat naudosite kitus tuo pačiu metu įkeltus duomenis.

Paprastai trivialus pavyzdys gali reikšti, kad linijinė paieška gali būti daug konkurencingesnė, kai binarinė paieška yra tikėtina. Įdėję vieną elementą iš talpyklos linijos, likusios šio talpyklos linijos duomenys yra beveik nemokami. Binarinė paieška tampa žymiai greitesnė tik tada, kai duomenys yra pakankamai dideli, kad dvejetainė paieška sumažina galimų talpyklų linijų skaičių.

  • Laikas

Laikinas dydis reiškia, kad kai kuriuos duomenis atliekate kai kuriais duomenimis, tuo pačiu metu norite (kiek įmanoma) atlikti visas operacijas su tais duomenimis.

Kadangi pažymėjote jį kaip „C ++“, nurodysiu klasikinį gana nedraugiško talpyklos dizaino pavyzdį: std::valarray . valarray perkrauna daugumą aritmetinių operatorių, todėl galiu (pavyzdžiui) pasakyti a = b + c + d; (kur a , b , c ir d yra visi „valarrays“), norėdami laipsniškai įtraukti šias masyvus.

Problema yra ta, kad ji eina per vieną pora įvesties, pateikia rezultatus į laikiną, pereina kitą įvesties porą ir pan. Su dideliu duomenų kiekiu, vieno skaičiavimo rezultatas gali išnykti iš talpyklos, kol jis bus naudojamas kitame skaičiavime, todėl baigiame skaityti (ir rašyti) duomenis dar prieš gaunant galutinį rezultatą. Jei kiekvienas galutinis rezultato elementas yra kažkas panašaus (a[n] + b[n]) * (c[n] + d[n]); , mes paprastai norime skaityti kiekvieną a[n] , b[n] , c[n] ir d[n] vieną kartą, atlikti skaičiavimus, rašyti rezultatą, prieaugį n ir pakartoti, kol baigsime. 2

Linijų mainai

Antras svarbus veiksnys yra išvengti eilutės pasidalijimo. Norėdami tai suprasti, tikriausiai turime sukurti atsarginę kopiją ir pamatyti, kaip tvarkomi talpyklos. Paprasčiausia talpyklos forma yra tiesiogiai susieta. Tai reiškia, kad vienas adresas pagrindinėje atmintyje gali būti saugomas tik vienoje konkrečioje talpyklos vietoje. Jei mes naudojame du duomenų elementus, kurie yra susieti su ta pačia vieta talpykloje, jis veikia blogai - kiekvieną kartą, kai mes naudojame vieną duomenų elementą, kitas turi būti išplautas iš talpyklos, kad patektų į kitą vietą. Likusi talpyklos dalis gali būti tuščia, tačiau šie elementai nenaudos kitų talpyklos dalių.

Kad tai būtų išvengta, dauguma talpyklų yra vadinamosios „asociatyvos“. Pavyzdžiui, keturių pozicijų asociatyviosios asociatyviosios talpyklos bet kuris elementas iš pagrindinės atminties gali būti saugomas bet kurioje iš keturių skirtingų talpyklos vietų. Taigi, kai talpykla įkelia elementą, ji ieško mažiausiai neseniai naudojamo 3 elemento tarp šių keturių, sumažina jį į pagrindinę atmintį ir įkelia naują elementą į savo vietą.

Problema tikriausiai yra akivaizdi: jei talpykla su tiesioginiu žemėlapiu, du operandai, kurie patenka į tą pačią talpyklos vietą, gali sukelti blogą elgesį. N-way set-asociatyvinė talpykla padidina skaičių nuo 2 iki N + 1. Cache organizacija daugiau „takų“ reikalauja papildomos schemos ir paprastai veikia lėčiau, todėl (pvz.) 8192-way set asociatyvinė talpykla taip pat yra retas sprendimas.

Galiausiai šį veiksnį yra sunkiau kontroliuoti nešiojamame kode. Paprastai jūsų duomenų perkėlimo kontrolė yra ribota. Dar blogiau, tikslus žemėlapio talpyklos adresas priklauso nuo kitų panašių procesorių. Tačiau kai kuriais atvejais gali būti verta daryti tokius dalykus, kaip didelės buferio skyrimas, ir tada naudoti tik tas dalis, kurias pasirinkote, kad užtikrintumėte, jog tos pačios talpyklos linijos yra bendrinamos (nors tikriausiai turėsite nustatyti tikslų procesorių ir veiksmą atitinkamai).

  • Neteisingas bendrinimas

Yra dar vienas susijęs elementas, vadinamas „klaidingu dalijimu“. Tai atsitinka daugiaprocesorinėje arba kelių branduolių sistemoje, kur du (ar daugiau) procesoriai / šerdys turi atskirų duomenų, bet patenka į tą pačią talpyklos liniją. Dėl to du procesoriai / branduoliai koordinuoja savo prieigą prie duomenų, nors kiekvienas iš jų turi atskirą duomenų elementą. Visų pirma, jei abu šie duomenys keičiasi interlace, tai gali lemti reikšmingą sulėtėjimą, nes duomenys turi būti nuolat pumpuojami tarp procesorių. Jis negali būti lengvai išgydomas organizuojant talpyklą daugiau „būdų“ arba kažką panašaus. Pagrindinis būdas užkirsti kelią šiam tikslui yra užtikrinti, kad du siūlai retai (pageidautina niekada) nekeistų duomenų, kurie gali būti toje pačioje talpykloje (tokie pat įspėjimai dėl adresų, kuriais duomenys yra platinami, valdymo sudėtingumo).


  • Tie, kurie žino „C + +“ šulinį, gali stebėtis, ar tai galima optimizuoti su išraiškos šablonais. Esu tikras, kad atsakymas yra toks: taip, tai gali būti padaryta, ir jei taip būtų, tai tikriausiai būtų gana didelė pergalė. Vis dėlto aš nežinau, kas tai padarė, ir, atsižvelgiant į tai, kaip naudojamasi mažai valarray , būčiau bent šiek tiek nustebęs, kad kažkas tai padarys.

  • В случае, если кто-то задается вопросом, как valarray (разработанный специально для производительности) может быть настолько ошибочным, это сводится к одному: он был действительно разработан для таких машин, как более старые Crays, которые использовали быструю основную память и нет кеша. Для них это действительно был идеальный дизайн.