С самого начала одной из главных идей, лежащих в основе GRID, была идея о том, что работу с электронными таблицами (spreadsheet) и, в частности, с моделями электронных таблиц, можно сделать легче, если перенести их в веб-среду, снабдив приятно выглядящими комментариями и привлекательными интерактивными возможностями. Это касается как таблиц, с которыми взаимодействует единственный пользователь, так и таблиц, которыми одни пользователи делятся с другими.
Если говорить об интерактивности — то мы заранее знали о том, что нам понадобится наибыстрейший движок электронных таблиц, совместимый с Excel и с Google Sheets (GSheets), способный полноценно работать, пользуясь лишь ресурсами браузера. Так как подобного движка (достаточно функционального) нам найти не удалось, мы, кроме прочего, знали и о том, что нам придётся писать его самостоятельно.
К настоящему моменту мы создали то, что, скорее всего, входит в число 4-5 самых совершенных движков электронных таблиц на планете. И это (вероятно — после Google Sheets) самый продвинутый движок, который полностью работает в браузере.
Это была совсем не тривиальная задача. Расскажу о том, что мы узнали в процессе создания нашего движка.
Основы: всё пронизано зависимостями
Я не устану говорить о том, что модель электронной таблицы — это программа. Главное отличие между созданием модели таблицы и тем, что большинство людей считает «программированием», заключается в следующем. Вместо того, чтобы писать инструкции, выполняемые последовательно, создатель электронной таблицы настраивает взаимоотношения между элементами данных, которые находятся в ячейках двумерной сетки.
Для того чтобы определить порядок, в котором нужно выполнять описанные разработчиком вычисления, и выяснить то, какие именно ячейки нуждаются в пересчёте при изменении некоего значения, движок электронных таблиц обязан поддерживать граф зависимостей. Это — ориентированный граф. Его вершины соответствуют ячейкам, в которых имеются формулы, а рёбра связывают ячейки с теми ячейками, от которых они зависят (на которые они ссылаются).
Именно такой граф зависимостей занимает центральное место в любом движке электронных таблиц.
На рисунке показан граф зависимостей для небольшой электронной таблицы. Подобные графы в процессе работы над таблицами очень быстро могут становиться невероятно сложными. Даже сравнительно скромная модель таблицы легко может оказаться представленной графом с дюжинами уровней, который описывает тысячи связей между ячейками. Мы, стремясь обеспечить поддержку достаточно крупных моделей, очень быстро столкнулись с необходимостью применения различных подходов к оптимизации, некоторые из которых мы затронем ниже.
Парсинг, функции и операторы
Для того чтобы построить граф зависимостей и получить возможность вычислить значение ячейки, содержимое каждой ячейки с формулой надо распарсить. А для того чтобы это сделать нам понадобится парсер.
Формула представляет собой комбинацию любых элементов из следующего списка:
Константы: это могут быть числовые значения (
100) или строки (“Quantity”).Ссылки: такие, как
A1илиB2:D10.Операторы:
+,-,*,/, или&.Функции: например —
SUM,IFилиBAHTTEXT.
Эти элементы должны подчиняться набору правил, определяющих порядок и способ их применения в формулах. Правила определяют синтаксис языка формул. Интересно то, что, хотя этот «язык формул», вероятно, является самым широко используемым языком программирования в мире, у него даже нет формального названия. Но, как я уже писал, его совершенно справедливо можно называть «Языком формул Excel».
Парсер читает формулы, написанные на этом языке, проверяет их синтаксис и, если всё выглядит правильным, превращает формулы в инструкции, описывающие то, как именно вычислять значения соответствующих ячеек.
Разобраться с константами и ссылками — это совсем несложно, а вот операторы и функции — это уже другое дело, так как они указывают на действия, которые необходимо выполнить над константами или вычисленными значениями. Как бы странно это ни звучало (по крайней мере для тех читателей, которые далеки от информатики), операторы и функции — это, более или менее, одно и то же. То есть это, с технической точки зрения, просто разные синтаксические конструкции, которые позволяют описывать те действия, которые нужно над чем-либо выполнить. В Google Sheets, кстати, почти у каждого оператора имеются функции-двойники, вроде ADD для + и MULTIPLY для *.
Наша система поддерживает около двух десятков операторов, а вот количество доступных функций выражается уже гораздо более серьёзным числом. На момент написания этого материала в Excel было 510 функций, в Google Sheets — 494 функции, при этом у них 445 общих функций. Последняя версия стандарта «Open Document Format for Office Applications» (OpenDocument) содержит сведения о 391 функции. Большинство (но не все) из них входит в число функций, общих для Excel и Google Sheets.
Если объединить всё то, что есть в Excel, в Google Sheets и в стандарте OpenDocument, то получится 574 уникальные функции и 22 оператора. А чтобы ещё сильнее всё усложнить — надо отметить, то, что некоторые из «одинаковых» функций обладают в разных системах немного отличающимся синтаксисом, а так же то, что такие функции могут быть по-разному реализованы в Excel и Google Sheets. В качестве примера рассмотрим функции FILTER и SORT.
=FILTER(array, include, [if_empty])(Excel)=FILTER(range, condition1, [condition2, …])(GSheets)=SORT(array, [sort_index], [sort_order], [by_col])(Excel)=SORT(range, sort_column, is_ascending, [sort_column2, is_ascending2, …])(GSheets)
То есть получается, что всего имеется более 600 уникальных операций, которые могут применяться в электронных таблицах.
Правда, не все эти функции используются с одинаковой интенсивностью. Тут, как можно догадаться, вырисовывается распределение с длинным хвостом. Например, SUM, IF, NOW и AVERAGE находятся в верхней части списка функций, используемых чаще всего, но существуют и функции, которые применяются очень редко. На самом деле, когда я, около 4 лет назад, начал исследовать идею, в которой видел возможность основания новой компании, мне попался анализ нескольких корпусов электронных таблиц. Примерно в 40000 электронных таблиц так или иначе использовались лишь 109 из имеющихся функций! Мы использовали эти сведения для принятия решений о том, какие функции нужно реализовать в первую очередь.
Теперь GRID — это уже достаточно зрелая система. Мы ежедневно «поглощаем» тысячи электронных таблиц. В нашем распоряжении имеется гораздо более обширный набор данных, чем был представлен в тех корпусах таблиц. Это позволяет нам анализировать то, что характерно именно для текущей ситуации с использованием электронных таблиц в бизнес-среде. Сейчас наш движок поддерживает 398 функций. Это покрывает нужды 99% всех электронных таблиц, с которыми мы сталкиваемся (в среднем ежедневно мы сталкиваемся с примерно двумя таблицами, где используются функции, которые мы не поддерживаем). Чаще всего среди неподдерживаемых функций встречаются специфические функции из Google Sheets — IMPORTRANGE и GOOGLEFINANCE. И та и другая создают соединения с внешними источниками данных, которые мы вряд ли реализуем в GRID так же, как в Google Sheets. Короче говоря — мы уже весьма далеко продвинулись по «длинному хвосту», но всё ещё продолжаем добавлять в систему новые функции. Например, в последнее обновление входит набор из 14 функций, которые недавно были добавлены в Excel. В GRID их полная поддержка появилась ещё до того, как они вышли из бета-версии в продуктах Microsoft.
Несколько слов о реализации нашего движка
Прежде чем переходить к более сложным вещам — скажу несколько слов о том, как реализован наш движок электронных таблиц.
Основная масса его кода написана на чистом JavaScript. В последнее время мы пишем некоторые его части на Rust, компилируя в WebAssembly. Производительность — это очень важно для нас. Поэтому GRID выглядит как идеальный проект для применения WebAssembly. Но, на самом деле, JavaScript, который компилируется в машинный код, что называется, «на лету», тоже работает невероятно быстро. Поэтому прирост производительности, который мы получили от WebAssembly, оказался не таким уж и большим.
WebAssembly хорошо поддерживают браузеры. Проблемы возникают лишь при работе со старыми браузерами (их уже нет в нашем списке поддерживаемых браузеров) и с Microsoft Edge, в котором заданы очень жёсткие параметры безопасности. Больше сложностей возникает от недостаточного уровня поддержки WebAssembly некоторыми программами, используемыми в нашем стеке разработки. Это, например, инструменты для сборки и тестирования проектов. Из-за всего этого мы до сих пор поддерживаем резервные JavaScript-реализации модулей, написанных на WebAssembly.
В таких частях нашего приложения, как редактор, средства для управления документами, различные веб-инструменты, мы широко используем множество фантастических сторонних библиотек. А вот в случае с движком электронных таблиц всё не так. Главная причина того, что в его разработке мы полагаемся только на себя, заключается в том, что для нас чрезвычайно важна его совместимость с ведущими системами обработки электронных таблиц.
Стоит сказать, что существуют опенсорсные реализации движков электронных таблиц. Например — это Formula.JS, POI и OpenOffice. Мы ими иногда интересовались, но чаще всего приходили к выводу о том, что они либо не соответствуют нашим стандартам качества, либо не обеспечивают достаточно полную поддержку того, что нам нужно (в том плане, что нам не нужна референсная реализация SUM; нам нужны реализации более сложных функций, отсутствующих в этих движках). Эти движки, кроме того, иногда просто «противоречат истине» — по меньшей мере в том смысле, что возвращают результаты, отличающиеся от тех, что выдают Excel и Google Sheets.
Поэтому в настоящий момент внешние библиотеки в нашем движке используются только для форматирования чисел и для выполнения статистических манипуляций, связанных с выборками из распределений вероятностей, используемых в статистических функциях вроде NORM.DIST.
Но, в то же время, мы используем внешние библиотеки для линтинга и тестирования движка. Делается это при прогоне большого набора ��втоматизированных тестов, выполняемых по расписанию. Они позволяют обеспечить качество нашей разработки и её совместимость с другими системами по мере того, как мы продолжаем её расширять и развивать. Подробнее об этом мы поговорим ниже.
Продвинутые возможности и тонкости реализации
До сих пор мы говорили о базовых аспектах реализации движка электронных таблиц, не касаясь более запутанных и неоднозначных тем. На самом же деле, если отойти от основ, ситуацию осложняют всяческие неочевидные детали, исключения и продвинутые возможности.
Вот несколько таких возможностей.
Волатильные функции
Обычно при изменении значения в ячейке пересчитаны должны быть только те ячейки, которые от неё зависят. Но ячейки, содержащие такие функции, как NOW и RAND, называемые волатильными функциями, пересчитываются каждый раз, когда в таблице что-либо меняется. В результате пересчитываются и все ячейки, зависящие от них.
Динамические ссылки
Вообще говоря, граф зависимостей конкретной электронной таблицы не изменяется до тех пор, пока не меняются содержащиеся в нём формулы. Но определённые функции, такие как OFFSET и INDIRECT, позволяют создавать ссылки, которые динамически меняются при изменении значений в электронной таблице. Это — невероятно мощная возможность для моделирования, но, как можно себе представить, этот механизм сильно усложняет ситуацию тогда, когда речь заходит о пересчёте ячеек.
«Проливание» данных
В то время как большинство функций электронных таблиц возвращает одиночные значения, некоторые из них способны возвращать массивы. До недавних пор это было лишь внутренним соглашением, применяемым при проведении вычислений, но в 2018 в Excel появились функции, способные возвращать динамические массивы (dynamic array functions). Их применение может привести к так называемому «проливанию» (spilling) данных. Смысл тут в том, что возвращённые ими массивы могут «перетекать» (проливаться) в соседние ячейки. Ячейки, в которые «пролились» данные, будут хранить значения, полученные после вычислений, проведённых в другой ячейке, но при этом не будут содержать никаких формул. Тут ещё надо учитывать и то, что в ячейках, куда должны были «пролиться» данные, уже может что-то содержаться. Если это так, то, ячейка возвращающая массив, должна выдать ошибку, а не перезаписать такие ячейки. И, чтобы было ещё интереснее, в Google Sheets есть похожий функционал, реализованный несколько иначе (это сначала появилось в Google Sheets, но мы полагаем, что в Excel эта возможность реализована лучше).
Итеративные вычисления
Иногда в модели электронной таблицы имеются циклические ссылки. То есть — ячейка зависит от другой ячейки, которая, в свою очередь (иногда — через длинную цепь ссылок), сама зависит от этой ячейки. Циклические ссылки обычно создают по ошибке и система, как только их видит, выдаёт предупреждение. Но в некоторых случаях они нужны для вычисления значений переменных, которые по-настоящему друг от друга зависят. Это означает, что граф зависимостей, о котором мы говорили выше, это больше не однонаправленный (ациклический) граф. Он вполне может стать графом циклическим. Это, кроме того, означает, что вычисления нужно проводить снова и снова — до тех пор, пока взаимозависимые значения не сойдутся к решению (или — пока не выйдет время, выделенное на вычисления, если они сойтись не могут). Подобные итеративные вычисления сложны, но они играют значительную роль в различных сложных и важных моделях. Например — в моделях, применяемых в финансах и в инженерном деле.
Ячейка C4 ссылается на ячейку C3, которая ссылается на C4. Это — циклическая ссылка (в исходной публикации доступна интерактивная таблица).
О поддержке продвинутых возможностей
GRID поддерживает все эти продвинутые возможности. А вот — небольшой список других интересных возможностей (по большей части GRID их тоже поддерживает), которые мы пока обсуждать не будем:
Именованные диапазоны.
Относительные ссылки.
Пересечения и объединения диапазонов ячеек.
Передача данных о форматировании ячейки вместе с результатами вычислений.
Оптимизации
Продвинутые возможности — это не единственное, что заставляет нас, занимаясь реализацией электронной таблицы, отклоняться от простых и понятных базовых вещей. Один из наших приоритетов — скорость системы. Поэтому для нас важна оптимизация. И речь идёт не только о том, чтобы как можно сильнее ускорить каждый шаг вычислений. На самом деле, множество возможностей по оптимизации кроется на уровне графа зависимостей, где разумное уклонение от ненужной работы способно очень сильно повысить производительность. Вот пара примеров (их, на самом деле, гораздо больше).
Ветвления по условию
В то время как условные функции, вроде IF, технически зависят от каждой ячейки, на которую ссылаются, вычислять нужно только те значения, для которых выполняются условия таких функций. Вот гипотетический пример. При обработке формулы =IF(2+2=5, SUM(A1:A500), SUM(B1:B500)) нужно вычислить лишь то, что относится к ветви FALSE, то есть — SUM(B1:B500). Это позволяет нам, не нарушив работу системы, пропустить сотни операций сложения, выполняемых командой SUM(A1:A500) в ветви TRUE.
Большие диапазоны ячеек
Работа с диапазонами, содержащими десятки или даже сотни тысяч ячеек, может привести к повышенной нагрузке на память и к ухудшению производительности в том случае, если каждая ячейка в графе зависимостей будет представлена в виде отдельной сущности. Предположим, имеется функция, которая ищет данные. Например — такая: =VLOOKUP("Mickey Mouse", A2:D10000, 4). Она ищет строку таблицы, в которой, в столбце A, имеется текст "Mickey Mouse" и возвращает значение из столбца D той же самой строки. Нам не хотелось бы, чтобы вышеописанная ссылка выглядела бы как примерно 40000 отдельных зависимостей. Лучше было бы, если бы она была представлена в виде единственной сущности. Именно так мы и обрабатываем подобные вещи в нашем движке. А именно — он использует структуру данных R-Tree для эффективного поиска всех ссылок на диапазоны, включающие в себя конкретную ячейку.
Совместимость
Как уже упоминалось, нам очень важно, чтобы модели пользователей, работающие в GRID, возвращали бы такие же результаты, как и при работе в Excel, и в Google Sheets. Если в GRID люди увидят что-то другое — это быстро подорвёт их доверие к нашему продукту. Что тут говорить? Надо просто сделать так, чтобы вычисления были бы правильными. Так?
Так то оно так, но вот — лишь некоторые соображения, которые нужно учесть для обеспечения совместимости GRID с другими системами.
А что вообще такое — «правильные» вычисления?
Некоторые задачи могут иметь несколько решений. Например — задачи, решаемые с помощью финансовых функций IRR и XIRR. Такой функции недостаточно просто вернуть какой-то результат. Она должна вернуть тот же самый результат, который обычно возвращают программы для обработки электронных таблиц. Поэтому нам очень важно понимание того, какой именно метод работы с такими функциями используется в других движках. Кроме того, при реализации различных механизмов имеется и достаточное количество пограничных случаев, которые тоже надо учитывать:
Что должна возвращать функция поиска в том случае, если она рассчитывает на то, что значения в некоем диапазоне отсортированы, а на самом деле это не так?
Как обходиться с международными символами при выполнении алфавитной сортировки?
Когда
FALSE = 0илиTRUE = 1? Вот интересный факт: в операциях сравнения, выполняемых в электронных таблицах, иTRUE, иFALSEбольше 1 (на самом деле — они больше любого числа), но при этомFALSE * 1 = 0иTRUE * 1 = 1!
И это — далеко не всё.
Странности
В существующих движках электронных таблиц имеется немало странностей, причуд и даже обычных багов. Пользователи к ним привыкли и даже используют их на практике. Вот лишь некоторые из них:
То, возвращает ли функция ошибку
#VALUE!или#N/A!, кажется, иногда зависит от того, какой именно программист давным давно первым реализовал эту функцию в Microsoft или даже в Lotus Software. То, какую именно ошибку возвращает функция, может иметь значение в том случае, если модель построена так, что она в каких-то ситуациях рассчитана на появление одной из них, но не другой (например — использует нечто вроде=IFNA(C3,C4)).Что произойдёт, если создатель таблицы пропустит параметры в вызове функции (например —
=FV(1,2,,4)? Обычно ответ на этот вопрос не отражается в документации, но многие опытные пользователи таблиц знают о том, как это работает, и используют это в своих проектах.В определённых ситуациях функция
DATEDIFвозвращает откровенно некорректные результаты. Это — известный баг, который Microsoft не исправляет «ради поддержки старых книг из Lotus 1–2–3». Речь идёт о программе, которой никто не пользуется уже более 25 лет!
Точность вычислений
Точность вычислений с плавающей запятой (вычислений, где используются дробные числа) — это всем известная проблема из мира информатики. Обычно программистам не надо особенно много об этом думать. Правда, такую роскошь не могут позволить себе те, кто занимается созданием вычислительного движка. Excel выполняет вычисления с точностью до 15 значащих цифр. Это редко становится проблемой при целочисленных вычислениях (попробуйте ввести в своей электронной таблице число в несколько сотен квадриллионов и отформатируйте его как обычное число — вы начнёте видеть нулевые младшие разряды). Но, если не проявлять осторожность, это может привести к неприятностям даже при выполнении простейших вычислений с дробными числами. Обеспечить то, что формула =0.1 + 0.2 даёт 0.3, а не точно вычисленные 0.30000000000000004 — это не так уж и просто. Чтобы этого добиться, движки электронных таблиц прилагают немалые усилия. Причём — даже на уровне отдельных функций.
Сравнение Google Sheets и Excel
Учитывая все вышеописанные странности и нюансы, вероятно, никого не удивит то, что результаты одних и тех же вычислений в Excel и в Google Sheets могут различаться. Это так несмотря на то, что разработчики Google Sheets, ещё на ранних этапах развития их системы, аккуратно воспроизвели базовый функционал Excel. С тех пор эти две системы немного разошлись. В некоторых случаях теперь Excel идёт по следу Google Sheets. Правда Microsoft, очевидно, меньше заботится о совместимости между разными платформами (вопиющий пример такого поведения, упомянутый выше — реализация функций, возвращающих динамические массивы, вроде FILTER и SORT). Мы, когда реализуем что-то новое, сначала смотрим на Excel, а потом — на Google Sheets. Если результаты, возвращаемые этими системами, разнятся, мы «делаем то же, что и Excel» (эта фраза часто звучит у нас в офисе). Если мы можем, без потеть, учесть и примирить оба варианта — мы так и поступаем. Обычно подобные различия сводятся примерно к таким вопросам: принимать ли при вызовах функций массивы или отдельные переменные, или принимать ли булевы или целочисленные значения.
Наш подход к совместимости с другими системами
Для того чтобы обеспечить высокий — как у Excel и Google Sheets — уровень качества и совместимости нашего движка, наша команда Engine при каждой сборке движка прогоняет десятки тысяч тестов. Эти тесты составлены вручную, но запускаются, конечно же, автоматически. Более того — мы регулярно проводим тесты с участием большой группы электронных таблиц, которые пользователи GRID подключили к своим документам. Проводя эти тесты, мы ищем расхождения в результатах вычислений. При таком подходе мы способны отслеживать несоответствия и учитывать то, насколько распространёнными, серьёзными и значительными они являются. Конечно, совсем без них не обойтись, но при таком подходе мы можем быть уверены в отсутствии серьёзных отличий нашей системы от других, отличий, способных оказать негативное воздействие на наших пользователей. Это позволяет нам формировать список улучшений нашей системы и назначать этим улучшениям приоритеты.
Что дальше?
Наш движок электронных таблиц уже давно вышел из детского возраста. Мы продолжаем улучшать его производительность, продолжаем реализовывать некоторые новые функции, устранять расхождения с традиционными системами электронных таблиц. Но при этом мы достигли уровня, когда самые интересные разработки выходят за пределы того, на что способны существующие движки. Вот три сферы, в которых мы сейчас работаем, или, как минимум, закладываем фундамент для будущей работы:
Группировка и агрегирование данных. Мы встраиваем в наш движок возможности преобразования данных уровня строк (это могут быть результаты опросов, записи о транзакциях, о заказах и так далее), что может помочь пользователям в анализе данных. Традиционные электронные таблицы подходят к решению этой задачи, в основном, через применение сводных таблиц. Но учитывая то, что в таблицах GRID представление данных отделено от самих данных и от логики, мы видим перспективу естественного встраивания этой возможности в саму электронную таблицу. При этом мы можем дать нашим пользователям удобный инструмент, который окажется гораздо проще, чем создание сводных таблиц (о том, как это делать, знает лишь небольшой процент пользователей электронных таблиц).
Поддержка режима совместимости. Выше мы упоминали о всяческих различиях между Excel и Google Sheets — от разных реализаций одних и тех же функций (или использования одинаковых имён для разных функций) до различий в результатах вычислений и до отсутствия поддержки одного и того же набора операторов. Наш подход, когда мы ориентируемся на Excel, хорошо себя показал, но аудитория Google Sheets тоже для нас важна, а им мы сейчас не даём того же уровня совместимости, что и пользователям Excel. Мы планируем решить эту проблему, сделав так, чтобы наш движок мог бы узнать о том, в какой системе изначально была создана модель электронной таблицы. Зная об этом, он сможет правильно работать с таблицей, созданной где угодно.
Создание наших собственных функций. В нашей системе уже имеются особенные функции, характерные только для GRID, но мы пока не открыли доступ к ним для внешних пользователей. Мы планируем реализовать ещё больше таких функций. Многие возможности из это�� сферы обусловлены самой уникальной природой GRID — природой системы, которая функционирует как часть веб-документа. Например, интересные перспективы открывает возможность сборки документа с учётом того, на каком именно устройстве, на настольном или мобильном, просматривают документ. То же касается и учёта идентификационных данных пользователя. Наш — пока экспериментальный — элемент
canvas(тут можно посмотреть на него в действии) тоже выйдет с набором уникальных функций, которые позволят пользователям электронных таблиц интерактивно работать с графическими представлениями данных на таком уровне, о которых они раньше и не мечтали.
Если вас интересуют вопросы разработки и оптимизации электронных таблиц — рекомендую взглянуть на эту книгу.
О, а приходите к нам работать? 🤗 💰
Мы в wunderfund.io занимаемся высокочастотной алготорговлей с 2014 года. Высокочастотная торговля — это непрерывное соревнование лучших программистов и математиков всего мира. Присоединившись к нам, вы станете частью этой увлекательной схватки.
Мы предлагаем интересные и сложные задачи по анализу данных и low latency разработке для увлеченных исследователей и программистов. Гибкий график и никакой бюрократии, решения быстро принимаются и воплощаются в жизнь.
Сейчас мы ищем плюсовиков, питонистов, дата-инженеров и мл-рисерчеров.
