Suboptimal (O(D^2)) memory usage

Offen
  • Stimmt etwas nicht?
#396 10 Kommentare 3 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen

Maintainer antworten meist innerhalb von 1 Tag

Dieses Issue hat noch niemand übernommen.

Bewertung

Schwierigkeit
5/5
Geschätzter Aufwand
Über eine Woche
Anfängerfreundlichkeit
25/100
Issue-Typ
Bug
Klarheit
Größtenteils klar
Aktivitätsstatus
Veraltet
Tech-Stack
javascript
Bereich
performance

Rechercherichtung

Beginne mit src/diff/base.js und vergleiche die dortige Speicherung von Pfaden und Komponenten mit der in Myers' Arbeit beschriebenen Linear-Space-Verfeinerung und der verknüpften diff-match-patch-Implementierung. Reproduziere das Problem mit den bereitgestellten Hearthstone-JSON-Befehlen und a.js; abgeschlossen ist die Aufgabe, wenn der Diff ohne die gemeldete übermäßige Speichernutzung und Verlangsamung durch die Garbage Collection abgeschlossen wird.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Beschreibung

performance

It seems https://github.com/kpdecker/jsdiff/blob/3b654c2ed7d5262ed9946de841ad8dae990286c7/src/diff/base.js does not implement "4b. A Linear Space Refinement" mentioned in Myers' paper. So the memory usage is O(D^2). From the code it looks like O(len(bestPath) * len(components in bestPath)) might be that complexity.

This makes it practically too slow to complete diff calculation if there are many changes. For example, comparing the prettified Hearthstone cards.json in different languages wouldn't complete in 20 minutes using jsdiff:

Reproduce:

# Prepare test data
wget https://api.hearthstonejson.com/v1/168129/enUS/cards.json -O 1
wget https://api.hearthstonejson.com/v1/168129/zhCN/cards.json -O 2
python3 -m json.tool < 1 > a
python3 -m json.tool < 2 > b

// a.js - Calculate diff
const fs = require('fs')
const diff = require('diff');

const a = fs.readFileSync('a', {encoding: 'utf-8'});
const b = fs.readFileSync('b', {encoding: 'utf-8'});

console.log(`pid: ${process.pid}`);
console.log(diff.diffLines(a, b).length);

Profiler shows that nodejs spent 70% time on GC:

image

As a comparison, it seems diff-match-patch implements the linear space refinement and can completes the above test case in ~24s. (For reference, git diff --stat --minimal completes in ~0.3s).

Vorherrschende Sprache
JavaScript
Sterne
9.2k
Forks
555
Ø Merge
1 T. 9 Std.
Gemergte PRs (30 T.)
5

Entwicklungsumgebung

Erste Schritte

  1. Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
  2. Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
  3. Forken Sie das Repository und arbeiten Sie in einem Branch.
  4. Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.

Mehr aus kpdecker/jsdiff

Alle Issues in kpdecker/jsdiff

Ähnliche Issues

Weitere Issues zu JavaScript

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.