Incremental: как jane street научила ocaml пересчитывать только нужное

Представьте: у вас таблица из 50 000 строк. Пользователь меняет одну ячейку. Обычный подход — пересчитать всю таблицу. Медленно, дорого, глупо. А что если пересчитать только связанные с этой ячейкой части?

Проблема: почему полный пересчёт — это больно

В реальных системах данные меняются постоянно. Пользователь редактирует документ, приходит новый API-ответ (Application Programming Interface — способ, которым программы общаются друг с другом, как розетка для подключения), обновляется конфигурация. И каждый раз мы вынуждены пересчитывать производные значения заново.

Классический пример — UI-интерфейс (User Interface — интерфейс, который видит пользователь: кнопки, поля ввода, меню). У вас есть данные, из них вычисляется заголовок, из заголовка — подсветка синтаксиса, из неё — позиция курсора. Изменились данные — пересчитывается всё, даже если данные поменялись незначительно.

Для маленьких проектов это не проблема. Для больших — уже серьёзное узкое место.

Что такое incremental

Incremental — это библиотека на языке OCaml (это функциональный язык программирования, используемый компанией Jane Street для своих проектов). Она позволяет описывать вычисления как набор узлов с зависимостями, а затем автоматически пересчитывает только затронутую часть графа при изменении входных данных.

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

Как это работает: граф зависимостей

Вся магия в направленном ациклическом графе (DAG). Каждый узел — это вычисление. Рёбра между узлами показывают зависимости.

ПРОСТОЙ ГРАФ ЗАВИСИМОСТЕЙ
──────────────────────────
        ┌─────────┐
        │  Input  │  ← данные от пользователя
        └────┬────┘
             │
     ┌───────┴───────┐
     ▼               ▼
┌─────────┐    ┌──────────┐
│Filter A │    │Filter B  │  ← промежуточные вычисления
└────┬────┘    └────┬─────┘
     │              │
     └──────┬───────┘
            ▼
     ┌───────────┐
     │ Aggregate │  ← итоговый результат
     └───────────┘

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

Базовые примитивы

Переменные (Var) — изменяемые входные данные. Вы создаёте Var (сокращение от Variable — изменяемая ячейка, куда можно записать новое значение), затем обновляете его значение через set.

Вычисления (Incr) — функции от других узлов. Создаются через map, bind, join (способы комбинировать вычисления друг с другом, как конструктор) и другие комбинаторы. Автоматически отслеживают свои зависимости.

Наблюдатели (Observer) — привязка к конкретным вычислениям. Observer (наблюдатель — механизм, который следит за изменениями и уведомляет об них) позволяет читать текущее значение и подписываться на обновления.

Типичный паттерн выглядит так:

Input (Var) → обработка (Incr) → результат (Observer)

Меняете Var — Observer получает новое значение. Всё.

ОБНОВЛЕНИЕ ПРИ ИЗМЕНЕНИИ
─────────────────────────
БЫЛО (полный пересчёт):
┌────────┐     Все 4 узла
│ Input  │──────────┌────────┐
└────────┘          │  Calc  │
          ▲         └────────┘
          │              ▲
          │         ┌────────┐
          └─────────│ Result │  Пересчитывается всегда
                     └────────┘

СТАЛО (инкрементальный):
┌────────┐     Только затронутые
│ Input  │──────▶┌────────┐──────▶┌────────┐
└────────┘       │  Calc  │       │ Result │  Пересчитывается
                 └────────┘       └────────┘  только при
                                        ▲    изменении Calc
                                   ┌────────┐
                                   │Cached. │  Не тронется
                                   └────────┘

Где это полезно

Сценарии, где Incremental показывает себя хорошо:

• UI-состояние. Таблица, график, документ — любой интерфейс с производными данными. Изменился фильтр — пересчитались строки, изменились строки — обновился счётчик, изменился счётчик — сдвинулся скролл.
• Аналитические дашборды. Метрики зависят от метрик, те — от сырых данных. Меняется один день — пересчитывается только цепочка до агрегированного отчёта.
• Реактивные модели. Если вы описываете состояние системы как граф вычислений, а не набор мутаций, код становится предсказуемым и тестируемым.

Ограничения

Библиотека не серебряная пуля. О чём стоит помнить:

• Граф должен быть ациклическим. Циклические зависимости не поддерживаются. Если вам нужна обратная связь, придётся изворачиваться, например через внешний цикл.
• OCaml-only. Если у вас проект на другом языке, эта библиотека не поможет. Есть аналоги для других экосистем, но прямой перенос отсутствует.
• Не для редких вычислений. Если данные меняются раз в час, выигрыш от инкрементальности минимален, а сложность графа — напрасная.

Как выглядит на практике

Jane Street использует Incremental внутри нескольких своих проектов. Библиотека хорошо интегрирована с их экосистемой, но может использоваться и отдельно.

Типичный сценарий: у вас есть конфиг (Var), из него вычисляются правила валидации (Incr), из правил — список ошибок (Incr), из списка — UI-сообщение (Observer). Пользователь меняет один параметр конфига — обновляется только связанная часть графа, а не весь интерфейс.

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

Практический вывод

Incremental — это инструмент для ситуаций, когда у вас есть вычислительный граф, данные меняются часто, а полный пересчёт слишком дорог. Она не магия и не замена реактивным фреймворкам целиком, но для структурированных вычислительных пайплайнов — элегантное решение.

Особенно интересна, если вы уже в экосистеме OCaml и Jane Street. Если нет — посмотрите на идею: понятие инкрементальных вычислений применимо далеко за пределами одной библиотеки.

Ссылки

• Incremental на GitHub — официальный репозиторий с документацией
• Jane Street — разработчики библиотеки