Switch über Strings

18. Juli 2012

Die Diskussion in einem früheren Beitrag zum Thema string interning hat mich dazu gebracht, etwas angestaubtes Wissen zu hinterfragen und zu aktualisieren: Was macht eigentlich eine switch Anweisung mit Strings?

Oder genauer: Finden hier String-Vergleiche statt? Wird das optimiert? Habe ich hier ein potentielles Performanceproblem?

 

switch basics

Bevor wir zu Strings kommen etwas Grundlagenwissen zu switch über Integers.

Das C# switch wird vom Compiler in ein MSIL switch übersetzt. Wesentlicher Unterschied ist, dass die IL-Variante den switch-Wert als 0-basierten Index in eine Tabelle von Sprungadressen verwendet. Der C# Compiler muss also die case labels in das dicht besetzte Intervall [0..N[ übersetzen. Ist das bereits der Fall – was gerade auch bei einfachen Enumerationen gegeben ist – dann hat der Compiler hiermit keine Arbeit:

   1: public enum Company

   2: {

   3:     SDX,

   4:     Apple,

   5:     Microsoft,

   6:     Google

   7: }

   8:  

   9: public static int EnumSwitch(Company company)

  10: {

  11:     switch (company)

  12:     {

  13:         case Company.SDX: Console.WriteLine(":-)"); break;

  14:         case Company.Apple: Console.WriteLine("iPhone"); break;

  15:         case Company.Microsoft: Console.WriteLine("Windows Phone"); break;

  16:         case Company.Google: Console.WriteLine("Android"); break;

  17:         default: Console.WriteLine("Festnetz..."); break;

  18:     }

  19:  

  20:     return 0;

  21: }

Wird vom Compiler zu:

   1: .method public hidebysig static int32 EnumSwitch(valuetype TestStringSwitch.Program/Company company) cil managed

   2: {

   3:     .maxstack 1

   4:     .locals init (

   5:         [0] valuetype TestStringSwitch.Program/Company CS$0$0000)

   6:     L_0000: ldarg.0 

   7:     L_0001: stloc.0 

   8:     L_0002: ldloc.0 

   9:     L_0003: switch (L_001a, L_0026, L_0032, L_003e)

  10:     L_0018: br.s L_004a

  11:     L_001a: ldstr ":-)"

  12:     L_001f: call void [mscorlib]System.Console::WriteLine(string)

  13:     L_0024: br.s L_0054

  14:     L_0026: ldstr "iPhone"

  15:     L_002b: call void [mscorlib]System.Console::WriteLine(string)

  16:     L_0030: br.s L_0054

  17:     L_0032: ldstr "Windows Phone"

  18:     L_0037: call void [mscorlib]System.Console::WriteLine(string)

  19:     L_003c: br.s L_0054

  20:     L_003e: ldstr "Android"

  21:     L_0043: call void [mscorlib]System.Console::WriteLine(string)

  22:     L_0048: br.s L_0054

  23:     L_004a: ldstr "Festnetz..."

  24:     L_004f: call void [mscorlib]System.Console::WriteLine(string)

  25:     L_0054: ldc.i4.0 

  26:     L_0055: ret 

  27: }

Treten Lücken auf, so füllt der Compiler diese mit Sprungadressen zum default-Zweig oder zerlegt das Intervall in Teilintervalle. Details nachzulesen hier.

 

switch über String – .NET 1.x

Strings sind keine Integers, also kann das eben beschriebene Verfahren so nicht funktionieren. In .NET 1.x kam hier string interning zum Einsatz:

Das Prinzip ist einfach: Da als case labels nur literale Strings zulässig sind, müssen diese interned sein. Und string.IsInterned liefert nicht etwa ein bool zurück, sondern die Referenz auf den String. Der vom C# Compiler generierte IL Code muss also zunächst mit der switch-Variable string.IsInterned befragen. Bekommt er hier null, dann kann er gleich zum default-Zweig springen; andernfalls bekommt er die Referenz auf den selben(!) String und kann die einzelnen case labels sehr effizient über object.ReferenceEquals überprüfen.

Nachzulesen in Applied Microsoft Windows .NET Framework Programming, Jeffrey Richter, 2002 – einen passenden Link habe ich leider nicht gefunden.

Nicht gerade vergleichbar dem switch über Integers, aber bei weitem keine Kaskade von String-Vergleichen… .

 

switch über String – .NET 2.0

Mit .NET 2.0 führte Microsoft CompilerRelaxations.NoStringInterning ein, womit das gerade beschriebene Verfahren nicht mehr tragfähig war. Seither fährt der Compiler zweigleisig:

Für wenige case labels (in meinen Experimenten bis zu 6 Werte) werden tatsächlich string.Equals Aufrufe verwendet. Beispiel:

   1: public static int ShortSwitch(string company)

   2: {

   3:     switch (company)

   4:     {

   5:         case "SDX AG": Console.WriteLine(":-)"); break;

   6:         case "Apple": Console.WriteLine("iPhone"); break;

   7:         case "Microsoft": Console.WriteLine("Windows Phone"); break;

   8:         case "Google": Console.WriteLine("Android"); break;

   9:         case null: Console.WriteLine("kein Anschluss..."); break;

  10:         default: Console.WriteLine("Festnetz..."); break;

  11:     }

  12:     return 0;

  13: }

Wird laut Reflector zu:

   1: public static int ShortSwitch(string company)

   2: {

   3:     string CS$0$0000 = company;

   4:     if (CS$0$0000 == null)

   5:     {

   6:         Console.WriteLine("kein Anschluss...");

   7:     }

   8:     else if (!(CS$0$0000 == "SDX AG"))

   9:     {

  10:         if (CS$0$0000 == "Apple")

  11:         {

  12:             Console.WriteLine("iPhone");

  13:         }

  14:         else if (CS$0$0000 == "Microsoft")

  15:         {

  16:             Console.WriteLine("Windows Phone");

  17:         }

  18:         else if (CS$0$0000 == "Google")

  19:         {

  20:             Console.WriteLine("Android");

  21:         }

  22:         else

  23:         {

  24:             Console.WriteLine("Festnetz...");

  25:         }

  26:     }

  27:     else

  28:     {

  29:         Console.WriteLine(":-)");

  30:     }

  31:     return 0;

  32: }

Die Art in der die if-Anweisungen geschachtelt sind variiert je nach der Verwendung von null als case label und dem default-Zweig. Grundsätzlich kann man aber sagen, dass die Vergleiche in der Reihenfolge auftauchen, in der sie auch im Code stehen.

Wer Bedenken bzgl. Performance hat, mag das im Hinterkopf behalten. Persönlich halte ich das aber für unsinnige Mikrooptimierung an der falschen Stelle. Falls sich hier tatsächlich ein Performanceproblem ergibt (objektiv, d.h. durch Messungen belegt!), dann ist eher die Verwendung von switch über Strings generell das Problem, nicht die Reihenfolge der case labels.

Daher würde ich in aller Regel der Wartbarkeit und Lesbarkeit den Vorzug geben und die case labels nach inhaltlichen Kriterien ordnen.

 

Wenn mehr case labels zum Einsatz kommen wird ein lokales Dictionary verwendet, das den String in einen Index übersetzt.

Das folgende Beispiel unterscheidet sich vom letzten nur durch ein zusätzliches case label:

   1: public static int LongSwitch(string company)

   2: {

   3:     switch (company)

   4:     {

   5:         case "SDX AG": Console.WriteLine(":-)"); break;

   6:         case "Apple": Console.WriteLine("iPhone"); break;

   7:         case "Microsoft": Console.WriteLine("Windows Phone"); break;

   8:         case "Google": Console.WriteLine("Android"); break;

   9:         case "Nokia": Console.WriteLine("Symbian"); break;

  10:         case null: Console.WriteLine("kein Anschluss..."); break;

  11:         default: Console.WriteLine("Festnetz..."); break;

  12:     }

  13:     return 0;

  14: }

Aber der generierte Code sieht deutlich anders aus:

   1: public static int LongSwitch(string company)

   2: {

   3:     string CS$0$0000 = company;

   4:     if (CS$0$0000 != null)

   5:     {

   6:         int CS$0$0001;

   7:         if (<PrivateImplementationDetails>{A83D8BBE-00B9-48D6-9018-AC3F6C8BDF0B}.$$method0x6000004-1.TryGetValue(CS$0$0000, out CS$0$0001))

   8:         {

   9:             switch (CS$0$0001)

  10:             {

  11:                 case 0:

  12:                     Console.WriteLine(":-)");

  13:                     goto Label_00D9;

  14:  

  15:                 case 1:

  16:                     Console.WriteLine("iPhone");

  17:                     goto Label_00D9;

  18:  

  19:                 case 2:

  20:                     Console.WriteLine("Windows Phone");

  21:                     goto Label_00D9;

  22:  

  23:                 case 3:

  24:                     Console.WriteLine("Android");

  25:                     goto Label_00D9;

  26:  

  27:                 case 4:

  28:                     Console.WriteLine("Symbian");

  29:                     goto Label_00D9;

  30:             }

  31:         }

  32:     }

  33:     else

  34:     {

  35:         Console.WriteLine("kein Anschluss...");

  36:         goto Label_00D9;

  37:     }

  38:     Console.WriteLine("Festnetz...");

  39: Label_00D9:

  40:     return 0;

  41: }

Was in der C#-Darstellung vom Reflector nicht angezeigt wird (wohl aber wenn man auf IL umschaltet) ist die Initialisierung des Dictionary’s: Hier werden die Strings der case labels als Key eingetragen, Value ist ein fortlaufender Index.

Dieses Vorgehen erfordert zwar den Aufbau eines zusätzlichen Dictionary’s je switch Anweisung, ist aber in der Konsequenz effizienter als die alte Variante über string interning:

  • Das Dictionary arbeitet nicht anders als der intern pool, enthält aber genau die für die spezielle switch Anweisung relevanten Einträge. Je nachdem wie “voll” der intern pool ist ein relevanter Gewinn.
  • Nach dem Lookup im Dictionary ist kein Referenz-Vergleich mehr notwendig, stattdessen steht ein numerischer Index zur Verfügung mit dem auch auf IL-Ebene die switch Anweisung verwendet werden. Ebenfalls ein Effizienzgewinn.

 

Optimierung?

Dass ein switch über Strings mit mehr Aufwand verbunden ist dürfte klar sein. Man findet deshalb gelegentlich den Hinweis, hier Optimierung zu betreiben, üblicherweise indem der String zunächst in ein semantisch gleichwertiges Enum geparst wird (etwa in diesem Kommentar).

Im Allgemeinen kann ich die Verwendung von Enums nur empfehlen. Aber nicht wegen eventueller Performanceeffekte beim switch, sondern wegen der zusätzlichen Typ-Sicherheit und der Unterstützung bei Intellisense und Refactoring. In diesen Fällen sollte dann aber auch durchgängig die Enumeration – nicht der String – im Programm verwendet werden. Typisches Beispiel ist ein Eintrag in den appSettings, der nur bestimmte Werte annehmen darf.

Bei Fällen in denen das nicht möglich ist und das Parsing nur wegen der switch Anweisung durchgeführt würde macht die genannte Optimierung hingegen keine großen Sinn. Im Gegenteil: Parsing eines Enums ist aufwendiger als ein Lookup in einem Dictionary!

 

Fazit

Gründe switch über Strings zu verwenden kann es viele geben. Möglicherweise sind die Texte zwar vorgegeben, entsprechen aber nicht der C# Syntax; möglicherweise muss man eine offene Menge an Werten unterstützen; oder strenge Typisierung behindert die Versionierungsstrategie.

In aller Regel kann man sich aber darauf verlassen, dass der Compiler gute Arbeit bei einer möglichst effizienten Umsetzung leistet.

In Fällen in denen ein Enum eine Option ist sollte man diese Möglichkeit trotzdem nutzen. Aber nicht um vorgeblichen Nachteilen des switch über Strings entgegenzuwirken, sondern weil die Vorteile der Typsicherheit einfach stechen – übrigens auch bezüglich switch über Integers.