String.Join vs. StringBuilder: que é mais rápido?
-
06-09-2019 - |
Pergunta
Em um anterior pergunta sobre a formatação de um double[][]
para formato CSV, foi sugerido que o uso de StringBuilder
seria mais rápido do que String.Join
. Isso é verdade?
Solução
Resposta curta:. Isso depende
Long resposta:. se você já tem uma matriz de strings para concatenar juntos (com um delimitador), String.Join
é a maneira mais rápida de fazê-lo
String.Join
pode olhar através de todas as cordas para trabalhar fora o comprimento exato que precisa, em seguida, ir novamente e copiar todos os dados. Isso significa que não será não cópia extra envolvido. O única desvantagem é que ele tem que passar as cordas duas vezes, o que significa potencialmente soprando o cache de memória mais vezes do que o necessário.
Se você não tem as cordas como uma matriz de antemão, é provavelmente mais rápido para uso StringBuilder
- mas haverá situações em que não é. Se estiver usando um meio StringBuilder
fazendo lotes e lotes de cópias, em seguida, construir uma matriz e, em seguida, chamando String.Join
pode muito bem ser mais rápido.
EDIT: Este é, em termos de uma única chamada para String.Join
vs um monte de chamadas para StringBuilder.Append
. Na pergunta original, tivemos dois níveis diferentes de chamadas String.Join
, então cada uma das chamadas aninhadas teria criado uma cadeia intermediária. Em outras palavras, é ainda mais complexo e mais difícil de adivinhar. Eu ficaria surpreso de ver uma ou outra maneira "ganhar" significativamente (em termos de complexidade) com dados típicos.
EDIT: Quando eu estou em casa, eu vou escrever-se um ponto de referência que é tão doloroso como possivelmente para StringBuilder
. Basicamente, se você tiver uma matriz onde cada elemento é o dobro do tamanho do anterior, e você obtê-lo apenas para a direita, você deve ser capaz de forçar uma cópia para cada acréscimo (de elementos, não do delimitador, embora que precisa ser tidos em conta também). Nesse ponto, é quase tão ruim quanto simples concatenação -. Mas String.Join
não terá problemas
Outras dicas
Aqui está o meu equipamento de teste, usando int[][]
pela simplicidade; resultados do primeiro:
Join: 9420ms (chk: 210710000
OneBuilder: 9021ms (chk: 210710000
(atualização para resultados double
:)
Join: 11635ms (chk: 210710000
OneBuilder: 11385ms (chk: 210710000
(update re 2048 * 64 * 150)
Join: 11620ms (chk: 206409600
OneBuilder: 11132ms (chk: 206409600
e com OptimizeForTesting ativado:
Join: 11180ms (chk: 206409600
OneBuilder: 10784ms (chk: 206409600
Assim, mais rápido, mas não maciçamente assim; rig (executado na consola, no modo de versão, 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();
}
}
}
Eu não penso assim. Olhando através do refletor, a implementação de olhares String.Join
muito otimizado. Ele também tem a vantagem de saber o tamanho total da cadeia a ser criado com antecedência, por isso não precisa de qualquer realocação.
Eu criei dois métodos de ensaio para compará-los:
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();
}
corri cada método 50 vezes, passando em uma matriz de tamanho [2048][64]
. Eu fiz isso por duas matrizes; um preenchido com zeros e outro cheio com valores aleatórios. Eu tenho os seguintes resultados na minha máquina (P4 3.0 GHz, single-core, não HT, que funcionam de modo lançamento de 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
O aumento do tamanho da matriz para [2048][512]
, ao diminuir o número de iterações a 10 me tem os seguintes 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
Os resultados são reprodutíveis (quase, com pequenas flutuações causadas por diferentes valores aleatórios). Aparentemente String.Join
é um pouco mais rápido na maioria das vezes (embora por uma margem muito pequena).
Este é o código que usei para testar:
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 as voltas 1% de diferença em algo significativo em termos de tempo todo o programa leva para executar, isso parece micro-otimização. Eu ia escrever o código que é a preocupação mais legível / compreensível e não sobre a diferença de desempenho de 1%.
Atwood tinha uma espécie cargo de relacionado a este cerca de um mês atrás:
Sim. Se você fazer mais do que um par de junta, será muito mais rápido.
Quando você faz uma string.join, o tempo de execução deve:
- Alocar memória para a cadeia resultante
- copiar o conteúdo da primeira corda para o início da cadeia de saída
- copiar o conteúdo da segunda cadeia para o fim da cadeia de saída.
Se você fizer dois junta-se, tem que copiar os dados duas vezes, e assim por diante.
StringBuilder atribui uma memória intermédia com espaço para reposição, de modo que os dados podem ser acrescentadas sem ter de copiar a cadeia original. Como não há espaço deixado no tampão, a cadeia anexa pode ser escrito na memória intermédia directamente. Em seguida, ele só tem que copiar toda a cadeia uma vez, no final.