String.Join против StringBuilder: что быстрее? - PullRequest
68 голосов
/ 25 февраля 2009

В предыдущем вопросе о форматировании double[][] в формат CSV Марк Гравелл сказал , что использование StringBuilder будет быстрее, чем String.Join. Это правда?

Ответы [ 6 ]

94 голосов
/ 25 февраля 2009

Краткий ответ: это зависит.

Длинный ответ: Если у вас уже есть массив строк для объединения (с разделителем), String.Join - самый быстрый способ сделать это.

String.Join может просмотреть все строки, чтобы определить нужную длину, затем снова пойти и скопировать все данные. Это означает, что * не потребует дополнительного копирования. Недостатком only является то, что он должен дважды проходить по строкам, что означает потенциальную загрузку кеша памяти больше раз, чем необходимо.

Если у вас нет строк в виде массива заранее, это вероятно быстрее для использования StringBuilder - но будут ситуации, когда это не так. Если использование StringBuilder означает выполнение большого и большого количества копий, то создание массива и последующий вызов String.Join могут быть быстрее.

РЕДАКТИРОВАТЬ: это касается одного звонка на String.Join против набора звонков на StringBuilder.Append. В исходном вопросе у нас было два разных уровня вызовов String.Join, поэтому каждый из вложенных вызовов создал бы промежуточную строку. Другими словами, об этом еще сложнее и сложнее догадаться. Я был бы удивлен, увидев, что в обоих случаях значительно (с точки зрения сложности) значительно выиграть с типичными данными.

РЕДАКТИРОВАТЬ: Когда я буду дома, я напишу тест, который является настолько болезненным, насколько возможно для StringBuilder. В основном, если у вас есть массив, в котором каждый элемент примерно в два раза больше предыдущего, и вы все сделаете правильно, вы должны иметь возможность принудительно создавать копию для каждого добавления (элементов, а не разделителя, хотя для этого нужно учитывать тоже). На данный момент это почти так же плохо, как простая конкатенация строк - но у String.Join проблем не будет.

30 голосов
/ 25 февраля 2009

Вот мой испытательный стенд, для простоты используется int[][]; Сначала результаты:

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

(обновление для double результаты:)

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

(обновление до 2048 * 64 * 150)

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

и с включенным OptimizeForTesting:

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

Так быстрее, но не так массово; Rig (запуск на консоли, в режиме выпуска и т. д.):

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();
        }
    }
}
17 голосов
/ 25 февраля 2009

Я так не думаю. При просмотре Reflector реализация String.Join выглядит очень оптимизированной. Он также имеет дополнительное преимущество, заключающееся в том, что заранее знает общий размер строки, поэтому не требует перераспределения.

Я создал два метода испытаний для их сравнения:

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

Я запускал каждый метод 50 раз, передавая массив размером [2048][64]. Я сделал это для двух массивов; один заполнен нулями, а другой заполнен случайными значениями. На моем компьютере были получены следующие результаты (P4 3,0 ГГц, одноядерный, без HT, запущен режим выпуска из 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

Увеличение размера массива до [2048][512] при уменьшении количества итераций до 10 дало мне следующие результаты:

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

Результаты повторяемы (почти; с небольшими колебаниями, вызванными различными случайными значениями). Очевидно, String.Join в большинстве случаев немного быстрее (хотя и с очень небольшим отрывом).

Это код, который я использовал для тестирования:

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));
    }
}
9 голосов
/ 25 февраля 2009

Если разница в 1% не превращается во что-то существенное с точки зрения времени, необходимого для запуска всей программы, это выглядит как микрооптимизация. Я написал бы код, который был бы наиболее читаемым / понятным, и не беспокоился бы о разнице в производительности в 1%.

0 голосов
/ 25 февраля 2009

У Этвуда был пост, связанный с этим около месяца назад:

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

0 голосов
/ 25 февраля 2009

да. Если вы сделаете больше пары соединений, это будет намного быстрее.

Когда вы делаете string.join, среда выполнения должна:

  1. Выделите память для полученной строки
  2. скопировать содержимое первой строки в начало выходной строки
  3. скопировать содержимое второй строки в конец выходной строки.

Если вы выполняете два объединения, необходимо дважды скопировать данные и т. Д.

StringBuilder выделяет один буфер с местом для резервирования, поэтому данные можно добавлять без необходимости копировать исходную строку. Поскольку в буфере осталось место, добавленная строка может быть записана в буфер напрямую. Затем нужно просто скопировать всю строку один раз, в конце.

...