Suboptimal (O(D^2)) memory usage
Les mainteneurs répondent en général sous 1 jour
Personne n'a encore pris cette issue.
Évaluation
- Difficulté
- 5/5
- Temps estimé
- Plus d'une semaine
- Accessibilité débutants
- 25/100
- Type d'issue
- Bug
- Clarté
- Plutôt claire
- Activité
- À l'abandon
- Stack technique
- javascript
- Domaine
- performance
Piste de recherche
Commencez par src/diff/base.js et comparez son stockage des chemins et des composants avec le raffinement en espace linéaire décrit dans l’article de Myers et dans l’implémentation diff-match-patch liée. Reproduisez le problème avec les commandes JSON Hearthstone fournies et a.js ; c’est terminé lorsque le diff s’achève sans l’utilisation excessive de mémoire ni le ralentissement du garbage collection signalés.
Rédigé par le modèle d'indexation à partir du texte de l'issue.
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).
- Langage dominant
- JavaScript
- Étoiles
- 9.2k
- Forks
- 555
- Merge moyen
- 1 j 9 h
- PR mergées (30 j)
- 5
Préparer son environnement
- Aucun Dockerfile ni fichier Docker Compose
- Aucun modèle de pull request
- Lire le guide de contribution
Par où commencer
- Lisez l'issue en entier, puis le guide de contribution du projet.
- Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
- Forkez le dépôt et travaillez sur une branche.
- Ouvrez une pull request qui référence le numéro de l'issue.
Autres issues de kpdecker/jsdiff
-
Difficulté 2/5 1-3 heures Accessibilité débutants 76/100
Les mainteneurs répondent en général sous 1 jour
-
Migrating to ESM onlyOuverte
Difficulté 5/5 Plus d'une semaine Accessibilité débutants 35/100
kpdecker/jsdiff#703 · 1 réaction ·
Les mainteneurs répondent en général sous 1 jour
-
Applying a patch with a fuzzFactor can be very very slowPeut-être pris @json-open-source l’a pris il y a 39 jours. Ouverteperformance
Difficulté 4/5 3-5 jours Accessibilité débutants 48/100
kpdecker/jsdiff#692 · 2 commentaires ·
Les mainteneurs répondent en général sous 1 jour
-
Difficulté 1/5 Moins d'une heure Accessibilité débutants 45/100
kpdecker/jsdiff#684 · 1 commentaire ·
Les mainteneurs répondent en général sous 1 jour
-
reversing a text diff?Ouverte
Difficulté 4/5 3-5 jours Accessibilité débutants 35/100
kpdecker/jsdiff#629 · 7 commentaires ·
Les mainteneurs répondent en général sous 1 jour
Toutes les issues de kpdecker/jsdiff
Issues similaires
-
Difficulté 2/5 1-3 heures Accessibilité débutants 78/100
simstudioai/sim#9831 ·
Les mainteneurs répondent en général sous 1 jour
-
status: waiting for maintainer
Difficulté 2/5 1-3 heures Accessibilité débutants 88/100
mui/material-ui#49751 ·
Les mainteneurs répondent en général sous 1 jour
-
Difficulté 2/5 1-3 heures Accessibilité débutants 88/100
Les mainteneurs répondent en général sous 2 jours
-
Edit: Monumental TV [PY]Ouvertechannels:edit check:passed
Difficulté 1/5 Moins d'une heure Accessibilité débutants 75/100
Les mainteneurs répondent en général sous 1 jour
-
Difficulté 2/5 1-3 heures Accessibilité débutants 76/100