⚖️ 4 основных алгоритма сравнения Git Diff: когда и какой алгоритм использовать
Обзор четырех алгоритмов git diff: Майерса, минимальный, «терпения» и гистограммный. Также приводятся наглядные примеры, чтобы можно было сравнить результат применения каждого алгоритма самостоятельно.
git diff — это команда Git для отображения изменений
- между рабочим деревом и индексом или другим деревом;
- между индексом и деревом;
- между двумя деревьями;
- в результате слияния;
- между двумя blob объектами;
- между двумя файлами на диске.
На момент написания статьи (прим. переводчика: 10 октября 2020) последняя версия git — 2.28.0, и она поддерживает в общей сложности четыре diff-алгоритма, а именно Майерса, минимальный, «терпения» и гистограммный. В следующих разделах я выскажу свое мнение о том, когда следует использовать каждый из этих алгоритмов. В этой статье не рассказывается о том, как работает алгоритм, и/или о его сложности — вы можете загуглить.
Прежде чем углубляться в детали, одно предостережение — ваши результаты могут отличаться от приведенных в зависимости от:
- типов сравниваемых файлов;
- изменений в файлах;
- пакета/версии git, который вы используете.
Одно из множества изменений может повлиять на эффективность алгоритма(-ов) сравнения. Я рекомендую рассматривать эту статью как руководство для начинающих, чтобы выяснить, какой алгоритм лучше всего соответствует вашим потребностям.
--diff-algorithm={myers|default}
Жадный алгоритм, применяемый по умолчанию, первоначально разработанный Юджином В. Майерсом в 1986 году, используется, когда указано myers, default или когда алгоритм для сравнения не указан явно. Он хорошо работает для большинства сценариев, предоставляя хорошо читаемый diff, с приемлемым затрачиваемым числом памяти и временем выполнения.
Когда использовать алгоритм Майерса:
- Для почти всех типов файлов и изменений, так как он хорошо работает с большинством;
- Если вы не уверены, какой алгоритм сравнения использовать.
--diff-algorithm={minimal}
Алгоритм Майерса использует эвристику, чтобы обеспечить достойный компромисс между временем выполнения и размером входных данных. Однако есть случаи, когда важнее иметь наименьший размер diff'а, пожертвовав для этого увеличением времени выполнения. В утилите Linux diff можно передать флаг, чтобы отключить эвристику и запустить полный набор итераций алгоритма. Следующий абзац о команде Linux diff хорошо описывает это:
Основной алгоритм описан в работе «O(ND) алгоритм поиска различий и его вариации» Юджина Майерса, Алгоритмика Том 1 № 2, 1986 г., с. 251-266; … Если не указана опция--minimal, этот код использует эвристикуTOO_EXPENSIVEПола Эггерта, чтобы ограничить стоимость доO(N**1,5 log N)ценой создания неоптимального вывода для больших входных данных с большими различиями.
Минимальный diff-алгоритм — это эквивалент в контексте Git'а.
Мы можем сравнить результаты, полученные алгоритмами Майерса и минимальным, используя достаточно большой размер входных данных. В приведенном ниже примере я сравниваю количество изменений между двумя наборами статей Википедии при использовании каждого алгоритма:
# Подготовка данных для сравнения
$ curl {article-A,article-B,article-C,article-D} > wikipediaSet1
$ curl {article-E,article-F,article-G,article-H} > wikipediaSet2
# Выполнение команды diff с алгоритмом Майерса
$ git diff --diff-algorithm=myers --shortstat wikipediaSet1 wikipediaSet2
1 file changed, 7990 insertions(+), 4463 deletions(-)
# Выполнение команды diff с минимальным алгоритмом
~$ git diff --diff-algorithm=minimal --shortstat wikipediaSet1 wikipediaSet2
1 file changed, 7712 insertions(+), 4185 deletions(-)
Обратите внимание, что можно использовать минимальный diff-алгоритм с небольшим размером входных данных, хотя выходные данные, вероятно, будут идентичны Майерсу, поскольку проблемное место — проитерировать полностью — находится в пределах эвристики.
Когда использовать минимальный алгоритм:
- Сравнение большого числа изменений между большими файлами.
- Вы не против потратить больше времени на создание меньшего набора различий/изменений.
--diff-algorithm={patience}
Алгоритм «терпения» был изобретен Брэмом Коэном (создателем BitTorrent), и ключевое отличие состоит в том, что он по-разному сопоставляет одинаковые строки между двумя файлами. Этот абзац из поста Джеймса Коглана прекрасно резюмирует это:
Первое, что нужно отметить, это то, что diff-алгоритм «терпения» сам по себе не является diff-алгоритмом. На самом деле это метод сопоставления строк в двух версиях документа, чтобы разбить их на более мелкие части, прежде чем использовать фактический diff-алгоритм, как Майерса, для этих частей.
Чтобы продемонстрировать, как алгоритм «терпения» может создавать более качественные diff'ы, чем Майерс, давайте сначала посмотрим на diff, созданный Майерсом на основе двух Java-файлов с псевдокодом (исходные файлы можно посмотреть в приложении к этой статье):
git diff --diff-algorithm=myers File1 File2
diff --git a/File1 b/File2
index 38ee31b..2624ba3 100644
--- a/File1
+++ b/File2
@@ -1,20 +1,24 @@
public class File1 {
- public int add (int a, int b)
+ public int sub (int a, int b)
{
+ // TODO: JIRA1234
+ if ( isNull(a, b) )
+ {
+ return null
+ }
log();
- return a + b;
+ return a - b;
}
- public int sub (int a, int b)
+ public int mul (int a, int b)
{
- if (a == b)
+ if ( isNull(a, b) )
{
- return 0;
+ return null;
}
log();
- return a - b;
- // TODO: JIRA1234
+ return a * b;
}
}
Мы можем заметить, что в результате работы алгоритма Майерса:
- найдены совпадающие строки, в которых лишь скобки, между двумя файлами (бесполезно для понимания изменений);
- добавлен и удален метод
sub()в одном и том же файле (на самом деле он был просто перенесен в другое место этого файла).
Такой список изменений понять непросто, так как почти каждая строчка — это изменение. Ревьюер может легко пропустить крайние случаи и/или ошибки в логике.
Давайте теперь посмотрим на diff, полученный алгоритмом «терпения»:
$ git diff --diff-algorithm=patience File1 File2
diff --git a/File1 b/File2
index 38ee31b..2624ba3 100644
--- a/File1
+++ b/File2
@@ -1,20 +1,24 @@
public class File1 {
- public int add (int a, int b)
- {
- log();
- return a + b;
- }
-
public int sub (int a, int b)
{
- if (a == b)
- {
- return 0;
- }
- log();
- return a - b;
// TODO: JIRA1234
+ if ( isNull(a, b) )
+ {
+ return null
+ }
+ log();
+ return a - b;
+ }
+
+ public int mul (int a, int b)
+ {
+ if ( isNull(a, b) )
+ {
+ return null;
+ }
+ log();
+ return a * b;
}
}
С этим diff, созданным алгоритмом «терпения», намного легче наблюдать за изменениями:
- метод
add()был удален; - добавлен метод
mul(); - метод
sub()имеет некоторые изменения в логике.
Когда использовать алгоритм «терпения»:
- Переупорядочивание кода/контента.
- Diff Майерса считает совпадающими тривиальные строки.
- Одни и те же строки добавляются и удаляются в одном и том же файле.
--diff-algorithm={histogram}
Гистограммный diff-алгоритм — это улучшение алгоритма «терпения», который произошел от jgit. Этот вопрос stackoverflow хорошо объясняет разницу и ссылается на класс jgit HistogramDiff, который содержит подробное объяснение:
Всегда выбирая позицию LCS (наибольшей общей подпоследовательности) с наименьшим числом вхождений, этот алгоритм ведет себя точно так же, как diff-алгоритм «терпения» Брэма Коэна, всякий раз, когда между двумя последовательностями есть уникальный общий элемент. Если уникальных элементов не существует, вместо них выбирается элемент с наименьшим вхождением. Это предлагает более удобочитаемые различия, чем простое использование стандартногоO(ND)алгоритма Майерса.
Чтобы лучше понять, почему этот подход лучше, давайте посмотрим на одно из предыдущих изменений при использовании diff-алгоритма «терпения»:
$ git diff --diff-algorithm=patience File1 File2
[...]
public int sub (int a, int b)
{
- if (a == b)
- {
- return 0;
- }
- log();
- return a - b;
// TODO: JIRA1234
+ if ( isNull(a, b) )
+ {
+ return null
+ }
+ log();
+ return a - b;
+ }
[...]
В связи с изменением логики в методе sub() я переместил комментарий TODO с последней строки на первую. К сожалению, алгоритм «терпения», кажется, думает, что комментарий между двумя файлами остался неизменным, а исходные строки были удалены.
Хотя это представление само по себе не является неверным, но предполагает, что вся исходная логика была выброшена (включая выражения log() и return) и вставлен новый набор выражений.
Мы можем показать изменения лучше с помощью гистограммного алгоритма:
$ git diff --diff-algorithm=histogram File1 File2
[..]
public int sub (int a, int b)
{
- if (a == b)
+ // TODO: JIRA1234
+ if ( isNull(a, b) )
{
- return 0;
+ return null
}
log();
return a - b;
- // TODO: JIRA1234
+ }
[...]
Теперь мы можем ясно видеть, что изменилось:
- изменение положения комментария в коде;
- новая логика проверки входных параметров.
Когда использовать гистограммный алгоритм:
- Этот алгоритм лучше описывает изменения кода согласно этому недавнему исследованию, проведенному Nugroho et al (2019).
- Когда у алгоритма «терпения» возникают проблемы с представлением некоторых сделанных изменений.
Резюме
Учитывая набор всех возможных изменений в различных типах файлов (например, source-код, YAML, документация), каждый алгоритм сравнения утилиты git diff лучше подходит для определенного подмножества. Хотя алгоритм Майерса по умолчанию работает хорошо в большинстве случаев, бывают случаи, когда изменение может быть лучше представлено с использованием другого подхода.
Я считаю, что существует набор изменений/файлов, где ни один из представленных diff-алгоритмов не будет работать идеально. В таких случаях либо используйте неоптимальный вывод diff, либо смотрите за пределами утилиты git diff.
Литература
[1] Nugroho, Y.S., Hata, H. & Matsumoto, K. How different are different diff algorithms in Git?. Empir Software Eng 25, 790–823 (2020). https://doi.org/10.1007/s10664-019-09772-z
public class File1 {
public int add (int a, int b)
{
log();
return a + b;
}
public int sub (int a, int b)
{
if (a == b)
{
return 0;
}
log();
return a - b;
// TODO: JIRA1234
}
}
public class File1 {
public int sub (int a, int b)
{
// TODO: JIRA1234
if ( isNull(a, b) )
{
return null
}
log();
return a - b;
}
public int mul (int a, int b)
{
if ( isNull(a, b) )
{
return null;
}
log();
return a * b;
}
}
Переведено: Екатериной Чехрановой