Suboptimal (O(D^2)) memory usage

Aberta
  • Algo errado?
#396 10 comentários 3 reações 0 responsáveis Ver no GitHub

Mantenedores costumam responder em até 1 dia

Ninguém assumiu esta issue ainda.

Avaliação

Dificuldade
5/5
Tempo estimado
Mais de uma semana
Facilidade para iniciantes
25/100
Tipo de issue
Bug
Clareza
Razoavelmente clara
Status de atividade
Estagnada
Stack de tecnologia
javascript
Domínio
performance

Direção de pesquisa

Comece com src/diff/base.js e compare o armazenamento de caminhos e componentes usado por ele com o refinamento de espaço linear descrito no artigo de Myers e na implementação vinculada do diff-match-patch. Reproduza o problema com os comandos JSON fornecidos do Hearthstone e a.js; considera-se concluído quando o diff for concluído sem o uso excessivo de memória e a lentidão da coleta de lixo relatados.

Escrita pelo modelo de indexação a partir do texto da issue.

Descrição

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).

Linguagem predominante
JavaScript
Estrelas
9.2k
Forks
555
Merge médio
1d 9h
PRs com merge (30d)
5

Preparar o ambiente

Primeiros passos

  1. Leia a issue inteira e depois o guia de contribuição do projeto.
  2. Comente na issue dizendo que vai assumir — evita que duas pessoas façam o mesmo trabalho.
  3. Faça um fork do repositório e trabalhe em uma branch.
  4. Abra um pull request que referencie o número da issue.

Mais de kpdecker/jsdiff

Todas as issues de kpdecker/jsdiff

Issues semelhantes

Mais issues de JavaScript

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.