Välimuistiystävälliset tietorakenteet
Suunnittele array of structures - ja structure of arrays -rakenteita ja pakkaa data välimuistin paikallisuuden hyödyntämiseksi.
Välimuistiystävälliset tietorakenteet on ilmainen C++ Academy-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea tästä oppimispolusta kokonaan mitkä tahansa 3 oppituntia ilmaiseksi — sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä käytännön harjoittelun sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. Oppitunti kuuluu C++ Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. C++ Academy-kurssilla on yhteensä 4 oppituntia.
Muistihierarkia
Suorittimissa on useita välimuistitasoja (L1, L2, L3), jotka ovat paljon päämuistia nopeampia. Välimuistiystävällinen koodi pitää usein käytetyt tiedot lähellä suoritinta.
Välimuistirivit
Muisti haetaan välimuistiriveinä, joiden koko on tyypillisesti 64 tavua. Yhden tavun lukeminen lataa koko rivin. Hyödyntäkää tätä.
Viittauspaikallisuus
Kaksi tärkeää ominaisuutta:
- Tilallinen paikallisuus — läheisen muistin käyttäminen pian
- Ajallinen paikallisuus — saman muistin käyttäminen uudelleen pian
Peräkkäiset ja linkitetyt rakenteet
Vektorit tallentavat tiedot peräkkäin, joten niiden läpikäynti on välimuistiystävällistä. Linkitetyt listat hajauttavat muistin ja rikkovat välimuistin jokaisella askeleella.
// Cache friendly
std::vector<int> v(1000);
for (auto& x : v) ++x;
// Cache UNfriendly
std::list<int> l(1000);
for (auto& x : l) ++x;AoS ja SoA
Tietuerakenteiden taulukoille on kaksi asettelua:
- AoS (rakenteiden taulukko) — luonteva, mutta yhden kentän läpikäynti koskettaa kaikkia kenttiä
- SoA (taulukoiden rakenne) — parempi, kun useimmat silmukat käyttävät vain joitakin kenttiä
// AoS
struct Particle { float x, y, z, vx, vy, vz; };
std::vector<Particle> particles;
// SoA
struct Particles {
std::vector<float> x, y, z, vx, vy, vz;
};Rakenteiden pakkaaminen
Järjestäkää jäsenet suurimmasta pienimpään koon mukaan täytteen minimoimiseksi. pahole-työkalujen kaltaiset työkalut näyttävät todellisen asettelun.
struct Bad { char c; double d; char c2; }; // padded
struct Good { double d; char c; char c2; }; // smallerFalse sharing
Kun kaksi säiettä kirjoittaa saman välimuistirivin eri muuttujiin, ne mitätöivät toistensa välimuistirivit. Tämä on suorituskyvyn kannalta tuhoisaa. Lisätkää täytettä, jotta koko on 64 tavua.
struct alignas(64) Counter {
std::atomic<int> value;
};Usein ja harvoin käytettyjen tietojen erottaminen
Erotelkaa usein käytetyt tiedot harvoin käytetyistä tiedoista sijoittamalla ne eri rakenteisiin. Suoritin tallentaa välimuistiin vain usein käytetyn osan.
Esivaraus
Varaa vektoreille tilaa etukäteen reserve-jäsenfunktiolla toistuvien uudelleenvarausten välttämiseksi. Jokainen uudelleenvaraus kopioi kaikki alkiot, mikä on kallista ja rikkoo välimuistin.
Peräkkäinen käyttö voittaa
Taulukoiden lineaarinen läpikäynti on nopeinta. Laitteiston esihakija ennustaa seuraavat välimuistirivit ja lataa ne automaattisesti.
Välttäkää indirektiota
Osoittimet pakottavat suorittimen seuraamaan riippuvuuksia. std::vector<T*> on läpikäynnissä hitaampi kuin std::vector<T>. Käyttäkää indirektiota vain, kun se on tarpeen.
Profiloikaa ennen optimointia
"Välimuistiystävällisyys" on suuntaviiva, ei sääntö. Mitatkaa työkaluilla, kuten perf tai VTune, missä välimuistihäiriöt aiheuttavat haittaa, ja optimoikaa vasta sitten.
Pikatarkistus
Miksi std::vector-säilön läpikäynti on tyypillisesti paljon nopeampaa kuin samankokoisen std::list-säilön?
Kertaus
Nykyaikaiset suorittimet ovat riippuvaisia välimuisteista. Suosikaa vierekkäisiä säilöjä, käyttäkää SoA:ta valikoivaan kenttien käsittelyyn, pakatkaa rakenteet, välttäkää false sharing -ilmiötä ja profiloikaa välimuistihäiriöitä työkaluilla perf tai VTune kuormituskohtien löytämiseksi.
Opi C++ tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 51
- Oppitunnit
- 203
Usein kysytyt kysymykset
Onko oppitunti ”Välimuistiystävälliset tietorakenteet” ilmainen?
Kyllä — voit lukea täällä verkossa kokonaan ilmaiseksi mitkä tahansa C++ Academy-oppimispolun 3 oppituntia, myös oppitunnin “Välimuistiystävälliset tietorakenteet”. Sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä interaktiiviset harjoitukset sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. C++ Academy-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Välimuistiystävälliset tietorakenteet”?
Suunnittele array of structures - ja structure of arrays -rakenteita ja pakkaa data välimuistin paikallisuuden hyödyntämiseksi. Harjoittelet C++ Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni C++ Academy-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin C++ Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.
Kuinka kauan ”Välimuistiystävälliset tietorakenteet”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä C++ Academy-oppitunnilla?
Kyllä. Jokainen C++ Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Välimuistiystävälliset tietorakenteet
- Haarautumisen ennustaminen ja kuumat silmukat
- Profilointi perfillä, vtunella ja Sanitizereilla
- Mikrovertailut Google Benchmarkilla