IL Assembly: IF vs. Switch, wydajność

Dzisiaj kolejny temat, który bardzo często budzi wątpliwości. Część programistów preferuje zawsze IF, część z kolei switch. Niektórzy argumentują wybór wydajnością.

Zawsze powinniśmy kierować się czytelnością konkretnego kodu. W poście pokażę jak wygląda sprawa wydajności poprzez oczywiście IL Assembly. Sprawa jest dość skomplikowana i wiele zależy od konkretnych wartości jakie mamy w switch.

Zacznijmy od porównania prostego IF\Switch operującego na liczbach całkowitych:

static string TestSwitch(int value)
{
  switch (value)
  {
      case 0:
          return "zero";
      case 1:
          return "one";
      case 2:
          return "two";
      default:
          return "unknown";
  }
}
static string TestIf(int value)
{
  if (value == 0)
  {
      return "zero";
  }
  else if (value == 1)
  {
      return "one";
  }
  else if (value == 2)
  {
      return "two";
  }
  else
  {
      return "unknown";
  }
}

Obie metody robią dokładnie to samo – w zależności od przekazanego interger’a zwrócą konkretny string. Spróbujmy napisać prosty benchmark:

const int n = 10000000;

Stopwatch stopwatch1 = Stopwatch.StartNew();
for (int i = 0; i < n; i++)
    TestSwitch(i);

Console.WriteLine(stopwatch1.ElapsedTicks);

Stopwatch stopwatch = Stopwatch.StartNew();
for (int i = 0; i < n; i++)
    TestIf(i);

Console.WriteLine(stopwatch.ElapsedTicks);

Wynik będzie następujący:

image

Oznacza to, że switch jest trochę szybszy niż IF. Różnica jest na tyle jednak spora, że wypada zadać pytanie dlaczego? IL posiada różny zestaw instrukcji dla switch i IF. IF jest uzyskiwany za pomocą instrukcji skoków o których pisałem już wcześniej (m.in. BR).

Zajrzyjmy najpierw do IL asm dla IF:

IL_0000: ldarg.0
IL_0001: brtrue.s IL_0009

IL_0003: ldstr "zero"
IL_0008: ret

IL_0009: ldarg.0
IL_000a: ldc.i4.1
IL_000b: bne.un.s IL_0013

IL_000d: ldstr "one"
IL_0012: ret

IL_0013: ldarg.0
IL_0014: ldc.i4.2
IL_0015: bne.un.s IL_001d

IL_0017: ldstr "two"
IL_001c: ret

IL_001d: ldstr "unknown"
IL_0022: ret

Nie ma tutaj nic nowego – wszystko jest osiągnięte za pomocą warunkowych instrukcji skoków. Przyjrzyjmy się teraz switch:

IL_0000: ldarg.0
IL_0001: stloc.0
IL_0002: ldloc.0
IL_0003: switch (IL_0016, IL_001c, IL_0022)

IL_0014: br.s IL_0028

IL_0016: ldstr "zero"
IL_001b: ret

IL_001c: ldstr "one"
IL_0021: ret

IL_0022: ldstr "two"
IL_0027: ret

IL_0028: ldstr "unknown"
IL_002d: ret

Mamy tutaj specjalną instrukcję – switch. Jako parametry przyjmuje ona adresy konkretnych gałęzi. Jak dokonywane jest porównanie? To bardzo ciekawa sprawa…

W switch widzimy wyłącznie adresy gałęzi a nie warunki. switch bierze wartość ze stosu i jeśli jest ona równa zero wtedy wykonuje pierwszą gałąź, jeśli jest ona równa jeden to druga gałąź jest wykonywana itd.  Innymi słowy, wszystkie warunki zaczynają się od zero. Co się zatem stanie, gdy nasza logika ma inne warunki? Zmodyfikujmy przykład do:

switch (value)
{
 case 10:
     return "10";
 case 11:
     return "11";
 case 12:
     return "12";
 default:
     return "unknown";
}

IL:

IL_0000: ldarg.0
IL_0001: stloc.0
IL_0002: ldloc.0
IL_0003: ldc.i4.s 10
IL_0005: sub
IL_0006: switch (IL_0019, IL_001f, IL_0025)

IL_0017: br.s IL_002b

IL_0019: ldstr "10"
IL_001e: ret

IL_001f: ldstr "11"
IL_0024: ret

IL_0025: ldstr "12"
IL_002a: ret

IL_002b: ldstr "unknown"
IL_0030: ret

Sam switch wygląda tak samo. Różnica polega na tym, że odejmujemy od wartości liczbę 10, tak aby pierwsza gałąź zaczynała się wciąż od zero:

IL_0000: ldarg.0
IL_0001: stloc.0
IL_0002: ldloc.0
IL_0003: ldc.i4.s 10
IL_0005: sub

Innymi słowy zamiast porównywać wartość z 10,11,12, odejmujemy 10 i porównujemy z 0,1,2 – efekt końcowy dokładnie taki sam.

Kolejne pytanie, to co jeśli mamy wartości nieuporządkowane np. 10,12,14:

switch (value)
{
 case 10:
     return "10";
 case 12:
     return "12";
 case 14:
     return "14";
 default:
     return "unknown";
}

IL_0000: ldarg.0
IL_0001: stloc.0
IL_0002: ldloc.0
IL_0003: ldc.i4.s 10
IL_0005: sub
IL_0006: switch (IL_0021, IL_0033, IL_0027, IL_0033, IL_002d)

IL_001f: br.s IL_0033

IL_0021: ldstr "10"
IL_0026: ret

IL_0027: ldstr "12"
IL_002c: ret

IL_002d: ldstr "14"
IL_0032: ret

IL_0033: ldstr "unknown"
IL_0038: ret
} // end of method Progra

Znów odejmujemy 10, aby podstawą była wartość zero. Nasze warunki to 10,12,14 zatem  mamy przerwę między kolejnymi warunkami. Pamiętamy również, że instrukcja switch przyjmuje, że pierwszy warunek to “zero”, drugi “jeden” itd. Wygenerowany switch to:

IL_0006: switch (IL_0021, IL_0033, IL_0027, IL_0033, IL_002d)

Po prostu, kompilator wypełnił lukę adresem IL_0033, który wskazuje na klauzule default. Co jeśli mamy większe przerwy np.:

switch (value)
{
 case 100:
     return "100";
 case 200:
     return "200";
 case 300:
     return "300";
 default:
     return "unknown";
}

Zapełnianie switch adresami defualt byłoby mało wydajne – oznaczałoby to ponad 200 duplikatów. Zaglądając do IL przekonamy się, że kompilator wie co robi:


IL_0000: ldarg.0
IL_0001: stloc.0
IL_0002: ldloc.0
IL_0003: ldc.i4.s 100
IL_0005: beq.s IL_0019

IL_0007: ldloc.0
IL_0008: ldc.i4 200
IL_000d: beq.s IL_001f

IL_000f: ldloc.0
IL_0010: ldc.i4 300
IL_0015: beq.s IL_0025

IL_0017: br.s IL_002b

IL_0019: ldstr "100"
IL_001e: ret

IL_001f: ldstr "200"
IL_0024: ret

IL_0025: ldstr "300"
IL_002a: ret

IL_002b: ldstr "unknown"
IL_0030: ret

Switch został zamieniony do klasycznego IF’a. Nie będzie więc żadnej różnicy w wydajności. Dla wartości, które są dosyć daleko od siebie, użycie switch’a oznacza dokładnie to samo co IF.

Kompilator jest jednak bardzo sprytny. Załóżmy, że mamy następujący IF:

switch (value)
{
    case 100:
        return "100";
    case 101:
        return "101";
    case 102:
        return "102";

    case 300:
        return "300";
    case 301:
        return "301";
    case 302:
        return "302";

    case 400:
        return "400";
    case 401:
        return "401";
    case 402:
        return "402";
    default:
        return "unknown";
}

Wartości od siebie różnią się skrajnie. Możemy jednak dostrzec pewne klastry. Kompilator wykryje to i stworzy trzy klastry oparte na switch:

IL_0000: ldarg.0
IL_0001: stloc.0
IL_0002: ldloc.0
IL_0003: ldc.i4.s 100
IL_0005: sub
IL_0006: switch (IL_0049, IL_004f, IL_0055)

IL_0017: ldloc.0
IL_0018: ldc.i4 300
IL_001d: sub
IL_001e: switch (IL_005b, IL_0061, IL_0067)

IL_002f: ldloc.0
IL_0030: ldc.i4 400
IL_0035: sub
IL_0036: switch (IL_006d, IL_0073, IL_0079)

IL_0047: br.s IL_007f

IL_0049: ldstr "100"
IL_004e: ret

IL_004f: ldstr "200"
IL_0054: ret

IL_0055: ldstr "200"
IL_005a: ret

IL_005b: ldstr "300"
IL_0060: ret

IL_0061: ldstr "300"
IL_0066: ret

IL_0067: ldstr "300"
IL_006c: ret

IL_006d: ldstr "300"
IL_0072: ret

IL_0073: ldstr "300"
IL_0078: ret

IL_0079: ldstr "300"
IL_007e: ret

IL_007f: ldstr "unknown"
IL_0084: ret

Nie musimy wypełniać tutaj żadnej luki w switch, bo każdy klaster jest spójny.

Enumy na switch działają tak samo jak integer’y bo tak naprawdę niczym nie różnią się (enum to integer).

Przetwarzanie string’ów to jednak zupełnie inna historia. Przykład:

switch (text)
{
 case "1":
     return 1;
 case "2":
     return 2;
 case "3":
     return 3;

 default:
     return -1;
}

Wygenerowany IL:

IL_0000: ldarg.0
IL_0001: dup
IL_0002: stloc.0
IL_0003: brfalse.s IL_0034

IL_0005: ldloc.0
IL_0006: ldstr "1"
IL_000b: call bool [mscorlib]System.String::op_Equality(string, string)
IL_0010: brtrue.s IL_002e

IL_0012: ldloc.0
IL_0013: ldstr "2"
IL_0018: call bool [mscorlib]System.String::op_Equality(string, string)
IL_001d: brtrue.s IL_0030

IL_001f: ldloc.0
IL_0020: ldstr "3"
IL_0025: call bool [mscorlib]System.String::op_Equality(string, string)
IL_002a: brtrue.s IL_0032

IL_002c: br.s IL_0034

IL_002e: ldc.i4.1
IL_002f: ret

IL_0030: ldc.i4.2
IL_0031: ret

IL_0032: ldc.i4.3
IL_0033: ret

IL_0034: ldc.i4.m1
IL_0035: ret

Jak widzimy, kod niczym nie różni się od IF’ow – wydajność będzie taka sama. Switch dla napisów został skonwertowany do IF’ow. Sprawa jednak będzie wyglądać trochę inaczej, jeśli dołożymy kilka nowych warunków:

switch (text)
{
 case "1":
     return 1;
 case "2":
     return 2;
 case "3":
     return 3;
 case "4":
     return 4;
 case "5":
     return 5;
 case "6":
     return 6;
 case "7":
     return 7;
 case "8":
     return 8;

 default:
     return -1;
}

IL:

IL_0000: ldarg.0
IL_0001: dup
IL_0002: stloc.0
IL_0003: brfalse IL_00c7

IL_0008: volatile.
IL_000a: ldsfld class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32> '<PrivateImplementationDetails>{F94F7878-6940-44E5-A06D-C84605A56EC1}'::'$$method0x6000002-1'
IL_000f: brtrue.s IL_007e

IL_0011: ldc.i4.8
IL_0012: newobj instance void class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::.ctor(int32)
IL_0017: dup
IL_0018: ldstr "1"
IL_001d: ldc.i4.0
IL_001e: call instance void class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)
IL_0023: dup
IL_0024: ldstr "2"
IL_0029: ldc.i4.1
IL_002a: call instance void class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)
IL_002f: dup
IL_0030: ldstr "3"
IL_0035: ldc.i4.2
IL_0036: call instance void class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)
IL_003b: dup
IL_003c: ldstr "4"
IL_0041: ldc.i4.3
IL_0042: call instance void class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)
IL_0047: dup
IL_0048: ldstr "5"
IL_004d: ldc.i4.4
IL_004e: call instance void class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)
IL_0053: dup
IL_0054: ldstr "6"
IL_0059: ldc.i4.5
IL_005a: call instance void class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)
IL_005f: dup
IL_0060: ldstr "7"
IL_0065: ldc.i4.6
IL_0066: call instance void class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)
IL_006b: dup
IL_006c: ldstr "8"
IL_0071: ldc.i4.7
IL_0072: call instance void class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)
IL_0077: volatile.
IL_0079: stsfld class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32> '<PrivateImplementationDetails>{F94F7878-6940-44E5-A06D-C84605A56EC1}'::'$$method0x6000002-1'

IL_007e: volatile.
IL_0080: ldsfld class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32> '<PrivateImplementationDetails>{F94F7878-6940-44E5-A06D-C84605A56EC1}'::'$$method0x6000002-1'
IL_0085: ldloc.0
IL_0086: ldloca.s CS$0$0001
IL_0088: call instance bool class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::TryGetValue(!0, !1&)
IL_008d: brfalse.s IL_00c7

IL_008f: ldloc.1
IL_0090: switch (IL_00b7, IL_00b9, IL_00bb, IL_00bd, IL_00bf, IL_00c1, IL_00c3, IL_00c5)

IL_00b5: br.s IL_00c7

IL_00b7: ldc.i4.1
IL_00b8: ret

IL_00b9: ldc.i4.2
IL_00ba: ret

IL_00bb: ldc.i4.3
IL_00bc: ret

IL_00bd: ldc.i4.4
IL_00be: ret

IL_00bf: ldc.i4.5
IL_00c0: ret

IL_00c1: ldc.i4.6
IL_00c2: ret

IL_00c3: ldc.i4.7
IL_00c4: ret

IL_00c5: ldc.i4.8
IL_00c6: ret

IL_00c7: ldc.i4.m1
IL_00c8: ret

Jak widzimy, kod opiera swoje działanie na słowniku danych. Kluczem jest oczywiście warunek, a wartością indeks gałęzi. Następnie wywołujemy TryGetValue na słowniku, przekazując parametr wejściowy (string). Uzyskamy w ten sposób numer gałęzi. Potem wystarczy, że wywołamy switch (indeks gałęzi zaczyna się od zero) i jak w poprzednich przykładach, zwrócimy odpowiednie wartości:

IL_0090: switch (IL_00b7, IL_00ba, IL_00bc, IL_00be, IL_00c0, IL_00c2, IL_00c4, IL_00c6)

IL_00b5: br.s IL_00c8

IL_00b7: ldc.i4.s 1
IL_00b9: ret

IL_00ba: ldc.i4.2
IL_00bb: ret

IL_00bc: ldc.i4.3
IL_00bd: ret

IL_00be: ldc.i4.4
IL_00bf: ret

IL_00c0: ldc.i4.5
IL_00c1: ret

IL_00c2: ldc.i4.6
IL_00c3: ret

IL_00c4: ldc.i4.7
IL_00c5: ret

IL_00c6: ldc.i4.8
IL_00c7: ret

IL_00c8: ldc.i4.m1
IL_00c9: ret

Powyższy przykład można byłoby zoptymalizować ponieważ indeksy gałęzi pokrywają się z wartościami jakie chcemy zwrócić. W praktyce jednak te dwie rzeczy są kompletnie od siebie niezależne.

Na koniec pozostaje napisać kolejny benchmark, porównujący IF dla napisów oraz SWITCH, który wygeneruje wewnętrzny słownik:

class Program
{
   private static void Main(string[] args)
   {
       const int n = 10000000;

       Stopwatch stopwatch1 = Stopwatch.StartNew();
       for (int i = 0; i < n; i++)
           TestSwitch(i.ToString());
       Console.WriteLine(stopwatch1.ElapsedTicks);


       Stopwatch stopwatch = Stopwatch.StartNew();
       for (int i = 0; i < n; i++)
           TestIf(i.ToString());
       Console.WriteLine(stopwatch.ElapsedTicks);
   }
   static int TestSwitch(string text)
   {
       switch (text)
       {
           case "1":
               return 1;
           case "2":
               return 2;
           case "3":
               return 3;
           case "4":
               return 4;
           case "5":
               return 5;
           case "6":
               return 6;
           case "7":
               return 7;
           case "8":
               return 8;

           default:
               return -1;
       }
   }
   static int TestIf(string text)
   {
       if (text == "1")
       {
           return 1;
       }
       else if (text == "2")
       {
           return 2;
       }
       else if (text == "3")
       {
           return 3;
       }
       else if (text == "4")
       {
           return 4;
       }
       else if (text == "5")
       {
           return 5;
       }
       else if (text == "6")
       {
           return 6;
       }
       else if (text == "7")
       {
           return 7;
       }
       else if (text == "8")
       {
           return 8;
       }
       else
       {
           return -1;
       }
   }
}

Wynik:

image

Jak widać nie ma większej różnicy dla przedstawionych warunków. Jeśli mamy ich dużo więcej, wtedy i tak nie chcemy przecież korzystać z IF lub SWITCH. Przewaga SWITCH ma miejsce wyłącznie w bardzo specyficznych warunkach, w których wartości są bardzo blisko siebie (nie ma przerw). Klasycznym przykładem są ENUM’y, które zwykle zawierają sekwencyjne wartości.

One thought on “IL Assembly: IF vs. Switch, wydajność”

Leave a Reply

Your email address will not be published.