{"thread":{"id":"3532","subject":"[PATCH] Added Packing Heursitics IRC writeup.","startedAt":"2006-03-03T01:19:29Z","lastAt":"2006-03-19T10:22:51Z","messageCount":5,"participants":["Jon Loeliger","Fredrik Kuivinen","Junio C Hamano","Jan-Benedict Glaw"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"17094","messageId":"E1FEyx7-0007vo-Je@jdl.com","threadId":"3532","inReplyTo":null,"subject":"[PATCH] Added Packing Heursitics IRC writeup.","fromName":"Jon Loeliger","fromEmail":"jdl@jdl.com","sentAt":"2006-03-03T01:19:29Z","receivedAt":"2006-03-03T01:19:29Z","isPatch":true,"sender":{"key":"jdl@jdl.com","avatar":"https://gravatar.com/avatar/75ce9a10b151acd2c28ec4ab2136dba7b2ff1634530bd04b155981a749d08a64?d=mp&s=160"},"body":"\nSigned-off-by: Jon Loeliger \n\n---\n\n Documentation/technical/pack-heuristics.txt | 466 +++++++++++++++++++++++++++\n 1 files changed, 466 insertions(+), 0 deletions(-)\n create mode 100644 Documentation/technical/pack-heuristics.txt\n\n0cbbcac437be6f8a0249f6cf83b90a6fe9d2362e\ndiff --git a/Documentation/technical/pack-heuristics.txt b/Documentation/technical/pack-heuristics.txt\nnew file mode 100644\nindex 0000000..eaab3ee\n--- /dev/null\n+++ b/Documentation/technical/pack-heuristics.txt\n@@ -0,0 +1,466 @@\n+ Concerning Git's Packing Heuristics\n+ ===================================\n+\n+ Oh, here's a really stupid question:\n+\n+ Where do I go\n+ to learn the details\n+\t of git's packing heuristics?\n+\n+Be careful what you ask!\n+\n+Followers of the git, please open the git IRC Log and turn to\n+February 10, 2006.\n+\n+It's a rare occasion, and we are joined by the King Git Himself,\n+Linus Torvalds (linus). Nathaniel Smith, (njs`), has the floor\n+and seeks enlightenment. Others are present, but silent.\n+\n+Let's listen in!\n+\n+ Oh, here's a really stupid question -- where do I go to\n+ learn the details of git's packing heuristics? google avails\n+ me not, reading the source didn't help a lot, and wading\n+ through the whole mailing list seems less efficient than any\n+ of that.\n+\n+It is a bold start! A plea for help combined with a simultaneous\n+tri-part attack on some of the tried and true mainstays in the quest\n+for enlightenment. Brash accusations of google being useless. Hubris!\n+Maligning the source. Heresy! Disdain for the mailing list archives.\n+Woe.\n+\n+ yes, the packing-related delta stuff is somewhat\n+ mysterious even for me ;)\n+\n+Ah! Modesty after all.\n+\n+ njs, I don't think the docs exist. That's something where\n+\t I don't think anybody else than me even really got involved.\n+\t Most of the rest of git others have been busy with (especially\n+\t Junio), but packing nobody touched after I did it.\n+\n+It's cryptic, yet vague. Linus in style for sure. Wise men\n+interpret this as an apology. A few argue it is merely a\n+statement of fact.\n+\n+ I guess the next step is \"read the source again\", but I\n+ have to build up a certain level of gumption first :-)\n+\n+Indeed! On both points.\n+\n+ The packing heuristic is actually really really simple.\n+\n+Bait...\n+\n+ But strange.\n+\n+And switch. That ought to do it!\n+\n+ Remember: git really doesn't follow files. So what it does is\n+ - generate a list of all objects\n+ - sort the list according to magic heuristics\n+ - walk the list, using a sliding window, seeing if an object\n+ can be diffed against another object in the window\n+ - write out the list in recency order\n+\n+The traditional understatement:\n+\n+ I suspect that what I'm missing is the precise definition of\n+ the word \"magic\"\n+\n+The traditional insight:\n+\n+ yes\n+\n+And Bable-like confusion flowed.\n+\n+ oh, hmm, and I'm not sure what this sliding window means either\n+\n+ iirc, it appeared to me to be just the sha1 of the object\n+ when reading the code casually ...\n+\n+ ... which simply doesn't sound as a very good heuristics, though ;)\n+\n+ .....and recency order. okay, I think it's clear I didn't\n+ even realize how much I wasn't realizing :-)\n+\n+Ah, grasshopper! And thus the enlightenment begins anew.\n+\n+ The \"magic\" is actually in theory totally arbitrary.\n+ ANY order will give you a working pack, but no, it's not\n+ ordered by SHA1.\n+\n+ Before talking about the ordering for the sliding delta\n+ window, let's talk about the recency order. That's more\n+ important in one way.\n+\n+ Right, but if all you want is a working way to pack things\n+ together, you could just use cat and save yourself some\n+ trouble...\n+\n+Waaait for it....\n+\n+ The recency ordering (which is basically: put objects\n+ _physically_ into the pack in the order that they are\n+ \"reachable\" from the head) is important.\n+\n+ okay\n+\n+ It's important because that's the thing that gives packs\n+ good locality. It keeps the objects close to the head (whether\n+ they are old or new, but they are _reachable_ from the head)\n+ at the head of the pack. So packs actually have absolutely\n+ _wonderful_ IO patterns.\n+\n+Read that again, because it is important.\n+\n+ But recency ordering is totally useless for deciding how\n+ to actually generate the deltas, so the delta ordering is\n+ something else.\n+\n+ The delta ordering is (wait for it):\n+ - first sort by the \"basename\" of the object, as defined by\n+ the name the object was _first_ reached through when\n+ generating the object list\n+ - within the same basename, sort by size of the object\n+ - but always sort different types separately (commits first).\n+\n+ That's not exactly it, but it's very close.\n+\n+ The \"_first_ reached\" thing is not too important, just you\n+ need some way to break ties since the same objects may be\n+ reachable many ways, yes?\n+\n+And as if to clarify:\n+\n+ The point is that it's all really just any random\n+ heuristic, and the ordering is totally unimportant for\n+ correctness, but it helps a lot if the heuristic gives\n+ \"clumping\" for things that are likely to delta well against\n+ each other.\n+\n+It is an important point, so secretly, I did my own research and have\n+included my results below. To be fair, it has changed some over time.\n+And through the magic of Revisionistic History, I draw upon this entry\n+from The Git IRC Logs on my father's birthday, March 1:\n+\n+ The quote from the above linus should be rewritten a\n+ bit (wait for it):\n+ - first sort by type. Different objects never delta with\n+\t each other.\n+ - then sort by filename/dirname. hash of the basename\n+ occupies the top BITS_PER_INT-DIR_BITS bits, and bottom\n+ DIR_BITS are for the hash of leading path elements.\n+ - then if we are doing \"thin\" pack, the objects we are _not_\n+ going to pack but we know about are sorted earlier than\n+ other objects.\n+ - and finally sort by size, larger to smaller.\n+\n+In one swell-foop, clarification and obscurification! Nonetheless,\n+authoritative. Cryptic, yet concise. It even solicits notions of\n+quotes from The Source Code. Clearly, more study is needed.\n+\n+ That's the sort order. What this means is:\n+ - we do not delta different object types.\n+\t- we prefer to delta the objects with the same full path, but\n+ allow files with the same name from different directories.\n+\t- we always prefer to delta against objects we are not going\n+ to send, if there are some.\n+\t- we prefer to delta against larger objects, so that we have\n+ lots of removals.\n+\n+ The penultimate rule is for \"thin\" packs. It is used when\n+ the other side is known to have such objects.\n+\n+There it is again. \"Thin\" packs. I'm thinking to myself, \"What\n+is a 'thin' pack?\" So I ask:\n+\n+ What is a \"thin\" pack?\n+\n+ Use of --objects-edge to rev-list as the upstream of\n+ pack-objects. The pack transfer protocol negotiates that.\n+\n+Woo hoo! Cleared that _right_ up!\n+\n+ There are two directions - push and fetch.\n+\n+There! Did you see it? It is not '\"push\" and \"pull\"'! How often the\n+confusion has started here. So casually mentioned, too!\n+\n+ For push, git-send-pack invokes git-receive-pack on the\n+ other end. The receive-pack says \"I have up to these commits\".\n+ send-pack looks at them, and computes what are missing from\n+ the other end. So \"thin\" could be the default there.\n+\n+ In the other direction, fetch, git-fetch-pack and\n+ git-clone-pack invokes git-upload-pack on the other end\n+\t(via ssh or by talking to the daemon).\n+\n+\tThere are two cases: fetch-pack with -k and clone-pack is one,\n+ fetch-pack without -k is the other. clone-pack and fetch-pack\n+ with -k will keep the downloaded packfile without expanded, so\n+ we do not use thin pack transfer. Otherwise, the generated\n+ pack will have delta without base object in the same pack.\n+\n+ But fetch-pack without -k will explode the received pack into\n+ individual objects, so we automatically ask upload-pack to\n+ give us a thin pack if upload-pack supports it.\n+\n+OK then.\n+\n+Uh.\n+\n+Let's return to the previous conversation still in progress.\n+\n+ and \"basename\" means something like \"the tail of end of\n+ path of file objects and dir objects, as per basename(3), and\n+ we just declare all commit and tag objects to have the same\n+ basename\" or something?\n+\n+Luckily, that too is a point that gitster clarified for us!\n+\n+If I might add, the trick is to make files that _might_ be similar be\n+located close to each other in the hash buckets based on their file\n+names. It used to be that \"foo/Makefile\", \"bar/baz/quux/Makefile\" and\n+\"Makefile\" all landed in the same bucket due to their common basename,\n+\"Makefile\". However, now they land in \"close\" buckets.\n+\n+The algorithm allows not just for the _same_ bucket, but for _close_\n+buckets to be considered delta candidates. The rationale is\n+essentially that files, like Makefiles, often have very similar\n+content no matter what directory they live in.\n+\n+ I played around with different delta algorithms, and with\n+ making the \"delta window\" bigger, but having too big of a\n+ sliding window makes it very expensive to generate the pack:\n+ you need to compare every object with a _ton_ of other objects.\n+\n+ There are a number of other trivial heuristics too, which\n+ basically boil down to \"don't bother even trying to delta this\n+ pair\" if we can tell before-hand that the delta isn't worth it\n+ (due to size differences, where we can take a previous delta\n+ result into account to decide that \"ok, no point in trying\n+ that one, it will be worse\").\n+\n+ End result: packing is actually very size efficient. It's\n+ somewhat CPU-wasteful, but on the other hand, since you're\n+ really only supposed to do it maybe once a month (and you can\n+ do it during the night), nobody really seems to care.\n+\n+Nice Engineering Touch, there. Find when it doesn't matter, and\n+proclaim it a non-issue. Good style too!\n+\n+ So, just to repeat to see if I'm following, we start by\n+ getting a list of the objects we want to pack, we sort it by\n+ this heuristic (basically lexicographically on the tuple\n+ (type, basename, size)).\n+\n+ Then we walk through this list, and calculate a delta of\n+ each object against the last n (tunable paramater) objects,\n+ and pick the smallest of these deltas.\n+\n+Vastly simplified, but the essence is there!\n+\n+ Correct.\n+\n+ And then once we have picked a delta or fulltext to\n+ represent each object, we re-sort by recency, and write them\n+ out in that order.\n+\n+ Yup. Some other small details:\n+\n+And of course there is the \"Other Shoe\" Factor too.\n+\n+ - We limit the delta depth to another magic value (right\n+ now both the window and delta depth magic values are just \"10\")\n+\n+ Hrm, my intuition is that you'd end up with really _bad_ IO\n+ patterns, because the things you want are near by, but to\n+ actually reconstruct them you may have to jump all over in\n+ random ways.\n+\n+ - When we write out a delta, and we haven't yet written\n+ out the object it is a delta against, we write out the base\n+ object first. And no, when we reconstruct them, we actually\n+ get nice IO patterns, because:\n+ - larger objects tend to be \"more recent\" (Linus' law: files grow)\n+ - we actively try to generate deltas from a larger object to a\n+ smaller one\n+ - this means that the top-of-tree very seldom has deltas\n+ (ie deltas in _practice_ are \"backwards deltas\")\n+\n+Again, we should reread that whole paragraph. Not just because\n+Linus has slipped Linus's Law in there on us, but because it is\n+important. Let's make sure we clarify some of the points here:\n+\n+ So the point is just that in practice, delta order and\n+ recency order match each other quite well.\n+\n+ Yes. There's another nice side to this (and yes, it was\n+\tdesigned that way ;):\n+ - the reason we generate deltas against the larger object is\n+\t actually a big space saver too!\n+\n+ Hmm, but your last comment (if \"we haven't yet written out\n+ the object it is a delta against, we write out the base object\n+ first\"), seems like it would make these facts mostly\n+ irrelevant because even if in practice you would not have to\n+ wander around much, in fact you just brute-force say that in\n+ the cases where you might have to wander, don't do that :-)\n+\n+ Yes and no. Notice the rule: we only write out the base\n+ object first if the delta against it was more recent. That\n+ means that you can actually have deltas that refer to a base\n+ object that is _not_ close to the delta object, but that only\n+ happens when the delta is needed to generate an _old_ object.\n+\n+ See?\n+\n+Yeah, no. I missed that on the first two or three readings myself.\n+\n+ This keeps the front of the pack dense. The front of the\n+ pack never contains data that isn't relevant to a \"recent\"\n+ object. The size optimization comes from our use of xdelta\n+ (but is true for many other delta algorithms): removing data\n+ is cheaper (in size) than adding data.\n+\n+ When you remove data, you only need to say \"copy bytes n--m\".\n+\tIn contrast, in a delta that _adds_ data, you have to say \"add\n+ these bytes: 'actual data goes here'\"\n+\n+ *** njs` has quit: Read error: 104 (Connection reset by peer)\n+\n+ Uhhuh. I hope I didn't blow njs` mind.\n+\n+ *** njs` has joined channel #git\n+\n+ :)\n+\n+The silent observers are amused. Of course.\n+\n+And as if njs` was expected to be omniscient:\n+\n+ njs - did you miss anything?\n+\n+OK, I'll spell it out. That's Geek Humor. If njs` was not actually\n+connected for a little bit there, how would he know if missed anything\n+while he was disconnected? He's a benevolent dictator with a sense of\n+humor! Well noted!\n+\n+ Stupid router. Or gremlins, or whatever.\n+\n+It's a cheap shot at Cisco. Take 'em when you can.\n+\n+ Yes and no. Notice the rule: we only write out the base\n+ object first if the delta against it was more recent.\n+\n+ I'm getting lost in all these orders, let me re-read :-)\n+\tSo the write-out order is from most recent to least recent?\n+ (Conceivably it could be the opposite way too, I'm not sure if\n+ we've said) though my connection back at home is logging, so I\n+ can just read what you said there :-)\n+\n+And for those of you paying attention, the Omniscient Trick has just\n+been detailed!\n+\n+ Yes, we always write out most recent first\n+\n+For the other record:\n+\n+ njs`: http://pastebin.com/547965\n+\n+The 'net never forgets, so that should be good until the end of time.\n+\n+ And, yeah, I got the part about deeper-in-history stuff\n+ having worse IO characteristics, one sort of doesn't care.\n+\n+ With the caveat that if the \"most recent\" needs an older\n+ object to delta against (hey, shrinking sometimes does\n+ happen), we write out the old object with the delta.\n+\n+ (if only it happened more...)\n+\n+ Anyway, the pack-file could easily be denser still, but\n+ because it's used both for streaming (the git protocol) and\n+ for on-disk, it has a few pessimizations.\n+\n+Actually, it is a made-up word. But it is a made-up word being\n+used as setup for a later optimization, which is a real word:\n+\n+ In particular, while the pack-file is then compressed,\n+ it's compressed just one object at a time, so the actual\n+ compression factor is less than it could be in theory. But it\n+ means that it's all nice random-access with a simple index to\n+ do \"object name->location in packfile\" translation.\n+\n+ I'm assuming the real win for delta-ing large->small is\n+ more homogenous statistics for gzip to run over?\n+\n+ (You have to put the bytes in one place or another, but\n+ putting them in a larger blob wins on compression)\n+\n+ Actually, what is the compression strategy -- each delta\n+ individually gzipped, the whole file gzipped, somewhere in\n+ between, no compression at all, ....?\n+\n+ Right.\n+\n+Reality IRC sets in. For example:\n+\n+ I'll read the rest in the morning, I really have to go\n+ sleep or there's no hope whatsoever for me at the today's\n+ exam... g'nite all.\n+\n+Heh.\n+\n+ pasky: g'nite\n+\n+ pasky: 'luck\n+\n+ Right: large->small matters exactly because of compression\n+ behaviour. If it was non-compressed, it probably wouldn't make\n+ any difference.\n+\n+ yeah\n+\n+ Anyway: I'm not even trying to claim that the pack-files\n+ are perfect, but they do tend to have a nice balance of\n+ density vs ease-of use.\n+\n+Gasp! OK, saved. That's a fair Engineering trade off. Close call!\n+In fact, Linus reflects on some Basic Engineering Fundamentals,\n+design options, etc.\n+\n+ More importantly, they allow git to still _conceptually_\n+ never deal with deltas at all, and be a \"whole object\" store.\n+\n+ Which has some problems (we discussed bad huge-file\n+ behaviour on the git lists the other day), but it does mean\n+ that the basic git concepts are really really simple and\n+ straightforward.\n+\n+ It's all been quite stable.\n+\n+ Which I think is very much a result of having very simple\n+ basic ideas, so that there's never any confusion about what's\n+ going on.\n+\n+ Bugs happen, but they are \"simple\" bugs. And bugs that\n+ actually get some object store detail wrong are almost always\n+ so obious that they never go anywhere.\n+\n+ Yeah.\n+\n+Nuff said.\n+\n+ Anyway. I'm off for bed. It's not 6AM here, but I've got\n+\t three kids, and have to get up early in the morning to send\n+\t them off. I need my beauty sleep.\n+\n+ :-)\n+\n+ appreciate the infodump, I really was failing to find the\n+ details on git packs :-)\n+\n+And now you know the rest of the story.\n-- \n1.0.7.g2b74\n"},{"id":"17659","messageId":"20060319003255.GA17124@c165.ib.student.liu.se","threadId":"3532","inReplyTo":"E1FEyx7-0007vo-Je@jdl.com","subject":"Re: [PATCH] Added Packing Heursitics IRC writeup.","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2006-03-19T00:32:56Z","receivedAt":"2006-03-19T00:32:56Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Thu, Mar 02, 2006 at 07:19:29PM -0600, Jon Loeliger wrote:\n> \n> Signed-off-by: Jon Loeliger \n> \n> ---\n> \n> Documentation/technical/pack-heuristics.txt | 466 +++++++++++++++++++++++++++\n> 1 files changed, 466 insertions(+), 0 deletions(-)\n> create mode 100644 Documentation/technical/pack-heuristics.txt\n> \n> 0cbbcac437be6f8a0249f6cf83b90a6fe9d2362e\n> diff --git a/Documentation/technical/pack-heuristics.txt b/Documentation/technical/pack-heuristics.txt\n> new file mode 100644\n> index 0000000..eaab3ee\n> --- /dev/null\n> +++ b/Documentation/technical/pack-heuristics.txt\n> @@ -0,0 +1,466 @@\n> + Concerning Git's Packing Heuristics\n> + ===================================\n> +\n\n[nice description of Git's packing heuristics]\n\nJunio, are there any specific reasons why this hasn't been applied\nyet?\n\n- Fredrik\n"},{"id":"17660","messageId":"7vr74zqhhi.fsf@assigned-by-dhcp.cox.net","threadId":"3532","inReplyTo":"20060319003255.GA17124@c165.ib.student.liu.se","subject":"Re: [PATCH] Added Packing Heursitics IRC writeup.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-19T02:46:17Z","receivedAt":"2006-03-19T02:46:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen writes:\n\n> [nice description of Git's packing heuristics]\n>\n> Junio, are there any specific reasons why this hasn't been applied\n> yet?\n\nFunny. I was just re-reading it last night.\n\nIt _is_ amusing, but I am not sure if it should go to\ntechnical/. If properly digested and reorganized, I suspect\nthat the document would become 1/3 of its current length.\n"},{"id":"17661","messageId":"E1FKoHA-0003St-4i@jdl.com","threadId":"3532","inReplyTo":"7vr74zqhhi.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Added Packing Heursitics IRC writeup.","fromName":"Jon Loeliger","fromEmail":"jdl@jdl.com","sentAt":"2006-03-19T03:08:16Z","receivedAt":"2006-03-19T03:08:16Z","isPatch":true,"sender":{"key":"jdl@jdl.com","avatar":"https://gravatar.com/avatar/75ce9a10b151acd2c28ec4ab2136dba7b2ff1634530bd04b155981a749d08a64?d=mp&s=160"},"body":"So, like, the other day Junio C Hamano mumbled:\n> Fredrik Kuivinen writes:\n> \n> > [nice description of Git's packing heuristics]\n> >\n> > Junio, are there any specific reasons why this hasn't been applied\n> > yet?\n> \n> Funny. I was just re-reading it last night.\n> \n> It _is_ amusing, but I am not sure if it should go to\n> technical/.\n\nYou know, I don't know what to do with it either. :-)\n\nI have half a notion to submit it to the OLS call for\n\"Linux Essay Contest\" just to see what happens....\n\n> If properly digested and reorganized, I suspect\n> that the document would become 1/3 of its current length.\n\nI suppose I could do a round of that, if you would like. :-)\n\nI should either drink more or less, I can't tell which...\n\njdl\n"},{"id":"17665","messageId":"20060319102251.GY20746@lug-owl.de","threadId":"3532","inReplyTo":"7vr74zqhhi.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] Added Packing Heursitics IRC writeup.","fromName":"Jan-Benedict Glaw","fromEmail":"jbglaw@lug-owl.de","sentAt":"2006-03-19T10:22:51Z","receivedAt":"2006-03-19T10:22:51Z","isPatch":true,"sender":{"key":"jbglaw@lug-owl.de","avatar":null},"body":"On Sat, 2006-03-18 18:46:17 -0800, Junio C Hamano wrote:\n> Fredrik Kuivinen writes:\n> > [nice description of Git's packing heuristics]\n> >\n> > Junio, are there any specific reasons why this hasn't been applied\n> > yet?\n> \n> Funny. I was just re-reading it last night.\n> \n> It _is_ amusing, but I am not sure if it should go to\n> technical/. If properly digested and reorganized, I suspect\n> that the document would become 1/3 of its current length.\n\nBut surely it should go somewhere, in its current form. It's *such* a\nnice reading and really amusing, so it shouldn't get lost.\n\nMfG, JBG\n\n-- \nJan-Benedict Glaw jbglaw@lug-owl.de . +49-172-7608481 _ O _\n\"Eine Freie Meinung in einem Freien Kopf | Gegen Zensur | Gegen Krieg _ _ O\n für einen Freien Staat voll Freier Bürger\" | im Internet! | im Irak! O O O\nret = do_actions((curr | FREE_SPEECH) & ~(NEW_COPYRIGHT_LAW | DRM | TCPA));\n"}]}