Для разработчиков ПО diff — привычный способ представления изменений: мы используем diff для сравнения различных версий одного файла (например, во время ревью кода или когда мы пытаемся понять историю файла), для визуализации разницы между непроходящим тестом и его ожиданиями или для автоматического применения изменений к файлам исходников.
В каждом моём профессиональном и личном проекте рано или требовался diff для визуализации изменения или применения патча. Однако меня никогда не устраивала ни одна из свободно доступных библиотек diff. В профессиональной деятельности это никогда не вызвало особых проблем, но в личных проектах я копировал и модифицировал из проекта в проект собственную библиотеку. Однажды я рассказал об этом коллеге, и тот наставил меня на путь публикации моей библиотеки на Go (порта библиотеки на C++, которую я раньше копировал и модифицировал). И оказалось, что я сильно недооценивал то, насколько близка моя библиотека к возможности публикации!
Как бы то ни было, я опубликовал её и узнал много нового об алгоритмах diff. Библиотеку можно найти по адресу znkr.io/diff, а в этой статье я расскажу о своих открытиях. Я ещё не завершил освоение, поэтому планирую дополнять статью в процессе изучения.
Существующие библиотеки diff
Начну я с объяснения того, почему меня не устраивают существующие библиотеки diff. Для меня важно большое количество атрибутов. Не каждый из этих атрибутов важен в каждом из сценариев использования, но библиотека diff, которую бы я мог применять во всех моих сценариях, должна удовлетворять им всем.
Обычно входными данными для алгоритма diff становится текст, и большинство библиотек diff поддерживают только его. Однако время от времени у меня возникают ситуации, когда нужно сравнивать не текст, поэтому все библиотеки, поддерживающие сравнение только текста, не удовлетворяют моим потребностям; мне нужна ещё и поддержка произвольных последовательностей.
Вывод diff предназначается для чтения людьми. Достаточно часто, особенно в случае текста, удобный способ представления diff — это unified format. Однако не всегда это наилучшее представление. Библиотека diff должна обеспечивать удобную возможность вывода diff в unified format, но в то же время должна и предоставлять возможность настройки представления реализацией структурированного результата.
Наряду с представлением, содержимое diff должно упрощать людям понимание diff. Это довольно субъективный критерий, однако существует большое количество случаев отказа, которые легко можно избежать; кроме того проводились исследования о читаемости diff, позволяющие выполнять сравнения. С другой стороны, diff должны быть минимальными, то есть как можно меньшего размера.
Кроме того, важно то, чтобы у библиотеки diff был простой API, она обеспечивала высокую производительность в среде исполнения и оптимально использовала память даже в наихудших сценариях1.
На основании этих критериев мы можем сравнить существующие библиотеки diff. Я подготовил краткую сводку библиотек на Go.
Название |
Ввод |
Вывод |
API |
Производительность2 |
Читаемость diff |
Минимальность diff2 |
|---|---|---|---|---|---|---|
❌3 |
❌4 |
?5 |
➖➖ |
➖ |
➖ |
|
❌3 |
❌6 |
? |
➕➕ |
➕➕ |
➕ |
|
❌3 |
✅ |
? |
➖➖➖ /?7 |
➕ |
➕➕ |
|
✅ |
❌4 |
?8 |
➖➖ |
➕ |
➕➕ |
|
❌3 |
✅ |
? |
➕9 |
➖ |
➖➖9 |
Стоит учесть, что принцип расстановки ➕ и ➖ в этой таблице не соответствует никакой научной методологии, а основан исключительно на проведении нескольких бенчмарков и ручном сравнении нескольких результатов. Если вы ищете библиотеку diff, отвечающую вашим требованиям, то призываю вас провести собственные сравнения. Код, который я использовал для этих сравнений, можно найти на Github.
Сложности
Из результатов следует, что далеко не так просто реализовать хорошую библиотеку diff, и та, с которой я начинал, тоже была ненамного лучше. Чтобы понять, почему существующие библиотеки именно таковы, нужно заглянуть в их реализацию.
Сложность
Все библиотеки, за исключением go-internal, для вычисления diff используют алгоритм Майерса. Это стандартный алгоритм, возвращающий минимальный diff, его используют для этой цели уже десятки лет; он имеет сложность ?︀(ND). Это означает, что алгоритм очень быстр для входных данных, имеющих высокую схожесть, что бывает достаточно часто. Однако в наихудшем случае он, по сути, квадратичный. То есть при сильно отличающихся входных данных сложность приближается к ?︀(N2).
Это означает, что можно относительно просто написать алгоритм поиска различий с высокой производительностью в случае малых или схожих входных данны��, но ему требуется очень много времени в случае больших, менее схожих входных данных. Из этого следует, что мы не можем доверять простым бенчмаркам и должны вместо них тестировать наихудший сценарий1.
Как всегда бывает в подобных случаях, можно повысить производительность, аппроксимировав оптимальное решение. Существует множество эвристик, снижающих временную сложность в обмен на минимальность diff. Например, diffmatchpatch использует дедлайн для остановки поиска оптимального diff, а udiff применяет крайне агрессивную эвристику.
Также вместо улучшения производительности алгоритма Майерса при помощи эвристик часто возможно находить diff при помощи одних только эвристик. Библиотека go-internal применяет для этого patience diff. Эта эвристика достаточно хороша для того, чтобы сама по себе обеспечивала хороший diff с временной сложностью ?︀(N logN). Однако patience diff может подводить нас в случае очень больших diff, и эффективно его можно реализовать только при помощи хэш-таблицы, что ограничивает возможные области применения.
Histogram Diff
Наряду с patience diff существует ещё одна интересная эвристика под названием histogram diff. Однако прежде чем писать о ней, мне нужно самому реализовать её и лучше в ней разобраться.
Читаемость
Алгоритмы diff обычно находят минимальный diff или его аппроксимацию. Однако, если не считать тривиальные случаи, всегда существует несколько минимальных diff. Например, этот простой diff
a
+b
-c
dстоль же минимален, как и этот
a
-c
+b
dНе все минимальные или почти минимальные diff обладают одинаковой удобочитаемостью для человека. Например10,
+int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
+{
+ if (chunk == NULL) return 0;
+
+ return start <= chunk->length && n <= chunk->length - start;
+}
+
void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
{
if (!Chunk_bounds_check(src, src_start, n)) return;
if (!Chunk_bounds_check(dst, dst_start, n)) return;
memcpy(dst->data + dst_start, src->data + src_start, n);
}
-
-int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
-{
- if (chunk == NULL) return 0;
-
- return start <= chunk->length && n <= chunk->length - start;
-}гораздо более читаем, чем столь же минимальный и корректный
-void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
+int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
{
- if (!Chunk_bounds_check(src, src_start, n)) return;
- if (!Chunk_bounds_check(dst, dst_start, n)) return;
+ if (chunk == NULL) return 0;
- memcpy(dst->data + dst_start, src->data + src_start, n);
+ return start <= chunk->length && n <= chunk->length - start;
}
-int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
+void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
{
- if (chunk == NULL) return 0;
+ if (!Chunk_bounds_check(src, src_start, n)) return;
+ if (!Chunk_bounds_check(dst, dst_start, n)) return;
- return start <= chunk->length && n <= chunk->length - start;
+ memcpy(dst->data + dst_start, src->data + src_start, n);
}Более того, если мы ослабим требование минимальности и будем принимать аппроксимации, количество возможных результатов существенно возрастёт.
Чтобы diff хорошо читались, нужно выбрать одно из множества возможных решений, удобочитаемое для человека. Многие считают, что читаемость diff определяется алгоритмом, однако это справедливо только отчасти, так как различные реализации одного и того же алгоритма могут обеспечивать сильно различающиеся результаты.
Кроме того, за последние несколько лет произошёл серьёзный прогресс в сфере читаемости diff. Пожалуй, лучшей работой стали diff-slider-tools Майкла Хэггерти. Он реализовал эвристику, применяющую этап постобработки для улучшения читаемости.
На самом деле, третий пример, показанный выше (example_03.diff), сгенерирован при помощи этой эвристики. Без эвристики сгенерированный реализацией варианта алгоритма Майерса в линейном пространстве diff выглядит так:
+int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
+{
+ if (chunk == NULL) return 0;
+
+ return start <= chunk->length && n <= chunk->length - start;
+}
+
void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
{
if (!Chunk_bounds_check(src, src_start, n)) return;
if (!Chunk_bounds_check(dst, dst_start, n)) return;
memcpy(dst->data + dst_start, src->data + src_start, n);
-}
-
-int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
-{
- if (chunk == NULL) return 0;
-
- return start <= chunk->length && n <= chunk->length - start;
}Заметили, что удаление начинается с конца предыдущей функции и оставляет небольшой остаток удаляемой функции? Эвристика Майкла устраняет эту проблему, создавая очень удобочитаемый example_03.diff.
Дело не в алгоритме
example_04.diffбыл найден при помощи другой реализации варианта алгоритма Майерса в линейном пространстве. То есть, дляexample_03.diffиexample_04.diffиспользовался один алгоритм! Разница возникла из-за реализации алгоритма и постобработки.
Новая библиотека нахождения diff для Go
Я создал znkr.io/diff для решения этих проблем подходящим для моих сценариев использования образом. Давайте повторим, что мне требуется от библиотеки diff:
Входные данные могут быть текстом и произвольными срезами
Вывод может быть в unified format и структурированным результатом
API должен быть простым
Diff должны быть минимальными или близкими к минимальным
Необходима превосходная производительность в среде исполнения и оптимальность использования памяти
Это гораздо больше того, что обеспечивают все существующие библиотеки. Когда я скопировал и модифицировал свою старую библиотеку diff, то смог адаптировать её под свои сценарии использования. Однако библиотека diff общего назначения должна быть достаточно обобщённой для того, чтобы охватывать подавляющее большинство сценариев. В то же время, она должна быть расширяемой, чтобы новые фичи можно было реализовывать, не загромождая постепенно API.
К сожалению, превосходная производительность и минимальные результаты достаточно сильно противоречат друг другу, поэтому в итоге я реализовал три режима работы: стандартный (сбалансированный между производительностью и минималистичностью), быстрый (жертвуем минимальными результатами ради высокой скорости), минимальный (минимальный результат любой ценой).
Режим |
Ввод |
Вывод |
API |
Производительность2 |
Читаемость diff |
Минимальность diff2 |
|---|---|---|---|---|---|---|
Default |
✅ |
✅ |
? |
➕➕ |
➕➕ |
➕➕ |
Fast |
✅ |
✅ |
? |
➕➕➕ |
➕➕ |
➕ |
Minimal |
✅ |
✅ |
? |
➕ |
➕➕ |
➕➕ |
Только текст
Эта таблица относится только к тексту (как и таблица выше), при нетекстовых входных данных производительность (если они не
comparable) или читаемость может быть другой.
API
При проектировании этого API я начал со структур данных, которые бы хотел использовать, как пользователь API, и отталкивался от этого. На очень высоком уровне существует два структурированных представления diff, оказавшихся полезными для меня: плоская последовательность всех удалений, вставок и совпадающих элементов (называемых edit), и вложенная последовательность идущих подряд изменений (называемых hunk).
Edit — это то, что я использую для описания изменений в этой статье; они содержат полное содержимое входных данных и то, как одно преобразуется в другое.
Hunk — это отличное представление юнит-тестов, потому что они пусты, если входные данные идентичны, и позволяют визуализировать только изменения даже в случае больших входных данных.
Произвольные срезы
Я начал проектирование с самого общего случая — с произвольных срезов. В качестве представления срезов diff на Go мне больше всего нравится это (см. также znkr.io/diff):
// Op описывает операцию редактирования.
type Op int
const (
Match Op = iota // Сопоставление двух элементов срезов
Delete // Удаление из элемента в первом срезе
Insert // Вставка элемента из правой части
)
// Edit описывает отдельный edit в diff.
// - Для Match и X, и Y содержат совпадающий элемент.
// - Для Delete X содержит удалённый элемент, а Y сброшен (нулевое значение).
// - Для Insert Y содержит вставленный элемент, а X сброшен (нулевое значение).
type Edit[T any] struct {
Op Op
X, Y T
}
// Hunk описывает последовательность идущих по порядку edit.
type Hunk[T any] struct {
PosX, EndX int // Начальная и конечная позиция в x.
PosY, EndY int // Начальная и конечная позиция в y.
Edits []Edit[T] // Edits для преобразования x[PosX:EndX] в y[PosY:EndY]
}Виденные мной альтернативы оказывались вариациями и сочетаниями двух тем. Они или использовали срезы для представления операций edit в Hunk
type Hunk[T any] struct {
Delete []T
Insert []T
Match []T
}или использовали индексы вместо элементов
type Edit struct {
Op Op
PosX, PosY []int
}Все эти представления подходят, но выяснилось, что в моих сценариях использования первые представления работают лучше. Особенность заключается в том, что Edit всегда содержит оба элемента. Часто это необязательно, но существуют сценарии использования, в которых это очень важно, потому что сами элементы могут быть неравными (например, если это указатели, сравниваемые с произвольной функцией).
Когда я определился со структурами данных, стало достаточно очевидно, что проще всего заполнять данными diff при помощи записи функций diff.Edits и diff.Hunks для возврата diff. Я сделал их расширяемыми при помощи функциональных опций.
// Edits сравнивает содержимое x и y и возвращает изменения, необходимые
// для преобразования из одного в другое.
//
// Edits возвращает по одному edit для каждого элемента во входных срезах. Если x и y are идентичны,
// вывод будет состоять из совпадающего edit для каждого элемента входных данных.
func Edits[T comparable](x, y []T, opts ...Option) []Edit[T]
// Hunks сравнивает содержимое x и y и возвращает изменения, необходимые
// для преобразования из одного в другое.
//
// Выводом будет последовательность hunk. Hunk описывает смежный блок изменений (вставок
// и удалений), а также некий окружающий контекст.
func Hunks[T comparable](x, y []T, opts ...Option) []Hunk[T]Эти опции обеспечивают возможность расширения в будущем, а также изменения поведения этих функций. Например, опция diff.Context(5) конфигурирует Hunks так, чтобы предоставлять пять элементов окружающего контекста.
Однако на текущем этапе API по-прежнему не поддерживает произвольные срезы и поддерживает только типы comparable. Чтобы это исправить, мне нужны ещё две функции, обеспечивающие функцию для сравнения двух элементов. Стандартная библиотека Go использует для подобных функций суффикс Func, поэтому я решил соответствовать:
// EditsFunc сравнивает содержимое x и y при помощи сравнения равенства и возвращает
// изменения, необходимые для преобразования из одного в другое.
func EditsFunc[T any](x, y []T, eq func(a, b T) bool, opts ...Option) []Edit[T]
// HunksFunc сравнивает содержимое x и y при помщи сравнения равенства и возвращает
// изменения, необходимые для преобразования из одного в другое.
func HunksFunc[T any](x, y []T, eq func(a, b T) bool, opts ...Option) []Hunk[T]Текст
Эта API хорошо справляется с выводом структурированного результата для произвольных срезов, однако не создаёт ввод в unified format для текстовых входных данных. Изначально я попробовал создать вспомогательную функцию, возвращающую diff в unified format: diff.ToUnified(hunks []Hunk[string]) string. Однако это сильно усложнит получение unified diff. Для этого потребуются не только два вызова функций, но и разделение входных данных на строки. А это, в свою очередь, можно реализовать разными способами, например, с вырезанием или сохранением разрывов строк, из-за чего могут возникать ошибки. Гораздо лучше создать простую функцию для сценария использования в целом.
// Unified сравнивает строки в x и y и возвращает изменения, необходимые для преобразования
// одного в другое в unified format.
func Unified[T string | []byte](x, y T, opts ...diff.Option) TКроме того, я переместил эту функцию в пакет textdiff , чтобы подчеркнуть разницу в ожидаемых входных данных.
У меня также есть сценарии, в которых требуются структурированные результаты для текстовых diff. Было бы очень неприятно разбивать их на строки вручную. Кроме того, я могу делать гораздо меньше допущений о тексте, что позволит немного упростить структуры данных:
// Edit описывает один edit построчного diff.
type Edit[T string | []byte] struct {
Op diff.Op // Операция edit
Line T // Строка, в том числе и символ новой строки (если он есть)
}
// Hunk описывает последовательность идущих по порядку edit.
type Hunk[T string | []byte] struct {
PosX, EndX int // Начальная и конечная строка в x (с отсчётом от нуля).
PosY, EndY int // Начальная и конечная строка в y (с отсчётом от нуля).
Edits []Edit[T] // Edit для преобразования строк x PosX..EndX в строки y PosY..EndY
}
// Edits сравнивает строки в x и y и возвращает изменения, необходимые для преобразования
// из одного в другое.
func Edits[T string | []byte](x, y T, opts ...diff.Option) []Edit[T]
// Hunks сравнивает строки в x и y и возвращает изменения, необходимые для преобразования
// из одного в другое.
func Hunks[T string | []byte](x, y T, opts ...diff.Option) []Hunk[T]Заключение
Полный API и примеры его использования можно посмотреть в документации по пакетам на znkr.io/diff и znkr.io/diff/textdiff. Наверняка существуют сценарии использования, не охваченные этим API, но уверен, что он сможет эволюционировать и охватить эти сценарии в будущем. На текущий момент все мои потребности удовлетворены, но если я столкнусь с ситуацией, которую нельзя разрешить при помощи API или которая потребует каких-то изменений, то напишите мне об этом.
Реализация
Для реализации этого API нам нужно реализовать алгоритм diff. Можно выбрать один из пары стандартных алгоритмов diff. Выбор алгоритма, а также способ его реализации важны для читаемости результата и для производительности.
Хорошей отправной точкой для этого проекта был алгоритм Майерса (просто потому, что это самый быстрый алгоритм, способный охватить весь API). В частности, варианты ...Func для типов any вместо comparable не могут использовать хэш-таблицу. Для эффективности реализации Patience и Histogram необходимо применение хэш-таблицы, поэтому алгоритм Майерса, на самом деле — это единственный вариант. Ещё одно преимущество Майерса по сравнению с Patience и Histogram заключается в том, что он возвращает оптимальные результаты.
С другой стороны, в показанном выше сравнении он кажется относительно медленным относительно алгоритма patience, и создаёт не самые удобочитаемые результаты. Однако, как оказалось, ситуацию можно улучшить и почти полностью устранить проблему для типов comparable при помощи сочетания предварительной обработки, эвристик и постобработки.
Я не собираюсь описывать здесь алгоритм diff. В вебе есть множество потрясающих постов с его описанием11, однако я рекомендую прочитать научную статью12: авторы всех изученных мной постов пытаются отдалиться от теории работы алгоритма, но это не особо полезно, если вы хотите понять, как и почему он работает.
Предварительная обработка
Самый эффективный способ повышения производительности алгоритма Майерса — это снижение объёма задачи. Проще всего вырезать общий префикс и суффикс. Это возможно всегда и при этом немного помогает. Однако это также снижает читаемость diff, потому что охотно потребляет совпадающие элементы.
Например, пусть у нас есть такое изменение:
name: "Freak Out!",
year: 1966,
},
+ {
+ name: "Absolutely Free",
+ year: 1967,
+ },
{
name: "We're Only in It for the Money",
year: 1967,Если мы сначала потребим общий префикс, а затем общий суффикс, то первые 11 строк будут идентичными, как и последние 4. В свою очередь, это приведёт к созданию другого diff:
year: 1966,
},
{
+ name: "Absolutely Free",
+ year: 1967,
+ },
+ {
name: "We're Only in It for the Money",
year: 1967,
},
}К счастью, это легко исправить в постобработке.
Гораздо эффективнее (но это применимо только к типам comparable) будет удалять все элементы, уникальные или левой, или правой части, потому что они всегда будут удалениями или вставками. Типы, не относящиеся к comparable , не могут быть в Go ключами хэш-таблицы, что необходимо для проверки уникальности. Для некоторых реальных diff наихудших случаев этот этап предварительной обработки снижал время исполнения даже на 99%.
В отличие от удаления суффиксов и префиксов, удаление уникальных элементов никак не влияет на читаемость.
Эвристики
Ещё один очень эффективный способ повышения производительности — это якоря. Они основаны на patience diff. Слово patience («терпение») здесь немного запутывает, потому что его легко связать с необходимостью ожидания, а это не особо точно описывает эвристику. Она находит элементы, встречающиеся ровно один раз и в левой, и в правой части. При сопоставлении этих уникальных пар мы создаём сегментацию входных данных на меньшие части, которые можно анализировать по отдельности. Ещё лучше то, что мы с большой вероятностью найдём совпадающие строки над и под такой парой уникальных элементов. Это позволит нам уменьшить сегменты, вырезав общие префиксы и суффиксы. Снижение времени исполнения, вызванное этой эвристикой, составляет до 95%. К сожалению, для нахождения и сопоставления уникальных элементов снова требуется хэш-таблица, то есть её тоже можно использовать только для типов comparable.
Также я реализовал ещё две эвристики. Они помогают при работе с типами, отличающимися от comparable, и используются в качестве запасного варианта, когда остальные эвристики не работают. Их основная задача — избежать стремительного квадратичного роста. Эвристика Good Diagonal прекращает поиск лучшего решения, если мы нашли достаточно хорошее решение, а эвристика Too Expensive прекращает поиск, если он становится слишком затратным; это снижает сложность наихудших случаев с ?︀(N2) до ?︀(N1,5logN).
Однако подобные эвристики обменивают минимальность diff на производительность, а это не всегда желательно. Иногда требуется именно минимальный diff. diff.Minimal отключает эти эвристики, чтобы всегда выполнялся поиск минимального diff, чего бы это ни стоило.
Постобработка
Выше мы выяснили, что алгоритм diff находит одно из множества возможных решений. Если у нас будет такое решение, то мы сможем обнаруживать другие решения локально, а затем выбирать наилучшее по какой-нибудь метрике решение. Именно так работает для текста эвристика indentation Майкла Хэггерти.
Для каждого конкретного diff часто можно перемещать edit вверх или вниз так, что это не поменяет смысла diff. Например,
["foo", "bar", "baz"].map do |i|
+ i
+end
+
+["foo", "bar", "baz"].map do |i|
i.upcase
endимеет такой же смысл, что и
+["foo", "bar", "baz"].map do |i|
+ i
+end
+
["foo", "bar", "baz"].map do |i|
i.upcase
endМы можем обозначить edit, которые можно перемещать вверх или вниз, как slider. Вопрос только в том, как же выбрать наилучший slider? Майкл собрал отзывы людей по разным slider в одном diff, и на их основе разработал эвристику, соответствующую этим оценкам: diff-slider-tools.
Однако эта эвристика работает только для текста и подстроена под код, а не под прозу. Я решил сделать её опциональной. Её можно включить при помощи опции textdiff.IndentHeuristic.
Представление diff
Представление, используемое при исполнении алгоритма diff, неожиданным образом влияет на производительность алгоритма и на читаемость результатов. Всё это совсем неочевидно, поэтому мне потребовалось какое-то время, чтобы понять, что лучше всего их сравнивать аналогично параллельному просмотру diff: мы используем два среза []bool для представления, соответственно, левой и правой части: true в левой части представляет удаление, а в правой — вставку. false —это совпадающий элемент.
Такое представление обладает четырьмя серьёзными преимуществами: её можно перераспределять, не важен порядок обнаружения edit, его легко изменять при постобработке и легко генерировать из него другие представления.
Вопросы, на которые пока нет ответов
По какой конкретно причине два разных алгоритма создают разные результаты? Я немного изучил этот вопрос, но конкретного ответа пока не нашёл.
Заключение
Сами по себе алгоритмы diff достаточно сложны, но они меркнут по сравнению с тем, что необходимо для создания высококачественной библиотеки diff. В этой статье я попытался объяснить, что входит в мою новую библиотеку diff, но мне ещё предстоит многое реализовать.
Вот один реальный пример того, почему наихудшие сценарии важны: представьте, что вы поломали существующую фичу так, что в тесте она вызывает наихудший сценарий. Если тест выполняется очень долго или у него заканчивается память, то вам придётся отлаживать не одну, а две проблемы.
Источник этих рейтингов находится в benchmark_comparison.txt.
Отсутствует поддержка произвольных последовательностей
Отсутствует поддержка unified diff
С API diffmatchpatch очень сложно работать
Отсутствует поддержка структурированных результатов
Квадратичное использование памяти; в моих тестовых случаях это привело к использованию более 30 ГБ памяти.
API mb0 появился во времена до дженериков, поэтому им довольно неудобно пользоваться
udiff имеет очень низкий порог, выше которого он начинает прекращать поиск оптимального решения. Это улучшает скорость, но и приводит к достаточно большим diff.
Украдено из https://blog.jcoglan.com/2017/03/22/myers-diff-in-linear-space-theory/
Могу порекомендовать https://blog.robertelder.org/diff-algorithm/ и серию постов из пяти частей https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/
Myers, E.W. An O(ND) difference algorithm and its variations. Algorithmica 1, 251-266 (1986). https://doi.org/10.1007/BF01840446