Обновлённая «МойОфис Таблица»: как мы ускорили работу с документами в 50 (и более) раз

В МойОфис мы регулярно прислушиваемся к пользователям и совершенствуем продукты с учётом их мнения. Речь не только о пожеланиях, которые мы напрямую получаем от коммерческих заказчиков: не менее внимательно мы анализируем и отзывы хабрасообщества.

В одном из хабр-постов автор @Coffe4wolf рассказал о своем опыте работы с приложением «МойОфис Таблица». Критические замечания относились, по большей части, к производительности решения: например, скорости открытия «тяжёлых» документов и высокому потреблению оперативной памяти при работе с ними.

С момента публикации этой статьи мы основательно улучшили табличный редактор. Уже в релизе 2.3, который вышел в начале прошлого года, работать в «МойОфис Таблица» стало гораздо комфортнее: открытие документов с большим количеством формул ускорилось на 66%, а потребление «оперативки» снизилось в среднем на 43%. Но это далеко не предел! Мы продолжаем оптимизировать приложение, и сегодня расскажем о том, чего добились в свежем релизе 2.7. Забегая вперед: теперь массивные документы с некоторыми популярными формулами открываются в нашем продукте в 20-50 раз быстрее, чем в предыдущей версии 2.6. А пересчёт формул при изменении содержания таблиц ускорился до 100 раз.

Об усовершенствовании работы с диапазонами и алгоритма действия формул в «МойОфис Таблица» читайте под катом.

С технической точки зрения на скорость работы с «тяжёлыми» файлами, содержащими формулы, в «МойОфис Таблица» влияли две основные проблемы.

Вот как мы справились с ними в релизе 2.7.

Эта проблема касалась следующих функций с заданным критерием:

При использовании этих функций пользователи, как правило, задают число строк с запасом — до предельно допустимого значения в 1048576. Учитывая, что всего на листе может содержаться порядка 17 миллиардов ячеек, покрытие формулой всего заданного диапазона приводило к медленному открытию документа. Пересчет формул при внесении изменений в содержание таблицы также приводил к резкому падению производительности: например, в продукте версии 2.2 этот процесс мог занимать несколько минут.

Для оптимизации нам потребовалось произвести обрезку диапазонов.

Упомянутые функции в «МойОфис Таблица» изначально были реализованы «в лоб»: совершался обход всего диапазона, который пользователь передавал в формулу, независимо от реального размера таблицы и наличия данных. Очевидно, что такой алгоритм избыточен — на практике достаточно совершить обход только ячеек с данными. Пустые же ячейки при необходимости можно обработать за одну операцию.

Например, так работает функция COUNTBLANK: вместо того, чтобы бегать по всему заданному диапазону и считать пустые ячейки, можно за константное время вычислить размер всего исходного диапазона, а затем вычесть из него количество ячеек с данными.

Технически оптимизация была реализована путем использования другого типа итератора по таблице и сопутствующего этому рефакторинга.

В ряде тестов зафиксировано ускорение открытия пользовательских файлов до 50 раз по сравнению с предыдущей версией продукта (2.6). Пересчет формул при изменении данных таблиц стал быстрее до 60 раз*.

*Конкретные показатели зависят от объёма документа и его содержания.

Тестирование проводилось на стационарном компьютере следующей конфигурации:

Тестовый файл — «Пустые диапазоны», содержащий на одном листе 6250 ячеек, формулы COUNTIF, COUNTIFS, AVERAGEIF, MAXIFS и SUMIF. Скачать его можно здесь.

Вторая проблема «МойОфис Таблица» относилась к функциям VLOOKUP и HLOOKUP. Здесь, помимо обрезки диапазонов, требовалось еще и оптимизировать алгоритм поиска. В предыдущих версиях продукта использовался линейный поиск: при поиске определённого типа данных (например, числа или строки) функция проходилась по всему заданному диапазону ячеек.

Анализ пользовательских файлов, где используются функции VLOOKUP/HLOOKUP, показывает, что поиск осуществляется, как правило, по одним и тем же диапазонам. Кроме того, пользователи склонны задавать диапазоны с большим запасом на будущее. При прямолинейном подходе два этих обстоятельства выливаются в серьёзную проблему производительности — при работе с тысячами вызовов поисковых функций и диапазонами для поиска в тысячи и миллионы ячеек.

В 2.7 реализация функций VLOOKUP/HLOOKUP была переписана с линейного алгоритма поиска на использование поисковых индексов. Данные функции в «МойОфис Таблица» умеют работать в разных режимах: поиск точного соответствия значению, поиск ближайшего значения, поиск паттерна, и с разными типами данных — числа, сроки, булевые значения. Для каждой ситуации лучше подходит тот или иной тип индекса. Например, при поиске ближайшего числа удобно использовать бинарное дерево поиска, для поиска точного соответствия строке можно взять хэш-таблицу, а при индексировании булевых значений достаточно запомнить координаты всего двух ячеек, где впервые встречаются TRUE либо FALSE. Поэтому в «МойОфис Таблица» была реализована целая группа поисковых индексов, которые покрывают все возможные варианты поиска. Более того, индексы по возможности группируются по типу данных. Таким образом, например, при поиске числа более не нужно проверять ячейки со строками, что даёт дополнительный прирост производительности.

Изначальная линейная реализация функций поиска также сильно страдала от вышеописанной проблемы с избыточными диапазонами. Использование поисковых индексов исключает данную проблему, так как обход диапазона происходит только один раз за сессию вычислений — при построении индекса. Само же построение индекса также происходит с учетом того факта, что диапазон может быть задан с большим запасом, поэтому читаются только ячейки, содержащие данные, и первая ячейка вне диапазона данных, а остальные ячейки игнорируются.

В ряде тестов зафиксировано ускорение открытия пользовательских файлов до 40 раз по сравнению с предыдущей версией продукта (2.6). Пересчёт формул при изменении данных таблиц стал быстрее до 100 раз*.

*Конкретные показатели зависят от объема документа и его содержания.

Тестирование проводилось на стационарном компьютере следующей конфигурации:

Тестовый файл — «ВПР 30 000 строк», содержащий суммарно 149 019 ячеек на двух листах и 29673 функций VLOOKUP, каждая из которых производит поиск по 30000 ячеек. Скачать его можно здесь.

Вышеописанные действия — лишь часть большого пути по оптимизации нашего продукта для работы с крупными таблицами. Прирост производительности ожидается и в будущих релизах «МойОфис Таблица»; как правило, в год мы выпускаем 4 больших продуктовых обновления. Так, команда разработки уже тестирует оптимизации, которые приведут к двукратному ускорению навигации между ячейками, десятикратному ускорению открытия документов со сводными таблицами, ускорению фильтрации данных на 30% и вставки/удаления столбца из большой таблицы — более чем в 20 раз. Всё это появится в наших коммерческих продуктах в 2024 году.