Ещё Достоевский на примере своих героев-картёжников показал: быть должником — удовольствие сомнительное в любую эпоху. В разработке тоже есть своя «долговая яма» —технический долг. Если продукт большой и развивается годами, полностью избежать его невозможно. Функциональность реализована, всё математически корректно работает, но из-за накопившихся архитектурных компромиссов всё сложнее укладываться в пользовательские ожидания по скорости и отзывчивости.
Меня зовут Дмитрий Шубин, я занимаюсь оптимизацией производительности в компании МойОфис — конкретно в Ядре редакторов (о нём ранее рассказывал мой коллега в статье «Как мы создаём редакторы документов. Ядро и его роль в кроссплатформенной разработке»).
Ядро — основа редакторов на любой платформе, и именно здесь чаще всего концентрируются проблемы производительности. В этой статье разберём, почему возникает такой долг и как мы с ним работаем на практическом примере оптимизации редактора «МояТаблица».
Почему образуется такой техдолг
Факторов много. Сначала важно реализовать функциональность максимально понятным и надёжным способом. Совсем плохие решения не проходят на ранних этапах, при этом заниматься преждевременной оптимизацией всего кода не является хорошей практикой. Продукт развивается, доработки наслаиваются друг на друга, появляются новые сценарии использования. И так, по мере развития продукта, узкие места начинают проявляться — на код-ревью, в тестировании или в реальных пользовательских сценариях, которые могут быть непредвиденными на этапе разработки.
Поэтому чаще всего мы исходим из существующего состояния системы и постепенно улучшаем наиболее проблемные участки. О том, как в целом устроен процесс работы с производительностью (измерения, формирование гипотез, приоритизация задач) заслуживает отдельной статьи. Здесь сосредоточимся именно на практическом опыте оптимизации редактора таблиц. Основные затронутые темы: время вычисления формул и расход памяти.
И вот с какими проблемами мы столкнулись:
Лишние вычисления
Начнём с класса оптимизаций, где удалось обнаружить и устранить ненужные вычисления. Это один из самых эффективных способов повышения производительности: если операция не нужна, лучше не выполнять её вовсе — в буквальном смысле сводя время выполнения к нулю.
Лишние вычисления могут скрываться внутри сложных операций редактирования или возникать из бизнес-логики, когда заранее понятно, что результат вычислений не изменится. В таких случаях важно не просто ускорять код, а пересматривать саму необходимость вычислений.
Автоматически выявлять такие места крайне сложно — обычно это ручная аналитика. Нужно внимательно изучать реальные сценарии работы с данными, особенно когда операции выполняются над большими массивами. Важно отслеживать повторные вычисления, регулярно мониторить возможные деградации производительности и критически смотреть на результаты измерений: адекватны ли временные затраты? соответствует ли алгоритмическая сложность задаче? не появилось ли где-то необоснованное O(n²) или хуже?
Пересчёт формул
Для начала кратко напомню, как устроен пересчёт формул в табличном редакторе. Формулы — это основа любой таблицы: они ссылаются на другие ячейки, формируя цепочки зависимостей. При изменении данных нужно определить все зависимые формулы и пересчита��ь их в корректной последовательности.
Связи между формулами, ячейками и диапазонами в памяти хранятся в виде графа зависимостей. Он строится при загрузке документа, обновляется при редактировании формул и используется при вычислениях.
Наша первоначальная «наивная» реализация инвалидировала все ячейки, которые как-либо редактировались, потому что в общем случае это может привести к изменению результатов вычислений зависимых формул. После окончания цикла применения изменений к документу, запускается цикл пересчёта и цикл обновления разметки (layout).
На практике пересчёты могут быть тяжёлыми и долгими: в сложных документах речь идёт о секундах, а иногда и десятках секунд. Причины обычно объективны — миллионы даже простых формул, большое количество функций по диапазонам (VLOOKUP, SUMIF, SUBTOTAL и др.). Всё это напрямую влияет на пользовательский опыт.
Мы проанализировали типовые сценарии редактирования и используемые функции и увидели, что далеко не все операции редактирования требуют пересчёта формул.
К таким операциям относятся изменения параметров шрифта (размер, стиль, цвет), выравнивания содержимого (горизонтального, вертикального, поворота, переноса строк), числовых форматов отображения, заливки ячеек, границ, а также изменение ширины столбцов и высоты строк.
Отдельно стоит упомянуть последний пункт. Существует функция CELL, которая может возвращать в том числе размеры ячеек. Однако анализ поведения конкурирующих решений показал, что при подобных изменениях формулы обычно не пересчитываются. Поэтому мы приняли компромиссное решение: не требовать идеальной моментальной консистентности в редких сценариях и не заставлять пользователя ждать лишние пересчёты.
Что было сделано. Ранее использовался единый список инвалидированных ячеек — одновременно для пересчёта формул и для обновления layout. Теперь эти процессы разделены: появились два независимых списка.
Обработчик изменений стал точнее классифицировать операции редактирования и распределять ячейки по соответствующим спискам. В результате пересчёт запускается только там, где он действительно необходим.
Результаты. Перечисленные выше операции выполняются практически мгновенно, не зависимо от наличия большого количества зависимых формул.
Не считать уже посчитанное
В одной из пользовательских заявок был приложен файл, где формулы пересчитывались порядка 5-8 минут (в зависимости от машины). Это происходило как при загрузке файла, так и при изменении фильтров в таблице. При этом размер данных вполне разумный: 150 тысяч строк и 15 столбцов.
Профилирование показало, что почти всё время пересчёта уходит на формулы с функциями SUBTOTAL. При этом их не много, порядка 500 на весь документ. Диапазоны между ними не пересекались: таблица фактически была разбита на независимые блоки с подытогами. Такой сценарий использования абсолютно нормален, поэтому проблема явно находилась в реализации.
Более глубокий анализ результатов профилирования показал, что основное время внутри вычисления SUBTOTAL тратилось на определение видимости строк. Действительно, результат функции зависит от того, скрыта строка фильтром или нет, нам надо это знать. Однако, для каждой функции SUBTOTAL видимость вычислялась заново путём повторного применения фильтров ко всему диапазону. Для таблицы на 150 тысяч строк это очевидно избыточная операция, потому что видимость не меняется пока мы вычисляем формулы, это статическая информация.
Была использована готовая функция получения видимости строки, и это казалось логичным. Но более глубокое изучение цепочек вызовов показало, что эта же функция используется в обработчике изменений таблиц для обновления атрибутов строк в модели документа. То есть видимость уже посчитана и сохранена! Надо использовать эти данные.
Что мы сделали. Модифицировали реализацию функций SUBTOTAL и AGGREGATE так, чтобы они брали готовое значение видимости для строк таблиц из модели документа.
Результаты. На контрольном документе время применения фильтра к таблице изменилось с 7 минут до 3-4 секунд — включая и саму фильтрацию, и пересчёт формул.
Многократный парсинг ссылок
Жалобы на долгую загрузку документов одна из самых частых категорий пользовательских обращений. Причины при этом не всегда бывают очевидные. Профилирование показало, что в ряде документов 20–30% времени загрузки уходит на парсинг формул.
Формулы в документах хранятся в текстовом виде (пример: «=A1+B1»), а работаем мы с ними в форме Абстрактного синтаксического дерева (AST). Следовательно, при загрузке текстовый вид нужно разобрать и построить дерево.
Исторически сложилось, что процесс разбора формул в коде был разделён на несколько этапов:
Грамматика лексера и парсера описывается с помощью связки flex-bison. На этом уровне формула разбирается на токены, и парсер строит дерево. Но ссылки хоть и разбираются правилами flex на соответствие формату (A1 или R1C1), наружу, в построитель дерева, передаются в виде строки.
Дальше, для строки ссылки, построитель дерева вызывал вспомогательные функции, которые разделяли ссылку на составляющие подстроки: имя документа, имя листа, столбец, строка, признак абсолютная ссылка или относительная. Эти функции использовали регулярные выражения, что медленно. Большая часть времени терялась именно здесь.
Затем подстроки-элементы ссылки преобразовывались в логические сущности: ссылка на лист, номер столбца и строки. Получаем объекты-ссылки, вставляем их в AST.
Тут наблюдаем две проблемы. Во-первых, происход��ли повторные вычисления: одни и те же ссылки фактически разбирались дважды. Во-вторых, для массовых вычислений был выбран не самый удачный инструмент — регулярные выражения. Они удобны для разовых операций, но в электронных таблицах число ссылок в формулах может исчисляться миллионами, и их стоимость становится критичной.
Чтобы устранить это узкое место, мы переработали процесс разбора ссылок. Второй этап парсинга был переведён на Boost.Spirit, что позволило заметно ускорить обработку и подготовить почву для дальнейших оптимизаций. Для контроля изменений мы добавили бенчмарки на базе Google Benchmark, чтобы сравнивать результаты «до» и «после» и отслеживать возможные регрессии.
Сам разбор ссылок ускорился примерно в 2–10 раз при сохранении идентичного результата. Дополнительно мы начали вычислять числовые индексы строк и столбцов прямо во время парсинга, так что на выходе сразу получаются значения вида 0-0, а не строки "A" и "1". Это дало ещё 2–6-кратное ускорение и позволило полностью убрать один из промежуточных этапов обработки.
Результаты. Получено заметное ускорение загрузки файлов с большим количеством формул, порядка 5-12% от всего времени загрузки.
Возможные улучшения. И почему они не были сделаны.
Оптимизации не затронули первый этап, общий парсинг (матчинг) ссылок по-прежнему выполняется flex-bison. Теоретически можно было бы передавать компоненты ссылок напрямую с уровня лексера, исключив часть промежуточной обработки. Но! Измерения и оценки показывают, что потенциальные затраты на переработку этого места сильно превышают потенциальный эффект.
Сейчас даже в худших сценариях формулы занимают около 10% общего времени загрузки документа, а сами ссылки лишь единицы процентов внутри этого времени. С практической точки зрения это уже приемлемый уровень вычислительных затрат.
Один из ключевых вопросов при оптимизации — расстановка приоритетов. Оптимизировать стоит прежде всего горячие участки системы, где эффект будет заметен пользователю. Поэтому в ближайших релизах мы сознательно завершили оптимизации в области парсинга формул и переключились на другие, более проблемные сценарии.
Использование индексов
Мы уже рассказывали как использование индексов для функций поиска VLOOKUP и HLOOKUP позволило получить ускорение вычислений в десятки раз. В той же статье упоминали и более сложные функции: семейства SUMIF(S), COUNTIF(S) и подобные им, где выполняется не просто поиск, а вычисление предиката для проверки условий.
На первом этапе для этих функций оптимизировали обход диапазонов: система начала работать только с потенциально значимыми ячейками. В следующих релизах мы пошли дальше — реализовали динамически строящиеся индексы для этих функций. Это дало ускорение на порядок.
Рассмотрим на простом примере функции COUNTIF(диапазон; условие). Первый параметр задаёт диапазон поиска, второй — предикат. Если условие содержит просто значение, выполняется проверка на равенство. Если указан оператор (>, < и т.п.), применяется соответствующее сравнение.
При «наивной» реализации происходит линейный проход по диапазону: значение каж��ой ячейки подставляется в предикат, вычисляется условие, и при положительном результате увеличивается счётчик. Функции с суффиксом -S выполняют аналогичные операции сразу по нескольким диапазонам — обычно это агрегирующие операции вроде суммы, среднего, минимума или максимума.
Что мы ещё знаем об особенностях применения IF-функций в формулах? Если посмотреть на реальные пользовательские документы, видно характерную закономерность: такие формулы часто «протянуты» по всей колонке. Диапазон поиска у них одинаковый — это постоянная часть, а условие зависит от текущей строки — это переменная часть. В результате один и тот же диапазон данных сканируется снова и снова для каждой строки.
Вывод: повторяющиеся вычисления стоит выполнять один раз и сохранять результат в индекс. Мы реализовали временные индексы, которые строятся для каждого диапазона с учётом типа сравнения и типа значения. При последующих вычислениях вместо полного обхода выполняется выборка из индекса.
Результаты. Пересчёт формул с большим количеством IF-функций ускорился в 10–20 раз, включая первый пересчёт при открытии документа. В реальных цифрах на контрольных документах полное время загрузки: 206 секунд -> 10 секунд, 427 секунд -> 18 секунд.
Коллекции без коллекции
Профилирование и вдумчивое чтение кода иногда приносит интересные идеи. Так мы нашли несколько мест, где использовались коллекции для возврата результата, но можно было обойтись без них.
Какие проблемы могут создавать коллекции? В первую очередь — накладные расходы: создание объектов, выделение и перераспределение памяти, вычисление хэшей и компараторов для ассоциативных контейнеров. Всё это само по себе не критично, но при массовых операциях начинает заметно влиять на производительность.
Дальше следует наблюдение, что из полученной коллекции используется только малая часть, либо вообще ничего. Например, только получение размера, а сами элементы мы без необходимости собирали и складывали. В долго живущем проекте такое может случаться. Не всегда возможно отслеживать все цепочки, оценивать сложность и затраты на отдельные операции. Есть готовая функция? Бери и используй.
Один из способов избежать лишних коллекций — переход к энумераторам или паттерну визитор. В этом случае вызывающий код получает элементы по мере необходимости, а не в виде заранее собранного контейнера. Конкретная реализация такой «виртуальной коллекции» скрыта: используются существующие структуры данных, внутренние фильтры и признаки отбора, но без промежуточных аллокаций. При этом внешний интерфейс остаётся тем же, а производительность выигрывает.
Здесь рассмотрим примеры таких мест и что с ними можно сделать для ускорения работы без потери функциональности.
Обход графа
Как уже говорилось выше, для корректных вычислений в таблицах нужен граф зависимостей. Сами вычисления итеративные, проходят «волнами» по графу. На каждом шаге из ещё не посчитанных узлов нужно выбрать те, у которых либо нет зависимостей, либо все зависимости уже вычислены. После расчёта такой «волны» процесс повторяется до тех пор, пока не останется необработанных узлов.
Первоначальная реализация работала максимально прямолинейно. Для получения списка узлов, которые зависят от данного, вызывался метод getNext(), возвращающий коллекцию (hash_set). Эти коллекции потом объединялись, фильтровались от дубликатов.
Работает? Да. Код понятный и простой. Но на сложных таблицах профайлер подсвечивает: половину времени обхода графа тратим на перекладывание элементов.
Шаг 1. Избавимся от коллекции в getNext() с помощью визитора.
using GraphNodeVisitor = std::function<void(GraphNode*)>; void iterateNext(GraphNode* node, GraphNodeVisitor& visitor);
Метод переименован в iterateNext(). Теперь вызывающий код не получает готовую коллекцию, а сам обрабатывает узлы по мере обхода. Это убрало один слой копирования, но проблема дубликатов осталась: если узел достигается через разные пути, визитор вызовется для него несколько раз. Раньше мы использовали hash_set, чтобы отсеять повторы, теперь этот контейнер пришлось бы создавать снова — возврат к тому же.
Шаг 2. Отсеиваем дубликаты без контейнера: уникальный тег.
Идея: хранить в каждом узле специальный тег, который меняется при каждом обходе. Если во время одного прохода мы уже посещали узел, тег совпадёт, и мы пропустим повторный вызов.
using Tag = uint64_t; struct GraphNode { Tag uniqueTag = std::numeric_limits<Tag>::max(); // остальные поля }; struct Graph { std::unordered_map<GraphNode*, std::vector<GraphNode*>> references; Tag nextTag = 0; };
Тогда iterateNext() схематично будет выглядеть так:
void iterateNext(GraphNode* node, GraphNodeVisitor visitor) { Tag currentTag = ++graph.nextTag; // уникальный номер прохода auto uniqueVisitor = [&](GraphNode* n) { if (n->uniqueTag != currentTag) { n->uniqueTag = currentTag; visitor(n); } }; for (auto* dep : references[node]) uniqueVisitor(dep); }
Никаких временных множеств и аллокаций. Узлы сами «запоминают», были ли они уже обработаны в этом проходе.
У этого подхода есть и недостатки, которые надо увидеть и явно принять.
Первое — расход памяти на тег в каждом узле графа. Много это или нет нужно смотреть в каждом конкретном случае. С учётом частого обхода и того факта, что мы уже сэкономили память на временных коллекциях, это оправдано.
Второе — в лоб оно не будет работать в многопоточном режиме. Только один процесс обхода графа в каждый момент времени, иначе теги будут конфликтовать и всё сломается.
Результаты. Тут многое зависит от конкретных формул и сложности зависимостей, но в среднем расчёт формул ускорился на 20-50% только за счёт избавления от коллекций.
Итератор для пересчитанных ячеек
Для пересчёта лэйаута необходимо знать, какие ячейки таблицы были фактически пересчитаны. Это множество в общем случае отличается от исходного множества ячеек для пересчёта. Так как есть зависимые ячейки, они тоже будут пересчитаны. Поэтому функция calc() возвращала коллекцию из множества пересчитанных ячеек.
Профилирование показало, что работа с этой коллекцией даёт заметные накладные расходы. Ситуацию усугубляла особенность использования calc(): при полном пересчёте формул во время загрузки документа эта коллекция не нужна, поскольку лэйаут перестраивается целиком. Получалось, что в самом тяжёлом сценарии система формировала наиболее «тяжёлую» коллекцию — и затем никак её не использовала. Но даже когда множество нужно, создание коллекции потребляет процессор и память.
Решение: использовать механизм тегов, но теперь для пометки пересчитанных узлов. Добавляем в GraphNode ещё одно поле – calcTag:
struct GraphNode { Tag uniqueTag; // для отсеивания дубликатов при обходе Tag calcTag; // для пометки «я пересчитан в текущем проходе» // ... };
Перед началом расчёта увеличиваем глобальный счётчик calculationTag. Каждый раз, когда узел успешно вычислен, присваиваем его полю calcTag текущее значение счётчика.
После завершения всех волн мы можем при необходимости обойти граф и собрать только те узлы, у которых calcTag == currentCalculationTag. Измерения показывают, что это дешевле коллекции. Для этого создаём специальный энумератор.
Результаты. Ускорение загрузки документов и пересчёты ускорились до 15%.
Итератор при запросе выделения
Ещё два случая, где коллекция не нужна, опишу уже без кода, только сами сценарии.
Сценарий 1. Проверка доступности операций форматирования текста. Например, при применении шрифтов или других параметров оформления нужно понять, есть ли в выделении ячейки с текстовым содержимым. Наивная реализация строила список всех выделенных ячеек и затем искала среди них первую непустую текстовую ячейку. На практике такая ячейка почти всегда находится значительно раньше конца списка, но ресурсы уже потрачены на обход всего выделения и хранение множества пустых ячеек. Использование итератора, который сразу проходит только по непустым выделенным ячейкам, позволило сократить и потребление памяти, и время выполнения.
Сценарий 2. Подсчёт статистики в статус-баре (сумма, среднее, минимум/максимум). Наивный подход был всё так же в получении выделенных ячеек (всех), затем обходе, для каждой числовой ячейки применить функцию, вернуть результат. Используем тот же итератор, что и в предыдущем примере.
Результат. Получаем заметное ускорение. Например, при операции «Выделить всё» ускорение достигает порядков, поскольку система перестаёт создавать огромные временные коллекции и сразу работает с нужными данными.
Оптимизация расхода памяти
Помимо скорости выполнения, второе крупное направление оптимизации — снижение потребления памяти. Перед нами стояла задача уменьшить расход памяти без изменения функциональности продукта. Подход здесь во многом совпадает с оптимизацией производительности: берём проблемные сценарии, профилируем, анализируем, формируем гипотезы и проверяем их на практике.
В табличном редакторе значительная часть памяти расходуется на хранение модели документа (DOM). Ячеек обычно очень много, каждая может содержать разные типы данных — число, текст, формулу и т.д., а также набор атрибутов оформления: цвет, шрифт, границы.
Первоначальная реализация хранила всё максимально универсально — с расчётом на поддержку всех возможных типов документов и сценариев редактирования. На схемах ниже показана общая структура представления содержимого документа и её применение в таблицах. Сразу оговорюсь: это упрощённые схемы, реальные контейнеры, указатели и детали реализации опущены — важна именно идея.
Удобно, единообразно для всех типов документов, подготовлено для работы с Operation Transformation: обобщённые операции над блоками и атрибутами (подробнее описано в статьях часть 1 и часть 2). Но очень расточительно по памяти! Есть поля для потенциального хранения данных, которых не может быть в таблице, например TableOfContents. Для представления простой числовой ячейки в итоге тратилось несколько сотен байт.
Посмотрим, что с этим можно сделать, не ломая и не переписывая всю бизнес-логику и механизмы совместного редактирования.
В таких ситуациях хорошо работает классическое правило: «мы не платим за то, что не используем». Статистика показала, что большинство ячеек содержат числа или формулы, реже — текст. При этом числа и формулы хранились внутри достаточно тяжёлой структуры FieldBlock.
Отсюда появилась гипотеза: ввести компактное внутреннее представление и хранить простые типы данных напрямую, без лишних обёрток. Для этого в ячейке появился вариант CellContent.
Все тяжелые объекты хранятся по указателю, в итоге размер такого Variant будет индекс + 8 байт (на 64 бит платформах).
Для «простых» данных типа чисел и формул Tombstones не нужны, они являются атомарными объектами и не редактируются по ��астям. Оставляем полное представление только для текстового контента где оно нужно.
В предложенном решении есть проблема — представление конфликтует с обобщёнными алгоритмами OT, на которых реализовано любое редактирование DOM. Им нужно полное, полноценное представление.
Для этого пришлось модифицировать методы редактирования. При записи определяем тип входящих блоков и конвертируем в компактное представление. При чтении алгоритмы ожидают получить полноценную коллекцию блоков, но у нас её нет для компактного представления. Какой выход? Применить энумерацию!
Добавляем метод enumerateBlocks, который выдаёт визитору ссылки на временные полноценные блоки (для наших "компактных" значений это всего один временный блок, созданный на стеке), не создавая всю коллекцию и всю полную структуру.
class Cell { public: Blocks getBlocks() const; // чтение с получением копии – редкие сценарии использования void enumerateBlocks(BlocksVisitor&) const; // бережливое чтение без выделения памяти };
Что ещё лишнего в ячейке? Это одновременное присутствие и контента, и сводной таблицы. Но это взаимоисключающие вещи и слишком расточительно в каждой ячейке держать даже один дополнительный указатель (место под указатель). Решение – вносим это поле тоже в вариант CellContent.
Всё вместе получится так:
Результаты. Размер объекта Cell уменьшился в разы, теперь мы не храним то, что не используем. Более сильное «ужимание» ячеек потребует переработки алгоритмов совместного редактирования, вернёмся к этому вопросу в будущих версиях. На реальных примерах с большими таблицами уменьшился расход памяти всего приложения на 20-50%.
Заключение
Производительность приложений — комплексный показатель, и проблемы скорости или памяти почти всегда являются частью технического долга. Сделать всё идеально сразу невозможно, особенно в больших и долго живущих продуктах.
Поэтому важно системно работать с такими задачами: отслеживать деградации, анализировать пользовательские сценарии, планировать оптимизации как отдельный поток работ.
Практика показывает, что даже точечные технические улучшения могут дать заметный эффект — ускорение работы продукта, снижение потребления ресурсов и, как следствие, рост его конкурентоспособности.
