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

Question

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

---

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

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

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

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

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

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

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

• StringBuilder
• Список внутренних строк
• LinkedList внутренних строк
• StringBuilder с эвристической емкостью
• Что-то еще?

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

EDIT: По запросу ссылка (.NET 3.5) на MSDN. Он говорит: "Новые данные добавляются в конец буфера, если доступно пространство; в противном случае выделяется новый, больший буфер, данные из исходного буфера копируются в новый буфер, затем новые данные добавляются в новый буфер. " Это для меня означает char [], который перераспределяется, чтобы сделать его больше (который требует копирования старых данных в массив с измененным размером) и затем добавляет.

Answer 1

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

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

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

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

Мнения

Answer 2

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

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

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

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

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

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

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

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

---

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

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

Answer 3

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

Answer 6

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

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

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

Answer 7

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

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

Если вы должны использовать 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();

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