Quadratic scaling for rich text snapshots based on number of spans

Aperta Adatta ai principianti
#1,292 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
2/5
Tempo stimato
1-3 ore
Idoneità per principianti
75/100
Tipo di issue
Bug
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
rust
Ambito
performance

Direzione di ricerca

Parti da RichtextState::decode_snapshot_fast in crates/loro-internal/src/state/richtext_state.rs intorno alla riga 1680, dove il look-forward chars().count() per span rende la decodifica degli snapshot quadratica. Riproduci con lo snippet di timing dell'issue confrontando ExportMode::Snapshot e ExportMode::all_updates() tramite to_delta(), poi applica il limite proposto chars().take(len as usize).count(). Fatto significa che il percorso snapshot non scala più in modo quadratico mentre l'output di to_delta() resta invariato e i test esistenti del crate passano.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

Hi folks,

I've been doing some performance testing on loro 1.17.1 (as part of a project I'm working on) and found a quadratic time complexity bug in the way LoroText handles snapshots. Specifically, a LoroText element whose content was written through a very large number of inserts becomes exponentially slower to read back from a snapshot as the number of inserts grows. Conversely, importing the same history as a sequence of updates completes in linear-time.

inserts text snapshot, then to_delta() updates, then to_delta()
2,500 0.3 MB 20 ms 1.8 ms
5,000 0.7 MB 69 ms 3.9 ms
10,000 1.4 MB 280 ms 8.5 ms
20,000 2.7 MB 1,500 ms 15.8 ms

With one mark per insert the snapshot takes 965 ms at 10,000 inserts and 4.5 s at 20,000. import itself
returns at once. The time is spent when the text state is first needed (to_delta, a cursor, an edit).

Let me know if you'd be open to a PR fixing this bug (in the way proposed below), and I'd be more than happy to submit it.

Theory

⚠️ This is Claude's own analysis of the cause from when it was trying to find a workaround.

In RichtextState::decode_snapshot_fast (crates/loro-internal/src/state/richtext_state.rs, line 1680 @ v1.17.1) you run the following once per text span, counting every character remaining in the string each time you process a span.

// Text
if s.as_str().chars().count() < len as usize {

This could reasonably be replaced by the following code, which limits the look-forward to just the length of the span (alternatively you could also keep a running count of what is left):

if s.as_str().chars().take(len as usize).count() < len as usize {

To reproduce

use std::time::Instant;

use loro::{ExportMode, LoroDoc};

fn main() {
    for inserts in [2_500usize, 5_000, 10_000, 20_000] {
        let doc = LoroDoc::new();
        let text = doc.get_text("body");
        let line = "The quick brown fox jumps over the lazy dog. ".repeat(3);
        // Each insert goes in front of the last, so each is a span of its own in the snapshot.
        for _ in 0..inserts {
            text.insert(0, &line).unwrap();
        }
        doc.commit();
        let snapshot = doc.export(ExportMode::Snapshot).unwrap();
        let updates = doc.export(ExportMode::all_updates()).unwrap();

        let time = |bytes: &[u8]| {
            let start = Instant::now();
            let doc = LoroDoc::new();
            doc.import(bytes).unwrap();
            doc.get_text("body").to_delta();
            start.elapsed()
        };
        println!("{inserts:>6} inserts: snapshot {:?}, updates {:?}", time(&snapshot), time(&updates));
    }
}

Workaround

Right now I'm just relying on ExportMode::all_updates() and avoiding snapshots - which solves the performance issue but isn't ultimately the right scaling model here.

Lingua principale
Rust
Stelle
6.3k
Fork
205
Merge medio
3g 18h
PR unite (30g)
45

Preparare l'ambiente

Apri in Codespaces

Avvia il container di sviluppo del progetto nel browser, con il tuo account GitHub.

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di loro-dev/loro

Tutte le issue di loro-dev/loro

Issue simili

Altre issue su Rust

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.