Ответ 1

Эта стратегия гистограммы была введена в git 1.7.7 (сентябрь 2011), со следующим описанием (как упоминалось в OP )

"git diff" выучил опцию --histogram ", чтобы использовать другое оборудование для разломов, украденное из jgit, которое может дать лучшую производительность.

JGit включает src/org/eclipse/jgit/diff/HistogramDiff.java и tst/org/eclipse/jgit/diff/HistogramDiffTest.java

Описание довольно полное:

HistogramDiff

Расширенная форма алгоритма ограничения терпения Брама Коэна.

Эта реализация была получена с использованием 4 правил, которые изложены в  блог Bram Cohen, а затем был расширен, чтобы поддерживать общие элементы с низким уровнем.

Основная идея алгоритма - создать гистограмму вхождений для каждого элемента последовательности A. Каждый элемент последовательности В затем рассматривается поочередно. Если элемент также существует в последовательности A и имеет меньшее число встречаемости, позиции рассматриваются как кандидат на самую длинную общую подпоследовательность (LCS).
После завершения сканирования B LCS, который имеет наименьшее количество вхождений, выбирается как точка разделения. Область разделяется вокруг LCS, и алгоритм рекурсивно применяется к разделам до и после LCS.

Всегда выбирая позицию LCS с наименьшим количеством встречаемости, этот алгоритм ведет себя точно так же, как терпение Bram Cohen diff, всякий раз, когда между этими двумя последовательностями существует уникальный общий элемент.
Если не существует уникальных элементов, вместо него выбирается наименьший элемент вхождения.
Это дает более читаемые отличия, чем просто отключение стандартного алгоритма Myers O(ND).

Чтобы алгоритм не имел время работы O(N^2), верхний предел количества уникальных элементов в веществе гистограммы настраивается #setMaxChainLength(int).
Если в последовательности А есть больше, чем это много элементов, хэш в один и тот же хэш-ведро, алгоритм передает области #setFallbackAlgorithm(DiffAlgorithm).
Если алгоритм резервного копирования не задан, область испускается как замена.

Во время сканирования последовательности B любой элемент из A, который встречается более чем #setMaxChainLength(int), никогда не рассматривается для позиции соответствия LCS, даже если это является общим для двух последовательностей. Это ограничивает количество мест в последовательности A, которые необходимо учитывать для поиска LCS, и помогает поддерживать более низкую временную привязку.

Пока #setMaxChainLength(int) является небольшой константой (например, 64), алгоритм работает в O(N * D) времени, где N - сумма входных длин, а D - количество изменений в результирующем EditList.
Если поставляемый SequenceComparator имеет хорошую хеш-функцию, эта реализация обычно выполняет MyersDiff, хотя его теоретическое время работы одинаковое.

Эта реализация имеет внутреннее ограничение, которое мешает ему обрабатывать последовательности с более чем 268 435 456 (2 28) элементами

Обратите внимание, что этот вид algo был уже использован для pack_check, еще в 2006 году (git 1.3), для git-verify-pack -v. Это было повторно использовано для индексного пакета в git 1.7.7

Commit 8c912ee фактически представил --histogram для разницы:

Порт JGit HistogramDiff алгоритм для C. Черные числа (TODO) показать что он быстрее, чем его двоюродный брат --patience, а также алгоритм Meyers по умолчанию.

Реализация была переработана для использования структур и указателей, вместо битмасков, тем самым устраняя лимит строк JGit 2^28.

Мы также используем xdiff реализацию хэш-таблицы по умолчанию (xdl_hash_bits()с XDL_HASHLONG()) для удобства.

commit 8555123 (git 1.7.10, апрель 2012) добавлено:

8c912ee (преподавать --histogram до diff, 2011-07-12) заявили, что разница в гистограмме был быстрее, чем Майерс и терпение.

С тех пор мы включили рамки тестирования производительности, поэтому добавим который сравнивает различные задачи diff, выполняемые в реальном "log -p", нагрузка.
Это действительно показывает, что разница в гистограмме немного превосходит Майерса, в то время как терпение намного медленнее, чем другие.

Наконец, совершить 07ab4de (git 1.8.2, март 2013) добавить

config: введите переменную diff.algorithm

Некоторые пользователи или проекты предпочитают разные алгоритмы над другими, например. терпение над моими или подобное.
Однако указание подходящего аргумента каждый раз, когда используется diff, нецелесообразно. Более того, создание псевдонима не очень хорошо работает с другими инструментами на основе diff (git-show, например).

Следовательно, необходима переменная конфигурации, которая может установить конкретный алгоритм.
На данный момент эти четыре значения принимаются:

• 'myers' (который имеет тот же эффект, что и не настраивает конфигурационную переменную вообще),
• 'minimal',
• 'patience' и
• histogram.

Commit 07924d4 добавлен одновременно параметр командной строки --diff-algorithm.
Поскольку OP Стюарт П. Бентли упоминает в комментариях:

вы можете настроить git на использование гистограммы по умолчанию с помощью

git config --global diff.algorithm histogram

Обновление: git 2.12 (Q1 2017) уйдет в отставку с "быстрым хешем", который имел катастрофические проблемы с производительностью в некоторых случаях.

См. commit 1f7c926 (01 декабря 2016 г.) Джефф Кинг (peff). ^{(Слияние Junio ​​C Hamano - gitster - в commit 731490b, 19 декабря 2016 г.)}

xdiff: drop XDL_FAST_HASH

Код xdiff хэширует каждую строку с обеих сторон diff, а затем сравнивает эти хэши, чтобы найти дубликаты. Общая производительность зависит как от того, насколько быстро мы можем вычислить хеши, так и от того, сколько коллизий хешей мы видим.

Идея XDL_FAST_HASH заключается в ускорении вычисления хэшей.
Но сгенерированные хэши имеют худшее поведение при столкновении. Это означает, что в некоторых случаях скорость ускоряется (работает git log -p "на git.git улучшается с помощью ~8% с ним), но в других он может замедлить работу. Один патологический случай увидел более 100-кратное замедление.

Может быть улучшенная хеш-функция, которая охватывает оба свойства, но тем временем нам будет лучше с исходным хэшем. Это немного медленнее в общем случае, но у него меньше неожиданных патологических случаев.