Перемежающиеся дельты - Interleaved deltas

Перемежающиеся дельты, или же SCCS плетение это метод, используемый Система контроля исходного кода для хранения всех ревизий файла. Все строки из всех ревизий «сплетены» вместе в единый блок данных, с чередующимися командами управления, указывающими, какие строки включены в какие ревизии файла. Чередующиеся дельты традиционно реализуются с учетом строчно-ориентированных текстовых файлов, хотя ничто не мешает применять этот метод и к двоичным файлам.

Чередующиеся дельты были впервые реализованы Марк Рохкинд в SCCS в 1975 году. Его дизайн делает все версии доступными одновременно, так что получение любой ревизии занимает одно и то же время. Также он содержит достаточно информации, чтобы идентифицировать автора каждой строчки (виновной) в одном блоке.[1] С другой стороны, поскольку все ревизии файла анализируются, каждая операция выполняется медленнее по мере добавления новых ревизий. Период, термин чередующаяся дельта был придуман позже в 1982 году Уолтер Ф. Тихи, автор Система контроля версий, который сравнивает переплетение SCCS с его новым обратная дельта механизм в RCS.[2]

Реализация в SCCS

В SCCS следующий блок плетения

 ^ AI 1 ^ AD 2 foo ^ AE 2 bar ^ AI 2 baz ^ AE 2 ^ AE 1

представляет файл, содержащий строки «foo» и «bar» в первой версии и строки «bar» и «baz» во второй версии. Строка «^ A» обозначает символ Control-A.

Линии управления в чередующемся блоке дельты имеют следующее значение:[3]

  • ^ AI серийный Начните блок строк, который был вставлен с указанным серийным номером.
  • ^ AD серийный Начните блок строк, который был удален с названного серийного номера.
  • ^ AE серийный Конец блока для соответствующего ^ AI или ^ AD заявление, использующее тот же серийный номер.

Преимущества

Время, необходимое для извлечения любой ревизии из такого чередующегося дельта-блока, пропорционально размеру архива. Размер архива - это сумма размеров всех различных строк во всех ревизиях.

Чтобы извлечь конкретную ревизию, необходимо создать массив структур, сообщающих, будет ли конкретный блок, помеченный серийным номером в чередующихся дельтах, копироваться на выход или нет. Исходная реализация SCCS требует ок. 100 байтов памяти для каждого серийного номера в дельтах, чтобы знать, как извлечь конкретную ревизию. Таким образом, для распаковки файла истории SCCS с одним миллионом дельт потребуется 100 МБ виртуальной памяти. Размер может быть уменьшен прибл. 32 байта на дельту, если получение аннотированного файла не требуется.

Преимущества метода плетения следующие:

  • Единое время поиска для всех ревизий файла.
  • Возможность аннотировать все строки файла с указанием ревизии последнего изменения, автора последнего изменения и времени последнего изменения без дополнительных затрат.
  • Возможность слияния неперекрывающихся веток без дополнительных затрат.

Программное обеспечение с использованием чередующихся дельт

Базар предназначен для использования чередующихся дельт в 2006 году,[5] но от него отказались из-за плохой производительности после того, как он был фактически реализован в bzr 0.1. Он по-прежнему обеспечивает алгоритм слияния в стиле плетения.[6]

Смотрите также

Рекомендации

  1. ^ http://www.basepath.com/aup/talks/SCCS-Slideshow.pdf Рохкинд, Марк. «Система управления исходным кодом (SCCS)». IEEE Transactions по разработке программного обеспечения 1, вып. 4 (1975)
  2. ^ Тихи, Уолтер (1982). «Разработка, внедрение и оценка системы контроля версий». ICSE '82 Труды 6-й Международной конференции по программной инженерии: 58–67. Получено 12 июн 2012.
  3. ^ http://sccs.sourceforge.net/man/sccsfile.4.html sccsfile (4) страница руководства
  4. ^ «Введение в бинарное переплетение». www.bitkeeper.org.
  5. ^ https://web.archive.org/web/20061006032137/http://blog.fxa.org/articles/2005/09/30/bzr-weaving-its-way-to-the-front
  6. ^ «BzrWeaveFormat». Bzr Wiki. Получено 16 января 2020.