Suboptimal (O(D^2)) memory usage
Maintainers usually reply within 1 day
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 25/100
- Issue type
- Bug
- Clarity
- Mostly clear
- Activity status
- Stale
- Tech stack
- javascript
- Domain
- performance
Research direction
Start with src/diff/base.js and compare its path and component storage with the linear-space refinement described in Myers' paper and the linked diff-match-patch implementation. Reproduce the issue with the supplied Hearthstone JSON commands and a.js; done means the diff completes without the reported excessive memory use and garbage-collection slowdown.
Written by the indexing model from the issue text.
Description
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:
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).
- Dominant language
- JavaScript
- Stars
- 9.2k
- Forks
- 555
- Avg merge
- 1d 9h
- Merged PRs (30d)
- 5
Getting set up
- No Dockerfile or Docker Compose file
- No pull request template
- Read the contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from kpdecker/jsdiff
-
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
Maintainers usually reply within 1 day
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
kpdecker/jsdiff#703 · 1 reaction ·
Maintainers usually reply within 1 day
-
Applying a patch with a fuzzFactor can be very very slowPossibly taken @json-open-source claimed this 39 days ago. Openperformance
Difficulty 4/5 3-5 days Newbie friendliness 48/100
kpdecker/jsdiff#692 · 2 comments ·
Maintainers usually reply within 1 day
-
Difficulty 1/5 Under an hour Newbie friendliness 45/100
kpdecker/jsdiff#684 · 1 comment ·
Maintainers usually reply within 1 day
-
Difficulty 4/5 3-5 days Newbie friendliness 35/100
kpdecker/jsdiff#629 · 7 comments ·
Maintainers usually reply within 1 day
Similar issues
-
channels:edit check:passed
Difficulty 1/5 Under an hour Newbie friendliness 75/100
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
Maintainers usually reply within 1 day
-
Difficulty 1/5 Under an hour Newbie friendliness 94/100
lidofinance/docs#1033 ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 75/100
Maintainers usually reply within 1 day