{"thread":{"id":"6999","subject":"pack v4 status","startedAt":"2007-02-27T15:50:42Z","lastAt":"2007-02-28T04:13:51Z","messageCount":9,"participants":["Shawn O. Pearce","Linus Torvalds","Johannes Schindelin","Nicolas Pitre","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"35679","messageId":"20070227155042.GB3230@spearce.org","threadId":"6999","inReplyTo":null,"subject":"pack v4 status","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-02-27T15:50:42Z","receivedAt":"2007-02-27T15:50:42Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nico's and my packv4 topic is available from my fastimport.git fork\non repo.or.cz:\n\n gitweb: http://repo.or.cz/w/git/fastimport.git\n git: git://repo.or.cz/git/fastimport.git\n branch: sp/pack4\n\nWe have thus far reformatted OBJ_TREEs with a new dictionary based\ncompression scheme. In this scheme we pool the filenames and modes\nthat appear within trees into a single table within the packfile.\nAll trees are then converted to use a 22 byte record format:\n\n - 2 byte network byte order index into the string pool\n - 20 byte SHA-1\n\nThese trees are then stored *uncompressed* within the packfile,\nbut are also still stored using our standard delta system (only the\ndeltas for these trees are also stored uncompressed). The resulting\nsavings is pretty good; on linux-2.6.git we are saving ~3.8 MiB as\na result of this encoding alone:\n\n\t141649022 pack2-linuxA.git\n\t137625761 pack4-linuxB.git\n\nread_sha1_file() has been modified to unpack this new tree format\nback into the canonical format; something that I think is very\nunncessary for runtime given how easy it is to iterate the encoded\ntree, but is still critically important for tools like git-cat-file,\ngit-index-pack and git-verify-pack. Future plans are to iterate\nthe encoded tree directly, but performance is already faster despite\nneeding to reconvert the tree:\n\n lh=825020c3866e7312947e17a0caa9dd1a5622bafc\n git --git-dir=pack2-linux.git rev-list $lh -- include/asm-m68k\n 3.97 real 3.60 user 0.15 sys\n 3.98 real 3.60 user 0.15 sys\n 3.98 real 3.60 user 0.15 sys\n 3.98 real 3.60 user 0.15 sys\n 3.98 real 3.60 user 0.15 sys\n\n git --git-dir=pack4-linux.git rev-list $lh -- include/asm-m68k\n 3.52 real 3.17 user 0.13 sys\n 3.46 real 3.17 user 0.13 sys\n 3.51 real 3.17 user 0.13 sys\n 3.52 real 3.18 user 0.13 sys\n 3.53 real 3.16 user 0.13 sys\n\nI'll take 500 milliseconds savings anyday, thanks! :-)\n\n\nNico and I have only started working on commits, so the above results\nstill utilize the packv2 format for OBJ_COMMIT and do not take into\naccount any of our proposed concepts there.\n\n\nThe impetus for packv4 is to format the packfile in such a way that\nwe can work with the data faster at runtime for common operations,\nlike rev-list and its builtin path limiter. We also want to make\nreachability analysis (critical for packing and fsck) faster.\nAny reduction in storage size is considered a bonus here, though\nobviously there is some correlation between size of input data and\nthe time required to process it. ;-)\n\nThe patch series for this is getting large. Right now we are up to\n32 patches in the series. Given where we are and where we want to\ngo I'm predicting this series will come out at close to 100 patches.\nOf course that's partly because I'm working in fairly small units,\nslowly iterating the code into the final version we want.\n\nI am constantly rebasing the sp/pack4 topic noted above, so the\npatch count is not really because I'm going back and fixing things\nin later patches. Its because I'm trying to slowly iterate the\nruntime side of things in digestable changes, then the packing side,\nso that the system still works at every single commit in the series.\nYes, its a *BIG* set of code changed.\n\nObviously this series has a heavy hand on sha1_file.c,\nbuiltin-pack-objects.c, builtin-unpack-objects.c, index-pack.c.\nBut it will also start to hit less obvious places like commit.c\nand tree-walk.c as we start to support walking the encoded objects\ndirectly.\n\nGiven the huge size of the series, and the amount of effort we are\ntossing into it, and the fact that I'm trying to make it pu-ready by\nearly next week, we would appreciate it if folks could keep changes\nto the above mentioned files limited to critical bug fixes only. :)\n\n-- \nShawn.\n"},{"id":"35697","messageId":"Pine.LNX.4.64.0702271348260.12485@woody.linux-foundation.org","threadId":"6999","inReplyTo":"20070227155042.GB3230@spearce.org","subject":"Re: pack v4 status","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-02-27T21:51:03Z","receivedAt":"2007-02-27T21:51:03Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 27 Feb 2007, Shawn O. Pearce wrote:\n> \n> We have thus far reformatted OBJ_TREEs with a new dictionary based\n> compression scheme. In this scheme we pool the filenames and modes\n> that appear within trees into a single table within the packfile.\n> All trees are then converted to use a 22 byte record format:\n> \n> - 2 byte network byte order index into the string pool\n> - 20 byte SHA-1\n\nUmm. Am I missing something, or is this totally braindamaged?\n\nAre you really expecting there to never be more than 64k basenames? Trust \nme, that's a totally broken assumption. Anything that tracks generated \nstuff will _easily_ have several tens of thousands of random filenames \neven in a single tree, much less over the whole history of the repository.\n\n\t\t\tLinus\n"},{"id":"35703","messageId":"Pine.LNX.4.63.0702272314540.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"6999","inReplyTo":"Pine.LNX.4.64.0702271348260.12485@woody.linux-foundation.org","subject":"Re: pack v4 status","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-02-27T22:15:43Z","receivedAt":"2007-02-27T22:15:43Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Tue, 27 Feb 2007, Linus Torvalds wrote:\n\n> On Tue, 27 Feb 2007, Shawn O. Pearce wrote:\n> > \n> > We have thus far reformatted OBJ_TREEs with a new dictionary based\n> > compression scheme. In this scheme we pool the filenames and modes\n> > that appear within trees into a single table within the packfile.\n> > All trees are then converted to use a 22 byte record format:\n> > \n> > - 2 byte network byte order index into the string pool\n> > - 20 byte SHA-1\n> \n> Umm. Am I missing something, or is this totally braindamaged?\n> \n> Are you really expecting there to never be more than 64k basenames? \n> Trust me, that's a totally broken assumption. Anything that tracks \n> generated stuff will _easily_ have several tens of thousands of random \n> filenames even in a single tree, much less over the whole history of the \n> repository.\n\nThe sane thing, of course, is to use some sort of prefix coding, together \nwith an escape code.\n\nCiao,\nDscho\n"},{"id":"35706","messageId":"alpine.LRH.0.82.0702271717080.29426@xanadu.home","threadId":"6999","inReplyTo":"Pine.LNX.4.64.0702271348260.12485@woody.linux-foundation.org","subject":"Re: pack v4 status","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-02-27T22:32:00Z","receivedAt":"2007-02-27T22:32:00Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 27 Feb 2007, Linus Torvalds wrote:\n\n> \n> \n> On Tue, 27 Feb 2007, Shawn O. Pearce wrote:\n> > \n> > We have thus far reformatted OBJ_TREEs with a new dictionary based\n> > compression scheme. In this scheme we pool the filenames and modes\n> > that appear within trees into a single table within the packfile.\n> > All trees are then converted to use a 22 byte record format:\n> > \n> > - 2 byte network byte order index into the string pool\n> > - 20 byte SHA-1\n> \n> Umm. Am I missing something, or is this totally braindamaged?\n> \n> Are you really expecting there to never be more than 64k basenames? Trust \n> me, that's a totally broken assumption. Anything that tracks generated \n> stuff will _easily_ have several tens of thousands of random filenames \n> even in a single tree, much less over the whole history of the repository.\n\nThe idea is to deal with only tree objects containing the 64K most \nfrequently used base names and fall back to the current tree object \nencoding for objects that couldn't be represented that way.\n\nFor reference the GIT tree itself has 585 unique names.\n\nThe Linux kernel has 12263 of them.\n\nIf we eventually find it is common and performance critical to have more \nbits to represent those indices because the number of unique path \ncomponents far exceeds that limit with an even distribution then we \nmight just add another tree encoding with a 3-byte index for those.\n\nIn the end everything translates back to the same object.\n\n\nNicolas\n"},{"id":"35708","messageId":"alpine.LRH.0.82.0702271732240.29426@xanadu.home","threadId":"6999","inReplyTo":"Pine.LNX.4.63.0702272314540.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: pack v4 status","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-02-27T22:33:33Z","receivedAt":"2007-02-27T22:33:33Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 27 Feb 2007, Johannes Schindelin wrote:\n\n> Hi,\n> \n> On Tue, 27 Feb 2007, Linus Torvalds wrote:\n> \n> > On Tue, 27 Feb 2007, Shawn O. Pearce wrote:\n> > > \n> > > We have thus far reformatted OBJ_TREEs with a new dictionary based\n> > > compression scheme. In this scheme we pool the filenames and modes\n> > > that appear within trees into a single table within the packfile.\n> > > All trees are then converted to use a 22 byte record format:\n> > > \n> > > - 2 byte network byte order index into the string pool\n> > > - 20 byte SHA-1\n> > \n> > Umm. Am I missing something, or is this totally braindamaged?\n> > \n> > Are you really expecting there to never be more than 64k basenames? \n> > Trust me, that's a totally broken assumption. Anything that tracks \n> > generated stuff will _easily_ have several tens of thousands of random \n> > filenames even in a single tree, much less over the whole history of the \n> > repository.\n> \n> The sane thing, of course, is to use some sort of prefix coding, together \n> with an escape code.\n\nNo. There is a fundamental reason for having a fixed size tree record.\n\n\nNicolas\n"},{"id":"35709","messageId":"7vwt23b54a.fsf@assigned-by-dhcp.cox.net","threadId":"6999","inReplyTo":"alpine.LRH.0.82.0702271717080.29426@xanadu.home","subject":"Re: pack v4 status","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-02-27T22:36:05Z","receivedAt":"2007-02-27T22:36:05Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> On Tue, 27 Feb 2007, Linus Torvalds wrote:\n>\n>> On Tue, 27 Feb 2007, Shawn O. Pearce wrote:\n>> > ...\n>> > All trees are then converted to use a 22 byte record format:\n>> > \n>> > - 2 byte network byte order index into the string pool\n>> > - 20 byte SHA-1\n>> \n>> Umm. Am I missing something, or is this totally braindamaged?\n>> \n>> Are you really expecting there to never be more than 64k basenames? Trust \n>> me, that's a totally broken assumption. Anything that tracks generated \n>> stuff will _easily_ have several tens of thousands of random filenames \n>> even in a single tree, much less over the whole history of the repository.\n>\n> The idea is to deal with only tree objects containing the 64K most \n> frequently used base names and fall back to the current tree object \n> encoding for objects that couldn't be represented that way.\n\nAh, I was wondering the same thing as Linus after seeing shawn\ntalked about the 2-byte prefix on #git. Falling back to an\nalternate encoding for rarer cases makes sense.\n"},{"id":"35749","messageId":"alpine.LRH.0.82.0702272011300.29426@xanadu.home","threadId":"6999","inReplyTo":"alpine.LRH.0.82.0702271717080.29426@xanadu.home","subject":"Re: pack v4 status","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-02-28T01:19:17Z","receivedAt":"2007-02-28T01:19:17Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 27 Feb 2007, Nicolas Pitre wrote:\n\n> For reference the GIT tree itself has 585 unique names.\n> \n> The Linux kernel has 12263 of them.\n\nOK I lied. In fact those are the frequency of the most used name \namongst all tree objects, not the number of unique names.\n\nThe real number of unique path components in the Linux repo is 16073.\n\nFor the GIT tree it is 1444.\n\nJust for fun here's the 10 most used path components in the Linux kernel \nwith their number of hits:\n\n12263: Makefile\n5541: Kconfig\n4050: kernel\n3960: net\n3818: lib\n3785: mm\n3665: crypto\n3337: sound\n3185: include\n3181: README\n\n\nNicolas\n"},{"id":"35764","messageId":"20070228034555.GA5597@spearce.org","threadId":"6999","inReplyTo":"7vwt23b54a.fsf@assigned-by-dhcp.cox.net","subject":"Re: pack v4 status","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-02-28T03:45:55Z","receivedAt":"2007-02-28T03:45:55Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> Nicolas Pitre writes:\n> > The idea is to deal with only tree objects containing the 64K most \n> > frequently used base names and fall back to the current tree object \n> > encoding for objects that couldn't be represented that way.\n> \n> Ah, I was wondering the same thing as Linus after seeing shawn\n> talked about the 2-byte prefix on #git. Falling back to an\n> alternate encoding for rarer cases makes sense.\n\nRight. Git is already fast, and already compresses the object data\nvery well. But I think we can make things faster without violating\nthe basic assumptions of \"whole project history\", and it just turns\nout that those encodings are also making the data smaller for the\ncommon case of human maintained source code. Which of course is\none of the primary uses for Git, but is obviously not the only use.\n\nIn the worst case scenario we'll be doing exactly what we are\ndoing today with regards to encoding. That performance and disk\nspace usage is already known and considered \"very, very fast\" and\n\"very small\". ;-)\n\nIn the best case scenario (human managed source like linux.git,\ngit.git) we'll scream with pack v4. The rev-list stats I posted\nfrom just the tree encoding switch not only saved 3 MiB of disk\nspace but improved total running time by 12.5%. Nico and I know\nwe can still do better.\n\nWith 15k basenames in linux.git we're filling only 23.6% of the\navailable namespace within a single packfile. I think that by the\ntime we have enough basenames to break 64K we'll be several years\nout and be talking about historical packs vs. active packs.\n\n-- \nShawn.\n"},{"id":"35771","messageId":"20070228041350.GD5597@spearce.org","threadId":"6999","inReplyTo":"20070227155042.GB3230@spearce.org","subject":"Re: pack v4 status","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-02-28T04:13:51Z","receivedAt":"2007-02-28T04:13:51Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"\"Shawn O. Pearce\" wrote:\n> Obviously this series has a heavy hand on sha1_file.c,\n> builtin-pack-objects.c, builtin-unpack-objects.c, index-pack.c.\n> But it will also start to hit less obvious places like commit.c\n> and tree-walk.c as we start to support walking the encoded objects\n> directly.\n> \n> Given the huge size of the series, and the amount of effort we are\n> tossing into it, and the fact that I'm trying to make it pu-ready by\n> early next week, we would appreciate it if folks could keep changes\n> to the above mentioned files limited to critical bug fixes only. :)\n\nAfter rereading this message[*1*] several hours later, and also\njust learning that Nico will be taking a probably much deserved\nvacation soon, my concept of getting this series ready for Junio's\npu-branch by next week is just far too aggressive to be practical.\n\nNico and I have had a lot of off-list discussion about possible\nthings we can do with the various encodings and what types of\nruntime optimizations they could actually support. These have\ncreated a lot of cases we really need to explore and confirm as\nuseful or verify as not-useful before submitting a series to Junio.\n\nImproving the packfile format is a relatively non-trivial change;\nwe would hate to see people actually start to use a pack v4 file\nonly to have the encoding change *again* in the near future due to\na better optimization being selected and employed.\n\nThat said, I would like to keep the development openly visible\n(hence its on repo.or.cz) and would like to encourage people to send\nideas, suggestions, etc. I think it is very helpful when everyone\nknows what is actively being worked on, so they can contribute to\nprojects they may be interested in, and avoid causing conflicts\nwith those projects when possible. ;-)\n\n\n*1*: Yea, I really do read my own email when vger finally gets\n around to bouncing it back to me. ;-)\n\n-- \nShawn.\n"}]}