String.Join Leistungsproblem in C#

Question

Ich habe eine Frage untersucht, die mir vorgestellt wurde: Wie schreibe ich eine Funktion, die eine Zeichenfolge als Eingabe verwendet und eine Zeichenfolge mit Leerzeichen zwischen den Zeichen zurückgibt. Die Funktion soll geschrieben werden, um die Leistung zu optimieren, wenn sie tausende Male pro Sekunde aufgerufen wird.

1. Ich weiß, dass .net eine Funktion hat String.Join genannt, auf die ich als Separator in dem Raum Charakter passieren kann mit der Original-Zeichenkette zusammen.

2. Abgesehen von der Verwendung von String.Join kann ich die Klasse StringBuilder verwenden, um Leerzeichen nach jedem Zeichen anzuhängen.

3. Eine andere Möglichkeit, diese Aufgabe auszuführen, besteht darin, ein Zeichenarray mit 2 * n-1 Zeichen zu deklarieren (Sie müssen n-1 Zeichen für die Leerzeichen hinzufügen). Das Zeichenarray kann in eine Schleife gefüllt und dann an die Zeichenfolge constructor übergeben werden.

Ich habe einige .net-Code geschrieben, dass jeder dieser Algorithmen eine Millionen mal jeweils mit dem Parameter "Hello, World" und Maßnahmen läuft, wie lange dauert es auszuführen. Methode (3) ist viel, viel schneller als (1) oder (2).

Ich weiß, dass (3) sollte sehr schnell sein, weil es vermeidet, zusätzliche String-Verweise zu erstellen, um Müll gesammelt werden, aber es scheint mir, dass eine integrierte. NET-Funktion wie String.Join sollte gute Leistung erbringen. Warum ist die Verwendung von String.Join so viel langsamer als die Arbeit mit der Hand?

public static class TestClass 
{ 
    // 491 milliseconds for 1 million iterations 
    public static string Space1(string s) 
    {    
     return string.Join(" ", s.AsEnumerable()); 
    } 

    //190 milliseconds for 1 million iterations 
    public static string Space2(string s) 
    { 
     if (s.Length < 2) 
      return s; 
     StringBuilder sb = new StringBuilder(); 
     sb.Append(s[0]); 
     for (int i = 1; i < s.Length; i++) 
     { 
      sb.Append(' '); 
      sb.Append(s[i]); 
     }    
     return sb.ToString(); 
    } 

    // 50 milliseconds for 1 million iterations 
    public static string Space3(string s) 
    { 
     if (s.Length < 2) 
      return s; 
     char[] array = new char[s.Length * 2 - 1]; 
     array[0] = s[0]; 
     for (int i = 1; i < s.Length; i++) 
     { 
      array[2*i-1] = ' '; 
      array[2*i] = s[i]; 
     } 
     return new string(array); 
    } 

Update: Ich habe mein Projekt auf „Release“ Modus und aktualisiert meine verstrichenen Zeiten in der Frage entsprechend.

Answer 1

Warum ist String.Join so viel langsamer als die Arbeit mit der Hand?

Der Grund String.Join langsamer in diesem Fall ist ist, dass Sie einen Algorithmus schreiben können, die vorherige Kenntnis der genauen Art Ihrer IEnumerable<T> hat.

String.Join<T>(string, IEnumerable<T>) (die Überladung, die Sie verwenden), auf der anderen Seite, soll mit jedem beliebigen aufzählbaren Typ arbeiten, was bedeutet, dass es nicht auf die richtige Größe vorbelegen kann. In diesem Fall ist es Handel Flexibilität für pure Leistung und Geschwindigkeit.

Viele der Framework-Methoden behandeln bestimmte Fälle, in denen Dinge beschleunigt werden könnten, indem sie nach Bedingungen suchen, aber dies wird normalerweise nur dann gemacht, wenn dieser "Spezialfall" üblich ist.

In diesem Fall erstellen Sie effektiv einen Edge-Fall, in dem eine handgeschriebene Routine schneller ist, aber es ist kein üblicher Anwendungsfall von String.Join. Da Sie genau wissen, was im Voraus erforderlich ist, können Sie in diesem Fall den gesamten für ein flexibles Design erforderlichen Overhead vermeiden, indem Sie ein Array mit genau der richtigen Größe vorab zuweisen und die Ergebnisse manuell erstellen.

Sie finden, dass im Allgemeinen zu finden, ist es oft möglich ein Verfahren zu schreiben, die aus einigen der Rahmen für spezifische Daten Eingaberoutinen wird ausführen. Dies ist üblich, da die Framework-Routinen mit jedem Dataset arbeiten müssen, was bedeutet, dass Sie nicht für ein bestimmtes Eingabeszenario optimieren können.

Answer 2

Da Sie nicht den Release-Build verwenden (der Optimierungen sollten standardmäßig aktiviert sein) und/oder Sie über Visual Studio debuggen, wird der JITer daran gehindert, viele Optimierungen vorzunehmen. Aus diesem Grund bekommen Sie kein gutes Bild davon, wie lange jede Operation wirklich dauert. Sobald Sie die Optimierungen hinzugefügt haben, können Sie sich ein Bild von dem machen, was vor sich geht.

Es ist auch wichtig, dass Sie im Visual Studio nicht debuggen. Gehen Sie zum Ordner bin/release und doppelklicken Sie auf die ausführbare Datei ganz außerhalb von Visual Studio.

Answer 3

Ihr String.Join Beispiel funktioniert auf einem IEnumerable<char>. Das Aufzählen einer IEnumerable<T> mit foreach ist oft langsamer als die Ausführung einer for-Schleife (das hängt vom Sammlertyp und anderen Umständen ab, wie Dave Black in einem Kommentar darauf hingewiesen hat). Auch wenn Join einen StringBuilder verwendet, muss der interne Puffer des StringBuilder mehrmals erhöht werden, da die Anzahl der anzuhängenden Elemente nicht im Voraus bekannt ist.

Answer 4

Die schlechte Leistung kommt nicht von String.Join, sondern von der Art, wie Sie mit jedem Zeichen umgehen. Da in diesem Fall die Zeichen einzeln behandelt werden müssen, erzeugt Ihre erste Methode viel mehr Zwischenzeichenfolgen, und die zweite Methode leidet unter zwei Methodenaufrufen für jedes Zeichen: .Append. Ihre dritte Methode enthält nicht viele Zwischenzeichenfolgen oder Methodenaufrufe und das ist der Grund, warum Ihre dritte Methode am schnellsten ist.

Answer 5

Wenn Sie eine IEnumerable an String.Join übergeben haben, hat es keine Ahnung, wie viel Speicher zugewiesen werden muss. Ich ordnet einen Teil des Speichers zu, ändert die Größe, wenn es nicht ausreicht, und wiederholt den Vorgang, bis genügend Speicher für alle Zeichenfolgen verfügbar ist.

Die Array-Version ist schneller, weil wir die Menge an Speicher gut voraus bekannt kennen.

Auch bitte nicht, dass, wenn Sie die 1. Version ausführen, GC möglicherweise aufgetreten sind.

Answer 6

In Ihrer ersten Methode verwenden Sie die Überladung von String.Join, die auf einer Enumerable ausgeführt wird, die erfordert, dass die Methode die Zeichen der Zeichenfolge mithilfe eines Enumerators führt. Intern verwendet dies eine StringBuilder, da die genaue Anzahl der Zeichen unbekannt ist.

Haben Sie in Betracht gezogen, die String.Join-Überladung zu verwenden, die stattdessen eine Zeichenfolge (oder ein Zeichenfolgenarray) verwendet? Diese Implementierung ermöglicht die Verwendung eines Puffers fester Länge (ähnlich Ihrer dritten Methode) zusammen mit einigen internen unsicheren Zeichenfolgenoperationen für die Geschwindigkeit. Der Anruf würde sich ändern in - String.Join(" ", s); Ohne die Beinarbeit tatsächlich zu messen, würde ich erwarten, dass dies gleich oder schneller ist als Ihr dritter Ansatz.

Answer 7

Sehr interessant zu lesen.Ich wollte erwähnen, dass

string.Join(" ", s.ToCharArray()) 

Performance Seite etwas über

string.Join(" ", s.AsEnumerable()) 

Hier ist ein Test verbessert ich mal vergleichen verwendet:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Diagnostics; 
using System.Text; 
using System.Web.UI; 
public partial class Test : Page 
{ 
    protected void Page_Load(object sender, EventArgs e) 
    { 
     var rankings = new Dictionary<string, double>(); 
     var test = new string('1', 1000000); 
     Response.Write("Testing space separating a string with length: " + test.Length + ". Numbers are total milliseconds.<br/><br/>"); 
     var timer = Stopwatch.StartNew(); 
     Space1(test); 
     timer.Stop(); 
     rankings.Add("string.join", timer.Elapsed.TotalMilliseconds); 
     timer = Stopwatch.StartNew(); 
     Space2(test); 
     timer.Stop(); 
     rankings.Add("stringbuilder", timer.Elapsed.TotalMilliseconds); 
     timer = Stopwatch.StartNew(); 
     Space3(test); 
     timer.Stop(); 
     rankings.Add("char array", timer.Elapsed.TotalMilliseconds); 
     var list = rankings.ToList(); 
     list.Sort((x, y) => x.Value.CompareTo(y.Value)); 
     foreach (var rank in list) 
     { 
      Response.Write(rank + "<br/>"); 
     } 
    } 
    private static string Space1(string s) 
    { 
     //return string.Join(" ", s.AsEnumerable()); 
     return string.Join(" ", s.ToCharArray()); 
    } 
    private static string Space2(string s) 
    { 
     if (s.Length < 2) 
     { 
      return s; 
     } 
     var sb = new StringBuilder(); 
     sb.Append(s[0]); 
     for (var i = 1; i < s.Length; i++) 
     { 
      sb.Append(' '); 
      sb.Append(s[i]); 
     } 
     return sb.ToString(); 
    } 
    private static string Space3(string s) 
    { 
     if (s.Length < 2) 
     { 
      return s; 
     } 
     var array = new char[s.Length * 2 - 1]; 
     array[0] = s[0]; 
     for (var i = 1; i < s.Length; i++) 
     { 
      array[2 * i - 1] = ' '; 
      array[2 * i] = s[i]; 
     } 
     return new string(array); 
    } 
} 

Beispielausgabe (fast immer die gleiche Bestellung):

Testzwischenraum, der eine Zeichenfolge mit der Länge trennt: 1000000. Die Zahlen sind die gesamten Millisekunden.

[char-Array, 14,7902]

[String, 25,6643]

[string.join, 61,7402]