String.Join a StringBuilder: co jest szybsze?

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

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.

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

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

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.

Atwood miał post związany z tym około miesiąc temu:

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

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.