Incremental — biblioteca para computação incremental

• Incremental é uma biblioteca que ajuda a atualizar com eficiência cálculos complexos quando as entradas mudam
• Inspirada na pesquisa de computação autoajustável (self-adjusting computation) de Umut Acar e outros
• Permite estruturar cálculos de grande escala, como planilhas, para reagirem com eficiência a mudanças nos dados
• Permite refletir novos dados com eficiência nas views de aplicações GUI
• Garante que dados derivados, como filtragens ou transformações inversas de mapeamentos, permaneçam sincronizados com os dados de origem

---

Áreas de uso

• Atualiza com eficiência cálculos complexos em resposta a entradas que mudam
• Permite estruturar cálculos de grande escala em formato de planilha para reagirem a mudanças nos dados
• Permite integrar novos dados com eficiência a views GUI
• Mantém continuamente sincronizados os dados derivados calculados a partir da origem
  • Filtragem de dados
  • Transformação inversa de mapeamentos

Contexto de design e documentação

• Inspirada na pesquisa de computação autoajustável de Umut Acar e outros
• A API detalhada e o modo de uso podem ser consultados em incremental/src/incremental_intf.ml
• Oferece, como materiais introdutórios não oficiais, um post no blog e um vídeo de introdução

[GN⁺]

Opiniões no Hacker News

• Esse tipo de programação reativa hoje é amplamente usado em frameworks de UI JavaScript com o nome de signals, e há também uma proposta de padronização em andamento.
  Vue, SolidJS, Svelte, Ember e Angular usam isso, e no React há implementações como MobX e Jotai. Também existem vários algoritmos para propagação de mudanças e avaliação de grafos acíclicos direcionados (DAG); pelo que sei, o SolidJS 2 usa um algoritmo baseado em altura semelhante ao do Incremental.
  Estou experimentando uma implementação que aloca nós em uma arena Int32Array e os encadeia por listas ligadas, evitando a carga de GC proporcional ao número de arestas de dependência.
  Em Rust também há várias implementações: como framework de UI, há o Leptos; como sistema genérico de computação incremental usado pelo rust-analyzer, há o Salsa. Isso também pode ser visto como um sistema de build que rastreia dependências automaticamente: o tup instrumenta as tarefas de build para detectar quais arquivos são lidos e configurar as dependências. O texto do autor e o clássico Build Systems à la Carte também valem a leitura.

  • É possível criar um grafo de dependências leve que pode ser esvaziado rapidamente. Não é preciso descrever exatamente como um signal mudou; basta marcar que ele pode ter mudado e, quando houver uma alteração, esvaziar seus dependentes e registrá-los novamente quando novos dados forem solicitados. Nesse processo, alguns assinantes podem receber notificações de mudanças pelas quais já não têm interesse.
    Dito isso, computação incremental e programação reativa funcional (FRP) são, na prática, áreas diferentes. A computação incremental deriva explicitamente funções que operam sobre deltas, enquanto a FRP pode usar apenas uma abordagem de encontrar partes invalidadas e repará-las.
  • Outro exemplo importante é o JetBrains Noria. O núcleo do Noria não é um framework de UI, mas uma plataforma de computação incremental; atualmente, porém, ele é usado para otimizar a renderização da GUI do JetBrains Air IDE.
  • Parece haver diferenças consideráveis no tratamento de atualizações de objetos complexos, e o agendamento provavelmente também difere bastante.

• A biblioteca Incremental parece tentar resolver o problema de rematerializar parcialmente um grafo de computação quando os dados de origem mudam. É uma abordagem útil, semelhante a sistemas de build bem projetados e também comum em programação funcional.
  No campo da computação incremental, também existem Differential Dataflow, a tecnologia adjacente Timely Dataflow e DBSP. A Feldera é baseada em DBSP, e a Materialize é liderada por pessoas ligadas ao Differential Dataflow.
  Estou desenvolvendo o modolap, uma abordagem separada especializada em dados e workloads financeiros. Há muitos problemas grandes e importantes a resolver. Sobre o tema, o episódio sobre sistemas de build do Signals and Threads também vale como referência.

  • É bem ousado clicar no botão principal do modolap e ser levado, sem nenhuma explicação, a um pagamento Stripe de US$ 2.000.
  • openivm é um compilador SQL-para-SQL que implementa uma ampla gama de operações de agregação como operações incrementais, e também oferece uma extensão do DuckDB que mantém automaticamente views materializadas.

• O Goldman também usava a mesma abordagem para precificação de produtos financeiros cerca de 30 anos atrás. Durante meus cerca de 13 anos lá, lembro de longas discussões sobre Node Purpling.
  A ciência da computação avançou e, na minha visão, isso não é uma abordagem de grafos, mas cálculos como derivadas são caros, então é preciso reduzir o número de execuções para o mais próximo possível do mínimo teórico. Há também uma discussão no HN relacionada.

  • Isso levou a um ambiente informalmente chamado de bank python, bem abordado neste texto.
    Mesmo que a pessoa não peça demissão de raiva ao ver uma IDE interna própria, o trecho que melhor descreve o problema é o de que novos funcionários demoram excepcionalmente para se adaptar e, mesmo depois de meses, ainda precisam continuar aprendendo elementos fundamentalmente diferentes. Eu também levei cerca de dois anos e meio para entender completamente o trabalho.
    Também quase não havia treinamento moderno, até perceberem que era preciso treinar as pessoas de novo. A pior parte era programar para criar UI, e isso não era aprovado para novos projetos.

• Uma das minhas apresentações técnicas favoritas é Seven Implementations of Incremental: https://www.janestreet.com/tech-talks/seven-implementations-of-incremental/

• Alguns anos atrás eu tinha muito interesse em programação dataflow, e parece que muita gente abordou esse problema por várias direções. Ao ver esta biblioteca, pensei imediatamente no Javelin, do Clojure.

• Se parecer interessante, também vale olhar a biblioteca de UI Bonsai, construída sobre o Incremental.
  Bibliotecas como React pulam trabalho desnecessário de forma eficiente com um DOM virtual, mas criar o próprio DOM virtual também leva tempo. O Bonsai incrementaliza até o DOM virtual, e também é divertido trabalhar com ele.
  Eu criei uma biblioteca de UI desktop para o Revery, que hoje não é mais mantido, mas ela usa uma versão bem antiga do Bonsai.

• Não entendi completamente em que isso difere do padrão Observable, que emite novos valores na entrada, passa pelo cálculo e entrega o novo resultado aos assinantes
  Deve haver detecção de mudanças e uma otimização para interromper a propagação quando o valor permanece igual, mas isso também é possível com Observables. A parte de processar mudanças em lote antes de recalcular com stabilize também é interessante, mas igualmente implementável com Observables
  Fico em dúvida se a diferença central está em construir automaticamente o grafo de cálculo por investigação interna, ou se há algo mais fundamental

  • Depende de como você define o padrão Observable. Aqui, o elemento fundamental é a avaliação preguiçosa e o acoplamento fraco entre os nós do grafo. Os valores dos nós só são materializados quando observados, e mudanças na estrutura do grafo durante a execução também são tratadas com flexibilidade
    Quando só alguns nós são observados, não é necessário materializar o grafo inteiro. Também é possível interromper o cálculo a qualquer momento, deixar o grafo em um estado apenas parcialmente atualizado, fazer novas alterações nas entradas e depois continuar a materialização dos nós de interesse; o algoritmo cuida de consolidar todas as mudanças
    Computação incremental é, por natureza, um termo que abrange essas características, e o mesmo sistema também poderia ser organizado com um modelo de observadores e assinantes. Uma planilha clássica do Excel é um bom exemplo, e a explicação do algoritmo Salsa também vale a leitura
  • Em linhas gerais, Observables são uma forma de assinar um alvo e ouvir valores, enquanto o Incremental se parece mais com um cache espalhado por um DAG de cálculos e estado. É possível otimizar recalculando apenas as partes necessárias
    A palestra do Ron Minsky é excelente
  • Este texto ajuda a entender o panorama dos sistemas incrementais e de streaming
  • Também pensei de forma parecida. À primeira vista, parece muito próximo de programação reativa com rastreamento de dependências. Fico em dúvida se a vantagem real é a usabilidade da API ou otimizações internas que, na prática, seriam difíceis com uma implementação comum de Observables
  • Fundamentalmente, é mesmo um grafo, mas é uma forma de calcular mudanças de maneira correta e eficiente em grafos enormes e dinamicamente mutáveis
    Dá para imaginar um subgrafo em forma de diamante que se divide em centenas de nós intermediários e depois se junta novamente por caminhos de comprimentos diferentes. Em alguns caminhos pode haver min(A, B), e só o lado do valor máximo muda
    Uma abordagem simples de observadores pode fazer a quantidade de cálculo explodir potencialmente de forma exponencial e também tem grande chance de causar problemas de concorrência. Esta biblioteca continua quase ótima e correta mesmo com mudanças dinâmicas na estrutura do grafo. É possível obter o mesmo resultado com observadores e afins, mas implementar isso corretamente evitando penhascos de desempenho é muito mais difícil

• O ponto forte dos projetos da Jane Street é empacotar ideias que estavam em pesquisa ou em sistemas de nicho em uma forma que desenvolvedores possam usar de verdade. Mesmo que você não adote a biblioteca, em geral vale a pena ler os documentos de design

• Electric Clojure oferece renderização incremental que atravessa a fronteira entre cliente e servidor. Acho que o mais parecido é o SolidJS, mas o SolidJS se aplica apenas ao front-end

• No passado, ao criar algo parecido, quase não encontrei precedentes. O objetivo de uso desapareceu e encerrei o projeto, mas gostaria de revisitá-lo; ele ainda está no npm com o nome data-rambler
  A ideia era fornecer streams de dados a uma linguagem específica de domínio (DSL) que pudesse ser carregada no runtime JavaScript. Os módulos transformavam os dados em vários streams de saída e os repassavam para uma biblioteca separada de relatórios para gerar relatórios dinâmicos baseados em templates
  Desde a primeira versão, já era bastante poderosa, mas também havia grandes planos para melhorá-la com uma sintaxe mais ao estilo JavaScript, a fim de reduzir a complexidade