Публикую на Хабр оригинал статьи, перевод которой размещен в блоге Codingsight.
Это вторая статья в цикле о жизни разработчиков IDE для баз данных. Ее структура будет похожа на первую. Как и в первой я расскажу о проблемах с которыми мы сталкивались, решениях успешных и не очень. Для понимания этой статьи не обязательно читать первую часть полностью, но первые несколько параграфов были бы полезны, для погружения в контекст.
Для ленивых основные тезисы первой статьи:
По мере публикации буду добавлять ссылки на следующие части:
Часть 1. Сложности парсинга. Истории о доработке ANTLR напильником
Часть 2. Оптимизация работы со строками и открытия файлов
Часть 3. Жизнь расширений для Visual Studio. Работа с IO. Необычное использование SQL
Часть 4. Работа с исключениями, влияние данных на процесс разработки. Использование ML.NET
В этой части я сосредоточусь на проблемах при работе со строками. Одно из самых критичных мест при работе со строками для нас — это стадия лексического анализа текста, когда скрипт разбивается на слова.
Крутые
Прошлая статья почти полностью сосредоточена на проблемах парсинга SQL кода. Для решения этих проблем мы используем ANTLR, с которым пришлось немало поработать. ANTLR это инструмент, что на вход принимает формальное описание языка в виде грамматики описанной специальным образом, на выход отдает парсер на одном из доступных языков. В какой-то момент генерируемый парсер вырос до таких размеров, что мы стали боятся его дебажить.
Почему? А потому, что стоило неудачно нажать F11(step-into) при отладке, попасть в файл парсера и Visual Studio просто схлопывалась. Подключившись одной VS к другой мы выяснили, что она падает с OutOfMemoryException во время анализа этого файла. Файл парсера состоял из более чем 200 тысяч строк кода. К сожалению, отладка парсера это неотъемлемая часть работы. Мы не могли просто не смотреть туда. К счастью C# поддерживает partial-классы. Таким образом уже сгенерированный парсер, мы анализировали регулярными выражениями и раскладывали по нескольким файлам. В результате удалось сократить размер основного файла примерно наполовину, после чего Visual Studio работала безупречно.
В .NET недавно появилось API для работы с подстроками и подмассивами без лишних аллокаций. К сожалению, задача оптимизировать лексический анализ появилась у нас задолго до этого. Задача лексического анализа — определение границ слов и их сопоставление со словарем — классификация. Изначально эта задача была решена у нас в лоб: цикл ходил по строке, встречая последовательность букв, шел до разделителя, обрезал при помощи Substring, приводил строку в нижний регистр, искал в словаре. Если слово было найдено, то лексер возвращал его индекс, иначе считал это слово идентификатором объекта. Это немного упрощенное описание алгоритма, чтобы быстро передать суть, не вдаваясь в подробности.
Результаты профилировки показали, что немалую часть времени занимали Substring и ToLower, в то время как поиск по словарю работал невероятно быстро. Было необходимо как-то оптимизировать это бутылочное горлышко. У нас получилось довольно круто прокачать метод ToLower используя тот факт, что в ключевых словах была только латиница. Результат был заметным, но недостаточным. Внезапно появилась идея разложить словарь в 26-ричное дерево, где индекс в массиве под-услов соответствует положению буквы в английском алфавите. Проходя по строке мы совершаем навигацию по такому дереву. Если на момент окончания слова значение номера токена в текущем узле отлично от нуля, значит в языке есть соответствующий keyword, если нет, то вероятно, это идентификатор пользовательского объекта. Такой трюк ускорил лексический разбор примерно на 30%.
Было бы интересно вернуться к оптимизации лексера с новыми знаниями и новыми инструментами. Уверен оттуда можно выжать еще немного. Например, где-то спустя пол года после решения этой задачи стала набирать популярность библиотека BenchmarkDotNet. Она органично влилась в workflow любой оптимизации: после того как при помощи профилировщика найдено бутылочное горлышко, создается бенчмарк, метод переписывается много раз, пока не достигается необходимый результат. Что удивляет, так это то, что результаты часто очень не очевидны.
Я уже писал, что люди работающие с SQL часто работают с большими файлами. Чего уж там, парсер на CSharp в 200 тысяч строк это нечто из ряда вон выходящее, с другой стороны дамп базы данных на полмиллиона никого даже не удивит. Встраиваясь в VS и SSMS мы не лезем в нативные механизм подсветки кода, но в наших standalone тулах нам приходится решать эту задачу. К счастью, мы работаем в 64 битном адресном пространстве и можем открыть даже очень большие файлы, если у пользователя окажется достаточно оперативной памяти. Только вряд ли кто-то будет рад ждать открытия такого файла слишком долго, верно? В одной из версий нам удалось существенно ускорить открытие файлов с помощью нескольких хитрых трюков. Раскраска текста происходит на основе лексического анализа. Эта операция, как правило, существенно медленнее чтения текста с диска. В чем же трюк? В одном потоке начинается чтение текста из файла, во второй его лексический разбор. Лексер запрашивает текст построчно и если он запросит строку, которой еще нет, то повиснет в ожидании. По этому принципу работает BlockingCollection<T> из BCL, а алгоритм является типичным применением многопоточного паттерна Producer-Consumer. Редактор, работающий в главном потоке запрашивает данные о первой раскрашенной строчки, если она недоступна, то повисает в ожидании. По сути producer-consumer и blocking-collection применены дважды:
Такой набор трюков позволил существенно сократить время открытия больших файлов. Первая страница документа показывается очень быстро, впрочем если пользователь в первую же секунду попытается переместиться в самый конец файла документ на некоторое время подвиснет, пока фоновый лексинг и фоновое чтение не дойдут до конца, но если вы работаете с началом документа или двигаетесь к концу постепенно, то даже не заметите этих фризов.
Синтаксический анализ разделяют на две части:
Работа со строками традиционно считается дорогостоящей операцией. У нас была идея как это оптимизировать: не делать полный лексический разбор текста каждый раз, а заново проанализировать лишь изменившуюся часть. Тут может возникнуть вопрос, а что делать с многострочными конструкциями, вроде блочных комментариев или строк? Для этого был интересный трюк — для каждой строки хранилось состояние для конца строки: “нет многострочных токенов” = 0, “начался блочный комментарий” = 1, “начался многострочный строковый литерал” = 2. Лексический разбор проводится от измененного участка и до того как не сойдется состояние на конце строки.
Звучит неплохо, не так ли? Так что же такого неочевидного в этой истории? Ей место в блоке с крутыми трюками. Сперва мы попробовали упаковать результаты разбора в легковесные промежуточные структуры: 2 байта на смещение в строке, 2 байта на тип токена, 2 байта на длину и сложить их в объект. На основе таких структур, на лету, для парсера создавались полноценные экземпляры класса Token из ANTLR. Померяли все, прирост производительности оказался менее 5%. Результаты профилировки стали еще более размазанными, не было видно никакого бутылочного горлышка, разве что оператор new занимал довольно много времени. С большой грустью ушли домой, на выходные. Как это часто бывает, когда всю неделю плотно работал над какой-то задачей, не доведя ее до логического решения, она продолжает вращаться в голове. В понедельник появилась идея отказаться от промежуточных структур и хранить сразу объекты Token. Идя на это мы понимали, что это займет больше оперативной памяти, чем легковесные структуры. Мы понимали, что число занимает в памяти меньше строки, но не удосужились в тот момент все тщательно просчитать. В этом решении была еще одна проблема: крайне неудобно следить за номерами строк в таких структурах, а номер строки является обязательным атрибутом ANTLR Token, ведь при вставки или удалении строки придется обновлять номера строк в каждом токене, что идет ниже. Решением этой проблемы стало проставление номера строки на лету, перед выдачей токена парсеру. Мы провели некоторые тесты, получили прирост производительности составил 15-25%. Здесь необходимо пояснить, что фактический прирост даже больше. Некоторые функции, например Quick Info, чья работа была завязана лишь на лексический анализ работали мгновенно. Quick Info — функциональность доступная в каждом продукте линейки, это та самая всплывающая подсказка с информацией об объекте при наведении курсора на его идентификатор в скрипте. Выигрыш оказывался фактически больше, когда требовалось совершить несколько проходов по токенам.
Количество оперативной памяти необходимое для такого отражения текста оказалось существенно больше чем мы ожидали. ANTLR Token состоял из: точки начала — 8 байт, точки конца — 8 байт, ссылки на текст слова — 4 или 8 байт, не говоря уже о самой строке, ссылки на текст документа — 4 или 8 байт, типа токена 4 байта. Важно сказать, что чаще всего токены не хранили свой текст, а лишь высчитывали его по необходимости, лишь в некоторых случаях текст кешировался. Кроме того это был класс, а не структура, а это означает еще ряд расходов. Общий размер всего объекта получился в несколько раз больше изначального размера текста. Поняли мы это значительно позже. Мало кто ожидает большого перерасхода памяти от класса с несколькими int`овыми полями. В теории, на скрипте с крайне длинными именами объектов и литералами мы могли бы получить даже какой-то выигрыш по памяти. Примерно с 30 символов на слово, такой способ представления скрипта даже становится выгодным.
Какие выводы? С одной стороны выигрыш производительности изначально получился ниже чем хотелось получить. Бутылочное горлышко казалось очевидным. Сфокусировались на производительности, получили перерасход по памяти, там где это не было очевидно. Нельзя сказать, что мы этого совсем не ожидали, но мы не предположили, ведь мы даже изначально пытались использовать легковесные структуры, вместо классов. Заменяя их полноценными объектами мы осознанно шли на дополнительный расход памяти, ради получения выигрыша в производительности. Проблема в том, что мы не сели и скрупулезно не посчитали сколько будет занимать такой класс. Но о том, что кучка int’ов может съесть так много памяти задумываешься, все таки не часто. К счастью, это послужило для нас важным уроком и теперь каждая оптимизация производительности заканчивается снятием профиля памяти и наоборот.
Изначально я хотел отнести эту историю к категории ошибок, но работая над текстом, поднимая переписки, общаясь с участниками, я переосмыслил свое отношение к ней. Это поучительная история, но ее итог все таки можно причислить к победам, ведь некоторые функции стали работать молниеносно, другие просто быстрее. В конце концов, невозможно было бы провернуть трюк с фоновым лексическим анализом, не существуй структуры куда бы один из потоков мог эти токены складывать.
Еще одно: полезно иногда останавливаться перед внедрением нового решение и еще раз в голове подумать о предположениях на которых оно строится, особенно на очевидных, еще раз вспомнить почему они кажутся такими очевидными.
Промежуточные итоги могут быть следующими:
Что будет в этой статье?
Это вторая статья в цикле о жизни разработчиков IDE для баз данных. Ее структура будет похожа на первую. Как и в первой я расскажу о проблемах с которыми мы сталкивались, решениях успешных и не очень. Для понимания этой статьи не обязательно читать первую часть полностью, но первые несколько параграфов были бы полезны, для погружения в контекст.
Для ленивых основные тезисы первой статьи:
- Мы делаем линейку IDE для СУБД MySQL, SQL Server, Oracle, PostgreSQL
- Это настольное приложение на .NET стеке со всеми вытекающими
- Много функций завязаны на анализ SQL кода. Используем для этого сильно доработанный ANTLR
По мере публикации буду добавлять ссылки на следующие части:
Часть 1. Сложности парсинга. Истории о доработке ANTLR напильником
Часть 2. Оптимизация работы со строками и открытия файлов
Часть 3. Жизнь расширений для Visual Studio. Работа с IO. Необычное использование SQL
Часть 4. Работа с исключениями, влияние данных на процесс разработки. Использование ML.NET
В этой части я сосредоточусь на проблемах при работе со строками. Одно из самых критичных мест при работе со строками для нас — это стадия лексического анализа текста, когда скрипт разбивается на слова.
Крутые велосипеды решения
OutOfMemory в Visual Studio и постпроцессинг ANTLR парсера
Прошлая статья почти полностью сосредоточена на проблемах парсинга SQL кода. Для решения этих проблем мы используем ANTLR, с которым пришлось немало поработать. ANTLR это инструмент, что на вход принимает формальное описание языка в виде грамматики описанной специальным образом, на выход отдает парсер на одном из доступных языков. В какой-то момент генерируемый парсер вырос до таких размеров, что мы стали боятся его дебажить.
Почему? А потому, что стоило неудачно нажать F11(step-into) при отладке, попасть в файл парсера и Visual Studio просто схлопывалась. Подключившись одной VS к другой мы выяснили, что она падает с OutOfMemoryException во время анализа этого файла. Файл парсера состоял из более чем 200 тысяч строк кода. К сожалению, отладка парсера это неотъемлемая часть работы. Мы не могли просто не смотреть туда. К счастью C# поддерживает partial-классы. Таким образом уже сгенерированный парсер, мы анализировали регулярными выражениями и раскладывали по нескольким файлам. В результате удалось сократить размер основного файла примерно наполовину, после чего Visual Studio работала безупречно.
Лексический анализ без substring до Span API
В .NET недавно появилось API для работы с подстроками и подмассивами без лишних аллокаций. К сожалению, задача оптимизировать лексический анализ появилась у нас задолго до этого. Задача лексического анализа — определение границ слов и их сопоставление со словарем — классификация. Изначально эта задача была решена у нас в лоб: цикл ходил по строке, встречая последовательность букв, шел до разделителя, обрезал при помощи Substring, приводил строку в нижний регистр, искал в словаре. Если слово было найдено, то лексер возвращал его индекс, иначе считал это слово идентификатором объекта. Это немного упрощенное описание алгоритма, чтобы быстро передать суть, не вдаваясь в подробности.
Результаты профилировки показали, что немалую часть времени занимали Substring и ToLower, в то время как поиск по словарю работал невероятно быстро. Было необходимо как-то оптимизировать это бутылочное горлышко. У нас получилось довольно круто прокачать метод ToLower используя тот факт, что в ключевых словах была только латиница. Результат был заметным, но недостаточным. Внезапно появилась идея разложить словарь в 26-ричное дерево, где индекс в массиве под-услов соответствует положению буквы в английском алфавите. Проходя по строке мы совершаем навигацию по такому дереву. Если на момент окончания слова значение номера токена в текущем узле отлично от нуля, значит в языке есть соответствующий keyword, если нет, то вероятно, это идентификатор пользовательского объекта. Такой трюк ускорил лексический разбор примерно на 30%.
Было бы интересно вернуться к оптимизации лексера с новыми знаниями и новыми инструментами. Уверен оттуда можно выжать еще немного. Например, где-то спустя пол года после решения этой задачи стала набирать популярность библиотека BenchmarkDotNet. Она органично влилась в workflow любой оптимизации: после того как при помощи профилировщика найдено бутылочное горлышко, создается бенчмарк, метод переписывается много раз, пока не достигается необходимый результат. Что удивляет, так это то, что результаты часто очень не очевидны.
Фоновый лексинг во время открытия файла
Я уже писал, что люди работающие с SQL часто работают с большими файлами. Чего уж там, парсер на CSharp в 200 тысяч строк это нечто из ряда вон выходящее, с другой стороны дамп базы данных на полмиллиона никого даже не удивит. Встраиваясь в VS и SSMS мы не лезем в нативные механизм подсветки кода, но в наших standalone тулах нам приходится решать эту задачу. К счастью, мы работаем в 64 битном адресном пространстве и можем открыть даже очень большие файлы, если у пользователя окажется достаточно оперативной памяти. Только вряд ли кто-то будет рад ждать открытия такого файла слишком долго, верно? В одной из версий нам удалось существенно ускорить открытие файлов с помощью нескольких хитрых трюков. Раскраска текста происходит на основе лексического анализа. Эта операция, как правило, существенно медленнее чтения текста с диска. В чем же трюк? В одном потоке начинается чтение текста из файла, во второй его лексический разбор. Лексер запрашивает текст построчно и если он запросит строку, которой еще нет, то повиснет в ожидании. По этому принципу работает BlockingCollection<T> из BCL, а алгоритм является типичным применением многопоточного паттерна Producer-Consumer. Редактор, работающий в главном потоке запрашивает данные о первой раскрашенной строчки, если она недоступна, то повисает в ожидании. По сути producer-consumer и blocking-collection применены дважды:
- Чтение из файла — Producer, лексер — Consumer
- Лексер уже является Producer, а текстовый редактор — Consumer
Такой набор трюков позволил существенно сократить время открытия больших файлов. Первая страница документа показывается очень быстро, впрочем если пользователь в первую же секунду попытается переместиться в самый конец файла документ на некоторое время подвиснет, пока фоновый лексинг и фоновое чтение не дойдут до конца, но если вы работаете с началом документа или двигаетесь к концу постепенно, то даже не заметите этих фризов.
Неочевидные победы
Неоднозначная оптимизация: частичный лексический анализ
Синтаксический анализ разделяют на две части:
- входящий поток символов разбивается на слова(token’ы) в рамках правил языка — это называют лексическим анализом;
- парсер идет уже по потоку token’ов, проверяя на соответствие правилам, часто строит синтаксическое дерево.
Работа со строками традиционно считается дорогостоящей операцией. У нас была идея как это оптимизировать: не делать полный лексический разбор текста каждый раз, а заново проанализировать лишь изменившуюся часть. Тут может возникнуть вопрос, а что делать с многострочными конструкциями, вроде блочных комментариев или строк? Для этого был интересный трюк — для каждой строки хранилось состояние для конца строки: “нет многострочных токенов” = 0, “начался блочный комментарий” = 1, “начался многострочный строковый литерал” = 2. Лексический разбор проводится от измененного участка и до того как не сойдется состояние на конце строки.
Звучит неплохо, не так ли? Так что же такого неочевидного в этой истории? Ей место в блоке с крутыми трюками. Сперва мы попробовали упаковать результаты разбора в легковесные промежуточные структуры: 2 байта на смещение в строке, 2 байта на тип токена, 2 байта на длину и сложить их в объект. На основе таких структур, на лету, для парсера создавались полноценные экземпляры класса Token из ANTLR. Померяли все, прирост производительности оказался менее 5%. Результаты профилировки стали еще более размазанными, не было видно никакого бутылочного горлышка, разве что оператор new занимал довольно много времени. С большой грустью ушли домой, на выходные. Как это часто бывает, когда всю неделю плотно работал над какой-то задачей, не доведя ее до логического решения, она продолжает вращаться в голове. В понедельник появилась идея отказаться от промежуточных структур и хранить сразу объекты Token. Идя на это мы понимали, что это займет больше оперативной памяти, чем легковесные структуры. Мы понимали, что число занимает в памяти меньше строки, но не удосужились в тот момент все тщательно просчитать. В этом решении была еще одна проблема: крайне неудобно следить за номерами строк в таких структурах, а номер строки является обязательным атрибутом ANTLR Token, ведь при вставки или удалении строки придется обновлять номера строк в каждом токене, что идет ниже. Решением этой проблемы стало проставление номера строки на лету, перед выдачей токена парсеру. Мы провели некоторые тесты, получили прирост производительности составил 15-25%. Здесь необходимо пояснить, что фактический прирост даже больше. Некоторые функции, например Quick Info, чья работа была завязана лишь на лексический анализ работали мгновенно. Quick Info — функциональность доступная в каждом продукте линейки, это та самая всплывающая подсказка с информацией об объекте при наведении курсора на его идентификатор в скрипте. Выигрыш оказывался фактически больше, когда требовалось совершить несколько проходов по токенам.
Количество оперативной памяти необходимое для такого отражения текста оказалось существенно больше чем мы ожидали. ANTLR Token состоял из: точки начала — 8 байт, точки конца — 8 байт, ссылки на текст слова — 4 или 8 байт, не говоря уже о самой строке, ссылки на текст документа — 4 или 8 байт, типа токена 4 байта. Важно сказать, что чаще всего токены не хранили свой текст, а лишь высчитывали его по необходимости, лишь в некоторых случаях текст кешировался. Кроме того это был класс, а не структура, а это означает еще ряд расходов. Общий размер всего объекта получился в несколько раз больше изначального размера текста. Поняли мы это значительно позже. Мало кто ожидает большого перерасхода памяти от класса с несколькими int`овыми полями. В теории, на скрипте с крайне длинными именами объектов и литералами мы могли бы получить даже какой-то выигрыш по памяти. Примерно с 30 символов на слово, такой способ представления скрипта даже становится выгодным.
Какие выводы? С одной стороны выигрыш производительности изначально получился ниже чем хотелось получить. Бутылочное горлышко казалось очевидным. Сфокусировались на производительности, получили перерасход по памяти, там где это не было очевидно. Нельзя сказать, что мы этого совсем не ожидали, но мы не предположили, ведь мы даже изначально пытались использовать легковесные структуры, вместо классов. Заменяя их полноценными объектами мы осознанно шли на дополнительный расход памяти, ради получения выигрыша в производительности. Проблема в том, что мы не сели и скрупулезно не посчитали сколько будет занимать такой класс. Но о том, что кучка int’ов может съесть так много памяти задумываешься, все таки не часто. К счастью, это послужило для нас важным уроком и теперь каждая оптимизация производительности заканчивается снятием профиля памяти и наоборот.
Изначально я хотел отнести эту историю к категории ошибок, но работая над текстом, поднимая переписки, общаясь с участниками, я переосмыслил свое отношение к ней. Это поучительная история, но ее итог все таки можно причислить к победам, ведь некоторые функции стали работать молниеносно, другие просто быстрее. В конце концов, невозможно было бы провернуть трюк с фоновым лексическим анализом, не существуй структуры куда бы один из потоков мог эти токены складывать.
Еще одно: полезно иногда останавливаться перед внедрением нового решение и еще раз в голове подумать о предположениях на которых оно строится, особенно на очевидных, еще раз вспомнить почему они кажутся такими очевидными.
Заключение
Промежуточные итоги могут быть следующими:
- Проблемы в работе инструментов разработчика могут быть неприятны и существенно мешать всему процессу. Нужно находить их проблемы и решать как можно быстрее
- Новые версии .NET дают нам новые крутые возможности. Возможно есть смысл вернуться к задачам решенным в прошлом и попробовать зайти с новыми инструментами
- Любая оптимизация состоит из двух частей: поиск бутылочного горлышка, для этого отлично подходят профилировщике и его оптимизация, для этого удобно создавать бенчмарки
- Не стоит оптимизировать без тщательного профилирования, даже если вы знаете где узкое место, полезно понять максимально возможный потенциал для оптимизации
- Когда счет идет на миллионы объектов, каждый байт решает
- После успешной оптимизации производительности, снимите профиль использования оперативной памяти и наоборот