Почему Git rebase не требует экспоненциального времени, как Darcs?

Question

Итак, согласно этой странице Википедии о слияниях в управлении версиями, Darcs использует коммутацию патчей и Git, когда она перезагружается.

Мне интересно знать, почему неGit rebase занимает экспоненциальное время в некоторых случаях так же, как это делает Даркс?

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

Answer 1

Вы можете увидеть, что происходит в примере, который я откуда-то вспоминаю: начните с шести строк A B C D E F, на одной ветви вставьте три строки G G G впереди, затем вставьте еще шесть строк A B C D E F впереди; в другой ветке (из этого первого патча / коммита) измените C на C4. Теперь объедините две ветви.

Git будет производить A B C4 D E F G G G A B C D E F; darcs изменит второй C, исходя из того, что его отслеживание идентичности дает лучший результат, чем отслеживание контекста и местоположения в Git. Если «4» является кодом инициализации для блока, результат Git неверен; если это код инициализации для функции или файла, то darcs неверен.

Это та идентификация, которая пожирает время.

Answer 2

Я не использовал даркс и мог быть вне базы, но просматривая статью в Википедии, я замечаю, что его утверждение здесь вводит в заблуждение:

Коммутация исправлений используется в Darcs для объединения изменений, а также реализована в git (но называется «rebasing»). Слияние коммутации патчей означает изменение порядка исправлений (то есть описания изменений), чтобы они формировали линейную историю. Фактически, когда два патча сделаны в контексте общей ситуации, после слияния один из них переписывается так, что кажется, что это делается в контексте другого.

Git не сохраняет патчи и не переупорядочивает их. ¹ Вы можете переупорядочивать патчи вручную, если хотите. Когда вы используете git rebase для преобразования коммитов (которые являются моментальными снимками) в наборы изменений, само преобразование выполняется простым способом: наихудший O (nd) , где n - количество строк и d длина сценария редактирования. (Независимо от того, обрабатывается ли это как патч или как вишня, которая является слиянием, зависит от того, какой алгоритм перебазирования вы выберете; случай слияния имеет тенденцию использовать больше процессорного времени, так как он также ищет операции переименования с трех сторон.)

Следовательно, если у вас есть общее количество коммитов C, наихудший случай для git rebase -i примерно равен O (Cnd). ² Git не будет пытаться выполнить какой-либо другой порядок для коммитов: это до Вам делать любые изменения порядка. Если ваша перебазировка не удалась, вы можете попробовать все возможные переупорядочения, которые будут являться факториальной функцией количества коммитов, но Git не сделает этого за вас.

---

¹ Если вы делаете git rebase для группы коммитов, в которой есть одно или несколько слияний внутри себя, Git «выравнивает» их и устраняет слияния, но не выполняет много заказов он просто делает один топологический обход всего этого. Здесь нет попыток проявить смекалку, и часто это приводит к ужасным конфликтам слияний, т. Е. Зачастую это плохая идея. Если вы используете новый флаг --rebase-merges, Git попытается сохранить слияния, но сделает это заново. Он просто создает идентичную топологию, используя мини-скриптовый язык, а затем позволяет редактировать ее вручную, если хотите.

² Если задействовано обнаружение переименования, то есть O (n ² ) в количестве файлов , которые могут быть обнаружены при переименовании. Git пытается ограничить это несколькими способами, включая максимальную длину очереди переименования, при этом текущим значением по умолчанию является 4000 файлов.