String.Join a StringBuilder: co jest szybsze?

80

W poprzednim pytaniu dotyczącym formatowania double[][]do formatu CSV zasugerowano, że użycie StringBuilderbędzie szybsze niż String.Join. Czy to prawda?

Hosam Aly
źródło
Dla jasności czytelników chodziło o użycie pojedynczego StringBuildera w porównaniu z wieloma ciągami. Dołącz, które następnie zostały połączone (łączy n + 1)
Marc Gravell
2
Różnica w wydajności szybko osiąga kilka rzędów wielkości. Jeśli zrobisz więcej niż kilka złączeń, możesz uzyskać dużo wydajności, przechodząc na stringbuilder
jalf

Odpowiedzi:

116

Krótka odpowiedź: to zależy.

Długa odpowiedź: jeśli masz już tablicę ciągów do połączenia (z separatorem), String.Joinjest to najszybszy sposób.

String.Joinmoże przejrzeć wszystkie ciągi, aby określić dokładną długość, jakiej potrzebuje, a następnie przejść ponownie i skopiować wszystkie dane. Oznacza to, że nie będzie żadnego dodatkowego kopiowania. Tylko minusem jest to, że musi przejść przez struny dwukrotnie, co oznacza potencjalnie dmuchanie pamięci podręcznej więcej razy niż jest to konieczne.

Jeśli wcześniej nie masz łańcuchów jako tablicy, prawdopodobnie jest ona szybsza w użyciu StringBuilder- ale będą sytuacje, w których tak nie jest. Jeśli użycie a StringBuilderoznacza wykonanie wielu, wielu kopii, to zbudowanie tablicy, a następnie wywołanie String.Joinmoże być szybsze.

EDYCJA: To jest w kategoriach pojedynczego połączenia z String.Joingrupą połączeń do StringBuilder.Append. W pierwotnym pytaniu mieliśmy dwa różne poziomy String.Joinwywołań, więc każde z zagnieżdżonych wywołań tworzyło łańcuch pośredni. Innymi słowy, jest to jeszcze bardziej złożone i trudniejsze do odgadnięcia. Byłbym zaskoczony, widząc, że w obu przypadkach "wygrywa" znacząco (pod względem złożoności) z typowymi danymi.

EDYCJA: Kiedy jestem w domu, napiszę test porównawczy, który jest tak bolesny, jak to tylko możliwe StringBuilder. Zasadniczo, jeśli masz tablicę, w której każdy element jest około dwa razy większy niż poprzedni i masz to dobrze, powinieneś być w stanie wymusić kopię dla każdego dodania (elementów, a nie separatora, chociaż to musi być brane pod uwagę). W tym momencie jest to prawie tak złe, jak zwykła konkatenacja ciągów - ale nie String.Joinbędzie żadnych problemów.

Jon Skeet
źródło
6
Nawet jeśli nie mam wcześniej łańcuchów, użycie String.Join wydaje się szybsze. Proszę sprawdzić moją odpowiedź ...
Hosam Aly,
2
At będzie zależało od tego jak tablica jest tworzona, jej rozmiar itp. Z przyjemnością podam dość definitywne "W <tym przypadku> String.Join będzie co najmniej tak samo szybkie" - nie chciałbym odwrócić.
Jon Skeet,
4
(W szczególności spójrz na odpowiedź Marca, gdzie StringBuilder pokonuje String.Join, prawie. Życie jest skomplikowane.)
Jon Skeet,
2
@BornToCode: Czy masz na myśli skonstruowanie a StringBuilderz oryginalnym ciągiem znaków, a następnie wywołanie Appendraz? Tak, spodziewałbym string.Joinsię tam wygrać.
Jon Skeet
13
[Nekromancja wątków]: Bieżąca (.NET 4.5) implementacja string.Joinzastosowań StringBuilder.
n0rd
31

Oto moje stanowisko testowe, używane int[][]dla uproszczenia; najpierw wyniki:

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

(aktualizacja doublewyników :)

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

(aktualizacja do 2048 * 64 * 150)

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

iz włączoną opcją OptimizeForTesting:

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

Tak szybciej, ale nie masowo; rig (uruchamiany na konsoli, w trybie wydania itp.):

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();
        }
    }
}
Marc Gravell
źródło
Dzięki Marc. Co otrzymasz za większe tablice? Na przykład używam [2048] [64] (około 1 MB). Czy Twoje wyniki w jakikolwiek sposób różnią się, jeśli zastosujesz OptimizeForTesting()metodę, której używam?
Hosam Aly,
Wielkie dzięki Marc. Ale zauważam, że to nie pierwszy raz, kiedy otrzymujemy różne wyniki dla mikro-benchmarków. Czy masz pojęcie, dlaczego tak się dzieje?
Hosam Aly,
2
Karma? Promieniowanie kosmiczne? Kto wie ... pokazuje jednak niebezpieczeństwa mikrooptymalizacji ;-p
Marc Gravell
Czy używasz na przykład procesora AMD? ET64? Może mam za mało pamięci podręcznej (512 KB)? A może platforma .NET w systemie Windows Vista jest bardziej zoptymalizowana niż ta dla XP SP3? Co myślisz? Naprawdę interesuje mnie, dlaczego tak się dzieje ...
Hosam Aly,
XP SP3, x86, Intel Core2 Duo T7250 @ 2GHz
Marc Gravell
20

Nie sądzę. Patrząc przez Reflector, realizacja String.Joinwygląda bardzo optymalnie. Ma również dodatkową zaletę, że zna z wyprzedzeniem całkowity rozmiar ciągu, który ma zostać utworzony, więc nie wymaga ponownej alokacji.

Stworzyłem dwie metody testowe, aby je porównać:

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

Uruchomiłem każdą metodę 50 razy, przekazując tablicę rozmiarów [2048][64]. Zrobiłem to dla dwóch tablic; jeden wypełniony zerami, a drugi wypełniony losowymi wartościami. Na moim komputerze otrzymałem następujące wyniki (P4 3,0 GHz, jednordzeniowy, bez HT, działający w trybie Release z 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

Zwiększenie rozmiaru tablicy do [2048][512], przy jednoczesnym zmniejszeniu liczby iteracji do 10, dało mi następujące wyniki:

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

Wyniki są powtarzalne (prawie; z małymi wahaniami spowodowanymi różnymi przypadkowymi wartościami). Najwyraźniej String.Joinprzez większość czasu jest trochę szybszy (choć z bardzo małym marginesem).

Oto kod, którego użyłem do testów:

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));
    }
}
Hosam Aly
źródło
13

O ile różnica 1% nie zmieni się w coś znaczącego pod względem czasu działania całego programu, wygląda to na mikro-optymalizację. Napisałbym kod, który jest najbardziej czytelny / zrozumiały i nie martwiłbym się o 1% różnicy wydajności.

tvanfosson
źródło
1
Uważam, że String.Join jest bardziej zrozumiały, ale post był bardziej zabawnym wyzwaniem. :) Warto też (IMHO) dowiedzieć się, że użycie kilku wbudowanych metod może być lepsze niż robienie tego ręcznie, nawet jeśli intuicja podpowiada inaczej. ...
Hosam Aly,
... Normalnie wiele osób zasugerowałoby użycie StringBuilder. Nawet gdyby String.Join okazał się 1% wolniejszy, wiele osób nie pomyślałoby o tym, tylko dlatego, że uważają , że StringBuilder jest szybszy.
Hosam Aly,
Nie mam żadnych problemów ze śledztwem, ale teraz, gdy masz odpowiedź, nie jestem pewien, czy wydajność jest nadrzędnym problemem. Ponieważ przychodzi mi do głowy jakikolwiek powód do skonstruowania łańcucha w CSV poza zapisaniem go w strumieniu, prawdopodobnie w ogóle nie skonstruowałbym łańcucha pośredniego.
tvanfosson
-3

tak. Jeśli zrobisz więcej niż kilka złączeń, będzie to znacznie szybsze.

Kiedy wykonujesz string.join, środowisko wykonawcze musi:

  1. Przydziel pamięć dla wynikowego ciągu
  2. skopiuj zawartość pierwszego ciągu na początek ciągu wyjściowego
  3. skopiuj zawartość drugiego ciągu na koniec ciągu wyjściowego.

Jeśli wykonasz dwa sprzężenia, musi dwukrotnie skopiować dane i tak dalej.

StringBuilder przydziela jeden bufor z wolną przestrzenią, dzięki czemu dane mogą być dołączane bez konieczności kopiowania oryginalnego ciągu. Ponieważ w buforze pozostało wolne miejsce, dołączony ciąg może zostać bezpośrednio zapisany w buforze. Następnie wystarczy raz skopiować cały ciąg na końcu.

jalf
źródło
1
Ale String.Join wie z góry, ile przydzielić, podczas gdy StringBuilder nie. Proszę zobaczyć moją odpowiedź, aby uzyskać więcej wyjaśnień.
Hosam Aly,
@erikkallen: Możesz zobaczyć kod dla String.Join w Reflector. red-gate.com/products/reflector/index.htm
Hosam Aly,