Laden...

[Artikel] Strings verketten: Performance-Betrachtung

Erstellt von 0815Coder vor 16 Jahren Letzter Beitrag vor 15 Jahren 41.566 Views
0
0815Coder Themenstarter:in
767 Beiträge seit 2005
vor 16 Jahren
[Artikel] Strings verketten: Performance-Betrachtung

Dieser Artikel beschäftigt sich mit dem Zusammenfügen von Strings. Dieses an sich triviale Thema wird interessanter, wenn man die verschiedenen Möglichkeiten des Zusammenfügens von Strings unter dem Gesichtspunkt Performance betrachtet, und man genau wissen möchte, was denn die performanteste Art ist, die Strings zu verknüpfen.

Damit Ihr alles nachvollziehen könnt, habe ich mein Projekt angehängt. Die Solution ist zwar eine 2008er, wurde aber für Framework 2.0 kompiliert, sollte also praktisch überall laufen. Wer es selbst kompilieren möchte aber kein VS 2008 hat, kann die paar Klassen einfach selber in ein eigenes 2005er Projekt hängen.

Es gibt zunächst mehrere Situationen, in denen man Strings zusammenfügen will (ich verwende hier der Einfachheit halber immer den + operator):

  1. Alle Strings sind bereits zur Compilezeit bekannt.
    Beispiel:

**Anmerkung **(gfoidl, 23.12.2019): SQL-Befehle sollten nie direkt verkettet werden, sondern per [Artikelserie] SQL: Parameter von Befehlen umgesetzt werden!


string sql = "SELECT * " +
             "FROM MyTable " +
             "WHERE x=@x";

  1. Die Strings werden zur Laufzeit aneinandergehängt, sind aber "gleichzeitig" bekannt.
    Beispiel:

public class Person
{
	public string Firstname;
	public string Name;
}

public void Example_Method_2(IEnumerable<Person> persons)
{
	foreach (Person person in persons)
	{
		string output = person.Firstname + " " + person.Name;
		Console.WriteLine(output);
	}
}

  1. Weiters gibt es die Situation, dass die String erst "nach und nach" bekannt werden:
    Beispiel:

public void Example_Method_3(IEnumerable<Person> persons)
{
	string output = string.Empty;
	foreach (Person person in persons)
	{
		output = output + person.Firstname + " ";
		// oder ähnlich:
		// output += (person.Firstname + " ");
	}
	Console.WriteLine(output);
}

Situation 1 ist schnell behandelt. Wenn man sich aus der Klasse Examples die Example_Method_1 im Reflector ansieht, sieht man, dass der Compiler bereits einen einzigen string daraus gemacht hat. Schneller gehts nicht. Thema erledigt 🙂

Situation 2 ist schon interessanter. Wieder muss man hier den Reflector bemühen, um zu sehen, was passiert. Dazu sieht man sich die Methode "Examples.Example_Method_2" an, und wählt "IL" statt "C#" aus. Da sieht man dann, dass der Compiler folgendes daraus gemacht hat:

call string [mscorlib]System.String::Concat(string, string, string)

Für string.Concat gibt es ein paar Overloads, darunter einen mit params string[] welchen der Compiler verwendet, sobald 5 oder mehr strings auf diese Art zusammengefügt werden, Reflector zeigt das in der Methode "Examples.PlusIsConcat":

call string [mscorlib]System.String::Concat(string[])

Bei der Kurzform string += string verwendet der Compiler den Overload System.String::Concat(string, string).

Es gibt aber auch noch andere Möglichkeiten, die Strings in dieser Situation zusammenzufügen. Die (meiner Meinung nach) am Besten lesbarste ist


string output = string.Format("{0} {1}", person.FirstName, person.Name);

und dann gibts noch den StringBuilder:


StringBuilder builder = new StringBuilder();
builder.Append(person.FirstName);
builder.Append(" ");
builder.Append(person.Name");
string output = builder.ToString();

In Situation 3 fällt string.Format schon aus praktischen Gründen aus. Da bleibt rein theoretisch also nur string.Concat (also + operator) oder StringBuilder. string.Concat ist aber nur performanter als der StringBuilder, wenn die Einzelstrings eher lang und die Anzahl der Strings eher gering ist - mehr dazu später.

Sehen wir uns an, wie sich die Methoden in der Performance unterscheiden. Dazu habe ich den Test mit einer unterschiedlichen Anzahl von Strings und einer unterschiedlichen Stringlänge ausgeführt. Dazu muss man noch folgendes beachten:

  • Die Werte sind in Microsekunden und von Rechner zu Rechner unterschiedlich
  • Es ergeben sich bei jedem Durchlauf leicht andere Zeiten
  • Es kommt zwischendrinn zu Ausreissern bei denen der Test 10-100x so lange dauert wie im Schnitt. Ich nehme an das passiert, wenn der GarbageCollector reinpfuscht, diese Ausreisser hab ich nicht aufgenommen.

Methode string.Concat(string arg0, string arg1)
string += string
für x Strings x-1 mal aufgerufen


	   | Anzahl
Länge  |      5 |     20 |     100 |    1000
-------|--------|--------|---------|---------
     5 |    0,9 |    2,4 |    28,9 |  2370,9
    20 |    1,0 |    5,8 |    82,0 |  8121,3   
   100 |    1,3 |   18,4 |   631,0 | 70338,3     
  1000 |   11,6 |  181,2 |  8042,3 |   959 k
 10000 |  134,1 | 2900,6 | 95449,3 |    10 M

Methode string.Concat(params string[])
string = string + string + string + string + ...
1x aufgerufen, mit x Argumenten


	   | Anzahl
Länge  |      5 |     20 |     100 |    1000
-------|--------|--------|---------|---------
     5 |    0,8 |    1,2 |     3,0 |    29,8
    20 |    1,0 |    1,4 |     4,2 |    37,4
   100 |    1,1 |    2,5 |    10,6 |   114,7
  1000 |    5,0 |   17,7 |   116,2 |  2352,9
 10000 |   52,3 |  201,8 |  2154,0 | 22804,9

Methode StringBuilder:


	   | Anzahl
Länge  |      5 |     20 |     100 |    1000
-------|--------|--------|---------|---------
     5 |    1,0 |    1,8 |     4,5 |    41,2
    20 |    1,2 |    2,0 |     7,6 |    83,5
   100 |    1,7 |    6,5 |    25,6 |   225,3
  1000 |   12,9 |   49,0 |   220,8 |  3011,6
 10000 |  115,5 |  480,9 |  3789,5 | 38181,2

Methode string.Format


	   | Anzahl
Länge  |      5 |     20 |     100 |    1000
-------|--------|--------|---------|---------
     5 |    1,3 |    2,5 |     7,4 |    72,8
    20 |    1,4 |    4,8 |     9,3 |    88,1
   100 |    2,5 |    7,5 |    35,5 |   233,9
  1000 |   13,3 |   53,2 |   249,2 |  4154,4
 10000 |  118,2 |  704,1 |  5010,4 | 46657,6

Aus diesen Tabellen ergeben sich ein paar interessante Fakten:

  1. string.Concat(params string[])oder string = string + string + string + string + ...
    ist immer die schnellste Methode, wenn beim Aufruf alle strings bekannt sind (Situation 2). Den Grund dafür findet man wieder mal im Reflector: Die Methode legt einmalig den gesamten Speicher an, den die Strings zusammen einnehmen werden (da alle bekannt sind, ist das nicht weiter schwierig), und kopiert danach die einzelnen Strings rein. Der StringBuilder ist deshalb langsamer, weil jedesmal, wenn der angelegte Buffer zu klein wird, ein neuer angelegt wird, und dann der bisher erstellte String umkopiert werden muss.

  2. Methode string.Concat(string arg0, string arg1) oder string += string:
    ist fast immer die langsamste Methode. Ausgenommen es sind nur sehr wenige strings, dann kann sie sogar etwas schneller sein als StringBuilder. In den allermeisten Fällen ist dieser geringe Gewinn allerdings irrelevant. Diese Art Strings zu verketten wird schon bei einigen Strings langsam und bei vielen Strings extrem langsam. Im Gegensatz zum StringBuilder bzw. String.Format, bei welchen der Aufwand linear steigt, steigt der Aufwand hier quadratisch. Der Grund dafür ist, das nicht tatsächlich an einen string angehängt wird. Stattdessen wird ein Speicherbereich angelegt der groß genug für das Ergebnis ist, und beide Strings werden dann hintereinander in diesen kopiert. Wenn man damit 100 Strings aneinander hängt, würde 99 mal Speicher angelegt werden, und der erste string 99 mal kopiert werden. Das Speicher anlegen und kopieren kostet dabei die meiste Zeit, und kann mit dem StringBuilder oder string.Format vermieden werden.

  3. StringBuilder:
    bietet die beste Performance wenns darum geht, eine unbekannte Anzahl an Strings zu verketten. Die Ausnahme bestätigt die Regel: wenn man weniger als 5-10 Strings verketten will, kann string.Concat(string arg0, string arg1) dennoch schneller sein, allerdings nur unwesentlich. Der Punkt, an dem sich die Performance der beiden Methoden kreuzt, ist bei gleichbleibender Anzahl von der Länge abhängig. Da in Realworld-Szenarien aber die die Längen unbekannt sind, lässt sich hier kein exakter Wert bestimmen.

  4. string.Format():
    ist zwischen 25% und 50% langsamer als StringBuilder, was man ihr aber nachsehen kann, wenn man bedenkt, dass man damit ja viel mehr machen kann als nur Strings aneinander hängen. Ich verwende die Methode aber dennoch gern, wenn ihre langsamere Performance keine Rolle spielt, weil sie wesentlich besser lesbar ist.

Zusammenfassung
Um beste Performance zu erreichen muss man also zunächst herausfinden, ob alle Strings gleichzeitig bekannt sind oder ob sich nacheinander bekannt werden.

Im Fall ersten Fall nimmt man string.Concat - oder den +operator.
Im zweiten Fall den StringBuilder, bis auf die beschriebenen Ausnahmen, die aber verhältnismässig selten sind.

Wenn Performance keine Rolle spielt kann man für sich selbst entscheiden, ob man string.Format verwenden will, um die Lesbarkeit zu steigern.

mfg,
0815Coder

PS: Im Zuge der Ermittlungen bin ich auf eine weitere performante Möglichkeit für Situation 3 gekommen: Anstatt den StringBuilder zu verwenden, und ihm alles der Reihe nach anzuhängen, ist es scheinbar schneller, wenn man die strings in eine List<string> reinhängt, und dann string.Concat(theList.ToArray()) aufruft. Den Beweis bleib ich erstmal schuldig.

loop:
btst #6,$bfe001
bne.s loop
rts

0
0815Coder Themenstarter:in
767 Beiträge seit 2005
vor 15 Jahren

Hab das Programm zum Messen grad stark erweitert:

  • Bissl was am UI rumgepfuscht 🙂

  • Es wird auch mitgetracked, wieviele GarbageCollections während der Tests durchgeführt werden - das gibt einen Hinweis auf Speicherverbrauch / Zahl der Objekterstellungen

  • neuer Test:
    Der Test verwendet eine List<string> zum sammeln der Strings die aneinander gehängt werden sollen, und fügt diese dann mit string.Concat(list.ToArray) zusammen. Das ist speziell bei Strings ab ca 5 Zeichen schneller als mit einem StringBuilder.
    Grund dafür ist der folgende: wird der Speicher beim StringBuilder zu klein, dann wird der gesamte bisher erstellte String in den neuen Speicher umkopiert. Bei der List<string> werden nur Referenzen gesammelt und wenn die nächste nicht mehr Platz hat, werden auch nur die Referenzen umkopiert.

loop:
btst #6,$bfe001
bne.s loop
rts

U
1.688 Beiträge seit 2007
vor 15 Jahren

Man kann auch den StringBuilder mit einer Kapazität erzeugen, die ungefähr der Endgröße entspricht bzw. die einfach genügend groß ist. Dann wird das Umkopieren wegfallen.

0
0815Coder Themenstarter:in
767 Beiträge seit 2005
vor 15 Jahren

sicher. der ganze Artikel geht aber davon aus, dass die Endgröße nicht bekannt oder schätzbar ist.

loop:
btst #6,$bfe001
bne.s loop
rts

104 Beiträge seit 2004
vor 15 Jahren

Schön mal zu sehen wie lange Stringverknüpfungen dauern. 🙂
Interessant wäre vielleicht noch die Rechenleistung der "Testmaschine".

Allerdings denke ich (wie ujr schon anmerkte), dass über die Startkapazität des StringBuilders noch einiges an Performance rauszuholen ist.

Wenn man den StringBuilder über den parameterlosen Konstruktor initialisiert, wie es in dem Performancetest gemacht wurde, wird automatisch eine Kapazität von 16 gewählt. Wird die Kapazität überschritten so verdoppelt sich diese (16, 32, 64, 128, ...). Bei jeder Verdopplung wird also der komplette String umkopiert wodurch die relativ schlechte Performance zu erklären ist.

Wenn du einen String bekannter Größe verwendest (wie es bei dem Test der Methode Concat der Fall ist) is es also nur Fair dem Stringbuilder eine InitialKapazität mitzugeben. Andernfalls kann man die Zeiten meiner Meinung nach nicht vergleichen.

Sind die zu verknüpfenen Strings erst zur Laufzeit bekannt (so wie es in praxsisnahen Scenarien meist der Fall ist), wird der StringBuilder vermutlich schon für eine kleine Anzahl von Strings schneller sein.

Schaut mal im IRC vorbei:
Server: irc.euirc.net
Channel: #C#

49.485 Beiträge seit 2005
vor 15 Jahren

Hallo Tachyon,

Interessant wäre vielleicht noch die Rechenleistung der "Testmaschine".

es kommt sowieso kaum auf die absoluten Laufzeiten an, sondern quasi nur um das Verhältnis zwischen denselben.

Wird die Kapazität überschritten so verdoppelt sich diese (16, 32, 64, 128, ...). Bei jeder Verdopplung wird also der komplette String umkopiert wodurch die relativ schlechte Performance zu erklären ist.

Man kann hier grob von Faktor 2 ausgehen, um den die StringBuilder-Operationen langsamer sind, wenn man die Endgröße nicht kennt und deshalb mit der Startgröße beginnt und so die Verdoppelungen inkaufnehmen muss.

herbivore