Каким образом git за доли секунды находит все мельчайшие изменения среди десятков тысяч файлов?

Ответить
Ответить
Комментировать
0
Подписаться
1
1 ответ
Поделиться

Как и любая система контроля версий (современная, начиная с SVN), git имеет так называемый номер ревизии. Соответственно, git-у не нужно перебирать все файлы проекта, а достаточно перебрать только те файлы, которые ревизии на которые расходятся.

Как пример.У меня в рабочем проекте файлы с ревизиями 123, 125, 335, я запрашиваю удаленный репозиторий, в котором лежат файлы с ревизиями 123, 128, 335. Соответсвенно, git, сравним только номера ревизий заберет и синхронизирует только один файл с ревизией 125-128. Но git еще хитрее, он делает ревизию не на каждый файл, а на каждый коммит и группу файлов в нем, поэтому ему не нужно перебирать ревизии всех файлов проекта (прощай SVN, CVS и иже с ними), а нужно найти сначала расхождения в ревизиях, и уж из этого подмножества найти различающиеся файлы. В этом случае задача поиска расхождений в группах файлов упрощается в логарифмической прогрессии (ну почти в логарифмической).

И да, рекомендую еще посмотреть и на mercurial, очень достойная альтернатива git, и мне более симпатична.

Алексей Черемисинотвечает на ваши вопросы в своейПрямой линии
0
0

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

0
Ответить

Ну, если мы можем индексировать измененные файлы, почему бы нам не индексировать измененные строки? Да и на самом деле, операция сравнения не такая уж и трудозатратная. Сравнить строки в паре сотен файлов - операция на пару миллисекунд. Это например хорошо делает утилита diff и diff3.

И почему же операция сравнения долгая? Если строки имеют разную длину, то они однозначно различаются, и я здесь могу сэкономить время, перескочив на следующую строчку. Если одинаковую, то мне достаточно одного цикла, чтобы сравнить их.

Я думаю, что Вы путаете две совершенно разные операции - побайтное чтение данных (особенно с диска) и побайтное сравнение! Побайтное чтение данных  - это да, кошмар кошмаров, но если читать не побайтно, а блоками, то очень даже быстро. Более того, современные операционные системы поддерживают такой вид чтения, который называется mmap - отображение файла в память.

Ну и для сравнения двух строк есть даже в стандартной библиотеке C функция srtcmp (bcmp/memcmp и и.д.), а в процессоре есть инструкции сдвига и сравнения в памяти, извиняюсь за подробности. Все это работает очень и очень быстро. Иначе, современные компьютеры не смогли бы работать с видео например.

0
Ответить
Прокомментировать
Ответить
Читайте также на Яндекс.Кью
Читайте также на Яндекс.Кью