Как разработчики программного обеспечения, мы всегда хотим, чтобы наше программное обеспечение работало правильно. Мы сделаем все для улучшения качества программного обеспечения. Для поиска оптимального решения мы готовы использовать распараллеливание или применение любых различных методов оптимизации. Одним из таких методов оптимизации является так называемое интернирование строк. Это позволяет пользователям уменьшить использование памяти. Это также ускоряет сравнение строк. Однако все хорошо в меру. Стажировка на каждом шагу не стоит. Далее я покажу вам, как не ошибиться с созданием скрытого узкого места в виде метода String.Intern для вашего приложения.
Если вы забыли, напомню, что строка - это ссылочный тип в C #. Следовательно, строковая переменная сама по себе является просто ссылкой, которая лежит в стеке и хранит адрес. Адрес указывает на экземпляр класса String, расположенный в куче.
Есть несколько способов подсчитать, сколько байтов занимает строковый объект в куче: версия Джона Скита и версия Тимура Гева (последняя статья на русском языке). На картинке выше я использовал второй вариант. Даже если эта формула не верна на 100%, мы все равно можем оценить размер строковых объектов. Например, около 4,7 миллиона строк (каждая по 100 символов) достаточно, чтобы занять 1 ГБ ОЗУ. Допустим, в программе есть большое количество дубликатов среди строк. Так что просто стоит использовать встроенные в фреймворк функции интернирования. А теперь почему бы нам вкратце не повторить, что такое интернирование струн?
Интернирование строк
Идея интернирования строк состоит в том, чтобы сохранить в памяти только один экземпляр типа String для идентичных строк. При запуске приложения виртуальная машина создает внутреннюю хеш-таблицу, называемую таблицей интернирования (иногда ее называют пулом строк). В этой таблице хранятся ссылки на каждый уникальный строковый литерал, объявленный в программе. Кроме того, используя два описанных ниже метода, мы можем самостоятельно получать и добавлять ссылки на строковые объекты в эту таблицу. Если приложение содержит множество строк (которые часто идентичны), нет смысла каждый раз создавать новый экземпляр класса String. Вместо этого вы можете просто сослаться на экземпляр типа String, который уже был создан в куче. Чтобы получить ссылку на него, откройте таблицу интернирования. Виртуальная машина сама стажирует все строковые литералы в коде (подробнее о приемах интернирования читайте в этой статье). Мы можем выбрать один из двух методов: String.Intern и String.IsInterned.
Первый принимает на вход строку. Если в таблице интернирования есть идентичная строка, она возвращает ссылку на объект типа String, который уже существует в куче. Если такой строки в таблице нет, ссылка на этот строковый объект добавляется в таблицу интернирования. Затем он возвращается из метода. Метод IsInterned также принимает строку в качестве входных данных и возвращает ссылку из таблицы интернирования на существующий объект. Если такого объекта нет, возвращается null (все знают о неинтуитивном возвращаемом значении этого метода).
Используя интернирование, мы уменьшаем количество новых строковых объектов, работая с существующими через ссылки, полученные с помощью метода Intern. Таким образом, мы не создаем большого количества новых объектов. Итак, мы экономим память и повышаем производительность программы. Ведь многие строковые объекты, ссылки на которые быстро исчезают из стека, могут привести к частой сборке мусора. Это негативно скажется на общей производительности программы. Интернированные строки не исчезнут до конца процесса, даже если ссылок на эти объекты больше нет в программе. На эту вещь стоит обратить внимание. Использование интернирования для уменьшения потребления памяти может дать противоположный эффект.
Интернирование строк может повысить производительность при сравнении этих самых строк. Давайте посмотрим на реализацию метода String.Equals:
public bool Equals(String value)
{
if (this == null)
throw new NullReferenceException();
if (value == null)
return false;
if (Object.ReferenceEquals(this, value))
return true;
if (this.Length != value.Length)
return false;
return EqualsHelper(this, value);
}Перед вызовом метода EqualsHelper, в котором выполняется посимвольное сравнение строк, метод Object.ReferenceEquals проверяет равенство ссылок. Если строки интернированы, метод Object.ReferenceEquals возвращает true, когда строки равны (без сравнения самих строк посимвольно). Конечно, если ссылки не равны, будет вызван метод EqualsHelper и последующее посимвольное сравнение будет происходить. В конце концов, метод Equals не знает, что мы работаем с интернированными строками. Кроме того, если метод ReferenceEquals возвращает false, мы знаем, что сравниваемые строки отличаются.
Если вы уверены, что входные строки интернированы в определенном месте программы, вы можете сравнить их с помощью метода Object.ReferenceEquals. Однако это не лучший подход. Всегда есть шанс, что код изменится в будущем. Также его можно повторно использовать в другой части программы. Так что в него могут попасть не интернированные строки. В этом случае при сравнении двух идентичных неинтернированных строк с помощью метода ReferenceEquals мы будем предполагать, что они не идентичны.
Интернирование строк для последующего сравнения кажется оправданным только в том случае, если вы планируете довольно часто сравнивать интернированные строки. Помните, что интернирование всего набора строк также требует времени. Поэтому не следует выполнять это для однократного сравнения нескольких экземпляров строк.
Что ж, мы пересмотрели, что такое интернирование струн. А теперь перейдем к проблеме, с которой я столкнулся.
Кратко о том, как это началось
В нашем багтрекере уже давно была создана задача. Потребовалось некоторое исследование того, как распараллеливание анализа кода C ++ может сэкономить время анализа. Было бы здорово, если бы анализатор PVS-Studio работал параллельно на нескольких машинах при анализе одного проекта. Я выбрал IncrediBuild в качестве программного обеспечения, которое позволяет такое распараллеливание. IncrediBuild позволяет запускать разные процессы параллельно на машинах, расположенных в одной сети. Например, вы можете распараллелить исходные файлы, компилируемые на разных компьютерах компании (или в облаке). Таким образом, мы экономим время на процессе строительства. Разработчики игр часто используют эту программу.
Что ж, я начал работать над этой задачей. Сначала я выбрал проект и проанализировал его с помощью PVS-Studio на своей машине. Затем я провел анализ с помощью IncrediBuild, распараллеливая процессы анализатора на машинах компании. В конце я подвел итоги такого распараллеливания. Так что, имея положительный результат, мы предложим своим клиентам такие решения для ускорения анализа.
Я выбрал проект Unreal Tournament. Нам удалось убедить программистов установить IncrediBuild на свои машины. В итоге у нас получился объединенный кластер примерно из 145 ядер.
Я проанализировал проект Unreal Tournament с помощью системы мониторинга компиляции в PVS-Studio. Итак, я работал следующим образом: я запускал программу CLMonitor.exe в режиме монитора и выполнил полную сборку Unreal Tournament в Visual Studio. Затем, после сборки, я снова запустил CLMonitor.exe, но уже в режиме запуска анализа. В зависимости от значения, указанного в настройках PVS-Studio для параметра ThreadCount, CLMonitor.exe одновременно запускает соответствующее количество дочерних процессов PVS-Studio.exe. Эти процессы занимаются анализом каждого отдельного исходного файла C ++. Один дочерний процесс PVS-Studio.exe анализирует один исходный файл. После анализа он передает результаты обратно в CLMonitor.exe.
Все просто: в настройках PVS-Studio я выставил параметр ThreadCount равным количеству доступных ядер (145). Я провожу анализ, готовясь к 145 процессам PVS-Studio.exe, выполняемым параллельно на удаленных машинах. IncrediBuild имеет Build Monitor, удобную систему мониторинга распараллеливания. С его помощью вы можете наблюдать за процессами, запущенными на удаленных машинах. То же самое я наблюдал в процессе анализа:
Казалось, что нет ничего проще. Расслабьтесь и наблюдайте за процессом анализа. Затем просто запишите его продолжительность с помощью IncrediBuild и без него. Однако на практике это оказалось немного сложнее ...
Сама проблема, ее местонахождение и решение
Во время анализа я мог переключиться на другие задачи. Я также мог бы просто поразмышлять, глядя на PVS-Studio.exe, запущенный в окне Build Monitor. Когда анализ с IncrediBuild закончился, я сравнил его продолжительность с результатами анализа без IncrediBuild. Разница была значительной. Однако общий результат мог быть лучше. Это было 182 минуты на одной машине с 8 потоками и 50 минут при использовании IncrediBuild с 145 потоками. Оказалось, что количество потоков увеличилось в 18 раз. Между тем время анализа сократилось всего в 3,5 раза. Наконец, я увидел результат в окне «Монитор сборки». Просматривая отчет, я заметил кое-что странное. Вот что я увидел на графике:
Я заметил, что PVS-Studio.exe успешно завершился. Но потом по какой-то причине процесс приостановился перед запуском следующего. Это происходило снова и снова. Пауза за паузой. Эти простои привели к заметной задержке и сыграли свою роль в увеличении времени анализа. Сначала я винил IncrediBuild. Наверное выполняет какую-то внутреннюю синхронизацию и тормозит запуск.
Я поделился результатами со своим старшим коллегой. Он не делал поспешных выводов. Он предложил посмотреть, что происходит внутри нашего приложения CLMonitor.exe, когда время простоя отображается на графике. Я снова провел анализ. Затем я заметил первый очевидный «провал» на графике. Я подключился к процессу CLMonitor.exe через отладчик Visual Studio и приостановил его. Открыв темы, мы с коллегой увидели около 145 приостановленных тем. Просматривая места в коде, где выполнение приостанавливалось, мы увидели строки кода с похожим содержанием:
....
return String.Intern(settings == null ? path
: settings
.TransformToRelative(path.Replace("/", "\\"),
solutionDirectory));
....
analyzedSourceFiles.Add( String.Intern(settings
.TransformPathToRelative(analyzedSourceFilePath,
solutionDirectory))
);
....Что общего у этих строк? Каждый из них использует метод String.Intern. И это кажется оправданным. Потому что именно здесь CLMonitor.exe обрабатывает данные из процессов PVS-Studio.exe. Данные записываются в объекты типа ErrorInfo, которые инкапсулируют информацию о потенциальной ошибке, обнаруженной анализатором. Также мы усваиваем вполне разумные вещи, а именно пути к исходным файлам. Один исходный файл может содержать много ошибок, поэтому для объектов ErrorInfo нет смысла содержать разные строковые объекты с одинаковым содержанием. Достаточно просто сослаться на один объект из кучи.
Не задумываясь, я понял, что интернирование строк было применено не в тот момент. Итак, вот ситуация, которую мы наблюдали в отладчике. По какой-то причине 145 потоков зависали при выполнении метода String.Intern. Между тем, настраиваемый планировщик задач LimitedConcurrencyLevelTaskScheduler внутри CLMonitor.exe не мог запустить новый поток, который позже запустил бы новый процесс PVS-Studio.exe. Тогда IncrediBuild уже запустил бы этот процесс на удаленном компьютере. В конце концов, с точки зрения планировщика, поток еще не завершил свое выполнение. Он выполняет преобразование полученных данных от PVS-Studio.exe в ErrorInfo с последующим интернированием строки. Завершение процесса PVS-Studio.exe ничего не значит для потока. Удаленные машины простаивают. Тема все еще активна. Также мы устанавливаем лимит в 145 потоков, что не позволяет планировщику запускать новый.
Большее значение параметра ThreadCount не решит проблему. Это только увеличило бы очередь потоков, зависающих при выполнении метода String.Intern.
Мы вообще не хотели убирать интернирование. Это увеличит объем оперативной памяти, потребляемой CLMonitor.exe. В итоге мы нашли довольно простое и элегантное решение. Мы решили перенести интернирование из потока, в котором запускается PVS-Studio.exe, на несколько более позднее место выполнения кода (в потоке, который непосредственно генерирует отчет об ошибке).
Как сказал мой коллега, нам удалось очень точно отредактировать всего две строчки. Таким образом, мы решили проблему с простаивающими удаленными машинами. Итак, мы снова провели анализ. Между запусками PVS-Studio.exe не было значительных временных интервалов. Время анализа уменьшилось с 50 минут до 26, то есть почти вдвое. Теперь давайте посмотрим на общий результат, который мы получили при использовании IncrediBuild и 145 доступных ядер. Общее время анализа уменьшилось в 7 раз. Это намного лучше, чем в 3,5 раза.
String.Intern - почему он такой медленный? Обзор кода CoreCLR
Стоит отметить, что как только мы увидели, что потоки висят в местах, где мы вызываем метод String.Intern, мы почти сразу подумали, что под капотом этого метода есть критическая секция с какой-то блокировкой. Поскольку каждый поток может писать в таблицу интернирования, внутри метода String.Intern должен быть какой-то механизм синхронизации. Это предотвращает перезапись данных друг друга несколькими потоками. Чтобы подтвердить мои предположения, мы решили взглянуть на реализацию метода String.Intern на справочном источнике. Мы заметили, что внутри нашего метода интернирования был вызов метода Thread.GetDomain (). GetOrInternString (str). Что ж, взгляните на его реализацию:
internal extern String GetOrInternString(String str);Теперь становится интереснее. Этот метод импортирован из какой-то другой сборки. Который из? Поскольку виртуальная машина CLR сама выполняет интернирование строк, мой коллега направил меня прямо в репозиторий времени выполнения .NET. Скачав репозиторий, мы перешли к решению CoreCLR. Мы открыли его и просмотрели все решение. Там мы нашли метод GetOrInternString с соответствующей сигнатурой:
STRINGREF *BaseDomain::GetOrInternString(STRINGREF *pString)Итак, мы увидели вызов метода GetInternedString. В теле этого метода мы заметили следующий код:
....
if (m_StringToEntryHashTable->GetValue(&StringData, &Data, dwHash))
{
STRINGREF *pStrObj = NULL;
pStrObj = ((StringLiteralEntry*)Data)->GetStringObject();
_ASSERTE(!bAddIfNotFound || pStrObj);
return pStrObj;
}
else
{
CrstHolder gch(&(SystemDomain::GetGlobalStringLiteralMap()
->m_HashTableCrstGlobal));
....
// Make sure some other thread has not already added it.
if (!m_StringToEntryHashTable->GetValue(&StringData, &Data))
{
// Insert the handle to the string into the hash table.
m_StringToEntryHashTable->InsertValue(&StringData, (LPVOID)pEntry, FALSE);
}
....
}
....Поток выполнения попадает в ветвь else только в том случае, если метод, который ищет ссылку на объект String (метод GetValue) в интернировании table возвращает false. Перейдем к коду в ветке else. Здесь нас интересует строка, в которой создается объект типа CrstHolder с именем gch. Теперь обратимся к конструктору CrstHolder и увидим следующий код:
inline CrstHolder(CrstBase * pCrst)
: m_pCrst(pCrst)
{
WRAPPER_NO_CONTRACT;
AcquireLock(pCrst);
}Мы замечаем вызов метода AcquireLock. Становится лучше. Вот код метода AcquireLock:
DEBUG_NOINLINE static void AcquireLock(CrstBase *c)
{
WRAPPER_NO_CONTRACT;
ANNOTATION_SPECIAL_HOLDER_CALLER_NEEDS_DYNAMIC_CONTRACT;
c->Enter();
}Фактически, это точка входа в критический раздел - вызов метода Enter. После того, как я прочитал комментарий «Получите блокировку», у меня не осталось сомнений, что этот метод имеет дело с блокировкой. Я не видел особого смысла углубляться в код CoreCLR. Итак, мы были правы. Когда новая запись вводится в таблицу интернирования, поток входит в критическую секцию, заставляя все другие потоки ждать снятия блокировки. Непосредственно перед вызовом метода m_StringToEntryHashTable- ›InsertValue выходит объект типа CrstHolder, и поэтому появляется критический раздел.
Блокировка исчезает сразу после выхода из ветви else. В этом случае деструктор, вызывающий метод ReleaseLock, вызывается для объекта gch:
inline ~CrstHolder()
{
WRAPPER_NO_CONTRACT;
ReleaseLock(m_pCrst);
}Когда потоков мало, время простоя может быть небольшим. Но когда их количество увеличивается, например, до 145 (как это произошло с IncrediBuild), каждый поток, который пытается добавить новую запись в таблицу интернирования, временно блокирует другие 144 потока, которые также пытаются добавить в нее новую запись. Результаты этих блокировок мы наблюдали в окне Build Monitor.
Заключение
Я надеюсь, что этот случай поможет вам более тщательно и осмысленно применить интернирование строк, особенно в многопоточном коде. Ведь эти блокировки, добавляющие новые записи в таблицу интернирования, могут стать узким местом, как в нашем случае. Здорово, что нам удалось узнать правду и решить обнаруженную проблему. Это заставило анализатор работать быстрее.
Спасибо за чтение.
