String.Join vs. StringBuilder: Was ist schneller?

In einer früheren Frage zur Formatierung eines double[][]CSV-Formats wurde vorgeschlagen, dass die Verwendung StringBuilderschneller als ist String.Join. Ist das wahr?

Kurze Antwort: es kommt darauf an.

Lange Antwort: Wenn Sie bereits eine Reihe von Zeichenfolgen zum Verketten haben (mit einem Trennzeichen), String.Joinist dies der schnellste Weg.

String.JoinSie können alle Zeichenfolgen durchsuchen, um die genaue Länge zu ermitteln. Kopieren Sie dann erneut alle Daten. Dies bedeutet, dass kein zusätzliches Kopieren erforderlich ist. Der einzige Nachteil ist, dass die Zeichenfolgen zweimal durchlaufen werden müssen, was bedeutet, dass der Speichercache möglicherweise öfter als erforderlich gelöscht wird.

Wenn Sie die Zeichenfolgen vorher nicht als Array haben, ist die Verwendung wahrscheinlich schneller StringBuilder- aber es wird Situationen geben, in denen dies nicht der Fall ist. Wenn Sie ein StringBuilderMittel verwenden, um viele, viele Kopien zu String.Joinerstellen , kann das Erstellen eines Arrays und das anschließende Aufrufen möglicherweise schneller sein.

BEARBEITEN: Dies ist in Bezug auf einen einzelnen Anruf an String.Joingegenüber einer Reihe von Anrufen an StringBuilder.Append. In der ursprünglichen Frage hatten wir zwei verschiedene Aufrufebenen String.Join, sodass jeder der verschachtelten Aufrufe eine Zwischenzeichenfolge erstellt hätte. Mit anderen Worten, es ist noch komplexer und schwieriger zu erraten. Ich wäre überrascht zu sehen, dass beide Arten mit typischen Daten signifikant (in Bezug auf die Komplexität) "gewinnen".

EDIT: Wenn ich zu Hause bin, schreibe ich einen Benchmark auf, der so schmerzhaft wie möglich ist StringBuilder. Wenn Sie ein Array haben, in dem jedes Element etwa doppelt so groß ist wie das vorherige, und Sie es genau richtig machen, sollten Sie in der Lage sein, eine Kopie für jedes Anhängen zu erzwingen (von Elementen, nicht vom Trennzeichen, obwohl dies erforderlich ist auch berücksichtigt werden). Zu diesem Zeitpunkt ist es fast so schlimm wie eine einfache Verkettung von Zeichenfolgen - aber es String.Joinwird keine Probleme geben.

Hier ist mein Prüfstand, der der int[][]Einfachheit halber verwendet wird. Ergebnisse zuerst:

Join: 9420ms (chk: 210710000
OneBuilder: 9021ms (chk: 210710000

(Update für doubleErgebnisse :)

Join: 11635ms (chk: 210710000
OneBuilder: 11385ms (chk: 210710000

(Update zu 2048 * 64 * 150)

Join: 11620ms (chk: 206409600
OneBuilder: 11132ms (chk: 206409600

und mit aktiviertem OptimizeForTesting:

Join: 11180ms (chk: 206409600
OneBuilder: 10784ms (chk: 206409600

So schneller, aber nicht massiv; Rig (an der Konsole, im Release-Modus usw. ausführen):

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;

namespace ConsoleApplication2
{
    class Program
    {
        static void Collect()
        {
            GC.Collect(GC.MaxGeneration, GCCollectionMode.Forced);
            GC.WaitForPendingFinalizers();
            GC.Collect(GC.MaxGeneration, GCCollectionMode.Forced);
            GC.WaitForPendingFinalizers();
        }
        static void Main(string[] args)
        {
            const int ROWS = 500, COLS = 20, LOOPS = 2000;
            int[][] data = new int[ROWS][];
            Random rand = new Random(123456);
            for (int row = 0; row < ROWS; row++)
            {
                int[] cells = new int[COLS];
                for (int col = 0; col < COLS; col++)
                {
                    cells[col] = rand.Next();
                }
                data[row] = cells;
            }
            Collect();
            int chksum = 0;
            Stopwatch watch = Stopwatch.StartNew();
            for (int i = 0; i < LOOPS; i++)
            {
                chksum += Join(data).Length;
            }
            watch.Stop();
            Console.WriteLine("Join: {0}ms (chk: {1}", watch.ElapsedMilliseconds, chksum);

            Collect();
            chksum = 0;
            watch = Stopwatch.StartNew();
            for (int i = 0; i < LOOPS; i++)
            {
                chksum += OneBuilder(data).Length;
            }
            watch.Stop();
            Console.WriteLine("OneBuilder: {0}ms (chk: {1}", watch.ElapsedMilliseconds, chksum);

            Console.WriteLine("done");
            Console.ReadLine();
        }
        public static string Join(int[][] array)
        {
            return String.Join(Environment.NewLine,
                    Array.ConvertAll(array,
                      row => String.Join(",",
                        Array.ConvertAll(row, x => x.ToString()))));
        }
        public static string OneBuilder(IEnumerable<int[]> source)
        {
            StringBuilder sb = new StringBuilder();
            bool firstRow = true;
            foreach (var row in source)
            {
                if (firstRow)
                {
                    firstRow = false;
                }
                else
                {
                    sb.AppendLine();
                }
                if (row.Length > 0)
                {
                    sb.Append(row[0]);
                    for (int i = 1; i < row.Length; i++)
                    {
                        sb.Append(',').Append(row[i]);
                    }
                }
            }
            return sb.ToString();
        }
    }
}

Das glaube ich nicht. Durch Reflector String.Joinsieht die Implementierung von sehr optimiert aus. Es hat auch den zusätzlichen Vorteil, dass die Gesamtgröße der zu erstellenden Zeichenfolge im Voraus bekannt ist, sodass keine Neuzuweisung erforderlich ist.

Ich habe zwei Testmethoden erstellt, um sie zu vergleichen:

public static string TestStringJoin(double[][] array)
{
    return String.Join(Environment.NewLine,
        Array.ConvertAll(array,
            row => String.Join(",",
                       Array.ConvertAll(row, x => x.ToString()))));
}

public static string TestStringBuilder(double[][] source)
{
    // based on Marc Gravell's code

    StringBuilder sb = new StringBuilder();
    foreach (var row in source)
    {
        if (row.Length > 0)
        {
            sb.Append(row[0]);
            for (int i = 1; i < row.Length; i++)
            {
                sb.Append(',').Append(row[i]);
            }
        }
    }
    return sb.ToString();
}

Ich habe jede Methode 50 Mal ausgeführt und dabei ein Array von Größen übergeben [2048][64]. Ich habe das für zwei Arrays gemacht; eine mit Nullen und eine mit zufälligen Werten. Ich habe die folgenden Ergebnisse auf meinem Computer erhalten (P4 3,0 GHz, Single-Core, kein HT, mit Release-Modus von CMD):

// with zeros:
TestStringJoin    took 00:00:02.2755280
TestStringBuilder took 00:00:02.3536041

// with random values:
TestStringJoin    took 00:00:05.6412147
TestStringBuilder took 00:00:05.8394650

Durch Erhöhen der Größe des Arrays auf [2048][512]und Verringern der Anzahl der Iterationen auf 10 wurden die folgenden Ergebnisse erzielt:

// with zeros:
TestStringJoin    took 00:00:03.7146628
TestStringBuilder took 00:00:03.8886978

// with random values:
TestStringJoin    took 00:00:09.4991765
TestStringBuilder took 00:00:09.3033365

Die Ergebnisse sind wiederholbar (fast; mit kleinen Schwankungen, die durch unterschiedliche Zufallswerte verursacht werden). Anscheinend String.Joinist es die meiste Zeit etwas schneller (wenn auch mit sehr geringem Abstand).

Dies ist der Code, den ich zum Testen verwendet habe:

const int Iterations = 50;
const int Rows = 2048;
const int Cols = 64; // 512

static void Main()
{
    OptimizeForTesting(); // set process priority to RealTime

    // test 1: zeros
    double[][] array = new double[Rows][];
    for (int i = 0; i < array.Length; ++i)
        array[i] = new double[Cols];

    CompareMethods(array);

    // test 2: random values
    Random random = new Random();
    double[] template = new double[Cols];
    for (int i = 0; i < template.Length; ++i)
        template[i] = random.NextDouble();

    for (int i = 0; i < array.Length; ++i)
        array[i] = template;

    CompareMethods(array);
}

static void CompareMethods(double[][] array)
{
    Stopwatch stopwatch = Stopwatch.StartNew();
    for (int i = 0; i < Iterations; ++i)
        TestStringJoin(array);
    stopwatch.Stop();
    Console.WriteLine("TestStringJoin    took " + stopwatch.Elapsed);

    stopwatch.Reset(); stopwatch.Start();
    for (int i = 0; i < Iterations; ++i)
        TestStringBuilder(array);
    stopwatch.Stop();
    Console.WriteLine("TestStringBuilder took " + stopwatch.Elapsed);

}

static void OptimizeForTesting()
{
    Thread.CurrentThread.Priority = ThreadPriority.Highest;
    Process currentProcess = Process.GetCurrentProcess();
    currentProcess.PriorityClass = ProcessPriorityClass.RealTime;
    if (Environment.ProcessorCount > 1) {
        // use last core only
        currentProcess.ProcessorAffinity
            = new IntPtr(1 << (Environment.ProcessorCount - 1));
    }
}

Sofern sich der Unterschied von 1% nicht in Bezug auf die Zeit, die das gesamte Programm benötigt, um etwas Wesentliches zu ändern, sieht dies nach einer Mikrooptimierung aus. Ich würde den Code schreiben, der am besten lesbar / verständlich ist, und mich nicht um den Leistungsunterschied von 1% sorgen.

Atwood hatte vor ungefähr einem Monat einen ähnlichen Beitrag dazu:

http://www.codinghorror.com/blog/archives/001218.html

Ja. Wenn Sie mehr als ein paar Joins ausführen, ist dies viel schneller.

Wenn Sie eine string.join ausführen, muss die Laufzeit:

1. Ordnen Sie Speicher für die resultierende Zeichenfolge zu
2. Kopieren Sie den Inhalt der ersten Zeichenfolge an den Anfang der Ausgabezeichenfolge
3. Kopieren Sie den Inhalt der zweiten Zeichenfolge an das Ende der Ausgabezeichenfolge.

Wenn Sie zwei Verknüpfungen durchführen, müssen die Daten zweimal kopiert werden, und so weiter.

StringBuilder weist einen Puffer mit freiem Speicherplatz zu, sodass Daten angehängt werden können, ohne dass die ursprüngliche Zeichenfolge kopiert werden muss. Da im Puffer noch Platz vorhanden ist, kann die angehängte Zeichenfolge direkt in den Puffer geschrieben werden. Dann muss es am Ende nur noch einmal die gesamte Zeichenfolge kopieren.