- A avaliação de que CRDT é lento na edição colaborativa muitas vezes resulta de misturar o algoritmo em si com a forma de implementação, e o desempenho pode mudar muito só com estrutura de dados e layout de memória
- O Automerge v1.0.0-preview2 usou 291 segundos e 880 MB de RAM para processar o rastreio de 260.000 edições, enquanto o Diamond types native processou a mesma carga em 56 ms e 1,1 MB de RAM
- O Yjs reduziu o mesmo rastreio para 0,97 s e 3,3 MB de RAM usando lista plana em vez de árvore, cache de posição, lista duplamente ligada e armazenamento por spans
- O Diamond types usa, em Rust, uma estrutura baseada em range tree/B-tree para tratar busca de posição, inserção e remoção em tempo
log(n), e registrou 193 ms no WebAssembly com base no Node.js - Este benchmark analisou apenas a reprodução local de edições de um único usuário e o uso de RAM, então na escolha real também é preciso considerar tempo de salvar/carregar, tamanho em rede/disco, binary encoding, protocolo, presence e binding com editor
Algoritmo e desempenho de implementação são coisas diferentes
- Uma comparação acadêmica implementou edição colaborativa em tempo real, como no Google Docs, com vários algoritmos CRDT e OT e fez benchmarks; alguns algoritmos levaram mais de 3 segundos para processar um simples paste
- As abordagens lentas eram os algoritmos usados no ShareJS e no Google Wave, mas aquela implementação tratava um paste de 1000 caracteres dividindo-o em 1000 operações individuais
- Esse caso mostra que é preciso separar o comportamento da edição concorrente da forma de implementação
- O comportamento significa em que ordem e com que regras as edições são mescladas quando a edição concorrente entra na mesma área
- A implementação inclui linguagem de programação, estrutura de dados e nível de otimização
- A mesma função text OT transform roda cerca de 100.000 vezes por segundo em JavaScript, mas 20M vezes por segundo em C, uma diferença de cerca de 200 vezes
- Uma implementação lenta não é prova de que todas as implementações daquele sistema sejam lentas; implementações mais rápidas são possíveis
O modelo básico de CRDT e do Automerge
- CRDT permite que vários usuários editem os mesmos dados ao mesmo tempo, trabalhando localmente sem latência e sincronizando depois para chegar à eventual consistency
- O Automerge é uma biblioteca de edição colaborativa criada por Martin Kleppmann e baseada no algoritmo RGA
- CRDTs como Automerge e Yjs tratam o documento compartilhado como uma lista de caracteres e atribuem um ID único a cada caractere
- Ao digitar
abcem um documento vazio, são atribuídos IDs como(seph, 0),(seph, 1),(seph, 2) - Cada novo caractere também registra “depois de qual item ele foi inserido”
- Ao digitar
- O Automerge/RGA adiciona um sequence number a cada item
- Um novo item recebe um valor 1 maior que o maior sequence number visto até então
- Se houver vários itens filhos, eles são ordenados por sequence number em ordem decrescente e, em caso de empate, por agent ID
- O comportamento do Automerge/RGA pode ser visto em três etapas
- Cada item é ligado ao parent para formar uma árvore
- Itens com vários filhos são ordenados por sequence number e ID
- A árvore é achatada com depth-first traversal para formar a lista final ou o documento de texto
Benchmark do Automerge e gargalos
- O benchmark usa o rastreio de edições do automerge-perf
- É um trace caractere por caractere do texto que Martin Kleppmann digitou em um artigo acadêmico
- O trace contém 260.000 edições e o documento final tem cerca de 100.000 caracteres
- Não inclui edição concorrente
- O teste mede apenas o tempo para aplicar o trace localmente
- O ambiente era uma workstation Ryzen 5800x, Nodejs v16.1 e Rust 1.52
- O Automerge v1.0.0-preview2 levou 291 segundos para processar esse trace, e a RAM no fim da execução era de 880 MB
- Isso equivale a cerca de 10 KB de RAM por tecla digitada
- O pico de RAM foi de 2,6 GB
- Nos piores spikes de lentidão, processar uma única edição levou 1,8 s
- Um baseline com splice direto em string JavaScript processou as mesmas edições em 0,61 s e 0,1 MB de RAM, mas é só um baseline de comparação que descarta todas as informações necessárias para edição colaborativa
- Há alguns motivos de implementação para a lentidão do Automerge
- À medida que o documento cresce, a estrutura de dados baseada em árvore também cresce e fica mais lenta
- O uso intenso de Immutablejs dificulta otimizações do V8 optimizer e do GC
- Cada caractere inserido é tratado como um item separado, então até um paste vira muitos itens
- A equipe do Automerge estava trabalhando em uma implementação alternativa que usa a implementação em Rust, automerge-rs, via WASM
- Na época, com base na branch master, o desempenho médio nesse teste não melhorou, mas o uso de memória caiu pela metade e a variação de desempenho ficou mais suave
Implementação em lista plana no estilo Yjs
- O Yjs é uma implementação CRDT open source criada por Kevin Jahns e armazena todos os itens em uma única lista plana em vez de uma árvore
- O acesso à lista plana encontra a posição de inserção escaneando a partir de logo depois do parent, ou seja, implementa um list CRDT como lista
- O experimental reference-crdts implementa o YATA do Yjs e o RGA do Automerge da mesma forma
- A função insert trata o funcionamento de Yjs e Automerge quase no mesmo codepath, exceto por pequenas diferenças
- A equivalência semântica é verificada com um fuzzer
- Essa abordagem tem três vantagens
- Usa flat array em vez de árvore desbalanceada, ficando menor e mais rápida
- O código é simples
- Pode ser aplicada a vários list CRDTs, como Yjs, Automerge e Sync9
- Em teoria, pode ficar lenta se houver muitas inserções concorrentes na mesma posição, mas na edição real a maioria das inserções acontece logo após o parent
- A implementação do reference-crdts foi cerca de 10 vezes mais rápida que o Automerge e usou cerca de 30 vezes menos RAM
| Teste | Tempo de processamento | Uso de RAM |
|---|---|---|
| automerge v1.0.0-preview2 | 291s | 880MB |
| reference-crdts Automerge/Yjs | 31s | 28MB |
| Plain string edits in JS | 0.61s | 0.1MB |
Reduzindo o custo de varredura e inserção
- A implementação com array plano ainda tinha dois gargalos
- era preciso varrer o documento para encontrar a posição de inserção
- ao inserir no meio do array com
doc.content.splice(destIdx, 0, newItem), era necessário deslocar os itens posteriores
- Itens excluídos não podem ser removidos do array porque outras inserções podem referenciá-los, então é preciso manter uma marca como
isDeleted- mesmo que o documento atual tenha 100.000 caracteres, pode haver 150.000 itens no array incluindo itens antigos
- para inserir na posição 50.000 do documento, pode ser necessário varrer cerca de 75.000 itens pulando os excluídos
- Nessa estrutura, inserir em um documento com
nitens exige cerca denetapas, e inserirncaracteres resulta em O(n²) - O Yjs armazena em cache pares de
(index, position)da última posição editada, de acordo com a forma como as pessoas editam documentos- como é provável que a próxima edição aconteça perto da anterior, ele faz uma varredura curta para frente e para trás
- ele também mantém um conjunto de posições em cache para casos em que vários usuários editam partes diferentes
- Em vez de array, o Yjs usa uma lista duplamente ligada e, depois de encontrar a posição, insere em tempo constante
- Ele também aproveita o fato de que pessoas digitam caracteres em sequência e armazena
hellocomo um único span, e não como 5 itens de caractere- só é possível colapsar quando o ID e o parent seguem sequencialmente
- neste conjunto de dados, o número de entradas no array caiu de 180.000 para 12.000, uma redução de 14 vezes
| Teste | Tempo de processamento | Uso de RAM |
|---|---|---|
| automerge v1.0.0-preview2 | 291s | 880MB |
| reference-crdts Automerge/Yjs | 31s | 28MB |
| Yjs v13.5.5 | 0.97s | 3.3MB |
| Plain string edits in JS | 0.61s | 0.1MB |
Rust e a abordagem de range tree do Diamond types
- Objetos JavaScript tendem a ficar com estruturas em que content, flag de exclusão, ID, seq, parent etc. ficam espalhados por ponteiros, aumentando a fragmentação de memória e o custo de cache miss
- Rust permite controlar diretamente o layout de memória e também pode ser usado na web via WebAssembly
- Diamond types é uma implementação de CRDT escrita em Rust; ela é quase igual ao Yjs, mas internamente usa uma range tree em vez de lista ligada
- A range tree interna é um B-tree levemente modificado
- em vez de armazenar keys como um
BTreeMapcomum, os nós internos armazenam a soma do número de caracteres contidos nos filhos - consultas, inserções e exclusões em posições arbitrárias do documento são feitas em tempo
log(n)
- em vez de armazenar keys como um
- Um trace de 260.000 edições fica armazenado nessa árvore com cerca de 3 níveis de leaf node, então qualquer item pode ser encontrado com aproximadamente 3 leituras de memória
- Também existe um pequeno índice que busca o B-tree por ID para fazer merge de edições remotas, mas esse codepath não está incluído neste benchmark
- Os leaf nodes armazenam blocos de 32 entradas em arrays de tamanho fixo bem compactados
- o autor afirma que o tamanho de 32 buckets funcionou bem após benchmarks com vários tamanhos, mas não sabe explicar por que ele é o ideal
- Ao compilar o Diamond para WASM com diamond-js e chamá-lo no Node.js, ele processa o mesmo trace em 193ms
- cerca de 5 vezes mais rápido que o Yjs
- cerca de 3 vezes mais rápido que o baseline com strings JavaScript
- A execução nativa em Rust registrou 56ms no benchmark
- mais de 5.000 vezes mais rápido que o Automerge
- processa 4.6M operações por segundo
- durante o processamento das 260.000 edições completas, houve 1394 chamadas a
malloc
| Teste | Tempo de processamento | Uso de RAM |
|---|---|---|
| automerge v1.0.0-preview2 | 291s | 880MB |
| reference-crdts Automerge/Yjs | 31s | 28MB |
| Yjs v13.5.5 | 0.97s | 3.3MB |
| Plain string edits in JS | 0.61s | 0.1MB |
| Diamond WASM via Node.js | 0.19s | desconhecido |
| Diamond native | 0.056s | 1.1MB |
Separação do Ropey e tradeoff
- A implementação do Diamond não coloca diretamente o conteúdo de texto do documento na lista de itens do CRDT, mas o armazena em uma estrutura de dados separada
- Para o conteúdo de texto, ele usa a biblioteca Rust Ropey, que também implementa um B-tree para gerenciar texto
- Essa abordagem envolve um tradeoff de engenharia
- o Ropey faz byte packing especializado para texto, o que pode reduzir o uso de RAM
- na inserção, é preciso atualizar duas estruturas de dados, o que torna a execução mais de 2 vezes mais lenta e aumenta o bundle WASM de 60KB para 120KB
- ao integrar com um editor como o VS Code, o editor mantém sua própria cópia do documento, então talvez não seja necessário armazenar o conteúdo do documento dentro da estrutura do CRDT
- Processar o trace apenas com o Ropey leva 29ms
- Ao desativar a atualização do conteúdo do documento no Diamond native, o resultado foi 23ms e 0.96MB de RAM
- cerca de 14.000 vezes mais rápido que o Automerge
- processa 11M operações por segundo
- esse resultado se aproxima mais de um experimento para observar o limite do processamento de metadados do CRDT do que de uma medição de utilidade prática
| Teste | Tempo de processamento | Uso de RAM | Estrutura de dados |
|---|---|---|---|
| automerge v1.0.0-preview2 | 291s | 880MB | naive tree |
| reference-crdts Automerge/Yjs | 31s | 28MB | array |
| Yjs v13.5.5 | 0.97s | 3.3MB | linked list |
| Plain string edits in JS | 0.61s | 0.1MB | nenhuma |
| Diamond WASM via Node.js | 0.20s | desconhecido | B-tree |
| Diamond native | 0.056s | 1.1MB | B-tree |
| Ropey Rust baseline | 0.029s | 0.2MB | nenhuma |
| Diamond native, no doc content | 0.023s | 0.96MB | B-tree |
Critérios para escolher uma biblioteca na prática
- Se você fosse criar agora um app colaborativo baseado em documentos, seria mais vantajoso usar o Yjs
- o Yjs oferece bom desempenho, baixo uso de memória e um bom ecossistema de suporte
- Kevin Jahns também oferece suporte pago para integração com Yjs
- A equipe do Automerge também tratava desempenho como a principal prioridade em 2021 e tinha planos de acelerar o Automerge com várias técnicas
- O Diamond é muito rápido, mas ainda falta bastante trabalho para chegar à mesma paridade de recursos de Yjs e Automerge
- uma biblioteca de CRDT precisa de mais do que velocidade de operação: binary encoding, network protocol, estruturas de dados não baseadas em lista, presence, editor bindings etc.
- Se for necessária semântica de banco de dados, o autor diz não conhecer uma boa implementação sobre CRDT e sugere usar o ShareDB, baseado em OT
- Redwood é um projeto que oferece suporte a edição P2P e planeja suporte completo a CRDT
Limitações da metodologia de medição
- Este benchmark mede apenas o tempo de reprodução do trace de edição local e o uso de RAM
- A entrada local do usuário só precisa ser rápida o suficiente, e se o CRDT processar uma única edição local em cerca de 1 ms ou menos, velocidades maiores podem não ser tão importantes
- O Automerge também geralmente atende a esse nível, exceto por pausas de GC azaradas
- Na prática, há métricas mais importantes
- número de bytes que o documento ocupa em disco ou na rede
- tempo necessário para salvar e carregar
- tempo para atualizar um documento salvo dentro de um banco de dados
- O trace usado inclui apenas edição de um único usuário, então ainda pode haver casos patológicos com muita edição simultânea
- Atualmente, para atualizar um único objeto do banco de dados com Yjs ou Automerge, em geral é preciso carregar o documento inteiro na RAM, modificá-lo e salvar o documento inteiro de novo, o que pode ser lento
- Kevin diz que, ajustando corretamente o provider do Yjs, isso pode ser implementado de forma razoável
- Os list CRDTs continuam crescendo por natureza por causa dos tombstones dos itens removidos, e pruning é uma abordagem separada
- O algoritmo de GC do Yjs e o Antimatter são citados como exemplos
- pruning é um problema ortogonal às otimizações de estrutura de dados discutidas no texto
A comparação não é um experimento totalmente controlado
- Como cada etapa de otimização mudou várias variáveis ao mesmo tempo, ela não isola a causa exata do ganho de velocidade
- Na transição de Automerge para reference-crdts, vários elementos mudaram
- a estrutura de dados principal mudou de árvore para lista
- o Immutablejs foi removido
- o protocolo frontend/backend do Automerge e várias estruturas Uint8Array desapareceram
- o estilo de JavaScript mudou de funcional para imperativo
- Nas transições de reference-crdts para Yjs e de Yjs para Diamond, as mudanças também não foram isoladas em uma única causa
- O fato de automerge-rs não ter sido mais rápido que Automerge neste teste serve como evidência de que o desempenho do Diamond não é apenas efeito do Rust, mas a contribuição exata não pode ser determinada
- Comparar RGA e YATA com a mesma forma de implementação também depende da premissa de que “o comportamento de merge concorrente é praticamente parecido e, mesmo mudando o comportamento, o desempenho da implementação se mantém”
- Na implementação de referência de CRDT, os comportamentos de Yjs e Automerge mostram praticamente o mesmo codepath e o mesmo desempenho
- Em traces com muitos conflitos pode haver diferença de desempenho, mas isso é considerado muito raro na prática
- O Yjs não armazena quando cada item foi removido, apenas se foi removido
- Se o Diamond armazenar o momento da remoção, o uso de memória aumenta de 1.12MB para 2.34MB e fica cerca de 5% mais lento
- Todos os benchmarks do Diamond neste texto usam a branch no estilo Yjs para corresponder à abordagem do Yjs
Código dos benchmarks e material de reprodução
- O código de teste do baseline com strings JS, Yjs, Automerge e reference-crdts está neste GitHub gist
- A maioria dos testes precisa de
automerge-paper.json.gzde josephg/crdt-benchmarks - O benchmark de reference-crdts depende desta versão de josephg/reference-crdts
- O benchmark do Diamond foi executado nesta versão de josephg/diamond-types
- O comando de execução é
RUSTFLAGS='-C target-cpu=native' cargo criterion yjs - As estatísticas de memória são verificadas com
cargo run --release --features memusage --example stats
- O comando de execução é
- O wrapper WASM do Diamond usa diamond-js, e o bundle wasm é otimizado com
wasm-opt - Os gráficos foram feitos no ObservableHQ
1 comentários
Opiniões no Hacker News
Se usaram inteiros de 2 bytes, é bem provável que tenha sido por causa da linha de cache de 64 bytes
32 entradas cabem exatamente em uma linha de cache, então cada linha de cache provavelmente continha um bucket inteiro e reduzia transferências caras da memória principal
Basicamente ele colocava um contador para contar quantas vezes algo precisava ser lido da memória, e fico me perguntando se daria para aproximar de modo parecido quantas vezes uma linha de cache precisa ser invalidada/esvaziada
Há saltos em limites como tamanho da palavra (64 bits), tamanho de busca alinhada do cache (normalmente os 64 bytes mencionados acima), tamanho de página do SO (4~16 KB), tamanho da L1 (cerca de 80 KB por core), L2 (na casa de alguns MB)
Tenho curiosidade de saber quais apps tiveram uma experiência muito boa usando CRDT em serviços reais
Lembro que o Notion era um deles, mas, na prática, duas pessoas fazendo anotações juntas no Notion é quase inutilizável em comparação com o Google Docs
É uma IDE para tarefas e planejamento, é um app multiusuário, com criptografia de ponta a ponta, offline-first, auto-hospedagem opcional, e todo o workspace é um único grafo, então CRDT foi uma escolha natural
Todas as ações no Thymer se reduzem a um pequeno número de transformações CRDT. Mover/copiar texto, alterar propriedades de "frontmatter", arrastar cards, fazer upload de arquivos e adicionar tags são todos tratados pelas mesmas poucas operações CRDT
No começo deu bastante trabalho implementar sem uma biblioteca, mas, quando o estado da aplicação é um único grafo, recursos como mover texto entre páginas, links de página com backlinks e transclusão podem ser criados sem se preocupar com sincronização, então valeu muito a pena
CRDT garante que todos os clientes convergem para o mesmo estado e, por ser essencialmente append-only, você ganha de graça versionamento em pontos específicos no tempo
Porém, por questões de desempenho, fizemos algumas concessões. O histórico de versões tem dados demais e não é oferecido offline; em alguns casos usamos resolução de conflitos last-writer-wins
No geral, é muito valioso, especialmente se você desenha o app pensando em CRDT desde o início. Se fosse uma situação de adicionar recursos multiusuário depois a um app AJAX mais tradicional, eu provavelmente não usaria CRDT
As mudanças de CRDT são aplicadas primeiro de forma otimista; quando a ordem autoritativa dos eventos é determinada, todos os clientes precisam voltar ao último estado compartilhado e reaplicar todos os eventos na ordem correta
Se ficou offline por muito tempo, talvez seja necessário reverter e reaplicar dias de mudanças. O usuário não sabe quantas transformações de árvore acontecem nos bastidores, mas CRDT influencia o desenho de toda a aplicação
A maioria dos apps populares de hoje foi projetada em uma época em que as transformações CRDT ainda não eram bem compreendidas
[1] https://thymer.com (quase pronto para beta)
Texto é last-writer-wins, e o texto ou as propriedades de cada bloco são registradores last-writer-wins. Eles estão trabalhando em um novo formato CRDT para texto de blocos
Isso inclui Notes e Reminders, e Photos talvez também. Ouvi em um bar de um ex-SRE da Apple bêbado que FoundationDB também é usado como parte do backend
A palestra da Local First Conf também vale conferir: https://youtu.be/VLgmjzERT08
Todos os jogos em rede que fazem rollback ou correção de alguma forma chegam perto disso. Um modelo de best effort com rollback como caminho alternativo talvez seja, entre os CRDTs amplamente usados, a forma com melhor experiência de usuário
Não é CRDT no sentido acadêmico estrito. Tecnicamente, o estado do jogo não é totalmente replicado em todos os clientes, e cada cliente recebe apenas um estado parcial do jogo
Além disso, clientes de jogos precisam de sincronização de baixa latência, e academicamente isso poderia ser visto como "coordenação". Na prática, o cliente aceita e renderiza localmente, de forma probabilística, o resultado da entrada antes que a resolução de conflito ou a correção por rollback chegue
Alguns puristas talvez contestem, mas, quando você chega ao terceiro exemplo, o tema comum fica claro. Os CRDTs mais populares, com melhor usabilidade e melhor implementados, na prática quebram as regras acadêmicas
Essa é uma armadilha típica de um modelo mental acadêmico demais. Algoritmos e tipos de dados do mundo real costumam ser muito mais criativos do que o "livro de regras" acadêmico. Timsort é um exemplo disso
Se você está criando um produto para usuários reais, e não para revisão por pares, não caia nas armadilhas de engenharia excessiva/acadêmicas. Aprenda as regras acadêmicas, mas quebre-as intencionalmente, e em vez de tentar implementar perfeitamente conceitos definidos com rigor suficiente para serem úteis só entre acadêmicos, agregue valor real e torne o produto bom de usar
CRDTs são poderosos, mas é uma pena que, sejam baseados em operações ou em estado, eles deixem rastros de operações ou elementos passados
Mesmo com compactação, isso continua sendo uma desvantagem e um ponto que faz pensar duas vezes antes de adotá-los
Ainda assim, graças a essa discussão, fiquei interessado na possibilidade de implementar algoritmos sem conflitos ou algoritmos de resolução de conflitos mais granulares sobre armazenamentos baseados em arquivos, como Dropbox e Syncthing
Meu projeto pós-CRDT, Diamond Types, basicamente cresce sem limite com o tempo, mas o overhead normalmente é de menos de 1 byte por caractere digitado até então
Se você ativar compressão LZ4 no texto armazenado, documentos editados com Diamond Types muitas vezes ficam menores do que o estado final do documento, mesmo armazenando todo o histórico de edição
Tecnicamente conheço várias formas de resolver isso, mas não tenho certeza de que isso seja um problema real na maioria dos sistemas
Ouvi dizer que alguém usando yjs em uma ferramenta de modelagem 3D teve problemas. O motivo foi que, enquanto arrastava um objeto, criava uma edição persistente a cada movimento do mouse em nível de pixel
Para esse tipo de operação, acho mais sensato usar edições temporárias, que a maioria das bibliotecas de CRDT não oferece
Aliás, o Git tem o mesmo problema. O repositório cresce com o tempo, e cresce muito mais rápido do que cresceria usando bibliotecas modernas de CRDT. Mas parece que ninguém se importa muito
Embora o Git permita clones rasos, quase ninguém faz isso. Se quiser, dá para fazer o mesmo em CRDTs
Por exemplo, se for possível garantir que todos os clientes receberam as alterações depois da data X, as operações anteriores a essa data podem ser descartadas com segurança
Estamos criando o Fireproof[1] para aproveitar as pesquisas mais recentes nessa área
Ao endereçar dados imutáveis por conteúdo, há o benefício adicional de que cada operação resulta em uma prova ou diferença com garantias criptográficas. Isso permite impor consistência causal e criar referências estáveis para snapshots
Ou seja, é possível rodar no edge ou no navegador um banco de dados interativo, que funciona offline e faz merge sem perdas, mantendo a integridade que antes se esperava de um banco de dados central ou de uma blockchain
Por exemplo, é possível colocar o CID de um snapshot em um PDF para assinatura ou em um smart contract, eliminando ambiguidades sobre o estado referenciado
[1] https://github.com/fireproof-storage/fireproof
No fim das contas, em vez de falar de forma ampla sobre o conjunto de leis matemáticas seguido por certo tipo de dado ou banco de dados, é mais correto criticar implementações específicas
É um texto de 2021 e parece incluir também a implementação em Rust do Automerge, então seria interessante ver benchmarks atualizados
Também tenho uma abordagem nova e completamente diferente para resolver esse problema
Seria ótimo atualizar os benchmarks. Tudo ficou mais rápido
Grande parte do conteúdo foi difícil de entender, mas o texto é tão bem escrito que é um daqueles raros artigos que você continua lendo sem parar
Discussões relacionadas anteriores
https://news.ycombinator.com/item?id=28017204 (3 anos atrás, 151 comentários)
https://news.ycombinator.com/item?id=33903563 (2 anos atrás, 22 comentários)
https://news.ycombinator.com/item?id=41372833 (post atual)
https://news.ycombinator.com/item?id=41373288 (comentário atual)
Citando o README atual do GitHub[0], dizem que, desde aquele post no blog, o desempenho melhorou mais 10 a 80 vezes
[0] https://github.com/josephg/diamond-types
Seria bom se alguém pudesse explicar por que CRDTs são lentos
Este texto parece mostrar o futuro: https://joelgustafson.com/posts/2023-05-04/merklizing-the-ke...
Seria interessante olhar para isto e comparar com Y.js ou Automerge: https://github.com/canvasxyz/okra-js
Desde que escrevi este texto alguns anos atrás, todas as principais bibliotecas de CRDT ficaram várias ordens de grandeza mais rápidas
Lembro de ter esbarrado neste texto alguns anos atrás
É um texto realmente divertido, e um dos meus favoritos dos últimos anos
Sobre “por que WASM é 4 vezes mais lento que execução nativa?”, achei que fosse porque todas as operações com strings precisavam ser copiadas para a memória do WASM e, quando o resultado fosse calculado, copiadas de volta para o JS.
Eu estava errado? Entendi mal o contexto? Tenho curiosidade de verdade
Antes de medir o tempo, carreguei todo o histórico para dentro do wasm e processei em um loop interno escrito em Rust que rodava no próprio contexto do wasm. Houve só umas duas chamadas ao wasm.
A causa de ficar 4 vezes mais lento não foi FFI; o código do algoritmo em si realmente estava executando 4 vezes mais devagar.
Seria interessante rodar o benchmark de novo agora. A saída wasm dos compiladores melhorou, e os runtimes de wasm também devem ter ficado mais rápidos. O código do benchmark ainda deve estar em algum lugar
Um problema recorrente em outra área é que falar de multithreading não é simples, e o suporte de bibliotecas e ferramentas também não está completo.
Tentei rodar no navegador engines de jogo e binários utilitários como ffmpeg e zip, e eles ficaram muito lentos por causa disso
Nunca trabalhei com interpretadores ou JIT de WASM, mas com que frequência passar por várias camadas de tradução é melhor do que passar por uma só?
Quando código de alto nível é traduzido para WASM ou para alguma linguagem assembly, perde-se muita da intenção contida no código de alto nível.
Em código de baixo nível, muitas vezes vemos uma sequência de idiomatismos específicos da linguagem para atingir um objetivo, que podem ou não ter correspondência direta na máquina real.
O x86-64 moderno tem muitas instruções bem mais poderosas do que o que é possível fazer em WASM.
Claro, existem decompiladores, e talvez haja uma lista de fusões de macro-operações com as quais um JIT de WASM consiga gerar bom código nativo usando pattern matching relativamente simples. Provavelmente não é o caso, e otimização multiplataforma deve ser mais difícil.
O LLVM também não é perfeito, então certamente há pontos fáceis que um otimizador de pós-processamento poderia melhorar. Portanto, não é teoricamente impossível tornar WASM mais rápido do que a saída nativa do LLVM.
Mas, a menos que exista um plano muito bem elaborado, ou que se crie um conjunto de instruções que seja, na prática, um superconjunto do que a ISA de destino oferece, acho muito difícil obter resultados no mesmo nível.
Do meu ponto de vista, WASM está mais para um subconjunto; portanto, padronizar operações e recombiná-las em tempo real não é fácil. Mesmo que não seja totalmente impossível, exigiria uma conquista considerável de engenharia.
Intuitivamente, se você traduzir um livro escrito em inglês para uma língua muito diferente e limitada a alguns milhares de palavras, e depois traduzir de volta para o inglês, o texto não sairá exatamente igual.
Surgem casos em que um conceito que em inglês seria expresso em uma palavra precisa ser explicado em um parágrafo. Para recuperar o inglês original, seria preciso ter uma tradução 1:1 para tudo, ou uma lista de traduções parágrafo→uma palavra acordada entre os dois tradutores