杂记 › 技术笔记 › 文本对比的代价全在 (m+1)×(n+1) 这张表:6000 行还能跑,8000 行直接堆内存崩

文本对比的代价全在 (m+1)×(n+1) 这张表:6000 行还能跑,8000 行直接堆内存崩

账单落在一张 (m+1)×(n+1) 的表上

问题是从一次很普通的粘贴开始的:两份各 2000 行的文本贴进去,页面没有报错,也没有进度条,但就是明显地停了一下。停在哪?停在 LCS 动态规划要填的那张二维表上。两个输入的行数记作 m 和 n,表面积就是 (m+1)×(n+1);2000 行对 2000 行,是 4004001 个单元,实测堆增量 31.3MB,摊到每个单元约 8.2 字节。

同一份输入我分别在两个地方计时:Node 里中位耗时 85.4ms,Chrome 154 里 lineDiff 是 112.7ms,而整个 doDiff 走到 176.8ms——多出来的部分是装配结果 DOM 的钱。这就是文本对比工具里唯一真正的开销项,剩下的读空白、切行、拼字符串都是零头。

输入规模Node 中位耗时堆占用结局
2000 行对 2000 行85.4ms增量 31.3MB正常出结果
4000 行对 4000 行402.5ms随行数平方涨正常出结果
6000 行对 6000 行844ms280.8MB堆上限压到 512MB 也过得去
8000 行对 8000 行1093.4ms773.4MB默认堆能过,512MB 下 exit=134
10000 行对 10000 行浏览器 2478.9msjsHeapLimit 3586MB仍然出结果,不崩

把行数翻倍看代价:85.4ms 到 402.5ms 是 4.7 倍。表面积只该翻 4 倍,多出来的那部分是分配器开始搬家——数组越涨越大,堆越拷越贵,所以曲线的斜率只会越来越陡,不会自己变平。

耗时由面积决定,跟你改了几行无关

两组对照很能说明问题。3000 行的文本只改 5 行,内层循环要走 9000000 次,实测 149.0ms,最后有 3005 个差异行;300 行的文本改掉 200 行,循环只有 90000 次,0.8ms 就完事,差异行却有 500 个。改动更多的一组快了近两百倍——因为算法只认 m×n,差异行数是它算完以后才顺手统计出来的副产品。换句话说,判断「这次对比会不会慢」,只看两边各有多少行,别去看改动幅度。

只改一个标点,也是整行标红

拿 5 行文本做实验,把第 3 行末尾的句号换成感叹号,页面给你的统计是「新增 1 行,删除 1 行」,左右两栏落下 12 个 .diff-line 节点,左栏整行的 background 是 rgba(255, 80, 80, 0.12)。关键是行内检查:childElems=0,那个红色长条里没有任何 span,也没有 mark。也就是说,这个工具的粒度到行为止,改在哪个字符上,界面不会告诉你,只能自己在两行里用眼睛找。别指望它「高亮到词」,实测它连一个字都没高亮。

统计只有两个数,第三个分支是死代码

结果区上面那行字的模板在 L91,输出格式固定是「新增 N 行,删除 M 行」。我在 18 组用例里把 lineDiff 返回的 type 全收集了一遍,只有 equal、removed、added 三种值;L79-85 那段处理 modified 的分支永远不会被走到,是死代码。所以文案里那种「能看出多少行被修改」的想象在 UI 上不存在:改一行,就只能读成一行删、一行增,两个数各加一。

空白不 trim,但换行符被浏览器先吃掉了

切行用的是 split('\n'),前后不做任何修剪,于是空白全部参与比较:「foo 」和「foo」比出「新增 1 行,删除 1 行」;a\nb 和 a\nb\n 只差末尾一个换行,也报「新增 1 行,删除 0 行」;一行只有空格的空白行对一个真正的空行,是 1 删 1 增。这类差异肉眼看不见,但它确实消耗表面积、也确实标红。

换行符是另一回事。给 textarea 赋一个值 "a\r\nb",读回来已经是 "a\nb",hasCR=false——浏览器在 L45 取值那一步就把 CRLF 和孤立的 CR 归一化成了 LF。所以同一对文本,页面统计是「新增 0 行,删除 0 行」,而把这两串原样喂给 Node 里的 lineDiff,结果是 1 删 1 增。也就是说,「对比前请先统一换行符」这句提醒,在浏览器这条路径上是白说的:差异早就被抹平了;只有你绕过页面直接调函数时,它才真实存在。

400px 的结果区,一屏只有 17 行

渲染层的尺寸是可以算的:.diff-line 的行盒高 22.390625px,容器 max-height:400px 实得 clientHeight=400,除一下就是 17 行。1000 行的半改输入会生成 3000 个 div,scrollHeight=33586px,两栏严格等高。也就是说,一次 1000 行的对比要在这个 400px 的框里来回翻很多轮才看得完——瓶颈从算法转移到了你的滚轮上。

清空不是销毁,而且根本没有复制入口

按钮只有两个:「对比差异」和「清空」。在模板里 grep 复制、clipboard、copy、download、execCommand,零命中——想把差异结果带走,只能选中文字自己复制,没有导出,也没有下载。而点「清空」之后发生的事也值得知道:它只是把结果区 display:none,统计文本和 3 个行节点还留在 DOM 里,要等下一次对比才被真正销毁。

Node 耗时 85.4 402.5 844 1093.4 2000 4000 6000 8000 毫秒 512MB 崩

图 1:行数翻倍,耗时翻的是面积。6000 行那个点是堆上限压到 512MB 时测的,同样 512MB 下 8000 行直接 exit=134。

三个常被问到的点

Q:几千行的文件到底能不能比?

能,但两边的天花板不一样,这正好把那篇讲在线文本对比的文章里「几千行没问题」的定性说法补成了实测:Node 侧 2000 行 85.4ms、4000 行 402.5ms、8000 行 1093.4ms 且吃掉 773.4MB;把堆上限压到 512MB,6000 行还要 844ms 但能过,8000 行就 exit=134——这种 OOM 不是能 try/catch 兜住的异常,进程直接没了。浏览器侧 jsHeapLimit 3586MB,10000 行实测 2478.9ms 照样出结果。结论:卡的从来不是算法,是给你那一次调用分配的堆。

Q:为什么我改了个逗号,整行都红了?

因为它是按行出结果的:句号换感叹号也是「新增 1 行,删除 1 行」,行内没有任何字符级标记。想要「只看那一处」,只能自己在那一行里找。

Q:结果太长,有没有导出差异的入口?

不行,实测的按钮只有「对比差异」和「清空」,没有复制也没有下载;「清空」还只是隐藏,节点留在 DOM 里等下一次对比才销毁。

📎 相关文章

10 万个键全进 DOM:JSON 视图的渲染规模、爆栈深度与复制重排 2026-10-28 带 g 的正则是有状态的:同一个 RegExp 连打 4 次 test 只过 2 个 2026-10-28 JPG 转 PNG:27760000 个像素一位没变、体积涨到 15.881 倍,JPEG 的块效应被原样锁进无损容器 2026-10-28 20 行文件名拆成 18 行两列:粘进 Excel 只占 1 列,1e5 变成 100000 2026-10-28 拖进去一整个文件夹,候选池只多了 1 个名字:文件随机抽取读不到目录里的 2558 个文件 2026-10-28