String.Join vs. StringBuilder: che è più veloce?
https://stackoverflow.com/questions/585860
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
In un domanda precedente sulla formattazione di un double[][] a formato CSV, è stato suggerito che l'uso di StringBuilder sarebbe più veloce di String.Join. È vero?
Soluzione
Risposta breve:. Dipende
Risposta lunga: se si dispone già di un array di stringhe per concatenare insieme (con un delimitatore), String.Join è il modo più veloce di farlo
String.Join può guardare attraverso tutte le stringhe di capire l'esatta lunghezza di cui ha bisogno, poi andare di nuovo e copiare tutti i dati. Questo significa che ci saranno non copia in più coinvolti. solo inconveniente è che essa deve passare attraverso le corde due volte, che significa potenzialmente soffia memoria cache più volte del necessario.
Se non avere le stringhe come un array in anticipo, è probabilmente più veloce da usare StringBuilder - ma ci saranno situazioni in cui non lo è. Se si utilizza un StringBuilder significa fare un sacco di copie, quindi la costruzione di un array e quindi chiamando String.Join potrebbe essere più veloce.
EDIT: Questo è in termini di una singola chiamata a String.Join vs un gruppo di chiamate a StringBuilder.Append. Nella domanda iniziale, abbiamo avuto due diversi livelli di chiamate String.Join, in modo che ogni delle chiamate annidate avrebbe creato una stringa intermedio. In altre parole, è ancora più complesso e più difficile da indovinare. Sarei sorpreso di vedere in entrambi i casi "vincere" in modo significativo (in termini di complessità) con i dati caratteristici.
EDIT: Quando sono a casa, scriverò un punto di riferimento che è doloroso come forse per StringBuilder. In pratica se si dispone di un array in cui ogni elemento è circa il doppio di quella precedente, e si ottiene solo a destra, si dovrebbe essere in grado di forzare una copia per ogni append (di elementi, non di delimitatore, anche se questo ha bisogno di essere prese in considerazione anche). A quel punto è quasi così male come semplice concatenazione di stringhe - ma String.Join non avrà problemi
Altri suggerimenti
Ecco il mio banco di prova, usando int[][] per semplicità; Primi risultati:
Join: 9420ms (chk: 210710000
OneBuilder: 9021ms (chk: 210710000
(aggiornamento per risultati double:)
Join: 11635ms (chk: 210710000
OneBuilder: 11385ms (chk: 210710000
(aggiornamento ri 2048 * 64 * 150)
Join: 11620ms (chk: 206409600
OneBuilder: 11132ms (chk: 206409600
e con OptimizeForTesting abilitato:
Join: 11180ms (chk: 206409600
OneBuilder: 10784ms (chk: 206409600
Quindi più veloce, ma non in maniera massiccia così; rig (gestito dalla console, nella modalità di rilascio, ecc):
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();
}
}
}
Non penso così. Guardando attraverso riflettore, l'attuazione di String.Join sembra molto ottimizzato. Essa ha anche il vantaggio di conoscere la dimensione totale della stringa da creare in anticipo, in modo che non ha bisogno di alcuna riallocazione.
Ho creato due metodi di prova per confrontarli:
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();
}
Ho eseguito ogni metodo 50 volte, passando in un array di dimensione [2048][64]. Ho fatto questo per due array; uno riempito con zeri e un'altra riempito con valori casuali. Ho ottenuto i seguenti risultati sulla mia macchina (P4 3.0 GHz, single-core, senza HT, in esecuzione in modalità di uscita da 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
L'aumento delle dimensioni della matrice per [2048][512], mentre diminuisce il numero di iterazioni da 10 mi ha fatto i seguenti risultati:
// 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
I risultati sono ripetibili (quasi; con piccole fluttuazioni causate da diversi valori casuali). A quanto pare String.Join è un po 'più veloce la maggior parte del tempo (anche se con un margine molto piccolo).
Questo è il codice che ho usato per il test:
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 meno che la differenza di 1% si trasforma in qualcosa di significativo in termini di tempo l'intero programma necessario per eseguire, questo appare come micro-ottimizzazione. Mi piacerebbe scrivere il codice che è il più leggibile / comprensibile e non preoccuparsi per la differenza 1% delle prestazioni.
Atwood aveva una specie di messaggio relativo a questo circa un mese fa:
Sì. Se fate più di un paio di join, sarà molto più veloce.
Quando si esegue uno string.join, il runtime deve:
- allocare memoria per la stringa risultante
- copiare il contenuto della prima stringa all'inizio della stringa di output
- copiare il contenuto della seconda stringa alla fine della stringa di output.
Se fate due si unisce, si deve copiare i dati due volte, e così via.
StringBuilder alloca un buffer con lo spazio per risparmiare, quindi i dati possono essere aggiunti senza dover copiare la stringa originale. Poiché v'è spazio che rimane nel buffer, la stringa allegata può essere scritto nel buffer direttamente. Poi si deve solo copiare l'intera stringa una volta, alla fine.
