Concerning Git’s Packing Heuristics

Concerning Git’s Packing Heuristics

Oh, here's a really stupid question:

Where do I go<br>to learn the details<br>of Git's packing heuristics?

Be careful what you ask!

Followers of the Git, please open the Git IRC Log and turn to<br>February 10, 2006.

It’s a rare occasion, and we are joined by the King Git Himself,<br>Linus Torvalds (linus). Nathaniel Smith, (njs`), has the floor<br>and seeks enlightenment. Others are present, but silent.

Let’s listen in!

Oh, here's a really stupid question -- where do I go to<br>learn the details of Git's packing heuristics? google avails<br>me not, reading the source didn't help a lot, and wading<br>through the whole mailing list seems less efficient than any<br>of that.

It is a bold start! A plea for help combined with a simultaneous<br>tri-part attack on some of the tried and true mainstays in the quest<br>for enlightenment. Brash accusations of google being useless. Hubris!<br>Maligning the source. Heresy! Disdain for the mailing list archives.<br>Woe.

yes, the packing-related delta stuff is somewhat<br>mysterious even for me ;)

Ah! Modesty after all.

njs, I don't think the docs exist. That's something where<br>I don't think anybody else than me even really got involved.<br>Most of the rest of Git others have been busy with (especially<br>Junio), but packing nobody touched after I did it.

It’s cryptic, yet vague. Linus in style for sure. Wise men<br>interpret this as an apology. A few argue it is merely a<br>statement of fact.

I guess the next step is "read the source again", but I<br>have to build up a certain level of gumption first :-)

Indeed! On both points.

The packing heuristic is actually really really simple.

Bait…​

But strange.

And switch. That ought to do it!

Remember: Git really doesn't follow files. So what it does is<br>- generate a list of all objects<br>- sort the list according to magic heuristics<br>- walk the list, using a sliding window, seeing if an object<br>can be diffed against another object in the window<br>- write out the list in recency order

The traditional understatement:

I suspect that what I'm missing is the precise definition of<br>the word "magic"

The traditional insight:

yes

And Babel-like confusion flowed.

oh, hmm, and I'm not sure what this sliding window means either

iirc, it appeared to me to be just the sha1 of the object<br>when reading the code casually ...

which simply doesn’t sound as a very good heuristics, though ;)

.....and recency order. okay, I think it's clear I didn't<br>even realize how much I wasn't realizing :-)

Ah, grasshopper! And thus the enlightenment begins anew.

The "magic" is actually in theory totally arbitrary.<br>ANY order will give you a working pack, but no, it's not<br>ordered by SHA-1.

Before talking about the ordering for the sliding delta<br>window, let's talk about the recency order. That's more<br>important in one way.

Right, but if all you want is a working way to pack things<br>together, you could just use cat and save yourself some<br>trouble...

Waaait for it…​.

The recency ordering (which is basically: put objects<br>_physically_ into the pack in the order that they are<br>"reachable" from the head) is important.

okay

It's important because that's the thing that gives packs<br>good locality. It keeps the objects close to the head (whether<br>they are old or new, but they are _reachable_ from the head)<br>at the head of the pack. So packs actually have absolutely<br>_wonderful_ IO patterns.

Read that again, because it is important.

But recency ordering is totally useless for deciding how<br>to actually generate the deltas, so the delta ordering is<br>something else.

The delta ordering is (wait for it):<br>- first sort by the "basename" of the object, as defined by<br>the name the object was _first_ reached through when<br>generating the object list<br>- within the same basename, sort by size of the object<br>- but always sort different types separately (commits first).

That's not exactly it, but it's very close.

The "_first_ reached" thing is not too important, just you<br>need some way to break ties since the same objects may be<br>reachable many ways, yes?

And as if to clarify:

The point is that it's all really just any random<br>heuristic, and the ordering is totally unimportant for<br>correctness, but it helps a lot if the heuristic gives<br>"clumping" for things that are likely to delta well against<br>each other.

It is an important point, so secretly, I did my own research and have<br>included my results below. To be fair, it has changed some over time.<br>And through the magic of Revisionistic History, I draw upon this entry<br>from The Git IRC Logs on my father’s birthday, March 1:

The quote from the above linus should be rewritten a<br>bit (wait for it):<br>- first sort by type. Different objects never delta with<br>each other.<br>- then sort by filename/dirname. hash of the basename<br>occupies the top BITS_PER_INT-DIR_BITS bits, and bottom<br>DIR_BITS are for the hash of leading path elements.<br>- then if we are doing "thin" pack, the objects we are _not_<br>going to pack but we know about...