Google Git
Sign in
chromium / external / gitster / git-htmldocs / babc36da06a886574fae916d8ec9ae08d173e0f6 / . / technical / pack-heuristics.html
blob: 979e8358993d88c511ebd0def7babcc6560b1264 [file] [log] [blame]
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
2 "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
3<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
4<head>
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]5<meta http-equiv="Content-Type" content="application/xhtml+xml; charset=UTF-8" />
6<meta name="generator" content="AsciiDoc 8.6.8" />
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]7<title></title>
8<style type="text/css">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]9/* Shared CSS for AsciiDoc xhtml11 and html5 backends */
10
11/* Default font. */
12body {
13 font-family: Georgia,serif;
14}
15
16/* Title font. */
17h1, h2, h3, h4, h5, h6,
18div.title, caption.title,
19thead, p.table.header,
20#toctitle,
21#author, #revnumber, #revdate, #revremark,
22#footer {
23 font-family: Arial,Helvetica,sans-serif;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]24}
25
26body {
27 margin: 1em 5% 1em 5%;
28}
29
30a {
31 color: blue;
32 text-decoration: underline;
33}
34a:visited {
35 color: fuchsia;
36}
37
38em {
39 font-style: italic;
40 color: navy;
41}
42
43strong {
44 font-weight: bold;
45 color: #083194;
46}
47
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]48h1, h2, h3, h4, h5, h6 {
49 color: #527bbd;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]50 margin-top: 1.2em;
51 margin-bottom: 0.5em;
52 line-height: 1.3;
53}
54
55h1, h2, h3 {
56 border-bottom: 2px solid silver;
57}
58h2 {
59 padding-top: 0.5em;
60}
61h3 {
62 float: left;
63}
64h3 + * {
65 clear: left;
66}
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]67h5 {
68 font-size: 1.0em;
69}
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]70
71div.sectionbody {
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]72 margin-left: 0;
73}
74
75hr {
76 border: 1px solid silver;
77}
78
79p {
80 margin-top: 0.5em;
81 margin-bottom: 0.5em;
82}
83
84ul, ol, li > p {
85 margin-top: 0;
86}
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]87ul > li { color: #aaa; }
88ul > li > * { color: black; }
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]89
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]90.monospaced, code, pre {
91 font-family: "Courier New", Courier, monospace;
92 font-size: inherit;
93 color: navy;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]94 padding: 0;
95 margin: 0;
96}
97
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]98
99#author {
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]100 color: #527bbd;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]101 font-weight: bold;
102 font-size: 1.1em;
103}
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]104#email {
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]105}
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]106#revnumber, #revdate, #revremark {
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]107}
108
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]109#footer {
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]110 font-size: small;
111 border-top: 2px solid silver;
112 padding-top: 0.5em;
113 margin-top: 4.0em;
114}
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]115#footer-text {
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]116 float: left;
117 padding-bottom: 0.5em;
118}
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]119#footer-badges {
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]120 float: right;
121 padding-bottom: 0.5em;
122}
123
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]124#preamble {
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]125 margin-top: 1.5em;
126 margin-bottom: 1.5em;
127}
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]128div.imageblock, div.exampleblock, div.verseblock,
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]129div.quoteblock, div.literalblock, div.listingblock, div.sidebarblock,
130div.admonitionblock {
131 margin-top: 1.0em;
132 margin-bottom: 1.5em;
133}
134div.admonitionblock {
135 margin-top: 2.0em;
136 margin-bottom: 2.0em;
137 margin-right: 10%;
138 color: #606060;
139}
140
141div.content { /* Block element content. */
142 padding: 0;
143}
144
145/* Block element titles. */
146div.title, caption.title {
147 color: #527bbd;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]148 font-weight: bold;
149 text-align: left;
150 margin-top: 1.0em;
151 margin-bottom: 0.5em;
152}
153div.title + * {
154 margin-top: 0;
155}
156
157td div.title:first-child {
158 margin-top: 0.0em;
159}
160div.content div.title:first-child {
161 margin-top: 0.0em;
162}
163div.content + div.title {
164 margin-top: 0.0em;
165}
166
167div.sidebarblock > div.content {
168 background: #ffffee;
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]169 border: 1px solid #dddddd;
170 border-left: 4px solid #f0f0f0;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]171 padding: 0.5em;
172}
173
174div.listingblock > div.content {
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]175 border: 1px solid #dddddd;
176 border-left: 5px solid #f0f0f0;
177 background: #f8f8f8;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]178 padding: 0.5em;
179}
180
181div.quoteblock, div.verseblock {
182 padding-left: 1.0em;
183 margin-left: 1.0em;
184 margin-right: 10%;
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]185 border-left: 5px solid #f0f0f0;
186 color: #888;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]187}
188
189div.quoteblock > div.attribution {
190 padding-top: 0.5em;
191 text-align: right;
192}
193
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]194div.verseblock > pre.content {
195 font-family: inherit;
196 font-size: inherit;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]197}
198div.verseblock > div.attribution {
199 padding-top: 0.75em;
200 text-align: left;
201}
202/* DEPRECATED: Pre version 8.2.7 verse style literal block. */
203div.verseblock + div.attribution {
204 text-align: left;
205}
206
207div.admonitionblock .icon {
208 vertical-align: top;
209 font-size: 1.1em;
210 font-weight: bold;
211 text-decoration: underline;
212 color: #527bbd;
213 padding-right: 0.5em;
214}
215div.admonitionblock td.content {
216 padding-left: 0.5em;
217 border-left: 3px solid #dddddd;
218}
219
220div.exampleblock > div.content {
221 border-left: 3px solid #dddddd;
222 padding-left: 0.5em;
223}
224
225div.imageblock div.content { padding-left: 0; }
226span.image img { border-style: none; }
227a.image:visited { color: white; }
228
229dl {
230 margin-top: 0.8em;
231 margin-bottom: 0.8em;
232}
233dt {
234 margin-top: 0.5em;
235 margin-bottom: 0;
236 font-style: normal;
237 color: navy;
238}
239dd > *:first-child {
240 margin-top: 0.1em;
241}
242
243ul, ol {
244 list-style-position: outside;
245}
246ol.arabic {
247 list-style-type: decimal;
248}
249ol.loweralpha {
250 list-style-type: lower-alpha;
251}
252ol.upperalpha {
253 list-style-type: upper-alpha;
254}
255ol.lowerroman {
256 list-style-type: lower-roman;
257}
258ol.upperroman {
259 list-style-type: upper-roman;
260}
261
262div.compact ul, div.compact ol,
263div.compact p, div.compact p,
264div.compact div, div.compact div {
265 margin-top: 0.1em;
266 margin-bottom: 0.1em;
267}
268
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]269tfoot {
270 font-weight: bold;
271}
272td > div.verse {
273 white-space: pre;
274}
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]275
276div.hdlist {
277 margin-top: 0.8em;
278 margin-bottom: 0.8em;
279}
280div.hdlist tr {
281 padding-bottom: 15px;
282}
283dt.hdlist1.strong, td.hdlist1.strong {
284 font-weight: bold;
285}
286td.hdlist1 {
287 vertical-align: top;
288 font-style: normal;
289 padding-right: 0.8em;
290 color: navy;
291}
292td.hdlist2 {
293 vertical-align: top;
294}
295div.hdlist.compact tr {
296 margin: 0;
297 padding-bottom: 0;
298}
299
300.comment {
301 background: yellow;
302}
303
304.footnote, .footnoteref {
305 font-size: 0.8em;
306}
307
308span.footnote, span.footnoteref {
309 vertical-align: super;
310}
311
312#footnotes {
313 margin: 20px 0 20px 0;
314 padding: 7px 0 0 0;
315}
316
317#footnotes div.footnote {
318 margin: 0 0 5px 0;
319}
320
321#footnotes hr {
322 border: none;
323 border-top: 1px solid silver;
324 height: 1px;
325 text-align: left;
326 margin-left: 0;
327 width: 20%;
328 min-width: 100px;
329}
330
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]331div.colist td {
332 padding-right: 0.5em;
333 padding-bottom: 0.3em;
334 vertical-align: top;
335}
336div.colist td img {
337 margin-top: 0.3em;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]338}
339
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]340@media print {
341 #footer-badges { display: none; }
342}
343
344#toc {
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]345 margin-bottom: 2.5em;
346}
347
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]348#toctitle {
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]349 color: #527bbd;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]350 font-size: 1.1em;
351 font-weight: bold;
352 margin-top: 1.0em;
353 margin-bottom: 0.1em;
354}
355
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]356div.toclevel0, div.toclevel1, div.toclevel2, div.toclevel3, div.toclevel4 {
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]357 margin-top: 0;
358 margin-bottom: 0;
359}
360div.toclevel2 {
361 margin-left: 2em;
362 font-size: 0.9em;
363}
364div.toclevel3 {
365 margin-left: 4em;
366 font-size: 0.9em;
367}
368div.toclevel4 {
369 margin-left: 6em;
370 font-size: 0.9em;
371}
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]372
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]373span.aqua { color: aqua; }
374span.black { color: black; }
375span.blue { color: blue; }
376span.fuchsia { color: fuchsia; }
377span.gray { color: gray; }
378span.green { color: green; }
379span.lime { color: lime; }
380span.maroon { color: maroon; }
381span.navy { color: navy; }
382span.olive { color: olive; }
383span.purple { color: purple; }
384span.red { color: red; }
385span.silver { color: silver; }
386span.teal { color: teal; }
387span.white { color: white; }
388span.yellow { color: yellow; }
389
390span.aqua-background { background: aqua; }
391span.black-background { background: black; }
392span.blue-background { background: blue; }
393span.fuchsia-background { background: fuchsia; }
394span.gray-background { background: gray; }
395span.green-background { background: green; }
396span.lime-background { background: lime; }
397span.maroon-background { background: maroon; }
398span.navy-background { background: navy; }
399span.olive-background { background: olive; }
400span.purple-background { background: purple; }
401span.red-background { background: red; }
402span.silver-background { background: silver; }
403span.teal-background { background: teal; }
404span.white-background { background: white; }
405span.yellow-background { background: yellow; }
406
407span.big { font-size: 2em; }
408span.small { font-size: 0.6em; }
409
410span.underline { text-decoration: underline; }
411span.overline { text-decoration: overline; }
412span.line-through { text-decoration: line-through; }
413
414div.unbreakable { page-break-inside: avoid; }
415
416
417/*
418 * xhtml11 specific
419 *
420 * */
421
422div.tableblock {
423 margin-top: 1.0em;
424 margin-bottom: 1.5em;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]425}
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]426div.tableblock > table {
427 border: 3px solid #527bbd;
428}
429thead, p.table.header {
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]430 font-weight: bold;
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]431 color: #527bbd;
432}
433p.table {
434 margin-top: 0;
435}
436/* Because the table frame attribute is overriden by CSS in most browsers. */
437div.tableblock > table[frame="void"] {
438 border-style: none;
439}
440div.tableblock > table[frame="hsides"] {
441 border-left-style: none;
442 border-right-style: none;
443}
444div.tableblock > table[frame="vsides"] {
445 border-top-style: none;
446 border-bottom-style: none;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]447}
448
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]449
450/*
451 * html5 specific
452 *
453 * */
454
455table.tableblock {
456 margin-top: 1.0em;
457 margin-bottom: 1.5em;
458}
459thead, p.tableblock.header {
460 font-weight: bold;
461 color: #527bbd;
462}
463p.tableblock {
464 margin-top: 0;
465}
466table.tableblock {
467 border-width: 3px;
468 border-spacing: 0px;
469 border-style: solid;
470 border-color: #527bbd;
471 border-collapse: collapse;
472}
473th.tableblock, td.tableblock {
474 border-width: 1px;
475 padding: 4px;
476 border-style: solid;
477 border-color: #527bbd;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]478}
479
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]480table.tableblock.frame-topbot {
481 border-left-style: hidden;
482 border-right-style: hidden;
483}
484table.tableblock.frame-sides {
485 border-top-style: hidden;
486 border-bottom-style: hidden;
487}
488table.tableblock.frame-none {
489 border-style: hidden;
490}
491
492th.tableblock.halign-left, td.tableblock.halign-left {
493 text-align: left;
494}
495th.tableblock.halign-center, td.tableblock.halign-center {
496 text-align: center;
497}
498th.tableblock.halign-right, td.tableblock.halign-right {
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]499 text-align: right;
500}
501
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]502th.tableblock.valign-top, td.tableblock.valign-top {
503 vertical-align: top;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]504}
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]505th.tableblock.valign-middle, td.tableblock.valign-middle {
506 vertical-align: middle;
507}
508th.tableblock.valign-bottom, td.tableblock.valign-bottom {
509 vertical-align: bottom;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]510}
511
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]512
513/*
514 * manpage specific
515 *
516 * */
517
518body.manpage h1 {
519 padding-top: 0.5em;
520 padding-bottom: 0.5em;
521 border-top: 2px solid silver;
522 border-bottom: 2px solid silver;
523}
524body.manpage h2 {
525 border-style: none;
526}
527body.manpage div.sectionbody {
528 margin-left: 3em;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]529}
530
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]531@media print {
532 body.manpage div#toc { display: none; }
533}
534
535
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]536</style>
537<script type="text/javascript">
538/*<![CDATA[*/
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]539var asciidoc = { // Namespace.
540
541/////////////////////////////////////////////////////////////////////
542// Table Of Contents generator
543/////////////////////////////////////////////////////////////////////
544
545/* Author: Mihai Bazon, September 2002
546 * http://students.infoiasi.ro/~mishoo
547 *
548 * Table Of Content generator
549 * Version: 0.4
550 *
551 * Feel free to use this script under the terms of the GNU General Public
552 * License, as long as you do not remove or alter this notice.
553 */
554
555 /* modified by Troy D. Hanson, September 2006. License: GPL */
556 /* modified by Stuart Rackham, 2006, 2009. License: GPL */
557
558// toclevels = 1..4.
559toc: function (toclevels) {
560
561 function getText(el) {
562 var text = "";
563 for (var i = el.firstChild; i != null; i = i.nextSibling) {
564 if (i.nodeType == 3 /* Node.TEXT_NODE */) // IE doesn't speak constants.
565 text += i.data;
566 else if (i.firstChild != null)
567 text += getText(i);
568 }
569 return text;
570 }
571
572 function TocEntry(el, text, toclevel) {
573 this.element = el;
574 this.text = text;
575 this.toclevel = toclevel;
576 }
577
578 function tocEntries(el, toclevels) {
579 var result = new Array;
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]580 var re = new RegExp('[hH]([1-'+(toclevels+1)+'])');
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]581 // Function that scans the DOM tree for header elements (the DOM2
582 // nodeIterator API would be a better technique but not supported by all
583 // browsers).
584 var iterate = function (el) {
585 for (var i = el.firstChild; i != null; i = i.nextSibling) {
586 if (i.nodeType == 1 /* Node.ELEMENT_NODE */) {
587 var mo = re.exec(i.tagName);
588 if (mo && (i.getAttribute("class") || i.getAttribute("className")) != "float") {
589 result[result.length] = new TocEntry(i, getText(i), mo[1]-1);
590 }
591 iterate(i);
592 }
593 }
594 }
595 iterate(el);
596 return result;
597 }
598
599 var toc = document.getElementById("toc");
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]600 if (!toc) {
601 return;
602 }
603
604 // Delete existing TOC entries in case we're reloading the TOC.
605 var tocEntriesToRemove = [];
606 var i;
607 for (i = 0; i < toc.childNodes.length; i++) {
608 var entry = toc.childNodes[i];
609 if (entry.nodeName.toLowerCase() == 'div'
610 && entry.getAttribute("class")
611 && entry.getAttribute("class").match(/^toclevel/))
612 tocEntriesToRemove.push(entry);
613 }
614 for (i = 0; i < tocEntriesToRemove.length; i++) {
615 toc.removeChild(tocEntriesToRemove[i]);
616 }
617
618 // Rebuild TOC entries.
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]619 var entries = tocEntries(document.getElementById("content"), toclevels);
620 for (var i = 0; i < entries.length; ++i) {
621 var entry = entries[i];
622 if (entry.element.id == "")
623 entry.element.id = "_toc_" + i;
624 var a = document.createElement("a");
625 a.href = "#" + entry.element.id;
626 a.appendChild(document.createTextNode(entry.text));
627 var div = document.createElement("div");
628 div.appendChild(a);
629 div.className = "toclevel" + entry.toclevel;
630 toc.appendChild(div);
631 }
632 if (entries.length == 0)
633 toc.parentNode.removeChild(toc);
634},
635
636
637/////////////////////////////////////////////////////////////////////
638// Footnotes generator
639/////////////////////////////////////////////////////////////////////
640
641/* Based on footnote generation code from:
642 * http://www.brandspankingnew.net/archive/2005/07/format_footnote.html
643 */
644
645footnotes: function () {
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]646 // Delete existing footnote entries in case we're reloading the footnodes.
647 var i;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]648 var noteholder = document.getElementById("footnotes");
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]649 if (!noteholder) {
650 return;
651 }
652 var entriesToRemove = [];
653 for (i = 0; i < noteholder.childNodes.length; i++) {
654 var entry = noteholder.childNodes[i];
655 if (entry.nodeName.toLowerCase() == 'div' && entry.getAttribute("class") == "footnote")
656 entriesToRemove.push(entry);
657 }
658 for (i = 0; i < entriesToRemove.length; i++) {
659 noteholder.removeChild(entriesToRemove[i]);
660 }
661
662 // Rebuild footnote entries.
663 var cont = document.getElementById("content");
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]664 var spans = cont.getElementsByTagName("span");
665 var refs = {};
666 var n = 0;
667 for (i=0; i<spans.length; i++) {
668 if (spans[i].className == "footnote") {
669 n++;
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]670 var note = spans[i].getAttribute("data-note");
671 if (!note) {
672 // Use [\s\S] in place of . so multi-line matches work.
673 // Because JavaScript has no s (dotall) regex flag.
674 note = spans[i].innerHTML.match(/\s*\[([\s\S]*)]\s*/)[1];
675 spans[i].innerHTML =
676 "[<a id='_footnoteref_" + n + "' href='#_footnote_" + n +
677 "' title='View footnote' class='footnote'>" + n + "</a>]";
678 spans[i].setAttribute("data-note", note);
679 }
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]680 noteholder.innerHTML +=
681 "<div class='footnote' id='_footnote_" + n + "'>" +
682 "<a href='#_footnoteref_" + n + "' title='Return to text'>" +
683 n + "</a>. " + note + "</div>";
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]684 var id =spans[i].getAttribute("id");
685 if (id != null) refs["#"+id] = n;
686 }
687 }
688 if (n == 0)
689 noteholder.parentNode.removeChild(noteholder);
690 else {
691 // Process footnoterefs.
692 for (i=0; i<spans.length; i++) {
693 if (spans[i].className == "footnoteref") {
694 var href = spans[i].getElementsByTagName("a")[0].getAttribute("href");
695 href = href.match(/#.*/)[0]; // Because IE return full URL.
696 n = refs[href];
697 spans[i].innerHTML =
698 "[<a href='#_footnote_" + n +
699 "' title='View footnote' class='footnote'>" + n + "</a>]";
700 }
701 }
702 }
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]703},
704
705install: function(toclevels) {
706 var timerId;
707
708 function reinstall() {
709 asciidoc.footnotes();
710 if (toclevels) {
711 asciidoc.toc(toclevels);
712 }
713 }
714
715 function reinstallAndRemoveTimer() {
716 clearInterval(timerId);
717 reinstall();
718 }
719
720 timerId = setInterval(reinstall, 500);
721 if (document.addEventListener)
722 document.addEventListener("DOMContentLoaded", reinstallAndRemoveTimer, false);
723 else
724 window.onload = reinstallAndRemoveTimer;
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]725}
726
727}
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]728asciidoc.install();
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]729/*]]>*/
730</script>
731</head>
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]732<body class="article">
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]733<div id="header">
734</div>
735<div id="content">
736<div class="literalblock">
737<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]738<pre><code>Concerning Git's Packing Heuristics
739===================================</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]740</div></div>
741<div class="literalblock">
742<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]743<pre><code>Oh, here's a really stupid question:</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]744</div></div>
745<div class="literalblock">
746<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]747<pre><code> Where do I go
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]748 to learn the details
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]749of git's packing heuristics?</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]750</div></div>
751<div class="paragraph"><p>Be careful what you ask!</p></div>
752<div class="paragraph"><p>Followers of the git, please open the git IRC Log and turn to
753February 10, 2006.</p></div>
754<div class="paragraph"><p>It&#8217;s a rare occasion, and we are joined by the King Git Himself,
755Linus Torvalds (linus). Nathaniel Smith, (njs`), has the floor
756and seeks enlightenment. Others are present, but silent.</p></div>
757<div class="paragraph"><p>Let&#8217;s listen in!</p></div>
758<div class="literalblock">
759<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]760<pre><code>&lt;njs`&gt; Oh, here's a really stupid question -- where do I go to
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]761 learn the details of git's packing heuristics? google avails
762 me not, reading the source didn't help a lot, and wading
763 through the whole mailing list seems less efficient than any
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]764 of that.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]765</div></div>
766<div class="paragraph"><p>It is a bold start! A plea for help combined with a simultaneous
767tri-part attack on some of the tried and true mainstays in the quest
768for enlightenment. Brash accusations of google being useless. Hubris!
769Maligning the source. Heresy! Disdain for the mailing list archives.
770Woe.</p></div>
771<div class="literalblock">
772<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]773<pre><code>&lt;pasky&gt; yes, the packing-related delta stuff is somewhat
774 mysterious even for me ;)</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]775</div></div>
776<div class="paragraph"><p>Ah! Modesty after all.</p></div>
777<div class="literalblock">
778<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]779<pre><code>&lt;linus&gt; njs, I don't think the docs exist. That's something where
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]780 I don't think anybody else than me even really got involved.
781 Most of the rest of git others have been busy with (especially
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]782 Junio), but packing nobody touched after I did it.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]783</div></div>
784<div class="paragraph"><p>It&#8217;s cryptic, yet vague. Linus in style for sure. Wise men
785interpret this as an apology. A few argue it is merely a
786statement of fact.</p></div>
787<div class="literalblock">
788<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]789<pre><code>&lt;njs`&gt; I guess the next step is "read the source again", but I
790 have to build up a certain level of gumption first :-)</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]791</div></div>
792<div class="paragraph"><p>Indeed! On both points.</p></div>
793<div class="literalblock">
794<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]795<pre><code>&lt;linus&gt; The packing heuristic is actually really really simple.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]796</div></div>
797<div class="paragraph"><p>Bait&#8230;</p></div>
798<div class="literalblock">
799<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]800<pre><code>&lt;linus&gt; But strange.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]801</div></div>
802<div class="paragraph"><p>And switch. That ought to do it!</p></div>
803<div class="literalblock">
804<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]805<pre><code>&lt;linus&gt; Remember: git really doesn't follow files. So what it does is
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]806 - generate a list of all objects
807 - sort the list according to magic heuristics
808 - walk the list, using a sliding window, seeing if an object
809 can be diffed against another object in the window
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]810 - write out the list in recency order</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]811</div></div>
812<div class="paragraph"><p>The traditional understatement:</p></div>
813<div class="literalblock">
814<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]815<pre><code>&lt;njs`&gt; I suspect that what I'm missing is the precise definition of
816 the word "magic"</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]817</div></div>
818<div class="paragraph"><p>The traditional insight:</p></div>
819<div class="literalblock">
820<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]821<pre><code>&lt;pasky&gt; yes</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]822</div></div>
823<div class="paragraph"><p>And Babel-like confusion flowed.</p></div>
824<div class="literalblock">
825<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]826<pre><code>&lt;njs`&gt; oh, hmm, and I'm not sure what this sliding window means either</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]827</div></div>
828<div class="literalblock">
829<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]830<pre><code>&lt;pasky&gt; iirc, it appeared to me to be just the sha1 of the object
831 when reading the code casually ...</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]832</div></div>
833<div class="olist lowerroman"><ol class="lowerroman">
834<li>
835<p>
836which simply doesn&#8217;t sound as a very good heuristics, though ;)
837</p>
838<div class="literalblock">
839<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]840<pre><code>&lt;njs`&gt; .....and recency order. okay, I think it's clear I didn't
841 even realize how much I wasn't realizing :-)</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]842</div></div>
843</li>
844</ol></div>
845<div class="paragraph"><p>Ah, grasshopper! And thus the enlightenment begins anew.</p></div>
846<div class="literalblock">
847<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]848<pre><code>&lt;linus&gt; The "magic" is actually in theory totally arbitrary.
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]849 ANY order will give you a working pack, but no, it's not
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]850 ordered by SHA1.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]851</div></div>
852<div class="literalblock">
853<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]854<pre><code>Before talking about the ordering for the sliding delta
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]855window, let's talk about the recency order. That's more
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]856important in one way.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]857</div></div>
858<div class="literalblock">
859<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]860<pre><code>&lt;njs`&gt; Right, but if all you want is a working way to pack things
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]861 together, you could just use cat and save yourself some
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]862 trouble...</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]863</div></div>
864<div class="paragraph"><p>Waaait for it&#8230;.</p></div>
865<div class="literalblock">
866<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]867<pre><code>&lt;linus&gt; The recency ordering (which is basically: put objects
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]868 _physically_ into the pack in the order that they are
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]869 "reachable" from the head) is important.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]870</div></div>
871<div class="literalblock">
872<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]873<pre><code>&lt;njs`&gt; okay</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]874</div></div>
875<div class="literalblock">
876<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]877<pre><code>&lt;linus&gt; It's important because that's the thing that gives packs
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]878 good locality. It keeps the objects close to the head (whether
879 they are old or new, but they are _reachable_ from the head)
880 at the head of the pack. So packs actually have absolutely
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]881 _wonderful_ IO patterns.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]882</div></div>
883<div class="paragraph"><p>Read that again, because it is important.</p></div>
884<div class="literalblock">
885<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]886<pre><code>&lt;linus&gt; But recency ordering is totally useless for deciding how
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]887 to actually generate the deltas, so the delta ordering is
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]888 something else.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]889</div></div>
890<div class="literalblock">
891<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]892<pre><code>The delta ordering is (wait for it):
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]893- first sort by the "basename" of the object, as defined by
894 the name the object was _first_ reached through when
895 generating the object list
896- within the same basename, sort by size of the object
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]897- but always sort different types separately (commits first).</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]898</div></div>
899<div class="literalblock">
900<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]901<pre><code>That's not exactly it, but it's very close.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]902</div></div>
903<div class="literalblock">
904<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]905<pre><code>&lt;njs`&gt; The "_first_ reached" thing is not too important, just you
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]906 need some way to break ties since the same objects may be
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]907 reachable many ways, yes?</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]908</div></div>
909<div class="paragraph"><p>And as if to clarify:</p></div>
910<div class="literalblock">
911<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]912<pre><code>&lt;linus&gt; The point is that it's all really just any random
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]913 heuristic, and the ordering is totally unimportant for
914 correctness, but it helps a lot if the heuristic gives
915 "clumping" for things that are likely to delta well against
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]916 each other.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]917</div></div>
918<div class="paragraph"><p>It is an important point, so secretly, I did my own research and have
919included my results below. To be fair, it has changed some over time.
920And through the magic of Revisionistic History, I draw upon this entry
921from The Git IRC Logs on my father&#8217;s birthday, March 1:</p></div>
922<div class="literalblock">
923<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]924<pre><code>&lt;gitster&gt; The quote from the above linus should be rewritten a
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]925 bit (wait for it):
926 - first sort by type. Different objects never delta with
927 each other.
928 - then sort by filename/dirname. hash of the basename
929 occupies the top BITS_PER_INT-DIR_BITS bits, and bottom
930 DIR_BITS are for the hash of leading path elements.
931 - then if we are doing "thin" pack, the objects we are _not_
932 going to pack but we know about are sorted earlier than
933 other objects.
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]934 - and finally sort by size, larger to smaller.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]935</div></div>
936<div class="paragraph"><p>In one swell-foop, clarification and obscurification! Nonetheless,
937authoritative. Cryptic, yet concise. It even solicits notions of
938quotes from The Source Code. Clearly, more study is needed.</p></div>
939<div class="literalblock">
940<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]941<pre><code>&lt;gitster&gt; That's the sort order. What this means is:
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]942 - we do not delta different object types.
943 - we prefer to delta the objects with the same full path, but
944 allow files with the same name from different directories.
945 - we always prefer to delta against objects we are not going
946 to send, if there are some.
947 - we prefer to delta against larger objects, so that we have
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]948 lots of removals.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]949</div></div>
950<div class="literalblock">
951<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]952<pre><code>The penultimate rule is for "thin" packs. It is used when
953the other side is known to have such objects.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]954</div></div>
955<div class="paragraph"><p>There it is again. "Thin" packs. I&#8217;m thinking to myself, "What
956is a <em>thin</em> pack?" So I ask:</p></div>
957<div class="literalblock">
958<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]959<pre><code>&lt;jdl&gt; What is a "thin" pack?</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]960</div></div>
961<div class="literalblock">
962<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]963<pre><code>&lt;gitster&gt; Use of --objects-edge to rev-list as the upstream of
964 pack-objects. The pack transfer protocol negotiates that.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]965</div></div>
966<div class="paragraph"><p>Woo hoo! Cleared that <em>right</em> up!</p></div>
967<div class="literalblock">
968<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]969<pre><code>&lt;gitster&gt; There are two directions - push and fetch.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]970</div></div>
971<div class="paragraph"><p>There! Did you see it? It is not <em>"push" and "pull"</em>! How often the
972confusion has started here. So casually mentioned, too!</p></div>
973<div class="literalblock">
974<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]975<pre><code>&lt;gitster&gt; For push, git-send-pack invokes git-receive-pack on the
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]976 other end. The receive-pack says "I have up to these commits".
977 send-pack looks at them, and computes what are missing from
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]978 the other end. So "thin" could be the default there.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]979</div></div>
980<div class="literalblock">
981<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]982<pre><code>In the other direction, fetch, git-fetch-pack and
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]983git-clone-pack invokes git-upload-pack on the other end
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]984(via ssh or by talking to the daemon).</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]985</div></div>
986<div class="literalblock">
987<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]988<pre><code>There are two cases: fetch-pack with -k and clone-pack is one,
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]989fetch-pack without -k is the other. clone-pack and fetch-pack
990with -k will keep the downloaded packfile without expanded, so
991we do not use thin pack transfer. Otherwise, the generated
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]992pack will have delta without base object in the same pack.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]993</div></div>
994<div class="literalblock">
995<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]996<pre><code>But fetch-pack without -k will explode the received pack into
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]997individual objects, so we automatically ask upload-pack to
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]998give us a thin pack if upload-pack supports it.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]999</div></div>
1000<div class="paragraph"><p>OK then.</p></div>
1001<div class="paragraph"><p>Uh.</p></div>
1002<div class="paragraph"><p>Let&#8217;s return to the previous conversation still in progress.</p></div>
1003<div class="literalblock">
1004<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1005<pre><code>&lt;njs`&gt; and "basename" means something like "the tail of end of
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1006 path of file objects and dir objects, as per basename(3), and
1007 we just declare all commit and tag objects to have the same
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1008 basename" or something?</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1009</div></div>
1010<div class="paragraph"><p>Luckily, that too is a point that gitster clarified for us!</p></div>
1011<div class="paragraph"><p>If I might add, the trick is to make files that <em>might</em> be similar be
1012located close to each other in the hash buckets based on their file
1013names. It used to be that "foo/Makefile", "bar/baz/quux/Makefile" and
1014"Makefile" all landed in the same bucket due to their common basename,
1015"Makefile". However, now they land in "close" buckets.</p></div>
1016<div class="paragraph"><p>The algorithm allows not just for the <em>same</em> bucket, but for <em>close</em>
1017buckets to be considered delta candidates. The rationale is
1018essentially that files, like Makefiles, often have very similar
1019content no matter what directory they live in.</p></div>
1020<div class="literalblock">
1021<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1022<pre><code>&lt;linus&gt; I played around with different delta algorithms, and with
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1023 making the "delta window" bigger, but having too big of a
1024 sliding window makes it very expensive to generate the pack:
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1025 you need to compare every object with a _ton_ of other objects.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1026</div></div>
1027<div class="literalblock">
1028<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1029<pre><code>There are a number of other trivial heuristics too, which
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1030basically boil down to "don't bother even trying to delta this
1031pair" if we can tell before-hand that the delta isn't worth it
1032(due to size differences, where we can take a previous delta
1033result into account to decide that "ok, no point in trying
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1034that one, it will be worse").</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1035</div></div>
1036<div class="literalblock">
1037<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1038<pre><code>End result: packing is actually very size efficient. It's
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1039somewhat CPU-wasteful, but on the other hand, since you're
1040really only supposed to do it maybe once a month (and you can
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1041do it during the night), nobody really seems to care.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1042</div></div>
1043<div class="paragraph"><p>Nice Engineering Touch, there. Find when it doesn&#8217;t matter, and
1044proclaim it a non-issue. Good style too!</p></div>
1045<div class="literalblock">
1046<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1047<pre><code>&lt;njs`&gt; So, just to repeat to see if I'm following, we start by
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1048 getting a list of the objects we want to pack, we sort it by
1049 this heuristic (basically lexicographically on the tuple
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1050 (type, basename, size)).</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1051</div></div>
1052<div class="literalblock">
1053<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1054<pre><code>Then we walk through this list, and calculate a delta of
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1055each object against the last n (tunable parameter) objects,
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1056and pick the smallest of these deltas.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1057</div></div>
1058<div class="paragraph"><p>Vastly simplified, but the essence is there!</p></div>
1059<div class="literalblock">
1060<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1061<pre><code>&lt;linus&gt; Correct.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1062</div></div>
1063<div class="literalblock">
1064<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1065<pre><code>&lt;njs`&gt; And then once we have picked a delta or fulltext to
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1066 represent each object, we re-sort by recency, and write them
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1067 out in that order.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1068</div></div>
1069<div class="literalblock">
1070<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1071<pre><code>&lt;linus&gt; Yup. Some other small details:</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1072</div></div>
1073<div class="paragraph"><p>And of course there is the "Other Shoe" Factor too.</p></div>
1074<div class="literalblock">
1075<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1076<pre><code>&lt;linus&gt; - We limit the delta depth to another magic value (right
1077 now both the window and delta depth magic values are just "10")</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1078</div></div>
1079<div class="literalblock">
1080<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1081<pre><code>&lt;njs`&gt; Hrm, my intuition is that you'd end up with really _bad_ IO
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1082 patterns, because the things you want are near by, but to
1083 actually reconstruct them you may have to jump all over in
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1084 random ways.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1085</div></div>
1086<div class="literalblock">
1087<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1088<pre><code>&lt;linus&gt; - When we write out a delta, and we haven't yet written
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1089 out the object it is a delta against, we write out the base
1090 object first. And no, when we reconstruct them, we actually
1091 get nice IO patterns, because:
1092 - larger objects tend to be "more recent" (Linus' law: files grow)
1093 - we actively try to generate deltas from a larger object to a
1094 smaller one
1095 - this means that the top-of-tree very seldom has deltas
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1096 (i.e. deltas in _practice_ are "backwards deltas")</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1097</div></div>
1098<div class="paragraph"><p>Again, we should reread that whole paragraph. Not just because
1099Linus has slipped Linus&#8217;s Law in there on us, but because it is
1100important. Let&#8217;s make sure we clarify some of the points here:</p></div>
1101<div class="literalblock">
1102<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1103<pre><code>&lt;njs`&gt; So the point is just that in practice, delta order and
1104 recency order match each other quite well.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1105</div></div>
1106<div class="literalblock">
1107<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1108<pre><code>&lt;linus&gt; Yes. There's another nice side to this (and yes, it was
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1109 designed that way ;):
1110 - the reason we generate deltas against the larger object is
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1111 actually a big space saver too!</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1112</div></div>
1113<div class="literalblock">
1114<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1115<pre><code>&lt;njs`&gt; Hmm, but your last comment (if "we haven't yet written out
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1116 the object it is a delta against, we write out the base object
1117 first"), seems like it would make these facts mostly
1118 irrelevant because even if in practice you would not have to
1119 wander around much, in fact you just brute-force say that in
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1120 the cases where you might have to wander, don't do that :-)</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1121</div></div>
1122<div class="literalblock">
1123<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1124<pre><code>&lt;linus&gt; Yes and no. Notice the rule: we only write out the base
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1125 object first if the delta against it was more recent. That
1126 means that you can actually have deltas that refer to a base
1127 object that is _not_ close to the delta object, but that only
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1128 happens when the delta is needed to generate an _old_ object.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1129</div></div>
1130<div class="literalblock">
1131<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1132<pre><code>&lt;linus&gt; See?</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1133</div></div>
1134<div class="paragraph"><p>Yeah, no. I missed that on the first two or three readings myself.</p></div>
1135<div class="literalblock">
1136<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1137<pre><code>&lt;linus&gt; This keeps the front of the pack dense. The front of the
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1138 pack never contains data that isn't relevant to a "recent"
1139 object. The size optimization comes from our use of xdelta
1140 (but is true for many other delta algorithms): removing data
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1141 is cheaper (in size) than adding data.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1142</div></div>
1143<div class="literalblock">
1144<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1145<pre><code>When you remove data, you only need to say "copy bytes n--m".
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1146In contrast, in a delta that _adds_ data, you have to say "add
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1147these bytes: 'actual data goes here'"</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1148</div></div>
1149<div class="ulist"><ul>
1150<li>
1151<p>
1152njs` has quit: Read error: 104 (Connection reset by peer)
1153</p>
1154<div class="literalblock">
1155<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1156<pre><code>&lt;linus&gt; Uhhuh. I hope I didn't blow njs` mind.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1157</div></div>
1158</li>
1159<li>
1160<p>
1161njs` has joined channel #git
1162</p>
1163<div class="literalblock">
1164<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1165<pre><code>&lt;pasky&gt; :)</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1166</div></div>
1167</li>
1168</ul></div>
1169<div class="paragraph"><p>The silent observers are amused. Of course.</p></div>
1170<div class="paragraph"><p>And as if njs` was expected to be omniscient:</p></div>
1171<div class="literalblock">
1172<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1173<pre><code>&lt;linus&gt; njs - did you miss anything?</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1174</div></div>
1175<div class="paragraph"><p>OK, I&#8217;ll spell it out. That&#8217;s Geek Humor. If njs` was not actually
1176connected for a little bit there, how would he know if missed anything
1177while he was disconnected? He&#8217;s a benevolent dictator with a sense of
1178humor! Well noted!</p></div>
1179<div class="literalblock">
1180<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1181<pre><code>&lt;njs`&gt; Stupid router. Or gremlins, or whatever.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1182</div></div>
1183<div class="paragraph"><p>It&#8217;s a cheap shot at Cisco. Take 'em when you can.</p></div>
1184<div class="literalblock">
1185<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1186<pre><code>&lt;njs`&gt; Yes and no. Notice the rule: we only write out the base
1187 object first if the delta against it was more recent.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1188</div></div>
1189<div class="literalblock">
1190<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1191<pre><code>I'm getting lost in all these orders, let me re-read :-)
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1192So the write-out order is from most recent to least recent?
1193(Conceivably it could be the opposite way too, I'm not sure if
1194we've said) though my connection back at home is logging, so I
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1195can just read what you said there :-)</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1196</div></div>
1197<div class="paragraph"><p>And for those of you paying attention, the Omniscient Trick has just
1198been detailed!</p></div>
1199<div class="literalblock">
1200<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1201<pre><code>&lt;linus&gt; Yes, we always write out most recent first</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1202</div></div>
1203<div class="paragraph"><p>For the other record:</p></div>
1204<div class="literalblock">
1205<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1206<pre><code>&lt;pasky&gt; njs`: http://pastebin.com/547965</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1207</div></div>
1208<div class="paragraph"><p>The 'net never forgets, so that should be good until the end of time.</p></div>
1209<div class="literalblock">
1210<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1211<pre><code>&lt;njs`&gt; And, yeah, I got the part about deeper-in-history stuff
1212 having worse IO characteristics, one sort of doesn't care.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1213</div></div>
1214<div class="literalblock">
1215<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1216<pre><code>&lt;linus&gt; With the caveat that if the "most recent" needs an older
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1217 object to delta against (hey, shrinking sometimes does
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1218 happen), we write out the old object with the delta.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1219</div></div>
1220<div class="literalblock">
1221<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1222<pre><code>&lt;njs`&gt; (if only it happened more...)</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1223</div></div>
1224<div class="literalblock">
1225<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1226<pre><code>&lt;linus&gt; Anyway, the pack-file could easily be denser still, but
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1227 because it's used both for streaming (the git protocol) and
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1228 for on-disk, it has a few pessimizations.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1229</div></div>
1230<div class="paragraph"><p>Actually, it is a made-up word. But it is a made-up word being
1231used as setup for a later optimization, which is a real word:</p></div>
1232<div class="literalblock">
1233<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1234<pre><code>&lt;linus&gt; In particular, while the pack-file is then compressed,
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1235 it's compressed just one object at a time, so the actual
1236 compression factor is less than it could be in theory. But it
1237 means that it's all nice random-access with a simple index to
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1238 do "object name-&gt;location in packfile" translation.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1239</div></div>
1240<div class="literalblock">
1241<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1242<pre><code>&lt;njs`&gt; I'm assuming the real win for delta-ing large-&gt;small is
1243 more homogeneous statistics for gzip to run over?</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1244</div></div>
1245<div class="literalblock">
1246<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1247<pre><code>(You have to put the bytes in one place or another, but
1248putting them in a larger blob wins on compression)</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1249</div></div>
1250<div class="literalblock">
1251<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1252<pre><code>Actually, what is the compression strategy -- each delta
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1253individually gzipped, the whole file gzipped, somewhere in
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1254between, no compression at all, ....?</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1255</div></div>
1256<div class="literalblock">
1257<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1258<pre><code>Right.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1259</div></div>
1260<div class="paragraph"><p>Reality IRC sets in. For example:</p></div>
1261<div class="literalblock">
1262<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1263<pre><code>&lt;pasky&gt; I'll read the rest in the morning, I really have to go
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1264 sleep or there's no hope whatsoever for me at the today's
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1265 exam... g'nite all.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1266</div></div>
1267<div class="paragraph"><p>Heh.</p></div>
1268<div class="literalblock">
1269<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1270<pre><code>&lt;linus&gt; pasky: g'nite</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1271</div></div>
1272<div class="literalblock">
1273<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1274<pre><code>&lt;njs`&gt; pasky: 'luck</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1275</div></div>
1276<div class="literalblock">
1277<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1278<pre><code>&lt;linus&gt; Right: large-&gt;small matters exactly because of compression
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1279 behaviour. If it was non-compressed, it probably wouldn't make
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1280 any difference.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1281</div></div>
1282<div class="literalblock">
1283<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1284<pre><code>&lt;njs`&gt; yeah</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1285</div></div>
1286<div class="literalblock">
1287<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1288<pre><code>&lt;linus&gt; Anyway: I'm not even trying to claim that the pack-files
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1289 are perfect, but they do tend to have a nice balance of
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1290 density vs ease-of use.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1291</div></div>
1292<div class="paragraph"><p>Gasp! OK, saved. That&#8217;s a fair Engineering trade off. Close call!
1293In fact, Linus reflects on some Basic Engineering Fundamentals,
1294design options, etc.</p></div>
1295<div class="literalblock">
1296<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1297<pre><code>&lt;linus&gt; More importantly, they allow git to still _conceptually_
1298 never deal with deltas at all, and be a "whole object" store.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1299</div></div>
1300<div class="literalblock">
1301<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1302<pre><code>Which has some problems (we discussed bad huge-file
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1303behaviour on the git lists the other day), but it does mean
1304that the basic git concepts are really really simple and
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1305straightforward.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1306</div></div>
1307<div class="literalblock">
1308<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1309<pre><code>It's all been quite stable.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1310</div></div>
1311<div class="literalblock">
1312<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1313<pre><code>Which I think is very much a result of having very simple
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1314basic ideas, so that there's never any confusion about what's
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1315going on.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1316</div></div>
1317<div class="literalblock">
1318<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1319<pre><code>Bugs happen, but they are "simple" bugs. And bugs that
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1320actually get some object store detail wrong are almost always
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1321so obvious that they never go anywhere.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1322</div></div>
1323<div class="literalblock">
1324<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1325<pre><code>&lt;njs`&gt; Yeah.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1326</div></div>
1327<div class="paragraph"><p>Nuff said.</p></div>
1328<div class="literalblock">
1329<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1330<pre><code>&lt;linus&gt; Anyway. I'm off for bed. It's not 6AM here, but I've got
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1331 three kids, and have to get up early in the morning to send
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1332 them off. I need my beauty sleep.</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1333</div></div>
1334<div class="literalblock">
1335<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1336<pre><code>&lt;njs`&gt; :-)</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1337</div></div>
1338<div class="literalblock">
1339<div class="content">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1340<pre><code>&lt;njs`&gt; appreciate the infodump, I really was failing to find the
1341 details on git packs :-)</code></pre>
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1342</div></div>
1343<div class="paragraph"><p>And now you know the rest of the story.</p></div>
1344</div>
1345<div id="footnotes"><hr /></div>
1346<div id="footer">
1347<div id="footer-text">
Junio C Hamano9d971152012-12-19 00:43:11[diff] [blame]1348Last updated 2011-11-15 13:45:02 PST
Junio C Hamanof2b74942012-11-20 21:06:26[diff] [blame]1349</div>
1350</div>
1351</body>
1352</html>