String.Join vs StringBuilder: ¿cuál es más rápido?

En una pregunta anterior sobre cómo formatear un formato double[][]a CSV, se sugirió que usar StringBuildersería más rápido que String.Join. ¿Es esto cierto?

Respuesta corta: depende.

Respuesta larga: si ya tiene una matriz de cadenas para concatenar juntas (con un delimitador), String.Joines la forma más rápida de hacerlo.

String.Joinpuede mirar a través de todas las cadenas para calcular la longitud exacta que necesita, luego ir de nuevo y copiar todos los datos. Esto significa que no habrá ninguna copia adicional involucrada. El único inconveniente es que tiene que pasar por las cadenas dos veces, lo que significa que potencialmente se agota la memoria caché más veces de las necesarias.

Si no tiene las cadenas como una matriz de antemano, probablemente sea más rápido de usar StringBuilder, pero habrá situaciones en las que no lo será. Si usa un StringBuildermedio para hacer muchas copias, entonces construir una matriz y luego llamar String.Joinpuede ser más rápido.

EDITAR: Esto es en términos de una sola llamada a String.Joinvs un montón de llamadas a StringBuilder.Append. En la pregunta original, teníamos dos niveles diferentes de String.Joinllamadas, por lo que cada una de las llamadas anidadas habría creado una cadena intermedia. En otras palabras, es aún más complejo y difícil de adivinar. Me sorprendería ver que cualquiera de las dos formas "gana" significativamente (en términos de complejidad) con datos típicos.

EDITAR: Cuando esté en casa, escribiré un punto de referencia que sea lo más doloroso posible StringBuilder. Básicamente, si tiene una matriz en la que cada elemento tiene aproximadamente el doble del tamaño del anterior y lo hace bien, debería poder forzar una copia para cada adición (de elementos, no del delimitador, aunque eso debe ser tenido en cuenta también). En ese punto, es casi tan malo como la simple concatenación de cadenas, pero String.Joinno tendrá problemas.

Aquí está mi plataforma de prueba, usando int[][]para simplificar; resultados primero:

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

(actualización de doubleresultados :)

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

(actualización de 2048 * 64 * 150)

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

y con OptimizeForTesting habilitado:

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

Tan rápido, pero no masivamente; rig (ejecutar en la consola, en modo de lanzamiento, etc.):

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();
        }
    }
}

No lo creo. Mirando a través de Reflector, la implementación de String.Joinparece muy optimizada. También tiene el beneficio adicional de conocer el tamaño total de la cadena que se creará de antemano, por lo que no necesita ninguna reasignación.

He creado dos métodos de prueba para compararlos:

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();
}

Ejecuté cada método 50 veces, pasando una matriz de tamaño [2048][64]. Hice esto para dos matrices; uno lleno de ceros y otro lleno de valores aleatorios. Obtuve los siguientes resultados en mi máquina (P4 3.0 GHz, un solo núcleo, sin HT, ejecutando el modo de liberación desde 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

Al aumentar el tamaño de la matriz a [2048][512], mientras se reduce el número de iteraciones a 10, obtuve los siguientes resultados:

// 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

Los resultados son repetibles (casi; con pequeñas fluctuaciones causadas por diferentes valores aleatorios). Aparentemente String.Joines un poco más rápido la mayor parte del tiempo (aunque por un margen muy pequeño).

Este es el código que usé para probar:

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));
    }
}

A menos que la diferencia del 1% se convierta en algo significativo en términos del tiempo que tarda todo el programa en ejecutarse, esto parece una microoptimización. Escribiría el código más legible / comprensible y no me preocuparía por la diferencia de rendimiento del 1%.

Atwood tenía una publicación relacionada con esto hace aproximadamente un mes:

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

si. Si hace más de un par de uniones, será mucho más rápido.

Cuando haces un string.join, el tiempo de ejecución tiene que:

1. Asignar memoria para la cadena resultante
2. copiar el contenido de la primera cadena al principio de la cadena de salida
3. copie el contenido de la segunda cadena al final de la cadena de salida.

Si hace dos combinaciones, tiene que copiar los datos dos veces, y así sucesivamente.

StringBuilder asigna un búfer con espacio de sobra, por lo que los datos se pueden agregar sin tener que copiar la cadena original. Como queda espacio en el búfer, la cadena adjunta se puede escribir directamente en el búfer. Luego, solo tiene que copiar toda la cadena una vez, al final.