Quadratic scaling for rich text snapshots based on number of spans
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
Avvia il container di sviluppo del progetto nel browser, con il tuo account GitHub.
- Nessun Dockerfile né file Docker Compose
- Nessun modello di pull request
- Leggi la guida per i contributori
Come iniziare
- Leggi tutta la issue e poi la guida ai contributi del progetto.
- Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
- Fai un fork del repository e lavora su un branch.
- Apri una pull request che faccia riferimento al numero della issue.
Altre issue di loro-dev/loro
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 68/100
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 3/5 1-2 giorni Idoneità per principianti 62/100
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 4/5 3-5 giorni Idoneità per principianti 42/100
I maintainer di solito rispondono entro 1 giorno
-
Shallow snapshot root retreats far below the requested frontier when two peers take turns (since 1.16.2)Forse già presa @avergin l’ha presa oggi. Aperta
Difficoltà 5/5 Più di una settimana Idoneità per principianti 15/100
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 4/5 3-5 giorni Idoneità per principianti 30/100
I maintainer di solito rispondono entro 1 giorno
Tutte le issue di loro-dev/loro
Issue simili
-
Difficoltà 1/5 Meno di un'ora Idoneità per principianti 85/100
I maintainer di solito rispondono entro 2 giorni
-
scheduled-for/27.3.0
Difficoltà 2/5 1-3 ore Idoneità per principianti 72/100
stackabletech/operator-rs#1331 ·
I maintainer di solito rispondono entro 1 giorno
-
enhancement
Difficoltà 2/5 1-3 ore Idoneità per principianti 70/100
zellij-org/zellij#5929 ·
I maintainer di solito rispondono entro 1 giorno
-
bug
Difficoltà 2/5 1-3 ore Idoneità per principianti 85/100
swc-project/swc-next-issues#396 ·
-
bug
Difficoltà 2/5 1-3 ore Idoneità per principianti 83/100
nautechsystems/nautilus_trader#5685 ·
I maintainer di solito rispondono entro 1 giorno