Конкатенация строк в C# с интернированными строками
Я знаю, что этот вопрос был решен, но у меня есть немного другой поворот к нему. Некоторые отметили, что это преждевременная оптимизация, что совершенно верно, если бы я просил только практичности и практичности. Моя проблема коренится в практической проблеме, но мне все равно интересно.
Я создаю кучу операторов SQL для создания сценария (так как он будет сохранен на диске) для воссоздания схемы базы данных (легко много сотен таблиц, представлений и т. Д.). Это означает, что моя конкатенация строк только для добавления. StringBuilder, согласно MSDN, работает путем сохранения внутреннего буфера (обязательно char[]),копирования в него строковых символов и перераспределения массива по мере необходимости.
Однако в моем коде много повторяющихся строк ("CREATE TABLE [", "GO\n" и т. Д.), Что означает, что я могу воспользоваться их интернированием, но я не буду использовать StringBuilder, поскольку они будут копироваться каждый раз. Единственными переменными являются имена таблиц и такие, которые уже существуют в виде строк в других объектах, которые уже находятся в памяти.
Итак, насколько я могу сказать, что после того, как мои данные прочитаны и мои объекты созданы, которые содержат информацию о схеме, тогда вся моя строковая информация может быть повторно использована интернированием, да?
Если предположить, что не будет ли список или LinkedList строк быстрее, потому что они сохраняют указатели на интернированные строки? Тогда это только один вызов String.Concat() для единственного выделения памяти всей строки, которая является точно правильной длины.
List должен был бы перераспределить строку [] интернированных указателей, а связанный список должен был бы создать узлы и модифицировать указатели, чтобы они не были "свободными", но если я объединяю многие тысячи интернированных строк, то они кажутся как бы они были более эффективными.
Теперь я полагаю, что мог бы придумать эвристический подсчет символов для каждого оператора SQL, подсчитать каждый тип, получить приблизительное представление и предварительно настроить емкость моего StringBuilder, чтобы избежать перераспределения его символа [], но мне пришлось бы перерегулировать с достаточным запасом уменьшить вероятность перераспределения.
Таким образом, для этого случая, который будет быстрее всего получить единственную объединенную строку:
- StringBuilder
- Список
внутренних строк - LinkedList
внутренних строк - StringBuilder с емкостью эвристики
- Что-то другое?
В качестве отдельного вопроса (я не всегда обращаюсь к диску) к вышесказанному: будет ли еще один StreamWriter к выходному файлу еще быстрее? В качестве альтернативы используйте List или LinkedList, а затем запишите их в файл из списка вместо того, чтобы сначала объединить в памяти.
РЕДАКТИРОВАТЬ: По запросу, ссылка (.NET 3.5) на MSDN. В нем говорится: "Новые данные добавляются в конец буфера, если доступно пространство; в противном случае выделяется новый, больший буфер, данные из исходного буфера копируются в новый буфер, затем новые данные добавляются в новый буфер ". Для меня это означает, что char [] перераспределяется, чтобы сделать его больше (что требует копирования старых данных в массив с измененным размером), а затем добавить его.
7 ответов
Для вашего отдельного вопроса, Win32 имеет функцию WriteFileGather, которая может эффективно записывать список (интернированных) строк на диск - но это будет иметь заметное значение только при асинхронном вызове, так как запись на диск будет затенять все, кроме очень больших конкатенаций.
На ваш главный вопрос: если вы не достигли мегабайт сценария или десятки тысяч сценариев, не волнуйтесь.
Можно ожидать, что 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 не использует char[] для хранения данных используется внутренняя изменяемая строка. Это означает, что нет никакого дополнительного шага для создания окончательной строки, как это происходит, когда вы объединяете список строк, StringBuilder просто возвращает внутренний строковый буфер как обычную строку.
Перераспределение, что StringBuilder означает увеличение емкости означает, что данные в среднем копируются дополнительно в 1,33 раза. Если вы можете предоставить хорошую оценку размера при создании StringBuilder Вы можете уменьшить это даже дальше.
Однако, чтобы получить немного перспективы, вы должны взглянуть на то, что вы пытаетесь оптимизировать. В вашей программе большую часть времени займет запись данных на диск, поэтому даже если вы сможете оптимизировать обработку строк, вы будете в два раза быстрее, чем при использовании StringBuilder (что очень маловероятно), общая разница все равно будет составлять всего несколько процентов.
Если все (или большинство) объединяемых строк являются интернированными, то ваша схема МОЖЕТ дать вам повышение производительности, так как она потенциально может использовать меньше памяти и может сохранить несколько больших копий строк.
Однако то, действительно ли оно улучшает производительность, зависит от объема обрабатываемых данных, потому что улучшение происходит в постоянных коэффициентах, а не в порядке величины алгоритма.
Единственный способ действительно сказать, это запустить ваше приложение, используя оба способа и измерить результаты. Однако, если вы не испытываете значительную нагрузку на память и не нуждаетесь в способе сохранения байтов, я бы не стал беспокоиться и просто использовал бы построитель строк.
На самом деле StringBuilder использует экземпляр String внутренне. String на самом деле изменчив в пределах System сборка, вот почему StringBuilder можно построить поверх него. Ты можешь сделать StringBuilder чуть более эффективно, назначая разумную длину при создании экземпляра. Таким образом вы исключите / уменьшите количество операций изменения размера.
Интернирование строк работает для строк, которые могут быть определены во время компиляции. Таким образом, если вы сгенерируете много строк во время выполнения, они не будут интернированы, если вы сами не сделаете это, вызвав метод интернирования для строки.
Стажировка принесет вам пользу только в том случае, если ваши строки идентичны. Практически идентичные строки не выигрывают от интернирования, поэтому "SOMESTRINGA" а также "SOMESTRINGB" будет две разные строки, даже если они интернированы.
Вы рассматривали 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 это ТАК важно.