if vs. switch

Néhány nappal ezelőtt egy kollegám említette, hogy vannak fejlesztők, akik vallási vitát képesek folytatni arról, hogy mikor melyik vezérlési szerkezetet érdemes használni. Mivel furcsa volt ez nekem, rákerestem a google-ön, és tényleg: elég sok emberben felmerül ez a kérdés. Alapvetően két részre lehet osztani a témát:

  • Melyik vezérlési szerkezet átláthatóbb.
  • Melyik vezérlési szerkezet rendelkezik nagyobb teljesítménnyel.

Az átláthatósággal kapcsolatban nem szeretnék semmit mondani, mivel elég szubjektív területről van szó. A teljesítménnyel kapcsolatban viszont vizsgálódhatunk egy kicsit, bár nyilván itt is nanoszekundumokat fogunk csak találni.

Az egyik leggyakrabban használt érv az if mellett, hogy ha a fejlesztő tudja, hogy jellemzően mi a vizsgált adat értéke, akkor ezt egy előre helyezett if-fel gyorsabban le tudja kezelni, mint ha switch-et használna. Érthetőbben, erről van szó:

Optimalizáció a jellemző paraméter ismeretében:

enum Szin { Piros, Sarga, Kek, Zold, Fekete }

static void Main(string[] args)
{
    var szin = Szin.Sarga;

    if (szin == Szin.Sarga)
    {
        Console.WriteLine("Sárga");
    }
    else if (szin == Szin.Zold)
    {
        Console.WriteLine("Zöld");
    }
    else
    {
        Console.WriteLine("Valamilyen szín");
    }
} // Main()

Natúr switch:

enum Szin { Piros, Sarga, Kek, Zold, Fekete }

static void Main(string[] args)
{
    var szin = Szin.Sarga;

    switch (szin)
    {
        case Szin.Sarga:
            Console.WriteLine("Sárga");
            break;

        case Szin.Zold:
            Console.WriteLine("Zöld");
            break;

        default:
            Console.WriteLine("Valamilyen szín");
            break;
    } // switch
} // Main()

A fenti két kód nem használható teljesítménymérésre, de kis átalakítás és egy tízmilliárdos ciklus után már mérhető a különbség: az if overhead-je 5 másodperc, míg a switch-é 20, azaz az if ebben az esetben négyszer gyorsabb. Másik oldalról ez 15 nanosec iterációnként.

A fenti teszt ugyanakkor egy speciális helyzetet vizsgál. Az a “gond”, hogy a példában megadott Szin felsorolt típus elemei a default értékeket veszik fel, amelyek sorban lesznek kiosztva. Ez azt jelenti, hogy a Piros a háttérben 0 értékkel szerepel a programban, a Sarga 1-gyel, és így tovább. Ezt kihasználva a jitter a switch megvalósítására egy táblázatot használ (az implementációs részleteket lásd a cikk vége felé), amely segítségével konstans időben ki tudja számolni, hogy melyik case ágra kell neki ugrani. Emiatt teljesen mindegy neki a case label-ek sorrendje, teljesen mindegy mi a vizsgált érték, ugyanannyi ideig tart a kód futása.

Ellenben, ha a lehetséges értékek nagyon széthúznak, a fent említett táblázatot nem tudja elkészíteni a jitter (ismét, implementációs részletek később), emiatt várhatólag lassabb lesz a futás. Próbáljuk hát ki a következő enum-mal:

Szin { Piros = 100, Sarga = 200, Kek = 300, Zold = 400, Fekete = 500 }

A futásidők a módosított enum-mal if esetében a korábbi 5 másodperc, a switch esetében pedig szintén 5 másodperc. Igen, valamiért a kód felgyorsult, pedig személy szerint én egyáltalán nem ezt vártam. Ennyit a mikro-optimalizációról.

Mi van a háttérben?

A cikk megírása előtt megvizsgáltam pár esetet, hogy mikor hogyan jár el a jitter a switch fordítása közben. A tapasztalatok alapján próbáltam felépíteni a cikket, és azt vártam, hogy a második példa lassabb lesz az elsőhöz képest (és valójában azt is vártam, hogy az első példa switch-e alig lesz lassabb, mint az if). A cikk írásához viszont egy rövidített példát használtam, ami így utólag szerencse, mivel nagyszerűen rámutat, hogy nehéz támaszkodni a compiler/jitter ismeretére, pontosabban nem lehet eléggé ismerni a compiler-t/jitter-t.

Ugyanakkor csak az érdekesség kedvéért érdemes megnézni pár esetet, hogyan jár el a jitter. Nézzük az alábbi példát, aminek a jellemzője, hogy a Szin minden értékéhez tartozik egy case:

enum Szin { Piros, Sarga, Kek, Zold, Fekete}

switch (szin)
{
    case Szin.Sarga:
        counter++;
        break;

    case Szin.Zold:
        counter++;
        break;

    case Szin.Piros:
        counter++;
        break;

    case Szin.Kek:
        counter++;
        break;

    case Szin.Fekete:
        counter++;
        break;

    default:
        counter++;
        break;
} // switch

A fordított kód a következő:

Ebben az esetben a jitter egy táblázatot generált, amiben összerendelte a Szin értékeit a case ágak címeivel. A Szin.Sarga értéke például 1, a táblázat második sora (ha nem nullától számolunk) a case Szin.Sarga címére ugrik. Sajnos a Visual Studio disassembly ablak a címeket átkonvertálja a függvény belépési pontját nullának véve, emiatt a táblázat értékeit nehezen rendeljük szemmel össze a program utasítások címeivel. Az EIP regiszterből azonban látszik, hogy kb jó értékek vannak a táblázatban – de ehhez figyelembe kell venni, hogy az intel little-endian architektúrája miatt a byte-ok fordítva szerepelnek (hátulról kell őket olvasni). Mivel a szin változó, amit most az EBX regiszter hordoz, 1-es értéket tárol, a vezérlés a 0x0196d21e címre adódik át.

Ezek alapján könnyű elfogadni, hogy nem igazán számít hány értéket vesz fel egy enum, illetve hány case ágat tettünk egy switch-be, konstans idő alatt találja meg a vezérlés a megfelelő case ágat.

Hogy lássuk miért gyorsabb az if, nézzük meg a kódját:

// edi regiszterben van a szin változó:
if (szin == Szin.Sarga)
00000041  cmp         edi,1      // 1 = Szin.Sarga
00000044  jne         00000049   // nem sárga, ugorj...
{
  counter++;
00000046  inc         esi  
00000047  jmp         00000052 
}
else if (szin == Szin.Zold)
00000049  cmp         edi,3 
0000004c  jne         00000051 
{
  counter++;
0000004e  inc         esi  
0000004f  jmp         00000052 
}
else
{
  counter++;
00000051  inc         esi  
}

A program felépítése egyszerű. Látszik, hogy az előbb vizsgált switch, amely 8 sec időt produkál, egy cmp/jae/jmp hármast futtat. Az if esetében, ha bejön a számításunk, és tényleg legtöbbször sárga értékkel futunk rá, akkor egy cmp/jne páros fut le, 5 sec idővel. Nagyjából tehát kijön az utasítások számából az időbeli különbség, de itt megint eszünkbe kell jusson, hogy egy gépi utasításról van szó egy 2-3 gigaherccel daráló processzoron. Amíg a plusz jmp lefut, a fény tíz centit képes megtenni, az idegsejtjeinkben az ingerület pedig esetleg néhány atomot (ez utóbbit nem számoltam ki).

Most nézzük meg, miért volt annyira lassú az alábbi kód:

switch (szin)
{
    case Szin.Sarga:
        counter++;
        break;

    case Szin.Zold:
        counter++;
        break;

    default:
        counter++;
        break;
} // switch

Ebből a következőt fordította:

Itt a Szin értékeinek csak egy részét vettük fel, Láthatólag a jitter próbál optimalizálni. Csak a Sárga/Kék/Zöld értékekre épít táblázatot, azaz az 1-3 intervallumra. Mivel a 2-es értéket (a kék-et) nem írtuk fel, a táblázat ehhez tartozó bejegyzése a default label-re mutat. Ahhoz, hogy a táblázat bejegyzéseit szinkronba hozza a lehetséges értékekkel, csökkent egyet a switch paraméterének értékén, ami egy plusz gépi utasítást igényel. A kód így összességében csak egy DEC utasítással több, ezért nehéz megérteni, miért fut ennyivel lassabban (8 sec-ről 20-secre nő a tesztciklus futásideje, miután levontuk az üres ciklus overhead-jét). Valószínű ennek a kérdésnek a megválaszolásához az intel processzorokról kellene többet tudnunk, másik oldalról újabb példa, hogy mik állhatnak az optimalizációk útjába. Ha egy szimpla gépi utasítás ekkora hatással lehet a futásidőkre, akkor nehéz kiszámolni milyen hatásokkal jár a C# szinten való trükközés, és ez számomra még egy érv ezek felesleges volta mellett.

Érdemes még megnézni azt az esetet, amikor a Szin mögött levő értékek nagyon szórnak, azaz lehetetlen a jitternek (vagy ha nem is lehetetlen, nagyon pazarló) táblázatot építeni. Ehhez a következő definíciót használjuk:

Szin { Piros = 100, Sarga = 200, Kek = 300, Zold = 400, Fekete = 500 }
...
switch (szin)
{
    case Szin.Sarga:
        counter++;
        break;

    case Szin.Zold:
        counter++;
        break;

    default:
        counter++;
        break;
} // switch

Ebben az esetben a generált kód a következő:

switch (szin)
0000004d  cmp         ebx,0C8h 
00000053  je          0000005F 
00000055  cmp         ebx,190h 
0000005b  je          00000062 
0000005d  jmp         00000065 
{
    case Szin.Sarga:
        counter++;
0000005f  inc         edi  
00000060  jmp         00000066 

    case Szin.Zold:
        counter++;
00000062  inc         edi  
00000063  jmp         00000066 

    default:
        counter++;
00000065  inc         edi  
        for (int i = 0; i < 1000000; i++)
00000066  inc         esi  
00000067  cmp         esi,0F4240h 
0000006d  jl          00000047 
    for (int n = 0; n < 10000; n++)
0000006f  inc         dword ptr [ebp-10h] 
00000072  cmp         dword ptr [ebp-10h],2710h 
00000079  jl          00000045 
        break;
} // switch

Ismerős? Igen, ez szinte egy az egyben az if-es szerkezet kódja, és ez megmagyarázza, hogy miért ugyanaz a futásidő. Azonban nem általános szabály, hogy széthúzó értékekkel a jitter a switch-t egy if-es szerkezetté alakítja át. Nézzük meg mi történik ekkor:

enum Szin { Piros = 100, Sarga = 200, Kek = 300, Zold = 400, Fekete = 500,
            Lila = 1100, Narancs = 1200, Cian = 1300, Feher = 1400, Ezust = 1500 }
...
switch (szin)
{
    case Szin.Sarga:
        counter++;
        break;

    case Szin.Zold:
        counter++;
        break;

// ... az összes label ...

    default:
        counter++;
        break;
} // switch

A futásidő itt 15 sec, a generált kód pedig a következő:

Mit látunk? A kb feleződő ugrálásokról beugorhat a bináris keresés, és itt pontosan ez történik. Lényegében egy “inline bináris keresőtáblát” látunk, aminek a végén meg lesz, hogy az érték alapján melyik címkére kell ugrani. Ez lehetővé teszi, hogy sok érték esetén is pár lépésen belül meglegyen a keresett címke.

Még ezeken felül is tud 1-2 trükköt a jitter, például képes két keresőtáblát készíteni, ha az úgy optimális, illetve nyilván vannak helyzetek, amire még rá sem jöttem. Az utolsó dolog, amit megnézünk, hogy mi történik string-ek esetében.

A C# nyelv lehetővé teszi, hogy a case címkéjeként stringeket használjunk. Ez nem természetes, a C nyelv pl ilyet nem tud, de közvetlen a CLI/CLR sem támogatja. A switch vezérlési szerkezet ugyanis megjelenik közvetlenül az IL nyelvben, tehát a .NET “gépikódja” ezt alapból tudja – csak épp nem stringekkel. A C# fordító viszont tud egy trükköt, és ennek köszönhetően tudunk switch-ben stringeket használni. Hogy mi történik, meg tudjuk nézni egy egyszerű programon keresztül:

var s = "répa";
var counter = 0;

switch (s)
{
    case "retek":
        counter++;
        break;

    case "mogyoro":
        counter++;
        break;

    default:
        counter++;
        break;
} // switch

Mivel a C# fordító munkájára vagyunk kíváncsiak, az IL kódot fogjuk vizsgálni. A kódtól nem kell megijedni, kommentben ott van, hogy mit csinálnak az egyes részek:

  .locals init ([0] string s,
           [1] int32 counter,
           [2] string CS$0$0000)

  // s = répa
  IL_0000:  ldstr      bytearray (72 00 E9 00 70 00 61 00 ) // répa
  IL_0005:  stloc.0

  // counter = 0
  IL_0006:  ldc.i4.0
  IL_0007:  stloc.1

  // A fordító készített egy ideiglenes változót (CS$0$0000),
  // most ennek az értéke felveszi s változó értékét
  IL_0008:  ldloc.0      // Azon felül, hogy s-et másoljuk CS$0$0000-be
  IL_0009:  dup          // szükség van az értékre az evaluation stackon, ezért
  IL_000a:  stloc.2      // van a dup. Az alábbi brfalse-nak kell

  // s == null ? Ugrás a default-ra
  IL_000b:  brfalse.s  IL_0033

  // if (s == "retek"), ugrás a retek címkére
  IL_000d:  ldloc.2
  IL_000e:  ldstr      "retek"
  IL_0013:  call       bool [mscorlib]System.String::op_Equality(string,string)
  IL_0018:  brtrue.s   IL_0029

  // if (s == "mogyoro"), ugrás a mogyoro címkére
  IL_001a:  ldloc.2
  IL_001b:  ldstr      "mogyoro"
  IL_0020:  call       bool [mscorlib]System.String::op_Equality(string,string)
  IL_0025:  brtrue.s   IL_002e

  // Ha semmi nem jött be, ugrás a defaultra
  IL_0027:  br.s       IL_0033

  // case "retek":
  // counter += 1
  IL_0029:  ldloc.1     // counter az evaluation stackre
  IL_002a:  ldc.i4.1    // konstans 1 az evaluation stackre
  IL_002b:  add         // stack két elemét összeadja, eredmény a veremre
  IL_002c:  stloc.1     // evaluation stack teteje a counter-be
  IL_002d:  ret         // Main()-ben vagyunk, switch után nem volt semmi, return

  // case ""mogyoro"":
  // counter += 1
  IL_002e:  ldloc.1
  IL_002f:  ldc.i4.1
  IL_0030:  add
  IL_0031:  stloc.1
  IL_0032:  ret

  // default:
  IL_0033:  ldloc.1
  IL_0034:  ldc.i4.1
  IL_0035:  add
  IL_0036:  stloc.1
  IL_0037:  ret

Azt látjuk tehát, hogy egyfajta if-es szerkezetté alakul át a kódunk. Sok case label esetében azonban ez nem lenne túl hatékony, mivel a string összehasonlítás viszonylag drága művelet ahhoz, hogy lineárisan keresgéljük a megfelelő címkét. Emiatt sok címke esetén a C# compiler bevet egy másik trükköt. Nem másolom ide a sok címkét tartalmazó switch-t, mert felesleges. Nem kísérleteztem ki, hogy pontosan mennyi címke kell, de 6-7 körül a fordító stratégiát vált. Íme a generált kód:

 .locals init ([0] string s,
           [1] int32 counter,
           [2] string CS$0$0000,
           [3] int32 CS$0$0001)

  // s = répa
  IL_0000:  ldstr      bytearray (72 00 E9 00 70 00 61 00 ) // répa
  IL_0005:  stloc.0

  // counter = 0
  IL_0006:  ldc.i4.0
  IL_0007:  stloc.1


  // A fordító készített egy ideiglenes változót (CS$0$0000),
  // most ennek az értéke felveszi s változó értékét
  IL_0008:  ldloc.0      // Azon felül, hogy s-et másoljuk CS$0$0000-be
  IL_0009:  dup          // szükség van az értékre az evaluation stackon, ezért
  IL_000a:  stloc.2      // van a dup. Az alábbi brfalse-nak kell

  // s == null ? Ugrás a default-ra
  IL_000b:  brfalse    IL_00d2

  // A fordító trükkje az, hogy generált egy osztályt egy statikus mezővel, aminek
  // a típusa egy Dictionary<string,int32>. Ez a mező kerül most az evaluation
  // stack-re:
  IL_0010:  volatile.
  IL_0012:  ldsfld     class Dictionary`2<string,int32> rondaclassname::rondafield

  // Ha a mező értéke nem null, akkor már egyszer inicializálták a dictionary-t, ugorás
  // az inicializáló kód mögé
  IL_0017:  brtrue.s   IL_007a

  // Első használat, a dictionary inicializálása. Az fog történni, hogy egy növekvő
  // számlálóval minden label belekerül a dictionary-be. Első lépésben a dictionary
  // létrehozása. Mivel 7 címkét adtam meg, a dictionary ehhez a mérethez lesz
  // létrehozva:
  IL_0019:  ldc.i4.7
  IL_001a:  newobj     instance void class Dictionary`2<string,int32>::.ctor(int32)

  // A létrehozott új dictionary referenciája most az evaluation stacken van.
  // Ez az érték egy tagfüggvény hívása után lekerülne a veremről, viszont én
  // sokszor akarok hívni. Emiatt mindig duplikálni kell a verem tetején levő
  // referenciát:
  IL_001f:  dup

  // Az első paraméter a veremre, ez címke értéke (string referencia lesz):
  IL_0020:  ldstr      "retek"

  // A "retek"-hez rendel szám, a counter értéke most még 0, mivel ez az első:
  IL_0025:  ldc.i4.0

  // "retek"-0 páros felvétele a dictionary-be
  IL_0026:  call       instance void class Dictionary`2<string,int32>::Add(!0,!1)

  // Az alábbi kód már csak ismétlődik minden címkére:
  IL_002b:  dup
  IL_002c:  ldstr      "mogyoro"
  IL_0031:  ldc.i4.1
  IL_0032:  call       instance void class Dictionary`2<string,int32>::Add(!0,!1)

// sok-sok címke a dictionary-be

  // A dup-ok miatt még van egy dictionary referencia a vermen, ezt most eltárolni az
  // ehhez a switch-hez létrehozott statikus fieldbe:
  IL_0073:  volatile.
  IL_0075:  stsfld     class Dictionary`2<string,int32> rondaclassname::rondafield

  // Ide ugrunk, ha már egyszer megtörtént az inicializáció. A switch-hez létrehozott
  // statikus mezőből a dictionary referenciája a veremre:
  IL_007a:  volatile.
  IL_007c:  ldsfld     class Dictionary`2<string,int32> rondaclassname::rondafield

  // Az s változóra switch-eltünk, de ez már a CS$0$0000 ideiglenes
  // változóban van, ami a local variable array 2-ik rekesze 
  IL_0081:  ldloc.2

  // kimenő paramétert használ a TryGetValue, emiatt a CS$0$0001
  // címét kérjük a veremre
  IL_0082:  ldloca.s   CS$0$0001

  // TryGetValue hívás, megkapjuk, hogy van-e mappelt érték az adott stringhez
  IL_0084:  call       instance bool class Dictionary`2<string,int32>::TryGetValue(!0,!1&)

  // Ha nem kaptunk értéket, ugrani a default ágra (azt a kódot
  // letöröltem a végéről, de ugyanaz mint a korábbi listán
  IL_0089:  brfalse.s  IL_00d2

  // A TryGetValue közvetlen az LVA 3-ik elemébe írta az eredményt, ez kell
  // most a veremre
  IL_008b:  ldloc.3

  // Hagyományos switch, ez innen már úgy működik, mint ha int-et használtunk
  // volna.
  IL_008c:  switch     ( 
                        IL_00af,
                        IL_00b4,
                        IL_00b9,
                        IL_00be,
                        IL_00c3,
                        IL_00c8,
                        IL_00cd)
  // ugrás a defaultra, ha nem volt a keresett érték
  // a táblázatban
  IL_00ad:  br.s       IL_00d2

  // counter++, ugyanaz mint az előző listán
  IL_00af:  ldloc.1
  IL_00b0:  ldc.i4.1
  IL_00b1:  add
  IL_00b2:  stloc.1
  IL_00b3:  ret
  IL_00b4:  ldloc.1
  IL_00b5:  ldc.i4.1
  IL_00b6:  add
  IL_00b7:  stloc.1
  IL_00b8:  ret

// a labelek mögötti, fentihez hasonló kód

Konklúzió

A mikro-optimalizálás egy újabb negatív példájával találkozhattunk. Kiderült, hogy bizonyos esetekben pár nanoszekundumot lehet spórolni, de ez százmilliós/milliárdos iterációkban hoz inkább csak hasznot. A kezdő példa négyszeres teljesítménynövekedése csalóka, mivel láttuk, hogy az egyetlen egy plusz gépi utasításból ered. A nagy különbség egy része abból adódik, hogy a nagyon lekopasztott ciklusban csak néhány gépi utasítás szerepel, és ekkor egy plusz utasítás is arányaiban nagy hatással van. Ilyen kiélezett helyzettel valós kódban csak nagyon ritkán lehet találkozni. A másik, és nagyobb komponense a sebességromlásnak valószínűleg valamilyen processzorfüggő dolog volt. Ennek kinyomozása mélyebb ismereteket igényelne, és elképzelhető, hogy egy másik processzoron, vagy a kódba egy-két további utasítást elhelyezve ez eltűnne (vagy a többi teszt hozzáromlana)

Összességében tehát az derül ki – legalábbis számomra – hogy az if/switch cserélgetésével nem érdemes trükközni.

  1. #1 by flata on 2011. August 24. - 01:07

    MythBuster rovat🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: