Suboptimal (O(D^2)) memory usage
维护者通常 1 天内回复
还没有人认领这个 Issue。
评估
- 难度
- 5/5
- 预计耗时
- 一周以上
- 新手友好度
- 25/100
- Issue 类型
- 缺陷
- 描述清晰度
- 基本清楚
- 活跃度
- 停滞
- 技术栈
- javascript
- 领域
- performance
调研方向
从 src/diff/base.js 开始，将其路径和组件存储方式与 Myers 论文及链接的 diff-match-patch 实现中描述的线性空间改进进行比较。使用提供的 Hearthstone JSON 命令和 a.js 重现该问题；完成标准是 diff 能够完成，且不会出现报告中的过度内存使用和垃圾回收变慢问题。
由索引模型根据 Issue 内容生成。
描述
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).
- 主要语言
- JavaScript
- 星标
- 9.2k
- 派生
- 555
- 平均合并
- 1 天 9 小时
- 30 天内合并 PR
- 5
环境准备
- 没有 Dockerfile 或 Docker Compose 文件
- 没有 Pull Request 模板
- 阅读贡献指南
从这里开始
- 先读完整个 Issue，再读项目的贡献指南。
- 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
- Fork 仓库，在一个分支上完成修改。
- 提交 Pull Request，并在描述里引用这个 Issue 编号。
kpdecker/jsdiff 的其他 Issue
-
难度 2/5 1-3 小时 新手友好度 76/100
维护者通常 1 天内回复
-
难度 5/5 一周以上 新手友好度 35/100
kpdecker/jsdiff#703 · 1 个 reaction ·
维护者通常 1 天内回复
-
Applying a patch with a fuzzFactor can be very very slow可能已有人在做 @json-open-source 于 39 天前认领。 未关闭performance
难度 4/5 3-5 天 新手友好度 48/100
维护者通常 1 天内回复
-
难度 1/5 1 小时以内 新手友好度 45/100
维护者通常 1 天内回复
-
难度 4/5 3-5 天 新手友好度 35/100
维护者通常 1 天内回复
相似的 Issue
-
channels:edit check:passed
难度 1/5 1 小时以内 新手友好度 75/100
维护者通常 1 天内回复
-
难度 2/5 1-3 小时 新手友好度 76/100
-
难度 2/5 1-3 小时 新手友好度 68/100
维护者通常 1 天内回复
-
难度 1/5 1 小时以内 新手友好度 94/100
lidofinance/docs#1033 ·
维护者通常 1 天内回复
-
难度 2/5 1-3 小时 新手友好度 75/100
维护者通常 1 天内回复