Строки, неизменяемость и персистентность
Сегодняшний пост основан на очередном вопросе со StackOverflow; мне он настолько понравился, что я подумал, а почему бы его не написать об этом сегодня здесь?
Строка в языке C# кажется коллекцией символов. Но, конечно же, на самом деле где-то существует структура данных в памяти, реализующая эту коллекцию символов. В CLR строки располагаются в памяти так же, как и BSTR-строки в OLE Automation; в буфере находится четырехбайтовая длина строки, за которой следуют двухбайтовые символы строки в формате UTF-16, за которыми следует два нулевых байта. (Напомню, что аббревиатура BSTR изначально расшифровывалась как “BASIC string”, поскольку команда OLE Automation была частью команды Visual Basic; а этот формат использовался в Visual Basic.)
Использование такой внутренней реализации строк имеет ряд преимуществ. Например, при создании строки требуется только одна операция выделения памяти в куче. Длину строки можно определить, не пересчитывая все символы строки. Строка может содержать нулевые байты, в отличие от форматов, которые используют нулевые байты, в качестве маркера конца строки. Если не обращать внимания на суррогатные пары, то n-й символ может быть получен за время O(1), в отличие от кодировки с переменной шириной символа, такой как UTF-8. Адрес зафиксированной (pinned) строки, которая не содержит нулевые символы, можно напрямую передавать в неуправляемый код, принимающий WCHAR*. И т.д.
Кроме того, строки в .NET неизменяемые, что также дает ряд преимуществ. Как я уже неоднократно рассказывал, неизменяемые структуры данных проще для понимания, потокобезопасны и более безопасны. (*)
Одним из преимуществ неизменяемых типов, как я говорил ранее, является не просто незменяемость, но еще и «персистентность». Под «персистентным» я понимаю тип, операции которого (как добавление элемента в очередь, удаление элемента из дерева) могут повторно использовать большую часть памяти, занимаемой существующей структурой данных. Поскольку тип неизменяемый, то вы можете повторно использовать его части, не беспокоясь за то, что кто-то их изменит.
Строки по своей природе являются неизменяемыми, но из-за своего расположения в памяти они не являются персистентными. Конкатенация двух строк не использует повторно память ни одной из строк; в процессе конкатенации создается новая строка, в которую копируется содержимое двух этих строк. Получение подстроки в строке не использует повторно содержимое исходной строки. Опять- таки, в этом случае просто создается новая строка нужного размера и все данные копируются в новую строку.
Это означает, что все операции над строками, такие как получение подстроки, выполняются за O(n) операций, от размера подстроки. Конкатенация выполняется за O(n + m) от размеров исходных строк. Эти операции могли бы выполняться за O(1) или за O(lg n), если бы строки были персистентными. Например, мы могли бы рассматривать строки как сцепляемые очереди (catenable deques) символов; существуют очень эффективные способы объединения сцепляемых очередей. (**) Или мы могли бы сказать, что у нас есть два типа строк; «простые» строки и связанные строки («ropes»), которые представляют собой бинарные деревья строк. Конкатенация строк – это создание нового узла дерева. Это делает поиск n-го символа такой связанной строки более дорогой операцией, и вы не сможете передать немодифицированный экземпляр такой строки в неуправляемый код, но вы всегда сможете избежать копирования потенциально длинных строк. Получение подстроки выполняется аналогичным образом: для получения подстроки необходимо создать обертку вокруг исходной строки и сохранить в ней смещение и длину. Никакого копирования не нужно.
Так почему мы не используем «персистентность», если строка и так уже неизменяема?
Мотивация использования подобной оптимизации обусловлена некорректным предположением о том, что О(1) всегда лучше чем O(lg n), что, в свою очередь, всегда лучше, чем O(n). Асимптотическая сложность операции важна только тогда, когда в реальных условиях n становится действительно большой величиною. Если n мало, то любая задача решается за O(1)!
И это справедливо в нашем случае. Лишь небольшое число разработчиков постоянно работает со строками, превышающими несколько сотен или несколько тысяч символов. При работе с длинными строками и большим количеством операций конкатенации, можно использовать StringBuilder; если же вы выполняете небольшое количество конкатенаций, то копирование будет выполняться очень быстро. При создании подстрок, наверняка речь будет идти о создании подстроки в несколько десятков символов из строк в несколько тысяч символов; маловероятно, что вы будете выкусывать сотни тысяч символов из миллионных строк. Очень мало разработчиков занимаются разбором строк ДНК, состоящих из миллионов символов; большинство получают имя книги из XML документа или адрес из csv-файла. Создание небольшого буфера и копирование в него нескольких десятков байт выполняется невероятно быстро, настолько быстро, что это не имеет смысла оптимизировать.
Нет смысла в оптимизации, если она не дает особого выигрыша. Лет двенадцать назад я все лето занимался переписыванием внутреннего механизма манипулирования строками в VBScript, чтобы каждый раз при конкатенации создавалось дерево, которое преобразовывалось в «настоящую» BSTR-строку только по необходимости. Исследование с реальными данными показало, что эта «оптимизация» вообще ничего не оптимизировала; в основном, после второй или третьей конкатенации деревья преобразовывались обратно к BSTR-строкам, а дополнительные расходы на выделение узлов дерева на самом деле привели к снижению производительности, по сравнению с созданием BSTR-строки каждый раз (***).
Некоторые люди манипулируют действительно большими строками, постоянно вставляя и удаляя подстроки. Моя команда этим постоянно занимается; мы пишем редакторы кода, которые должны очень быстро работать с огромными файлами. Поскольку операции над строками выполняются за O(n), и n может принимать большие значения, то мы не используем больших строк; вместо этого, мы используем неизменяемые персистентные структуры данных, представляющие изменения документа, которые мы затем «скармливаем» механизму, поддерживающему неизменяемую, персистентную модель лексического и синтаксического анализа программы. Чтобы гарантировать высокую производительность и минимальный расход памяти, мы хотим иметь возможность использовать повторно как можно больше проанализированного текста.
Этот код достаточно сложный и хотя он прекрасно работает в нашем случае, такой подход однозначно не подойдет для людей, выполняющий анализ строк ДНК или для решения любой другой задачи, требующей манипуляции огромными строками. Вместо оптимизации строк в CLR под конкретный редкий случай, значительно лучше оставить их простыми и оптимальными для самых распространенных случаев применения, и рассчитывать на то, что процессор выполнить копирование коротких строк невероятно быстро.
-------------------
(*) Подумайте об атаке, когда злонамеренный код с частичным доверием, передает строку с «безопасным» путем в метод File.Open. Затем система безопасности проверяет, является ли путь безопасным для кода с частичным доверием. А затем этот злонамеренный код изменяет строку из другого потока непосредственно перед открытием файла! Если атакующий правильно рассчитает время, то проверка безопасности пройдет успешно, но будет открыт другой файл. Но с неизменяемыми строками такой фокус не пройдет.
(**) В моей статье про очереди не показано, как сцепление сделать эффективным; за подробностями обращайтесь к приведенным ссылкам.
(***) Если у вас есть доступ к исходному коду VBScript, то я думаю, что мой код все еще там, просто он не используется. Попробуйте найти FANCY_STRING.