imara-diff

imara-diff 是一个可靠的 (imara 在斯瓦希里语中意为“坚固”) Rust 差分库。可靠是指 imara-diff 即使在病态情况下也能提供很好的运行时性能，因此您的应用程序在等待差分时永远不会冻结。性能提升是通过使用经过实战检验的启发式算法实现的，这些算法在 gnu-diff 和 git 中已知表现良好，同时提供良好的结果。

imara-diff 还被设计成具有灵活性，使其可以与任意集合一起使用，而不仅仅是列表和字符串，甚至允许在比较同一文件和多个不同文件时重用计算的大部分。

imara-diff 提供两种差分算法

• 著名 Myers 算法 的线性空间变体
• 直方图 算法，它是耐心差分算法的变体。

Myers 算法通过预处理和多种启发式方法得到了增强，以确保在病态情况下的快速运行时，避免二次时间复杂度，并紧密匹配 gnu-diff 和 git 的行为。直方图算法最初是从 git 转移过来的，但已经进行了大量优化。《直方图算法在 各种工作负载 上比 Myers 算法表现优异 10% - 100%。

限制

即使在这个 crate 中进行了优化，进行大范围差分而不进行任何标记化（如字符串的字符差分）表现不佳。为了解决这个问题，可以首先对整个文件进行带有大标记（如字符串的行）的差分。然后，Sink 实现可以对更改区域进行细粒度差分。请注意，这种细粒度差分不应用于纯插入、纯删除和非常大的更改。

为了提高性能，imara-diff大量使用了指针压缩。这意味着它只能支持最多含有2^31 - 2个标记的文件。在实际情况中，对于文本差异，这通常很少成为问题，因为大多数（大型）真实世界的文件平均行长度至少为8。这意味着这个限制只有在进行行差异时，文件大小超过16GB才会成为问题。

基准测试

在 Rust 生态系统中最常用的差异库是similar和dissimilar。这两个库提供的最快的差异实现都是没有预处理或额外启发式算法的 Myers 算法简单实现。由于这些实现非常相似，因此只在基准测试中包含了similar。

为了提供一个反映实际工作负载的基准，使用了不同开源项目的 Git 历史。对于每个存储库，选择了两个（相当不同）的标签。使用gitoxide执行树差异，并将应保存的文件对存储在内存中。使用这种方法收集的差异通常相当大，因为存储库在很长的时间内进行比较。因此，还包括了标签前最后30次提交的树差异（相当于git diff TAG^ TAG，git diff TAG^^ TAG^^），以便也包括较小的差异。

基准测试测量了在收集的文件之间执行行差异的运行时间。为了衡量每次更改的复杂性，使用了(M + N) D作为度量，其中M和N是两个比较文件的长度，而D是将这些文件转换成对方的编辑脚本所需的长度（使用 Myers 算法确定）。这种复杂性度量用于将更改分为10个类别。每个类别中计算行差异的时间都被基准测试了。

下方的图表显示了每个平均复杂性的运行时间（运行时间按差异数量标准化）。请注意，由于similar在复杂差异上的运行时间很长，因此这些图表是按对数尺度显示的。此外，为了更好地突出直方图算法的性能，还单独显示了与 Myers 算法相比直方图算法的加速比。

• Linux
• Rust
• VSCode
• Helix

Linux

Linux 内核的源代码。

• 存储库 - https://kernel.org
• 标签 - v5.7和v6.0

Rust

Rust 编译器、标准库和各种相关工具的源代码。

• 存储库 - https://github.com/rust-lang/rust
• 标签 - 1.50.0和1.64.0

VScode

VScode 编辑器的源代码。

• 存储库 - https://github.com/microsoft/vscode
• 标签 - 1.41.0 和 1.72.2

Helix

螺旋编辑器的源代码。

• 仓库 - https://github.com/helix-editor/helix
• 标签 - v0.5.0 和 22.08.1

稳定性策略

imara-diff 使用 语义版本控制 (SemVar)。所有对公共 Rust API 的非破坏性更改将导致小版本号的 SemVar 升级。所有对公共 Rust API 的破坏性更改将导致大版本号的 SemVar 升级。如果生成的差异文件有效，则生成的差异文件中的更改也被视为破坏性更改。如果生成的差异文件无效，则更改将被视为修复错误。

此外，对最小稳定 Rust 版本 (MSRV) 的所有更改也被视为破坏性更改。当前的 MSRV 是 1.61。 imara-diff 将大致遵循 Firefox 的 MSRV (稳定版本) 以保持与许多尝试包含其最新版本的平台的兼容性。要预测 MSRV 的未来变化，可以查阅 Firefox 文档。