tguev Apr 17 2013 at 00:52

StringBuilder прошлое и настоящее

13 min

62K

.NET *C# *

+56

Comments 32

impwx Apr 17 2013 at 01:11

Спасибо за детальное исследование. Иногда полезно знать такие мелочи.

+13

CrazyViper Apr 17 2013 at 07:29

Да, иногда полезно. На собеседованиях.

Меня вот однажды спросили: а какое приведение типов работает быстрее: явное или через оператор as.

impwx Apr 17 2013 at 09:38

Чую вопрос с подвохом. Само по себе приведение работает одинаково, а вот способы обработки ошибок, предлагаемые этими вариантами, различаются по скорости. Или нет?

UFO just landed and posted this here

impwx Apr 17 2013 at 11:38

Ответ крайне подробный, но экспериментально не подтверждается. Проверяю в LinqPad:

void Main()
{
	var times = 100000000;
	A a;
	B b = new B();
	DateTime st, res;
	
	st = DateTime.Now;
	for(var idx = 0; idx < times; idx++)
		a = (A)b;
	res = DateTime.Now;
	(res - st).TotalMilliseconds.Dump();
	
	st = DateTime.Now;
	for(var idx = 0; idx < times; idx++)
		a = b as A;
	res = DateTime.Now;
	(res - st).TotalMilliseconds.Dump();
}

class A { }
class B : A { }

Выдает 245 и 220 секунд соответствено. Но что любопытно — если поменять порядок проверок, результаты не изменятся! Из чего делаю вывод, что разница в 25 миллисекунд вызвана накладными расходами jit-компилятора, а не разницей в производительности подходов.

UFO just landed and posted this here

marcor Apr 19 2016 at 15:57

Зачем DateTime, если есть Stopwatch? Раз.
Два: сделав times константой, получишь повышение производительности по очевидным причинам.
Три: ты меряешь здесь ещё и предсказания выбора, чего делать не надо. В идеале, в тестируемом коде вообще не должно быть if'ов, если они — не часть алгоритма.

На моей машине в MSVS 2015 твой код (переписанный на Stopwatch)

Код

private static void Main()
{
	int times = 1000 * 1000 * 100;
	A a;
	B b = new B();

	Stopwatch sw1 = new Stopwatch();

	sw1.Start();
	for (int i = 0; i < times; i++)
	{
		a = (A)b;
	}
	sw1.Stop();
	Console.WriteLine(sw1.ElapsedTicks);

	Stopwatch sw2 = new Stopwatch();

	sw2.Start();
	for (int i = 0; i < times; i++)
	{
		a = b as A;
	}
	sw2.Stop();
	Console.WriteLine(sw2.ElapsedTicks);
}

private class A
{ }

private class B : A
{ }

выдавал 735 187 и 738 557 тиков, мой же —

Код

private static void Main()
{
	const int times = 1000 * 1000 * 100 / 16;
	A a;
	B b = new B();

	Stopwatch sw = new Stopwatch();

	sw.Start();
	for (int i = 0; i < times; i++)
	{
		a = (A)b;
		a = (A)b;
		a = (A)b;
		a = (A)b;
		a = (A)b;
		a = (A)b;
		a = (A)b;
		a = (A)b;
		a = (A)b;
		a = (A)b;
		a = (A)b;
		a = (A)b;
		a = (A)b;
		a = (A)b;
		a = (A)b;
		a = (A)b;
	}
	sw.Stop();
	Console.WriteLine(sw.ElapsedTicks);

	Stopwatch sw2 = new Stopwatch();

	sw2.Start();
	for (int i = 0; i < times; i++)
	{
		a = b as A;
		a = b as A;
		a = b as A;
		a = b as A;
		a = b as A;
		a = b as A;
		a = b as A;
		a = b as A;
		a = b as A;
		a = b as A;
		a = b as A;
		a = b as A;
		a = b as A;
		a = b as A;
		a = b as A;
		a = b as A;
	}
	sw2.Stop();
	Console.WriteLine(sw2.ElapsedTicks);
}

private class A
{ }

private class B : A
{ }

отрабатывает за 118 109 и 117 323 тиков.

impwx Apr 19 2016 at 16:08

Ваша оптимизация впечатляет, однако на результаты теста это никак не повлияло — в любом случае оба варианта приведения типов работают одинаково быстро.

marcor Apr 19 2016 at 16:24

Более того, первый стал работать дольше)
В итоге, и правда всё равно.

ant99 Apr 17 2013 at 09:48

После прочтения Вашего комментария остаётся дивное ощущение — как после упоминания анекдота в компании, когда все сдержанно отсмеялись, и только ты один теряешься, ни разу этот анекдот не слышав.

UFO just landed and posted this here

Suvitruf Apr 17 2013 at 09:57

Заинтриговали.
Не томите, расскажите, в чём подвох (:

CrazyViper Apr 18 2013 at 08:04

Эх… тяжкий вчера был день, даже некогда было сюда заглянуть, так что извиняюсь за столь поздний ответ.

Выше уже все ответили по существу. А на собеседовании я столько теорий выдвинул, рассуждая на эту тему. Это было самое запоминающее собеседование в моей жизни.

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

nikita2206 Apr 18 2013 at 10:32

А взяли?:)

CrazyViper Apr 18 2013 at 10:59

Мы на финансовом вопросе не сошлись тогда ;)

GrigoryPerepechko Apr 17 2013 at 10:04

В случае успешного приведения одинаково быстро.

ngreduce Apr 17 2013 at 18:50

**комментарий удален пользователем

PsyHaSTe Apr 28 2013 at 12:26

Насколько я знаю, прямое приведение быстрее, потому что с помощью as Работает примерно так:

public T OperatorAs<T>(object source)
{
   return source is T ? (T) source : null;
}

Nagg Apr 17 2013 at 09:42

На моей памяти это уже 4ая статья про .net строки и SB на хабре :-)

CrazyViper Apr 18 2013 at 08:05

Не порядок! Версий .NET Framework уже явно больше 4! Надо больше статей про StringBuilder.

vics001 Apr 17 2013 at 10:11

>>> То есть такой сценарий конкатенации требует памяти пропорционально O(n2), n — длина строки.
Что-то не понятно как вы так посчитали… Проверьте, память линейна.

tguev Apr 17 2013 at 12:51

Я ведь указал, что полученная сумма есть сумма арифметической прогрессии.
(n2+n) / 2 = O(n2)

encyclopedist Apr 17 2013 at 12:59

Ну так эти строки не используются одновременно. старые строки могут освобождаться. Так что если GC их освобождает, то потребление памяти будет линейно, в вот нагрузка на процессор будет квадратична.

tguev Apr 17 2013 at 13:17

Конечно старые строки будут освобождаться сборщиком мусора. Имелось виду, что на создание строки потребуется памяти пропорционально квадрату длины, а не то что она будет использовать столько памяти.

vics001 Apr 17 2013 at 14:04

К чему все эти рассуждения можно же померить

Исходный код

public static void main(String[] args) {
String s = "";
measure(s, 1000);
measure(s, 2000);
measure(s, 3000);
measure(s, 4000);
measure(s, 5000);
}

private static String measure(String s, int n) {
long t = System.currentTimeMillis();
for(int i = 0; i <= n; i++ ) {
s += «T»;
}
System.out.println(«N=» + n + " " + (System.currentTimeMillis() — t) + " ms");
return s;
}

Результаты измерений для малых чисел показывают что скорость линейна

N=1000 4 ms
N=2000 10 ms
N=3000 15 ms
N=4000 21 ms
N=5000 19 ms

Результаты измерений для больших чисел

N=10000 133 ms
N=20000 297 ms
N=30000 512 ms
N=40000 911 ms
N=50000 1552 ms

Результаты измерений с GC logging

[GC 16448K->176K(62848K), 0.0010550 secs]
[GC 16622K->144K(79296K), 0.0006340 secs]
[GC 33040K->176K(79296K), 0.0005890 secs]
[GC 33072K->184K(112192K), 0.0005770 secs]
[GC 65974K->179K(112192K), 0.0007630 secs]
N=10000 122 ms
[GC 65971K->168K(175552K), 0.0004370 secs]
[GC 131752K->175K(175552K), 0.0008520 secs]
[GC 131759K->164K(307136K), 0.0004220 secs]
[GC 263332K->173K(307136K), 0.0007190 secs]
N=20000 301 ms
[GC 263341K->140K(392960K), 0.0003920 secs]
[GC 349132K->167K(392960K), 0.0003900 secs]
[GC 349159K->177K(376128K), 0.0004860 secs]
[GC 332529K->185K(360512K), 0.0004810 secs]
[GC 316729K->191K(345344K), 0.0004400 secs]
[GC 301695K->197K(331072K), 0.0005320 secs]
N=30000 530 ms
[GC 287429K->160K(317440K), 0.0005690 secs]
[GC 273824K->170K(304768K), 0.0007380 secs]
[GC 260970K->178K(292352K), 0.0005290 secs]
[GC 248754K->183K(280896K), 0.0004380 secs]
[GC 237111K->188K(269696K), 0.0005000 secs]
[GC 226044K->193K(259200K), 0.0005720 secs]
[GC 215553K->197K(249216K), 0.0005790 secs]
[GC 205573K->200K(239744K), 0.0004120 secs]
[GC 196104K->203K(230720K), 0.0005490 secs]
[GC 187083K->206K(222144K), 0.0004270 secs]
[GC 178510K->208K(214016K), 0.0003710 secs]
[GC 170354K->211K(206272K), 0.0004750 secs]
[GC 162643K->213K(198912K), 0.0003800 secs]
[GC 155285K->215K(191936K), 0.0005550 secs]
[GC 148307K->217K(185280K), 0.0005060 secs]
N=40000 949 ms
[GC 141657K->151K(178944K), 0.0004260 secs]
[GC 135319K->159K(172928K), 0.0006030 secs]
[GC 129311K->165K(167360K), 0.0003990 secs]
[GC 123621K->169K(198144K), 0.0006310 secs]
[GC 154537K->174K(191360K), 0.0004140 secs]
[GC 147630K->178K(184640K), 0.0004070 secs]
[GC 141042K->181K(178432K), 0.0005010 secs]
[GC 134773K->184K(212032K), 0.0005700 secs]
[GC 168440K->188K(204480K), 0.0003480 secs]
[GC 160828K->191K(197248K), 0.0005430 secs]
[GC 153599K->194K(190336K), 0.0005200 secs]
[GC 146690K->184K(183744K), 0.0004400 secs]
[GC 140098K->259K(177600K), 0.0005770 secs]
[GC 133963K->321K(171648K), 0.0003460 secs]
[GC 128071K->323K(166016K), 0.0005310 secs]
[GC 122459K->324K(160576K), 0.0003830 secs]
[GC 117124K->391K(155584K), 0.0003710 secs]
[GC 112111K->393K(180224K), 0.0005830 secs]
[GC 136727K->395K(208896K), 0.0004890 secs]
[GC 165403K->397K(243520K), 0.0006960 secs]
[GC 200141K->472K(234368K), 0.0004700 secs]
[GC 191000K->475K(225600K), 0.0003940 secs]
[GC 182235K->477K(217280K), 0.0004250 secs]
[GC 173917K->479K(209408K), 0.0003490 secs]
[GC 165967K->481K(201920K), 0.0004630 secs]
[GC 158495K->483K(194816K), 0.0004200 secs]
[GC 151393K->485K(188032K), 0.0004890 secs]
[GC 144620K->486K(181568K), 0.0005560 secs]
[GC 138151K->488K(175424K), 0.0005800 secs]
[GC 132009K->489K(169600K), 0.0005440 secs]
[GC 126196K->490K(164096K), 0.0005160 secs]
[GC 120722K->492K(158848K), 0.0004920 secs]
[GC 115497K->493K(153856K), 0.0005540 secs]
[GC 110452K->494K(149120K), 0.0003550 secs]
N=50000 1571 ms

Результаты измерений для огромных чисел для StringBuilder зависимость линейная

N=10000000 218 ms
N=20000000 402 ms
N=30000000 628 ms
N=40000000 877 ms
N=50000000 1033 ms

Так что делаем простой и однозначный вывод, скорость обоих алгоритмов линейна при наличии достаточной памяти!!! При нехватке памяти скорость алгоритма памяти падает в прямой зависимости от нехватки памяти! У String метода память действительно выделяется квадратично и освобождается (посчитать количество GC), у StringBuilder скорость линейна и при нехватки памяти, так как память выделяется маленькими кусочками.

nikita2206 Apr 17 2013 at 13:06

Да, там дело не в памяти, она вернется в кучу после конкатенации, а во времени на аллокации+копирование+релиз

MikeMirzayanov Apr 17 2013 at 10:19

>>> Это значит, что следующий код имеет весьма серьезные проблемы с нагрузкой на память.

Большая проблема с производительностью — такой код работает за O(n^2). Кстати, можно вспомнить аналогичный пример из мира С:

for (i = 0; i < strlen(s); i++) {
    // process s[i]
}

vics001 Apr 17 2013 at 13:37

Не знаю я никакой аналогии не вижу :) Компилириуемый и managed языки видут себя по разному. Тут да квадратична :)

jakobz Apr 17 2013 at 11:33

Стоит заметить, что StringBuilder на деле не так часто требуется. Во многих местах достаточно слепить массив и позвать String.Contat. В других — можно выплевывать строки прямо в выходной TextWriter, без промежуточного склеивания. Как это делается, скажем, при рендеринге html-страничек в ASP.NET. Я уже даже и не помню когда мне StringBuilder требовался в последний раз.

Стоит присматриваться к местам где используется StringBuilder на предмет нельзя ли переделать метод, например, из string GetTable() в void WriteTable(TextWriter writer). Второй вариант позволяет и в поток писать, и в буфер через StringWriter (который является оберткой того же StringBuilder-а)

UFO just landed and posted this here

xonix Apr 17 2013 at 15:14

Интересно.
Интересно бы еще сравнить с Java-подходом в плане эффективности. Кстати, судя по исходникам, подход Java проще всего:

    /**
     * The value is used for character storage.
     */
    char[] value;

    /**
     * The count is the number of characters used.
     */
    int count;