streamalism.org

1. Bemutatkozás

Az elõrejelzés egy érdekes fogalom a számítástechnikában, és mély hatással lehet alkalmazásaink teljesítményére. Még általában nem érthető jól, és a legtöbb fejlesztő nagyon kevés figyelmet fordít rá.

Ebben a cikkben pontosan meg fogjuk vizsgálni, hogy mi az, hogyan befolyásolja szoftverünket, és mit tehetünk ellene.

2. Mik azok az utasításvezetékek?

Bármely számítógépes program írása közben egy sor parancsot írunk, amelyeket elvárjuk, hogy a számítógép sorrendben hajtson végre.

A korai számítógépek ezeket egyenként futtatták. Ez azt jelenti, hogy minden parancs betöltődik a memóriába, teljes egészében végrehajtva, és csak a befejezése után töltődik be a következő.

Utasítási csővezetékek előrelépés ehhez képest. Lehetővé teszik a processzor számára, hogy darabokra bontsa a művet, majd különböző részeket párhuzamosan hajtson végre. Ez lehetővé tenné a processzor számára az egyik parancs végrehajtását a következő, indulásra kész betöltés közben.

A processzor belsejében lévő hosszabb csővezetékek nem csak lehetővé teszik az egyes részek egyszerűsítését, hanem több részének párhuzamos végrehajtását is. Ez javíthatja a rendszer általános teljesítményét.

Például lehet egy egyszerű programunk:

int a = 0; a + = 1; a + = 2; a + = 3;

Ezt feldolgozhatja egy folyamat, amely a Fetch, Decode, Execute, Store szegmenseket tartalmazza:

Itt láthatjuk, hogy a négy parancs teljes végrehajtása párhuzamosan fut, így az egész sorozat gyorsabbá válik.

3. Melyek a veszélyek?

Bizonyos parancsok, amelyeket a processzornak végre kell hajtania, problémákat okoznak a csővezetéken. Ezek olyan parancsok, amelyeknél a csővezeték egy részének végrehajtása a korábbi részektől függ, de előfordulhat, hogy ezeket a korábbi részeket még nem hajtották végre.

Az ágak a veszély sajátos formája. A végrehajtás a két irány egyikében halad, és nem lehet tudni, melyik irányba, amíg az ág le nem oldódik. Ez azt jelenti a parancsok elágazáson túl történő betöltése nem biztonságos, mert nincs módunk tudni, honnan töltsük be őket.

Változtassuk meg az egyszerű programunkat egy fiók bevezetésével:

int a = 0; a + = 1; ha (a <10) {a + = 2; } a + = 3;

Ennek eredménye ugyanaz, mint korábban, de bevezettünk egy ha állítása annak közepén. A számítógép látja ezt, és nem tudja betölteni az ezen túlmenő parancsokat, amíg nem oldják meg. Mint ilyen, az áramlás valami ilyennek fog kinézni:

Rögtön láthatjuk, hogy ennek milyen hatása van a programunk végrehajtására, és hány óra lépésre volt szükség ugyanazon eredmény végrehajtásához.

4. Mi az ágjóslás?

Az elágazás előrejelzése a fentiek továbbfejlesztése, ahol számítógépünk megpróbálja megjósolni, hogy az ág melyik irányba halad, majd ennek megfelelően jár el.

A fenti példánkban a processzor ezt megjósolhatja ha (a <10) valószínűleg az lesz igaz, és így úgy fog működni, mintha az utasítás a + = 2 volt a következő, akit kivégeztek. Ez akkor az áramlást olyannak tűnné, mint:

Rögtön láthatjuk, hogy ez javította programunk teljesítményét - ez most kilenc kullancsot vesz és nem 11-et, tehát 19% -kal gyorsabb.

Ez azonban nem kockázat nélküli. Ha az elágazás-előrejelzés téves, akkor elkezdi sorba állítani azokat az utasításokat, amelyeket nem szabad végrehajtani. Ha ez megtörténik, akkor a számítógépnek el kell dobnia őket, és elölről kell kezdenie.

Fordítsuk meg a feltételünket úgy, hogy most legyen hamis:

int a = 0; a + = 1; ha (a> 10) {a + = 2; } a + = 3;

Ez olyasmit hajthat végre, mint:

Ez most lassabb, mint a korábbi folyamat, bár kevesebbet csinálunk! A processzor helytelenül jósolta meg, hogy az ág értékelni fog igaz, elkezdte sorba állítani a a + = 2 utasítást, majd el kellett vetnie és újra kellett kezdenie, amikor az ág értékelte hamis.

5. Valódi hatás a kódra

Most, hogy tudjuk, mi az elágazás-jóslat, és milyen előnyökkel jár, hogyan hathat ránk? Végül, néhány processzorciklus elvesztéséről beszélünk nagy sebességű számítógépeken, így biztosan nem lesz észrevehető.

És néha ez igaz. De néha meglepő különbséget jelenthet alkalmazásaink teljesítménye. Nagyon függ attól, hogy pontosan mit csinálunk. Pontosabban attól függ, hogy mennyit csinálunk rövid idő alatt.

5.1. Számlálási bejegyzések

Próbáljuk meg számlálni a bejegyzéseket egy listában. Készítünk egy listát a számokról, majd megszámoljuk, hogy hányan vannak kisebbek egy bizonyos határértéknél. Ez nagyon hasonlít a fenti példákhoz, de ciklusban csináljuk, nem csak egyetlen utasításként:

Lista számai = LongStream.range (0, top) .boxed () .collect (Collectors.toList ()); if (shuffle) {Gyűjtemények.keverés (számok); } hosszú levágás = felső / 2; hosszú számlálás = 0; hosszú indítás = System.currentTimeMillis (); for (Hosszú szám: számok) {if (szám <cutoff) {++ count; }} hosszú vég = System.currentTimeMillis (); LOG.info ("Számolt {} / {} {} számok {} ms-ban", count, top, shuffle? "Shuffled": "sorted", end-start);

Ne feledje, hogy csak azt a ciklust időzítjük, amelyik elvégzi a számlálást, mert ez érdekel bennünket. Szóval, mennyi időbe telik?

Ha elég kicsi listákat állítunk elő, akkor a kód olyan gyorsan fut, hogy nem lehet időzíteni - a 100 000 méretű listán még mindig 0 ms idő jelenik meg. Amikor azonban a lista elég nagy lesz ahhoz, hogy időzítsük, jelentős különbséget láthatunk attól függően, hogy összekevertük-e a listát vagy sem. 10.000.000 szám listájához:

• Rendezve - 44ms
• Vegyes - 221ms

Vagyis az összekevert lista számolása ötször hosszabb ideig tart, mint a rendezett lista, annak ellenére, hogy a tényleges számlálandó számok megegyeznek.

A lista rendezése azonban lényegesen drágább, mint csak a számlálás elvégzése. Mindig át kell alakítanunk a kódunkat, és meg kell határoznunk, hogy a teljesítménynövekedés hasznos-e.

5.2. Fióktelepek rendje

A fentieket követve ésszerűnek tűnik, hogy az ágak sorrendje egy ha más állításnak fontosnak kell lennie. Vagyis arra számíthatunk, hogy a következők jobban teljesítenek, mintha újrarendelnénk az ágakat:

if (mostLikely) {// Csinálj valami mást} if (lessLikely) {// Csinálj valamit} más if

Azonban, a modern számítógépek elkerülhetik ezt a problémát az elágazás-előrejelző gyorsítótár használatával. Valóban, ezt is tesztelhetjük:

Lista számai = LongStream.range (0, top) .boxed () .collect (Collectors.toList ()); if (shuffle) {Gyűjtemények.keverés (számok); } hosszú cutoff = (hosszú) (top * cutoffPercentage); hosszú alacsony = 0; hosszú magas = 0; hosszú indítás = System.currentTimeMillis (); for (Hosszú szám: számok) {if (szám <cutoff) {++ alacsony; } else {++ magas; }} hosszú vég = System.currentTimeMillis (); LOG.info ("Számolt {} / {} számok {} ms-ban", alacsony, magas, vég - kezdet);

Ez a kód nagyjából egyidőben fut - ~ 35ms rendezett számoknál, ~ 200ms vegyes számoknál - amikor 10 000 000 számot számolunk, függetlenül a cutoffPercentage.

Ez azért van, mert az ágjelző mindkét ágat egyformán kezeli és helyesen kitalálni, hogy melyik utat fogjuk megtenni értük.

5.3. Feltételek kombinálása

Mi van, ha egy vagy két feltétel közül választhatunk? Lehetséges, hogy más módon írjuk át a logikánkat, ugyanolyan viselkedéssel, de ezt kell tennünk?

Például, ha két számot összehasonlítunk a 0-val, akkor alternatív megközelítés az, ha összeszorozzuk őket, és az eredményt 0-val hasonlítjuk össze. Ez akkor egy feltételt egy szorzással helyettesít. De vajon érdemes ez?

Vegyünk egy példát:

hosszú [] első = LongStream.range (0, TOP) .térkép (n -> Math.random () Math.random () <FRACTION? 0: n) .toArray (); hosszú számlálás = 0; hosszú indítás = System.currentTimeMillis (); mert (int i = 0; i <TOP; i ++) {if (első [i]! = 0 && második [i]! = 0) {++ számít; }} hosszú vég = System.currentTimeMillis (); LOG.info ("Számolt {} / {} számok külön módban {} ms-ban", count, TOP, end-start);

A hurok belsejében lévő állapotunk a fent leírtak szerint pótolható. Ez valójában befolyásolja a futási időt:

• Külön feltételek - 40ms
• Többszörös és egyetlen feltétel - 22 ms

Tehát a két különböző feltételt használó opció végrehajtása valójában kétszer hosszabb ideig tart.

6. Következtetés

Láttuk, mi az elágazás-előrejelzés, és hogyan lehet hatással a programjainkra. Ez további eszközöket nyújthat nekünk az övünkben, hogy programjaink a lehető leghatékonyabbak legyenek.

Azonban, mint mindig, meg kell emlékeznünk a kódunk profilozásáról, mielőtt nagyobb változtatásokat végeznénk. Néha előfordulhat, hogy az elágazás-előrejelzés elősegítésére irányuló változtatások más módon többe kerülnek.

A cikk esetei a GitHub oldalon találhatók.