{"thread":{"id":"5429","subject":"Why do base objects appear behind the delta in packs?","startedAt":"2006-08-29T13:42:33Z","lastAt":"2006-08-29T19:23:52Z","messageCount":9,"participants":["Shawn Pearce","Nicolas Pitre","Jakub Narebski","Junio C Hamano","Jon Smirl"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"26091","messageId":"20060829134233.GA21335@spearce.org","threadId":"5429","inReplyTo":null,"subject":"Why do base objects appear behind the delta in packs?","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-29T13:42:33Z","receivedAt":"2006-08-29T13:42:33Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Sorry but this really is a pretty stupid question on my part:\n\nIn builtin-pack-objects.c write_one(), why is the base object written\nbehind the first delta that depends on it (if it hasn't been written\nalready) rather than BEFORE the first delta that depends on it?\n\nIf the base always had to appear before any delta that uses it then\nunpack-objects wouldn't need to cache a delta in memory waiting\nfor the base to get unpacked.\n\n>From a data locality perspective putting the base object before\nor after the delta shouldn't matter, as either way the delta\nis useless without the base. So placing the base immediately\nbefore the delta should perform just as well as placing it after.\nEither way the OS should have the base in cache by the time the\ndelta is being accessed.\n\nIn other words, why not apply this patch and make it a requirement\nof the pack file format?\n\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 46f524d..5dd97b9 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -341,11 +341,11 @@ static unsigned long write_one(struct sh\n \t\t * if it is written already.\n \t\t */\n \t\treturn offset;\n-\te->offset = offset;\n-\toffset += write_object(f, e);\n \t/* if we are deltified, write out its base object. */\n \tif (e->delta)\n \t\toffset = write_one(f, e->delta, offset);\n+\te->offset = offset;\n+\toffset += write_object(f, e);\n \treturn offset;\n }\n \n"},{"id":"26092","messageId":"Pine.LNX.4.64.0608291024470.2598@xanadu.home","threadId":"5429","inReplyTo":"20060829134233.GA21335@spearce.org","subject":"Re: Why do base objects appear behind the delta in packs?","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-29T14:40:50Z","receivedAt":"2006-08-29T14:40:50Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 29 Aug 2006, Shawn Pearce wrote:\n\n> Sorry but this really is a pretty stupid question on my part:\n> \n> In builtin-pack-objects.c write_one(), why is the base object written\n> behind the first delta that depends on it (if it hasn't been written\n> already) rather than BEFORE the first delta that depends on it?\n\nMost of the time the base object will have been written already since we \nfavor backward deltas, and newer objects are written first. But that \nmight not always be the case.\n\n> If the base always had to appear before any delta that uses it then\n> unpack-objects wouldn't need to cache a delta in memory waiting\n> for the base to get unpacked.\n\nLike mentioned above this is not the common case. And deltas are small \nanyway. And when you think about it the delta and base objects have to \nbe both in memory so this doesn't change anything in the end. So in \npractice there is no really special caching.\n\n> >From a data locality perspective putting the base object before\n> or after the delta shouldn't matter, as either way the delta\n> is useless without the base. So placing the base immediately\n> before the delta should perform just as well as placing it after.\n> Either way the OS should have the base in cache by the time the\n> delta is being accessed.\n\nNot necessarily. In fact if you checkout a particular revision with \nsuch a case, putting the base first will force a seek over it since what \nis referenced first is the delta, then seek back to the base. If it is \nright after the delta then there is no need to seek back and some read \nahead might have picked the base by the time it is referenced. OK since \nall this is mmap()'ed there might not be much difference in practice, \nbut in theory the current arrangement could have a slight advantage.\n\n> In other words, why not apply this patch and make it a requirement\n> of the pack file format?\n\nI don't think this should be a requirement.\n\n\nNicolas\n"},{"id":"26093","messageId":"ed1kn3$c3r$1@sea.gmane.org","threadId":"5429","inReplyTo":"20060829134233.GA21335@spearce.org","subject":"Re: Why do base objects appear behind the delta in packs?","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-08-29T14:58:59Z","receivedAt":"2006-08-29T14:58:59Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Shawn Pearce wrote:\n\n> From a data locality perspective putting the base object before\n> or after the delta shouldn't matter, as either way the delta\n> is useless without the base.  So placing the base immediately\n> before the delta should perform just as well as placing it after.\n> Either way the OS should have the base in cache by the time the\n> delta is being accessed.\n\n_Should_ perform? Have you got any measurements of speed of creating \"base\nbefore delta\" pack, and reading objects from this kind of pack?\n\n-- \nJakub Narebski\nWarsaw, Poland\nShadeHawk on #git\n"},{"id":"26094","messageId":"20060829162747.GA21729@spearce.org","threadId":"5429","inReplyTo":"ed1kn3$c3r$1@sea.gmane.org","subject":"Re: Why do base objects appear behind the delta in packs?","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-29T16:27:47Z","receivedAt":"2006-08-29T16:27:47Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jakub Narebski wrote:\n> Shawn Pearce wrote:\n> \n> > From a data locality perspective putting the base object before\n> > or after the delta shouldn't matter, as either way the delta\n> > is useless without the base.  So placing the base immediately\n> > before the delta should perform just as well as placing it after.\n> > Either way the OS should have the base in cache by the time the\n> > delta is being accessed.\n> \n> _Should_ perform? Have you got any measurements of speed of creating \"base\n> before delta\" pack, and reading objects from this kind of pack?\n\nNo, not yet. It just seemed odd to me that the base was put behind\nthe delta which then forces unpack-objects to hold a delta in memory\nuntil it finds the corresponding base later in the stream when it\ncould have been just as simple to require the base appear before\nthe delta. I wondered what the rationale was for the additional\ncomplexity in unpack-objects.\n\nNicolas' reply pointed out that the current arrangement of base\nafter delta may actually offer improved performance due to the\nOS performing read-ahead when you seek to the delta. But he also\npointed out this base after delta situtation should be rather rare\nas we try to delta older objects against newer objects and we try to\nplace newer objects at the front of the pack, so it likely shouldn't\nmatter that much.\n\n\nI just instrumented builtin-pack-objects.c to count how many times\nwe put the delta before the base and then repacked a current Git\nrepo with `git repack -a -d -f`. 28167 objects, 19170 deltas. 6003\ndeltas appeared before their base objects. So 31% of the time.\nThat's certainly not the common case but it does occur with some\nfrequency. However resorting the output of verify-pack -v by offset\nand visually looking at the entries you can clearly see it doesn't\nhappen very often early in the pack. Most of the objects in the\nfront of the pack are undeltafied commits.\n\nThis particular Git repository has 6723 commits and 905 trees that\nweren't deltafied. That's a total of 4 MiB of uncompressed data,\nmost of which appears at the front of the pack. Only 68 commits\nwere deltas but 8067 trees were made into deltas. The compressed\ncommits seemed to occupy the first 2 MiB of the pack file; that's\n25% of the 8 MiB pack. A commit-specific pack local dictionary\ncould be interesting here as it might some pack space.\n\n\nI'm going to shutup now and not say anything further on the subject\nunless I've got some hard results indicating a different organization\nis better or worse than what we have right now.\n\n-- \nShawn.\n"},{"id":"26095","messageId":"7v8xl7moo7.fsf@assigned-by-dhcp.cox.net","threadId":"5429","inReplyTo":"20060829162747.GA21729@spearce.org","subject":"Re: Why do base objects appear behind the delta in packs?","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-08-29T17:34:16Z","receivedAt":"2006-08-29T17:34:16Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Shawn Pearce writes:\n\n>> Shawn Pearce wrote:\n>> \n>> > From a data locality perspective putting the base object before\n>> > or after the delta shouldn't matter, as either way the delta\n>> > is useless without the base.  So placing the base immediately\n>> > before the delta should perform just as well as placing it after.\n>> > Either way the OS should have the base in cache by the time the\n>> > delta is being accessed.\n>... \n> I'm going to shutup now and not say anything further on the subject\n> unless I've got some hard results indicating a different organization\n> is better or worse than what we have right now.\n\nI think that may be a sensible thing to do (no sarcasm -- I\nthink this measurement is long overdue).\n\nThe code was initially proposed just like you suggested but is\nin the current form precisely for the reason of avoiding\nback-seek. I distinctly remember me asking Linus \"does mmap()\nfavor forward scan by doing readahead? I thought its point was\nto allow random access\" (the answer is \"yes\" and \"yes but\nforward is the common case\").\n\nThe pack-using side in sha1_file.c used to read deltified object\n(both header and delta) in full, pick up and read base, and\napply delta to base. This was thought to be memory hungry on a\nlonger delta chain, so the current code reads only the header of\na deltified object, reads base, then reads the delta to apply.\nThe last step involves seeking back, and might make the\nback-seek avoidance less effective than before.\n"},{"id":"26096","messageId":"20060829174448.GD21729@spearce.org","threadId":"5429","inReplyTo":"7v8xl7moo7.fsf@assigned-by-dhcp.cox.net","subject":"Re: Why do base objects appear behind the delta in packs?","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-29T17:44:48Z","receivedAt":"2006-08-29T17:44:48Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> Shawn Pearce writes:\n> \n> >> Shawn Pearce wrote:\n> >> \n> >> > From a data locality perspective putting the base object before\n> >> > or after the delta shouldn't matter, as either way the delta\n> >> > is useless without the base.  So placing the base immediately\n> >> > before the delta should perform just as well as placing it after.\n> >> > Either way the OS should have the base in cache by the time the\n> >> > delta is being accessed.\n> >... \n> > I'm going to shutup now and not say anything further on the subject\n> > unless I've got some hard results indicating a different organization\n> > is better or worse than what we have right now.\n> \n> I think that may be a sensible thing to do (no sarcasm -- I\n> think this measurement is long overdue).\n> \n> The code was initially proposed just like you suggested but is\n> in the current form precisely for the reason of avoiding\n> back-seek. I distinctly remember me asking Linus \"does mmap()\n> favor forward scan by doing readahead? I thought its point was\n> to allow random access\" (the answer is \"yes\" and \"yes but\n> forward is the common case\").\n> \n> The pack-using side in sha1_file.c used to read deltified object\n> (both header and delta) in full, pick up and read base, and\n> apply delta to base. This was thought to be memory hungry on a\n> longer delta chain, so the current code reads only the header of\n> a deltified object, reads base, then reads the delta to apply.\n> The last step involves seeking back, and might make the\n> back-seek avoidance less effective than before.\n\nThank you. That was the sort of response I was looking for. :-)\n\nI know Jon wants to shrink that ~500 MB Mozilla pack to something\na lot smaller, and I'd like to help him do that without losing huge\namounts of performance on the read. Very long delta chains (5000!)\nare simply impossible to wade through for even one object; doing it\nfor an entire commit to checkout the files is something I wouldn't\nwant to wish on anyone.\n\nSo I'm probably going to wind up spending some time doing research\nand experimentation on pack storage. I may just discover we're\nas good as we can get. Or I may find that doing something else\nsaves us only 5% at the cost of far too much complexity and thus\nisn't really worth doing. Or I may get lucky and discover a way\nto improve on what we have.\n\nMore on this thread (maybe) in a few months. I have other stuff\nI should be doing right now. :)\n\n-- \nShawn.\n"},{"id":"26097","messageId":"Pine.LNX.4.64.0608291410290.9796@xanadu.home","threadId":"5429","inReplyTo":"20060829174448.GD21729@spearce.org","subject":"Re: Why do base objects appear behind the delta in packs?","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-08-29T18:16:28Z","receivedAt":"2006-08-29T18:16:28Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 29 Aug 2006, Shawn Pearce wrote:\n\n> So I'm probably going to wind up spending some time doing research\n> and experimentation on pack storage. I may just discover we're\n> as good as we can get. Or I may find that doing something else\n> saves us only 5% at the cost of far too much complexity and thus\n> isn't really worth doing. Or I may get lucky and discover a way\n> to improve on what we have.\n\nI'm periodically looking for improvements on packing performances \nmyself.\n\nI look forward to being able to use your (and Jon's) fast-import work in \norder to play with (re)generation of big packs myself.\n\n\nNicolas\n"},{"id":"26098","messageId":"20060829183239.GH21729@spearce.org","threadId":"5429","inReplyTo":"Pine.LNX.4.64.0608291410290.9796@xanadu.home","subject":"Re: Why do base objects appear behind the delta in packs?","fromName":"Shawn Pearce","fromEmail":"spearce@spearce.org","sentAt":"2006-08-29T18:32:39Z","receivedAt":"2006-08-29T18:32:39Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> I look forward to being able to use your (and Jon's) fast-import work in \n> order to play with (re)generation of big packs myself.\n\nMy repository is here:\n\n http://www.spearce.org/projects/scm/git.git\n\nbranch 'refs/heads/sp/fastpack'.\n\nI'd appreciate it if folks didn't clone directly from me but instead\nused an existing clone to pull the branch down into. Its based on\na fairly recent 'next' branch. Anything not available via Junio's\n'next' on kernel.org is loose objects in this repository and are\nspecific to my fast-import work.\n\nDocumentation of the protocol used to stuff a pack is in the\nheader of fast-import.c. Its a relatively trivial stream format.\nIt should be quite simple to generate a random large project and\npipe it into fast-import to get a resulting pack to play with.\n\nI don't have Jon's cvs2svn code and I don't know if its ready for\npublic consumption yet. git-fast-import however looks like its\nalmost there, so I'm making the URL publicly available for those\nthat may be interested in it.\n\n[Junio: please do the lazy thing and don't pull this into Git just\n yet, I don't think this branch is ready for that, not even for pu.]\n\n-- \nShawn.\n"},{"id":"26100","messageId":"9e4733910608291223s7ca574bfh88627f2bec60e424@mail.gmail.com","threadId":"5429","inReplyTo":"20060829183239.GH21729@spearce.org","subject":"Re: Why do base objects appear behind the delta in packs?","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2006-08-29T19:23:52Z","receivedAt":"2006-08-29T19:23:52Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 8/29/06, Shawn Pearce wrote:\n> I don't have Jon's cvs2svn code and I don't know if its ready for\n> public consumption yet. git-fast-import however looks like its\n> almost there, so I'm making the URL publicly available for those\n> that may be interested in it.\n\nIf anyone is interested in cvs2svn mods let me know (they are in\nPython) and I will send you a snap shot. The current code gets all the\nblobs, tree and commits into a pack via fast-import, but the trees not\nbeing generated correctly for complex branching when there are issues\nwith the symbols in CVS.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"}]}