Interleaved deltas или SCCS weave — это метод, используемый Source Code Control System для хранения всех ревизий файла. Все строки из всех ревизий «сплетаются» вместе в один блок данных с вкраплениями инструкций управления, указывающих, какие строки включены в какие ревизии файла. Interleaved deltas традиционно реализуются с учетом строчно-ориентированных текстовых файлов, хотя ничто не мешает применять этот метод и к двоичным файлам.
Interleaved deltas были впервые реализованы Марком Рохкиндом в SCCS в 1975 году. Его конструкция делает все версии доступными одновременно, так что для извлечения любой ревизии требуется одинаковое время. Он также содержит достаточно информации для идентификации автора каждой строки (обвинения) в одном блоке. [1] С другой стороны, поскольку все ревизии для файла анализируются, каждая операция становится медленнее по мере добавления новых ревизий. Термин interleaved delta был придуман позже в 1982 году Уолтером Ф. Тичи , автором Revision Control System , который сравнивает SCCS weave с его новым механизмом обратной дельты в RCS. [2]
В SCCS следующий блок переплетения
^AI 1 ^2 г. н.э. фу ^AE 2 бар ^AI 2 баз ^AE 2 ^AE 1
представляет файл, содержащий строки "foo" и "bar" в первом выпуске и строки "bar" и "baz" во второй ревизии. Строка "^A" обозначает символ control-A.
Управляющие линии в перемежающемся дельта-блоке имеют следующее значение: [3]
Время, необходимое для извлечения любой ревизии из такого чередующегося дельта-блока, пропорционально размеру архива. Размер архива представляет собой сумму размеров всех различных строк во всех ревизиях.
Для извлечения конкретной ревизии необходимо построить массив структур, сообщающий, будет ли конкретный блок, помеченный серийным номером в чередующихся дельтах, скопирован на выход или нет. Исходной реализации SCCS требуется около 100 байт памяти для каждого отдельного серийного номера в дельтах, чтобы знать, как извлечь конкретную ревизию. Таким образом, файл истории SCCS с одним миллионом дельт потребует 100 МБ виртуальной памяти для распаковки. Размер можно уменьшить примерно на 32 байта на дельту, если не требуется извлечение аннотированного файла.
Преимущества метода плетения следующие:
Bazaar намеревался использовать чередующиеся дельты в 2006 году, [5] но это было отклонено из-за плохой производительности после того, как оно было фактически реализовано в bzr 0.1. Он по-прежнему предоставляет алгоритм слияния в стиле переплетения. [6]