This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article is written like a personal reflection, personal essay, or argumentative essay that states a Wikipedia editor's personal feelings or presents an original argument about a topic. Please help improve it by rewriting it in an encyclopedic style. (February 2015) (Learn how and when to remove this template message) The topic of this article may not meet Wikipedia's general notability guideline. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merged, redirected, or deleted.Find sources: "Interleaved deltas" – news · newspapers · books · scholar · JSTOR (February 2015) (Learn how and when to remove this template message) A major contributor to this article appears to have a close connection with its subject. It may require cleanup to comply with Wikipedia's content policies, particularly neutral point of view. Please discuss further on the talk page. (February 2015) (Learn how and when to remove this template message) (Learn how and when to remove this template message)

Interleaved deltas, or SCCS weave is a method used by the Source Code Control System to store all revisions of a file. All lines from all revisions are "woven" together in a single block of data, with interspersed control instructions indicating which lines are included in which revisions of the file. Interleaved deltas are traditionally implemented with line oriented text files in mind, although nothing prevents the method from being applied to binary files as well.

Interleaved deltas were first implemented by Marc Rochkind in the SCCS in 1975. Its design makes all versions available at the same time, so that it takes the same time to retrieve any revision. It also contains sufficient information to identify the author of each line (blaming) in one block.[1] On the other hand, because all revisions for a file are parsed, every operation grows slower as more revisions are added. The term interleaved delta was coined later in 1982 by Walter F. Tichy, author of the Revision Control System, which compares the SCCS weave to his new reverse delta mechanism in RCS.[2]

Implementation in SCCS

In SCCS, the following weave block

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

represents a file that contains the lines "foo" and "bar" in the first release and the lines "bar" and "baz" in the second revision. The string "^A" denotes a control-A character.

The control lines in the interleaved delta block have the following meaning:[3]

Advantages

The time it takes to extract any revision from such an interleaved delta block is proportional to the size of the archive. The size of the archive is the sum of the size of all different lines in all revisions.

In order to extract a specific revision, an array of structures needs to be constructed, telling whether a specific block, tagged by a serial number in the interleaved deltas, will be copied to the output or not. The original SCCS implementation needs approx. 100 bytes of storage for each different serial number in the deltas in order to know how to extract a specific revision. A SCCS history file with one million deltas would thus need 100 MBytes of virtual memory to unpack. The size could be reduced by approx. 32 bytes per delta if no annotated file retrieval is needed.

The advantages of the weave method are the following:

Software using interleaved deltas

Bazaar intended to use interleaved deltas in 2006,[5] but it was ditched due to poor performance after it was actually implemented in bzr 0.1. It still provides a weave-style merge algorithm.[6]

See also

References

  1. ^ http://www.basepath.com/aup/talks/SCCS-Slideshow.pdf Rochkind, Marc. “The source code control system (SCCS).” IEEE Transactions on Software Engineering 1, no. 4 (1975)
  2. ^ Tichy, Walter (1982). "Design, implementation, and evaluation of a Revision Control System". ICSE '82 Proceedings of the 6th International Conference on Software Engineering: 58–67. Retrieved 12 June 2012.
  3. ^ http://sccs.sourceforge.net/man/sccsfile.4.html sccsfile(4) manual page
  4. ^ "Intro to binary weave". www.bitkeeper.org.
  5. ^ "Archived copy". blog.fxa.org. Archived from the original on 6 October 2006. Retrieved 12 January 2022.((cite web)): CS1 maint: archived copy as title (link)
  6. ^ "BzrWeaveFormat". Bzr Wiki. Retrieved 16 January 2020.