Jane Street выложила OCaml-библиотеку — на Goldman это называли иначе 30 лет назад

Что именно пропускает Incremental и почему узел стоит 30 наносекунд

Incremental — это OCaml-библиотека, которую Jane Street использует внутри компании и выложила на GitHub; вдохновлена исследованиями Умута Акара по self-adjusting computation. Идея: построить вычисление один раз, а затем обновлять его при изменении входных данных без полного перезапуска — тот же трюк, что и в таблице, где редактирование одной ячейки пересчитывает только формулы, которые её касаются.

Библиотека моделирует вычисление как граф. Узлы Var — это входные данные, в которые пишет программа. Обычные узлы выводят новые значения через функции вроде map и bind. Узлы Observer помечают, какие выходы программа реально читает. Ничего не пересчитывается, пока программа не вызовет stabilize — эта функция обходит граф зависимостей и запускает только те узлы, что находятся ниже по потоку от изменения. Пост Jane Street, представляющий библиотеку, оценивает накладные расходы на узел примерно в 30 наносекунд — мелочь по сравнению с альтернативой, и платить её стоит только тогда, когда вычисление самого узла заметно тяжелее, как в случае с расчётом риска портфеля, смешивающим live-данные рынка с настройками трейдера.

Более интересный ход в том, что граф может менять форму прямо во время работы. bind позволяет зависимостям узла зависеть от другого значения: усредните первые length элементов массива — и если length равно 7, вычисление затронет только length и эти семь ячеек, перестраиваясь заново в момент изменения length. Для массивов с обратной операцией unordered_array_fold обновляется за константное время вместо привычной логарифмической стоимости слияния сбалансированного дерева. Собственный UI-фреймворк Jane Street, Bonsai, построен на том же графе: он делает инкрементальным само построение виртуального DOM, вместо перестройки всего дерева на каждом кадре, как это делает наивный UI-код.

Тред: у этого уже есть три других названия

Тред на 65 комментариев не спорил о том, работает ли Incremental. Он спорил о том, сколько раз этот же самый граф уже строили где-то ещё. Инженер Notion назвал ближайшего живого родственника:

«Такой стиль реактивного программирования сейчас довольно популярен во фронтенд-фреймворках под названием «сигналы»… Насколько я понимаю, SolidJS2 использует алгоритм на основе высоты узлов, похожий на Incremental» — инженер, разрабатывающий продукт Notion

Он указал на предложение TC39 по стандартизации сигналов, реализации в Vue, SolidJS, Svelte, Ember и Angular, Mobx и Jotai для React, а также на Salsa в Rust — инкрементальный движок внутри rust-analyzer.

Другой голос ушёл дальше в прошлое, чем любой веб-фреймворк:

«Goldman использовал такой же подход для расчёта цен инструментов около 30 лет назад. Помню долгие обсуждения «Node Purpling» за мои примерно 13 лет там» — разработчик, проработавший 13 лет в Goldman Sachs

Не все были уверены, что паттерн заслуживает такого признания. Квант, решивший ту же задачу ещё до появления OCaml на сцене, попутно усомнился в выборе языка:

«Я построил нечто похожее для своего фонда 7 лет назад. Мы занимались параметрической оптимизацией на больших вычислительных графах… Насколько я понимаю, интроспекция — слабое место этого языка» — квант, построивший похожий граф для собственного фонда

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

Одна идея, переоткрытая везде, где полный пересчёт стал слишком медленным

«У нас в Feldera мы занимаемся IVM для SQL, но задачи инкрементальных вычислений всплывают повсюду: в UI, таблицах, control-plane, компиляторах и не только» — инженер Feldera

Сложите весь тред вместе: деск деривативов Goldman, риск-модели хедж-фонда, пять JavaScript-фреймворков, кэш компилятора на Rust и теперь SQL-движок. Никто из них не позаимствовал идею у Jane Street. Каждый упёрся в ту же стену сам и построил то же решение. Что реально отличает Incremental — не сам алгоритм, а то, что именно Jane Street записала свою внутреннюю версию, дала ей имя и выложила на GitHub, вместо того чтобы оставить её тихо жить внутри трейдингового деска.