Конкатенация строк в C# с интернированными строками

StackOverflow https://stackoverflow.com/questions/812503

Вопрос

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

Я создаю несколько операторов SQL для создания сценария (поскольку он будет сохранен на диске) для воссоздания схемы базы данных (легко многих, многих сотен таблиц, представлений и т. д.).Это означает, что моя конкатенация строк доступна только для добавления.StringBuilder, согласно MSDN, работает, сохраняя внутренний буфер (обязательно char[]) и копирование строковых символов в это и перераспределение массив по мере необходимости.

Однако в моем коде много повторяющихся строк («CREATE TABLE [», «GO » и т. д.), что означает, что я могу ими воспользоваться. быть интернированным но не в том случае, если я использую StringBuilder, поскольку они будут копироваться каждый раз.Единственными переменными являются, по сути, имена таблиц и такие переменные, которые уже существуют в виде строк в других объектах, которые уже находятся в памяти.

Насколько я могу судить, после того, как мои данные прочитаны и созданы мои объекты, содержащие информацию о схеме, вся моя строковая информация может быть повторно использована путем интернирования, да?

Если предположить это, то не будут ли строки List или LinkedList быстрее, потому что они сохраняют указатели на интернированные строки?Тогда достаточно одного вызова String.Concat() для выделения памяти для всей строки точно правильной длины.

Список должен будет перераспределить строку [] интернированных указателей, а связанный список должен будет создавать узлы и изменять указатели, поэтому они не «свободны», но если я объединение многих тысяч интернированных строк тогда они будут казаться более эффективными.

Теперь я полагаю, что мог бы придумать некоторую эвристику по подсчету символов для каждого оператора SQL, подсчитать каждый тип, получить примерное представление и предварительно установить емкость StringBuilder, чтобы избежать перераспределения его char[], но мне пришлось бы с изрядной долей промахнуться. чтобы уменьшить вероятность перераспределения.

Итак, в этом случае быстрее всего получить одну объединенную строку:

  • Строитель строк
  • Список<строка> интернированных строк
  • LinkedList<string> интернированных строк
  • StringBuilder с эвристикой емкости
  • Что-то другое?

Как отдельный вопрос (возможно, я не всегда захожу на диск) к вышесказанному:будет ли один StreamWriter для выходного файла быстрее?Альтернативно, используйте List или LinkedList, а затем записывайте их в файл из списка вместо предварительного объединения в памяти.

РЕДАКТИРОВАТЬ:Как просили, ссылка (.NET 3.5) в MSDN.Там говорится: «Новые данные добавляются в конец буфера, если место доступно;в противном случае выделяется новый буфер большего размера, данные из исходного буфера копируются в новый буфер, затем новые данные добавляются в новый буфер». Для меня это означает, что char[] перераспределяется, чтобы увеличить его (что требует копирования старых данных в массив с измененным размером), а затем добавления.

Это было полезно?

Решение

Для тебя отдельный вопрос, в Win32 есть ЗаписьФайлСобрать функция, которая могла бы эффективно записывать список (внутренних) строк на диск, но она будет иметь заметное значение только при асинхронном вызове, поскольку запись на диск затмит все конкатенации, кроме чрезвычайно больших.

Для тебя главный вопрос:не беспокойтесь, если вы не используете мегабайты сценариев или десятки тысяч сценариев.

Вы можете ожидать, что StringBuilder удвоит размер выделения при каждом перераспределении.Это означало бы, что увеличение буфера с 256 байт до 1 МБ потребует всего 12 перераспределений — неплохо, учитывая, что ваша первоначальная оценка была на 3 порядка выше целевой.

Чисто в качестве упражнения, некоторые оценки:Строительство буфера 1 МБ подметает примерно 3 МБ памяти (источник 1 МБ, 1 МБ цели, 1 МБ из -за копирования во время реального уровня).

Реализация связанного списка будет занимать около 2 МБ (и это игнорирует 8-байтовые накладные расходы на объект на ссылку на строку).Таким образом, вы экономите 1 МБ операций чтения/записи в памяти по сравнению с типичной пропускной способностью памяти 10 Гбит/с и 1 МБ кэш-памяти второго уровня.)

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

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

Использование связанного списка также уменьшит проблему перераспределения с O (количества символов) до O (количества сегментов) — ваш список ссылок на строки сталкивается с той же проблемой, что и строка символов!

Итак, IMO, реализация StringBuilder - правильный выбор, оптимизированный для общего случая и ухудшающийся в основном для неожиданно больших целевых буферов.Я ожидаю, что реализация списка сначала ухудшится для очень многих небольших сегментов, что на самом деле является крайним вариантом сценария, для которого StringBuilder пытается оптимизировать.

Тем не менее, было бы интересно увидеть сравнение двух идей и узнать, когда список станет быстрее.

Другие советы

Если бы я реализовал что-то подобное, я бы никогда не создавал StringBuilder (или любой другой в буфере памяти вашего скрипта).Вместо этого я бы просто передал это в ваш файл и сделал все строки встроенными.

Вот пример псевдокода (синтаксически неправильный или что-то в этом роде):

FileStream f = new FileStream("yourscript.sql");
foreach (Table t in myTables)
{
    f.write("CREATE TABLE [");
    f.write(t.ToString());
    f.write("]");
    ....
}

Тогда вам никогда не понадобится представление вашего сценария в памяти со всем копированием строк.

Мнения?

По моему опыту, правильное размещение StringBuilder превосходит все остальное при работе с большими объемами строковых данных.Стоит даже потратить немного памяти, превысив оценку на 20–30 %, чтобы предотвратить перераспределение.В настоящее время у меня нет точных цифр, которые могли бы подтвердить мои собственные данные, но взгляните на на этой странице больше.

Однако, как любит подчеркивать Джефф, не оптимизируйте преждевременно!

РЕДАКТИРОВАТЬ:Как отметил @Colin Burnett, тесты, которые проводил Джефф, не согласуются с тестами Брайана, но смысл ссылки на пост Джеффа заключался в преждевременной оптимизации в целом.Несколько комментаторов на странице Джеффа отметили проблемы с его тестами.

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

Интернирование строк работает для строк, которые можно идентифицировать во время компиляции.Таким образом, если вы сгенерируете много строк во время выполнения, они не будут интернированы, если вы не сделаете это самостоятельно, вызвав метод интернирования для строки.

Стажировка принесет вам пользу только в том случае, если ваши строки идентичны.Практически идентичные строки не выигрывают от интернирования, поэтому "SOMESTRINGA" и "SOMESTRINGB" будут две разные строки, даже если они интернированы.

Если все (или большинство) объединяемых строк интернированы, то ваша схема МОЖЕТ повысить производительность, поскольку потенциально может использовать меньше памяти и сохранить несколько больших копий строк.

Однако то, улучшит ли это производительность на самом деле, зависит от объема обрабатываемых данных, поскольку улучшение происходит в постоянных факторах, а не в порядке величины алгоритма.

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

А StringBuilder не использует char[] для хранения данных используется внутренняя изменяемая строка.Это означает, что для создания окончательной строки не требуется никаких дополнительных действий, как при объединении списка строк. StringBuilder просто возвращает внутренний строковый буфер как обычную строку.

Перераспределения, которые StringBuilder Увеличение емкости означает, что данные в среднем копируются дополнительно 1,33 раза.Если вы можете дать точную оценку размера при создании StringBuilder вы можете уменьшить это еще больше.

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

Вы рассматривали C++ для этого?Существует ли класс библиотеки, который уже создает выражения T/SQL, желательно написанные на C++.

Самая медленная вещь в строках — это malloc.На 32-битных платформах требуется 4 КБ на строку.Рассмотрите возможность оптимизации количества создаваемых строковых объектов.

Если вам необходимо использовать C#, я бы порекомендовал что-то вроде этого:

string varString1 = tableName;
string varString2 = tableName;

StringBuilder sb1 = new StringBuilder("const expression");
sb1.Append(varString1);

StringBuilder sb2 = new StringBuilder("const expression");
sb2.Append(varString2);

string resultingString = sb1.ToString() + sb2.ToString();

Я бы даже пошел дальше и позволил компьютеру оценить лучший путь для создания экземпляров объекта с помощью фреймворков внедрения зависимостей, если производительность НАСТОЛЬКО важна.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top