{"thread":{"id":"34898","subject":"Re-Transmission of blobs?","startedAt":"2013-09-10T13:08:38Z","lastAt":"2013-09-24T20:36:51Z","messageCount":19,"participants":["Josef Wolf","Junio C Hamano","Jeff King","Pyeron, Jason J CTR (US)","Jason Pyeron","Duy Nguyen"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"227320","messageId":"20130910130837.GA14259@raven.wolf.lan","threadId":"34898","inReplyTo":null,"subject":"Re-Transmission of blobs?","fromName":"Josef Wolf","fromEmail":"jw@raven.inka.de","sentAt":"2013-09-10T13:08:38Z","receivedAt":"2013-09-10T13:08:38Z","isPatch":false,"sender":{"key":"jw@raven.inka.de","avatar":null},"body":"Hello,\n\nas we all know, files are identified by their SHA. Thus I had the impression\nthat when transfering files, git would know by the SHA whether a given file is\nalready available in the destination repository and the transfer would be of\nno use. But this don't seem to be tha case. Lets see this example:\n\n $ cat t.sh\n #! /bin/sh -ex\n \n LANG=\n \n rm -rf 1 2\n git init 1\n git clone 1 2\n \n cd 1\n git commit --allow-empty -m \"initial structure\"\n git co -b somebranch\n dd if=/dev/urandom count=10 bs=1024k >t\n git add t\n git commit -m \"blah\"\n \n cd ../2\n git pull\n git cherry-pick origin/somebranch\n git push -v\n \n $ ./t.sh\n + LANG=\n + rm -rf 1 2\n + git init 1\n Initialized empty Git repository in /home/jw/test/1/.git/\n + git clone 1 2\n Cloning into '2'...\n warning: You appear to have cloned an empty repository.\n done.\n + cd 1\n + git commit --allow-empty -m 'initial structure'\n [master (root-commit) 97e52e2] initial structure\n + git co -b somebranch\n Switched to a new branch 'somebranch'\n + dd if=/dev/urandom count=10 bs=1024k\n 10+0 records in\n 10+0 records out\n 10485760 bytes (10 MB) copied, 1.3202 s, 7.9 MB/s\n + git add t\n + git commit -m blah\n [somebranch b11cf51] blah\n 1 file changed, 0 insertions(+), 0 deletions(-)\n create mode 100644 t\n + cd ../2\n + git pull\n remote: Counting objects: 5, done.\n remote: Compressing objects: 100% (3/3), done.\n remote: Total 5 (delta 0), reused 0 (delta 0)\n Unpacking objects: 100% (5/5), done.\n From /home/jw/test/1\n * [new branch] master -> origin/master\n * [new branch] somebranch -> origin/somebranch\n + git cherry-pick origin/somebranch\n [master 9e8f1c6] blah\n 1 file changed, 0 insertions(+), 0 deletions(-)\n create mode 100644 t\n + git push -v\n warning: push.default is unset; its implicit value is changing in\n Git 2.0 from 'matching' to 'simple'. To squelch this message\n and maintain the current behavior after the default changes, use:\n \n git config --global push.default matching\n \n To squelch this message and adopt the new behavior now, use:\n \n git config --global push.default simple\n \n See 'git help config' and search for 'push.default' for further information.\n (the 'simple' mode was introduced in Git 1.7.11. Use the similar mode\n 'current' instead of 'simple' if you sometimes use older versions of Git)\n \n Pushing to /home/jw/test/1\n Counting objects: 4, done.\n Delta compression using up to 2 threads.\n Compressing objects: 100% (2/2), done.\n Writing objects: 100% (3/3), 10.00 MiB, done.\n Total 3 (delta 0), reused 0 (delta 0)\n To /home/jw/test/1\n 97e52e2..9e8f1c6 master -> master\n updating local tracking ref 'refs/remotes/origin/master'\n $\n\n\nAs we can see in this example, the big file is tranferred back to the first\nrepository, although it is already available there. This is very annoying if\nyou have a very slow connection.\n\nAm I missing some important point here?\n\n-- \nJosef Wolf\njw@raven.inka.de\n"},{"id":"227349","messageId":"xmqqsixcy395.fsf@gitster.dls.corp.google.com","threadId":"34898","inReplyTo":"20130910130837.GA14259@raven.wolf.lan","subject":"Re: Re-Transmission of blobs?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-09-10T17:51:02Z","receivedAt":"2013-09-10T17:51:02Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Josef Wolf writes:\n\n> as we all know, files are identified by their SHA. Thus I had the impression\n> that when transfering files, git would know by the SHA whether a given file is\n> already available in the destination repository and the transfer would be of\n> no use.\n\nThat is unfortunately not how things work. It is not like the\nreceiving end sends the names of all objects it has, and the sending\nend excludes these objects from what it is going to send.\n\nConsider this simple history with only a handful of commits (as\nusual, time flows from left to right):\n\n E\n / \n A---B---C---D\n\nwhere D is at the tip of the sending side, E is at the tip of the\nreceiving side. The exchange goes roughly like this:\n\n (receiving side): what do you have?\n\n (sending side): my tip is at D.\n\n (receiving side): D? I've never heard of it --- please give it\n to me. I have E.\n\n (sending side): E? I don't know about it; must be something you\n created since you forked from me. Tell me about\n its ancestors.\n\n (receiving side): OK, I have C.\n\n (sending side): Oh, C I know about. You do not have to tell me\n anything more. A packfile to bring you up to\n date will follow.\n\nAt this point, the sender knows that the receiver needs the commit\nD, and trees and blobs in D. It does also know it has the commit C\nand trees and blobs in C. It does the best thing it can do using\nthese (and only these) information, namely, to send the commit D,\nand send trees and blobs in D that are not in the commit C.\n\nYou may happen to have something in E that match what is in D but\nnot in C. Because the sender does not know anything about E at all\nin the first place, that information cannot be used to reduce the\ntransfer.\n\nThe sender theoretically _could_ also exploit the fact that any\nreceiver that has C must have B and A and all trees and blobs\nassociated with these ancestor commits [*1*], but that information\nis not currently discovered nor used during the object transfer.\n\nThere may happen to be a tree or a blob in A that matches a tree or\na blob in D. But because the common ancestor discovery exchange\nabove stops at C, the sender does not bother enumerating all the\nobjects that are in the ancestor commits of C when figuring out what\nobjects to send to ensure that the receiving end has all the objects\nnecessary to complete D. If you modified a blob at B (or C) and\nthen resurrected the old version of the blob at D, it is likely that\nthe blob is going to be sent again when the receiving end asks for\nD.\n\nThere are some work being done to optimize this further using\nvarious techniques, but they are not ready yet.\n\n\n[Footnote]\n\n*1* only down to the shallow boundary, if the receiving end is a\nshallow clone.\n"},{"id":"227444","messageId":"20130911112758.GB14259@raven.wolf.lan","threadId":"34898","inReplyTo":"xmqqsixcy395.fsf@gitster.dls.corp.google.com","subject":"Re: Re-Transmission of blobs?","fromName":"Josef Wolf","fromEmail":"jw@raven.inka.de","sentAt":"2013-09-11T11:27:58Z","receivedAt":"2013-09-11T11:27:58Z","isPatch":false,"sender":{"key":"jw@raven.inka.de","avatar":null},"body":"On Di, Sep 10, 2013 at 10:51:02 -0700, Junio C Hamano wrote:\n> Consider this simple history with only a handful of commits (as\n> usual, time flows from left to right):\n> \n> E\n> / \n> A---B---C---D\n> \n> where D is at the tip of the sending side, E is at the tip of the\n> receiving side. The exchange goes roughly like this:\n> \n> (receiving side): what do you have?\n> \n> (sending side): my tip is at D.\n> \n> (receiving side): D? I've never heard of it --- please give it\n> to me. I have E.\n\nAt this point, why would the receiving side not tell all the heads it knows\nabout? That would enable the sending side to see whether it knows any of those\ncommits. It then would be able to remove from the sending list all the objects\nthat can be reached from the commits it knows about.\n\n> (sending side): E? I don't know about it; must be something you\n> created since you forked from me. Tell me about\n> its ancestors.\n\nThis is not exactly true. In the example I had given, the sending side has all\nthree commits: C, D and E. So the sending side has no reason to say that it\ndoesn't know anything about E. Therefore the sending side has all information\nit needs to deduce exactly which objects need to be sent to the receiving side.\n\nWhat needs to be sent are all the objects in C..D but without all the objects\nin C..E. I guess this operation would be called set-difference in english.\n\nAnd if the receiving side would have told that it has heads X Y Z in addition,\nand the sending side happens to have Y, then the sending side could in\naddition remove any objects that can be reached from Y from the sending list.\n\n-- \nJosef Wolf\njw@raven.inka.de\n"},{"id":"227466","messageId":"xmqqsixbth4h.fsf@gitster.dls.corp.google.com","threadId":"34898","inReplyTo":"20130911112758.GB14259@raven.wolf.lan","subject":"Re: Re-Transmission of blobs?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-09-11T17:14:54Z","receivedAt":"2013-09-11T17:14:54Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Josef Wolf writes:\n\n> On Di, Sep 10, 2013 at 10:51:02 -0700, Junio C Hamano wrote:\n>> Consider this simple history with only a handful of commits (as\n>> usual, time flows from left to right):\n>> \n>> E\n>> / \n>> A---B---C---D\n>> \n>> where D is at the tip of the sending side, E is at the tip of the\n>> receiving side. The exchange goes roughly like this:\n>> \n>> (receiving side): what do you have?\n>> \n>> (sending side): my tip is at D.\n>> \n>> (receiving side): D? I've never heard of it --- please give it\n>> to me. I have E.\n>\n> At this point, why would the receiving side not tell all the heads it knows\n> about?\n\nIt did. The receiving end had only one branch whose tip is E. It\nmay have a tracking branch that knows where the tip of the sending\nend used to be when it forked (which is C), so the above may say \"I\nhave E and C\". It actually would say \"I have B and A and ...\" for a\nbounded number of commits, but that does not fundamentally change\nthe picture---the important point is it is bounded and there is a\nhorizon.\n\n>> There are some work being done to optimize this further using\n>> various techniques, but they are not ready yet.\n\nAnd this still stands.\n"},{"id":"227510","messageId":"20130912074241.GC14259@raven.wolf.lan","threadId":"34898","inReplyTo":"xmqqsixbth4h.fsf@gitster.dls.corp.google.com","subject":"Re: Re-Transmission of blobs?","fromName":"Josef Wolf","fromEmail":"jw@raven.inka.de","sentAt":"2013-09-12T07:42:41Z","receivedAt":"2013-09-12T07:42:41Z","isPatch":false,"sender":{"key":"jw@raven.inka.de","avatar":null},"body":"On Mi, Sep 11, 2013 at 10:14:54 -0700, Junio C Hamano wrote:\n> Josef Wolf writes:\n> > On Di, Sep 10, 2013 at 10:51:02 -0700, Junio C Hamano wrote:\n> >> Consider this simple history with only a handful of commits (as\n> >> usual, time flows from left to right):\n> >> \n> >> E\n> >> / \n> >> A---B---C---D\n> >> \n> >> where D is at the tip of the sending side, E is at the tip of the\n> >> receiving side. The exchange goes roughly like this:\n> >> \n> >> (receiving side): what do you have?\n> >> \n> >> (sending side): my tip is at D.\n> >> \n> >> (receiving side): D? I've never heard of it --- please give it\n> >> to me. I have E.\n> >\n> > At this point, why would the receiving side not tell all the heads it knows\n> > about?\n> \n> It did. The receiving end had only one branch whose tip is E. It\n> may have a tracking branch that knows where the tip of the sending\n> end used to be when it forked (which is C), so the above may say \"I\n> have E and C\". It actually would say \"I have B and A and ...\" for a\n> bounded number of commits, but that does not fundamentally change\n> the picture---the important point is it is bounded and there is a\n> horizon.\n\nTherefore, the sending sinde has all information it needs to do any\noptimizations you can think of...\n\n> >> There are some work being done to optimize this further using\n> >> various techniques, but they are not ready yet.\n> \n> And this still stands.\n\nDo you have a pointer or something? I'd like to check out whether I can\ncontribute to this work.\n\n-- \nJosef Wolf\njw@raven.inka.de\n"},{"id":"227514","messageId":"20130912092339.GA30702@sigill.intra.peff.net","threadId":"34898","inReplyTo":"20130912074241.GC14259@raven.wolf.lan","subject":"Re: Re-Transmission of blobs?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-09-12T09:23:40Z","receivedAt":"2013-09-12T09:23:40Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Sep 12, 2013 at 09:42:41AM +0200, Josef Wolf wrote:\n\n> > >> There are some work being done to optimize this further using\n> > >> various techniques, but they are not ready yet.\n> > \n> > And this still stands.\n> \n> Do you have a pointer or something? I'd like to check out whether I can\n> contribute to this work.\n\nI think Junio is referring to the reachability bitmap work. We may know\nthat the other side has commit \"E\" (and therefore every object reachable\nfrom it), but we do not walk the graph to find the complete set of\nreachable objects. Doing so requires a lot of CPU and I/O, and in most\ncases does not help much.\n\nHowever, if we had an index of reachable objects (e.g., a bitmap) for\neach commit, then we could very cheaply compute the set difference\nbetween what the other side wants and what they have.\n\nJGit has support for pack bitmaps already. There was a patch series a\nfew months ago to implement a similar functionality for C git, but the\non-disk format was not compatible with JGit's. That series has been\nreworked off-list to be compatible with the JGit implementation.\n\nThose patches need a little cleanup before they are ready for the list,\nbut hopefully that should happen soon-ish.\n\n-Peff\n"},{"id":"227526","messageId":"20130912103531.GD14259@raven.wolf.lan","threadId":"34898","inReplyTo":"20130912092339.GA30702@sigill.intra.peff.net","subject":"Re: Re-Transmission of blobs?","fromName":"Josef Wolf","fromEmail":"jw@raven.inka.de","sentAt":"2013-09-12T10:35:32Z","receivedAt":"2013-09-12T10:35:32Z","isPatch":false,"sender":{"key":"jw@raven.inka.de","avatar":null},"body":"On Do, Sep 12, 2013 at 05:23:40 -0400, Jeff King wrote:\n> On Thu, Sep 12, 2013 at 09:42:41AM +0200, Josef Wolf wrote:\n>\n> I think Junio is referring to the reachability bitmap work. We may know\n> that the other side has commit \"E\" (and therefore every object reachable\n> from it), but we do not walk the graph to find the complete set of\n> reachable objects. Doing so requires a lot of CPU and I/O, and in most\n> cases does not help much.\n\nI'm not sure I understand correctly. I see that bitmaps can be used to\nimplement set operations. But how comes that walking the graph requires a lot\nof CPU? Isn't it O(n)?\n\n> However, if we had an index of reachable objects (e.g., a bitmap) for\n> each commit, then we could very cheaply compute the set difference\n> between what the other side wants and what they have.\n\nThose bitmaps would be stored in the git metadata? Is it worth it? Storing a\nbitmap for every commit just to be used once-in-a-while seems to be a pretty\nbig overhead to me. Not to mention the interoperability problems you mentioned\nbelow.\n\n> JGit has support for pack bitmaps already. There was a patch series a\n> few months ago to implement a similar functionality for C git, but the\n> on-disk format was not compatible with JGit's. That series has been\n> reworked off-list to be compatible with the JGit implementation.\n> \n> Those patches need a little cleanup before they are ready for the list,\n> but hopefully that should happen soon-ish.\n\nSounds like you're already almost done and don't really need help\nanymore. Just out of curiosity, I'd be interested in a pointer anyway ;-)\n\n-- \nJosef Wolf\njw@raven.inka.de\n"},{"id":"227530","messageId":"871B6C10EBEFE342A772D1159D132085571A7A1B@umechphj.easf.csd.disa.mil","threadId":"34898","inReplyTo":"20130912092339.GA30702@sigill.intra.peff.net","subject":"RE: Re-Transmission of blobs?","fromName":"Pyeron, Jason J CTR (US)","fromEmail":"jason.j.pyeron.ctr@mail.mil","sentAt":"2013-09-12T12:45:44Z","receivedAt":"2013-09-12T12:45:44Z","isPatch":false,"sender":{"key":"jason.j.pyeron.ctr@mail.mil","avatar":null},"body":"> -----Original Message-----\n> From: Jeff King\n> Sent: Thursday, September 12, 2013 5:24 AM\n> \n> On Thu, Sep 12, 2013 at 09:42:41AM +0200, Josef Wolf wrote:\n> \n> > > >> There are some work being done to optimize this further using\n> > > >> various techniques, but they are not ready yet.\n> > >\n> > > And this still stands.\n> >\n> > Do you have a pointer or something? I'd like to check out whether I\n> can\n> > contribute to this work.\n> \n> I think Junio is referring to the reachability bitmap work. We may know\n> that the other side has commit \"E\" (and therefore every object\n> reachable\n> from it), but we do not walk the graph to find the complete set of\n> reachable objects. Doing so requires a lot of CPU and I/O, and in most\n> cases does not help much.\n\nIf the rules of engagement are change a bit, the server side can be release from most of its work (CPU/IO).\n\nClient does the following, looping as needed:\n\nHeads=server->heads();\nKnownCommits=Local->AllCommits();\nMissingblobs=[];\nForeach(commit:heads) if (!knownCommits->contains(commit)) MissingBlobs[]=commit;\nForeach(commit:knownCommit) if (!commit->isValid()) MissingBlobs[]=commit->blobs();\nIf (missingBlobs->size()>0) server->FetchBlobs(missingBlobs);\n\n\nThis should work efficiently for the server if\na) the client is empty\nb) the client is corrupt\nc) the client is up to date\n\nExtending the server->fetchBlobs() to be more fancy, like taking patterns, such as between aaaaaa and dddddd exclusive is an exercise for someone else.\n\n\n"},{"id":"227562","messageId":"20130912194453.GD32069@sigill.intra.peff.net","threadId":"34898","inReplyTo":"20130912103531.GD14259@raven.wolf.lan","subject":"Re: Re-Transmission of blobs?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-09-12T19:44:53Z","receivedAt":"2013-09-12T19:44:53Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Sep 12, 2013 at 12:35:32PM +0200, Josef Wolf wrote:\n\n> I'm not sure I understand correctly. I see that bitmaps can be used to\n> implement set operations. But how comes that walking the graph requires a lot\n> of CPU? Isn't it O(n)?\n\nYes and no. Your \"n\" there is the entirety of history. Whereas a simple\n\"git push\" generally only has to look at the recent history. So even\nthough you are looking at each commit and tree only once, it's still a\nlarge number of them (and each one needs to be pulled off of the disk,\ndecompressed, and reconstructed from deltas).\n\nSecondly, the graph traversal ends up seeing the same sha1s over and\nover again in tree entries (because most entries in the tree don't\nchange from commit to commit). We spend a non-trivial amount of time\nlooking those up in a hash table.\n\nJust try \"git rev-list --objects --all\" in your favorite repository to\nget a sense. It takes something like 30 seconds in the kernel repo. You\nwould probably not want to add 30 seconds of CPU time to a trivial push.\n\n> Those bitmaps would be stored in the git metadata? Is it worth it? Storing a\n> bitmap for every commit just to be used once-in-a-while seems to be a pretty\n> big overhead to me. Not to mention the interoperability problems you mentioned\n> below.\n\nThere are tricks to make them smaller (run-length compression,\nbitmapping a subset of commits and traversing to the nearest one,\nstoring bitmaps as deltas against nearby bitmaps). And how often it is\nused depends on your git workload. For a repository serving git clones\nand fetches, it speeds up every operation.\n\nTry starting a clone of:\n\n git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git\n\nversus\n\n git://github.com/torvalds/linux.git\n\nand see which one starts sending you data more quickly.\n\n> Sounds like you're already almost done and don't really need help\n> anymore. Just out of curiosity, I'd be interested in a pointer anyway\n> ;-)\n\nShawn gave a talk on JGit here:\n\n http://www.eclipsecon.org/2013/sites/eclipsecon.org.2013/files/Scaling%20Up%20JGit%20-%20EclipseCon%202013.pdf\n\nand the scrapped patches for git are here:\n\n http://article.gmane.org/gmane.comp.version-control.git/228918\n\n-Peff\n"},{"id":"227566","messageId":"20130912195654.GE32069@sigill.intra.peff.net","threadId":"34898","inReplyTo":"871B6C10EBEFE342A772D1159D132085571A7A1B@umechphj.easf.csd.disa.mil","subject":"Re: Re-Transmission of blobs?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-09-12T19:56:54Z","receivedAt":"2013-09-12T19:56:54Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Sep 12, 2013 at 12:45:44PM +0000, Pyeron, Jason J CTR (US) wrote:\n\n> If the rules of engagement are change a bit, the server side can be release from most of its work (CPU/IO).\n> \n> Client does the following, looping as needed:\n> \n> Heads=server->heads();\n> KnownCommits=Local->AllCommits();\n> Missingblobs=[];\n> Foreach(commit:heads) if (!knownCommits->contains(commit)) MissingBlobs[]=commit;\n> Foreach(commit:knownCommit) if (!commit->isValid()) MissingBlobs[]=commit->blobs();\n> If (missingBlobs->size()>0) server->FetchBlobs(missingBlobs);\n\nThat doesn't quite work. The client does not know the set of missing\nobjects just from the commits. It knows the sha1 of the root trees it is\nmissing. And then if it fetches those, it knows the sha1 of any\ntop-level entries it is missing. And when it gets those, it knows the\nsha1 of any 2nd-level entries it is missing, and so forth.\n\nYou can progressively ask for each level, but:\n\n 1. You are spending a round-trip for each request. Doing it per-object\n is awful (the dumb http walker will do this if the repo is not\n packed, and it's S-L-O-W). Doing it per-level would be better, but\n not great.\n\n 2. You are losing opportunities for deltas (or you are making the\n state the server needs to maintain very complicated, as it must\n remember from request to request which objects you have gotten that\n can be used as delta bases).\n\n 3. There is a lot of overhead in this protocol. The client has to\n mention each object individually by sha1. It may not seem like a\n lot, but it can easily add 10% to a clone (just look at the size of\n the pack .idx files versus the packfiles themselves).\n\n-Peff\n"},{"id":"227567","messageId":"871B6C10EBEFE342A772D1159D132085571A7E5C@umechphj.easf.csd.disa.mil","threadId":"34898","inReplyTo":"20130912195654.GE32069@sigill.intra.peff.net","subject":"RE: Re-Transmission of blobs?","fromName":"Pyeron, Jason J CTR (US)","fromEmail":"jason.j.pyeron.ctr@mail.mil","sentAt":"2013-09-12T20:06:35Z","receivedAt":"2013-09-12T20:06:35Z","isPatch":false,"sender":{"key":"jason.j.pyeron.ctr@mail.mil","avatar":null},"body":"> -----Original Message-----\n> From: Jeff King\n> Sent: Thursday, September 12, 2013 3:57 PM\n> \n> On Thu, Sep 12, 2013 at 12:45:44PM +0000, Pyeron, Jason J CTR (US)\n> wrote:\n> \n> > If the rules of engagement are change a bit, the server side can be\n> release from most of its work (CPU/IO).\n> >\n> > Client does the following, looping as needed:\n> >\n> > Heads=server->heads();\n> > KnownCommits=Local->AllCommits();\n> > Missingblobs=[];\n> > Foreach(commit:heads) if (!knownCommits->contains(commit))\n> MissingBlobs[]=commit;\n> > Foreach(commit:knownCommit) if (!commit->isValid())\n> MissingBlobs[]=commit->blobs();\n> > If (missingBlobs->size()>0) server->FetchBlobs(missingBlobs);\n> \n> That doesn't quite work. The client does not know the set of missing\n\n\"looping as needed\"\n\n> objects just from the commits. It knows the sha1 of the root trees it\n> is\n> missing. And then if it fetches those, it knows the sha1 of any\n> top-level entries it is missing. And when it gets those, it knows the\n> sha1 of any 2nd-level entries it is missing, and so forth.\n> \n> You can progressively ask for each level, but:\n> \n> 1. You are spending a round-trip for each request. Doing it per-\n> object\n> is awful (the dumb http walker will do this if the repo is not\n> packed, and it's S-L-O-W). Doing it per-level would be better, but\n> not great.\n\nYes, but it is those awfully slow connections (slower that the looping issue) which happen to always drop while cloning from our office. And the round trip should be mitigated by http-keep-alives.\n\n> \n> 2. You are losing opportunities for deltas (or you are making the\n> state the server needs to maintain very complicated, as it must\n> remember from request to request which objects you have gotten\n> that\n> can be used as delta bases).\n\nBut, again if the connection drops, we have already lost the delta advantage. I would think the scenario would go like this:\n\ngit clone url://blah/blah\n[fail]\ncd blah\ngit clone --resume #uses normal methods....\n[fail]\nwhile ! git clone --resume --HitItWithAStick\n\nreplace clone with fetch for that use case too\n\n> \n> 3. There is a lot of overhead in this protocol. The client has to\n> mention each object individually by sha1. It may not seem like a\n> lot, but it can easily add 10% to a clone (just look at the size\n> of\n> the pack .idx files versus the packfiles themselves).\n\nBut if it finishes in a week, it is a lot better than it never, ever finishes.\n\nI draw attention to the time I had to download DB2 UDB in Thailand via 28k modem. It was resumable with wget, if it were not, it would have required the use of a plane to sneaker net it back.\n\n\n"},{"id":"227619","messageId":"20130913100934.GE14259@raven.wolf.lan","threadId":"34898","inReplyTo":"20130912194453.GD32069@sigill.intra.peff.net","subject":"Re: Re-Transmission of blobs?","fromName":"Josef Wolf","fromEmail":"jw@raven.inka.de","sentAt":"2013-09-13T10:09:35Z","receivedAt":"2013-09-13T10:09:35Z","isPatch":false,"sender":{"key":"jw@raven.inka.de","avatar":null},"body":"On Thu, Sep 12, 2013 at 03:44:53PM -0400, Jeff King wrote:\n> On Thu, Sep 12, 2013 at 12:35:32PM +0200, Josef Wolf wrote:\n> \n> > I'm not sure I understand correctly. I see that bitmaps can be used to\n> > implement set operations. But how comes that walking the graph requires a lot\n> > of CPU? Isn't it O(n)?\n> \n> Yes and no. Your \"n\" there is the entirety of history.\n\nIs this really true?\n\n> (and each one needs to be pulled off of the disk,\n> decompressed, and reconstructed from deltas).\n\nWhile you need to unpack commits/trees to traverse further down, I can't see\nany reason to unpack/reconstruct blobs just to see whether you need to send\nit. The SHA is all you need to know, isn't it?\n\n> Secondly, the graph traversal ends up seeing the same sha1s over and\n> over again in tree entries (because most entries in the tree don't\n> change from commit to commit).\n\nWhenever you see an object (whether commit or tree) that you already have\nseen, you can stop traversing further down this part of the graph/tree, as\neverything you will see on this part has already be seen before.\n\nWhy would you see the same commits/trees over and over again? You'd stop\ntraversing on the boundary of the already-seen-territory, leaving the vast\nmajority of the \"duplicated\" structure under the carpet. Somehow I fail to see\nthe problem here.\n\n-- \nJosef Wolf\njw@raven.inka.de\n"},{"id":"227620","messageId":"20130913102316.GF14259@raven.wolf.lan","threadId":"34898","inReplyTo":"871B6C10EBEFE342A772D1159D132085571A7E5C@umechphj.easf.csd.disa.mil","subject":"Re: Re-Transmission of blobs?","fromName":"Josef Wolf","fromEmail":"jw@raven.inka.de","sentAt":"2013-09-13T10:23:16Z","receivedAt":"2013-09-13T10:23:16Z","isPatch":false,"sender":{"key":"jw@raven.inka.de","avatar":null},"body":"On Thu, Sep 12, 2013 at 08:06:35PM +0000, Pyeron, Jason J CTR (US) wrote:\n\n> Yes, but it is those awfully slow connections (slower that the looping\n> issue) which happen to always drop while cloning from our office. And the\n> round trip should be mitigated by http-keep-alives.\n[ ... ]\n> But, again if the connection drops, we have already lost the delta\n> advantage. I would think the scenario would go like this:\n> \n> git clone url://blah/blah\n> [fail]\n> cd blah\n> git clone --resume #uses normal methods....\n> [fail]\n> while ! git clone --resume --HitItWithAStick\n> \n> replace clone with fetch for that use case too\n\nLast time I checked, cloning could not be resumed:\n\nhttp://git.661346.n2.nabble.com/git-clone-and-unreliable-links-td7570652.html\n\nIf you're on a slow/unreliable link, you've lost.\n\n:-( :-( :-(\n\n-- \nJosef Wolf\njw@raven.inka.de\n"},{"id":"227627","messageId":"43FBD2453ED7483F9EEB5B0D43C02C54@porsche","threadId":"34898","inReplyTo":"20130913102316.GF14259@raven.wolf.lan","subject":"RE: Re-Transmission of blobs?","fromName":"Jason Pyeron","fromEmail":"jpyeron@pdinc.us","sentAt":"2013-09-13T11:51:58Z","receivedAt":"2013-09-13T11:51:58Z","isPatch":false,"sender":{"key":"jpyeron@pdinc.us","avatar":"https://gravatar.com/avatar/c2e53452caa53d940768a1ffc9cf76196d851b9b534b7a39cd39852a70a0508f?d=mp&s=160"},"body":"> -----Original Message-----\n> From: Josef Wolf\n> Sent: Friday, September 13, 2013 6:23\n> \n> On Thu, Sep 12, 2013 at 08:06:35PM +0000, Pyeron, Jason J CTR \n> (US) wrote:\n> \n> > Yes, but it is those awfully slow connections (slower that \n> the looping\n> > issue) which happen to always drop while cloning from our \n> office. And \n> > the round trip should be mitigated by http-keep-alives.\n> [ ... ]\n> > But, again if the connection drops, we have already lost the delta \n> > advantage. I would think the scenario would go like this:\n> > \n> > git clone url://blah/blah\n> > [fail]\n> > cd blah\n> > git clone --resume #uses normal methods....\n\nI am using the mythical --resume, where it would fetch packs and indexes.\n\n> > [fail]\n> > while ! git clone --resume --HitItWithAStick\n> > \n> > replace clone with fetch for that use case too\n> \n> Last time I checked, cloning could not be resumed:\n> \n> http://git.661346.n2.nabble.com/git-clone-and-unreliable-links-td7570652.html\n> \n> If you're on a slow/unreliable link, you've lost.\n\n\nThat is kind of the point. It should be possible.\n\n\n--\n-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n- -\n- Jason Pyeron PD Inc. http://www.pdinc.us -\n- Principal Consultant 10 West 24th Street #100 -\n- +1 (443) 269-1555 x333 Baltimore, Maryland 21218 -\n- -\n-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\nThis message is copyright PD Inc, subject to license 20080407P00.\n\n \n"},{"id":"227628","messageId":"CACsJy8AdG=fY-utKdrsnJg-vnpdPqazLzqWO-bsikw3XLXGUgg@mail.gmail.com","threadId":"34898","inReplyTo":"871B6C10EBEFE342A772D1159D132085571A7E5C@umechphj.easf.csd.disa.mil","subject":"Re: Re-Transmission of blobs?","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-09-13T12:16:08Z","receivedAt":"2013-09-13T12:16:08Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Sep 13, 2013 at 3:06 AM, Pyeron, Jason J CTR (US)\n wrote:\n> But, again if the connection drops, we have already lost the delta advantage. I would think the scenario would go like this:\n>\n> git clone url://blah/blah\n> [fail]\n> cd blah\n> git clone --resume #uses normal methods....\n> [fail]\n> while ! git clone --resume --HitItWithAStick\n>\n> replace clone with fetch for that use case too\n\nSorry if I missed something in this thread. But I think we could\nstablize the transferred pack so that --resume works. The sender\nconstructs exactly the same pack as in the first \"git clone\" then it\nstarts sending from the offset given by the client. For that to work,\nthe first \"git clone\" must also be \"git clone --resume\". I started\nworking on that but now my focus is pack v4, so that has to wait.\n-- \nDuy\n"},{"id":"227720","messageId":"20130916215536.GB5477@sigill.intra.peff.net","threadId":"34898","inReplyTo":"20130913100934.GE14259@raven.wolf.lan","subject":"Re: Re-Transmission of blobs?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-09-16T21:55:36Z","receivedAt":"2013-09-16T21:55:36Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Sep 13, 2013 at 12:09:35PM +0200, Josef Wolf wrote:\n\n> > > I'm not sure I understand correctly. I see that bitmaps can be used to\n> > > implement set operations. But how comes that walking the graph requires a lot\n> > > of CPU? Isn't it O(n)?\n> > \n> > Yes and no. Your \"n\" there is the entirety of history.\n> \n> Is this really true?\n\nYes. If you know that the receiver has commit X, and you want to know if\nit has some blob Y, the only way to know for sure is to look at every\ntree of every commit reachable from X, and see whether any of them\nreferences Y. You might get lucky and see that one of the first commits\nyou looked at mentions Y, but in the negative case, you have to go all\nthe way down to the roots.\n\n> > (and each one needs to be pulled off of the disk,\n> > decompressed, and reconstructed from deltas).\n> \n> While you need to unpack commits/trees to traverse further down, I can't see\n> any reason to unpack/reconstruct blobs just to see whether you need to send\n> it. The SHA is all you need to know, isn't it?\n\nCorrect. The full sentence that you partially quoted above was:\n\n So even though you are looking at each commit and tree only once,\n it's still a large number of them (and each one needs to be pulled\n off of the disk, decompressed, and reconstructed from deltas).\n\nI.e., the \"each one\" is \"commits and trees\". Even reading just them\ntakes a fair bit of time. Pulling each blob off of disk, too, takes even\nlonger. You can try it yourself like this:\n\n git rev-list --objects --all |\n cut -d' ' -f1 |\n git cat-file --batch-check >all-objects\n for i in commit tree blob; do\n grep $i all-objects | cut -d' ' -f1 >$i-objects\n echo >&2 \"==> $i\"\n time git cat-file --batch <$i-objects >/dev/null\n done\n\nFor git.git, commits take about 0.5 seconds on my machine, trees 1\nsecond, and blobs 13 seconds. For the kernel, it's 5, 22, and 210\nseconds, respectively.\n\nNow those are times to actually cat the content to /dev/null. Just\nlooking at it internally is cheaper, but it gives you a ballpark figure\n(and most of that time goes to zlib inflation, which is the same either\nway).\n\n> > Secondly, the graph traversal ends up seeing the same sha1s over and\n> > over again in tree entries (because most entries in the tree don't\n> > change from commit to commit).\n> \n> Whenever you see an object (whether commit or tree) that you already have\n> seen, you can stop traversing further down this part of the graph/tree, as\n> everything you will see on this part has already be seen before.\n> \n> Why would you see the same commits/trees over and over again? You'd stop\n> traversing on the boundary of the already-seen-territory, leaving the vast\n> majority of the \"duplicated\" structure under the carpet. Somehow I fail to see\n> the problem here.\n\nYes, you do not have to recurse into sub-trees (or commits) you have\nalready seen. And we already do that optimization. So you do not see\nthe whole recursive tree over and over, but you see \"almost same\"\nsingle-level trees repeatedly.\n\nLet me try to give an example. Here's the root tree of git.git's v1.8.4\nrelease:\n\n $ git ls-tree v1.8.4 | wc -l\n 361\n\nSo we have to do 361 lookups, one per entry, to find that we haven't\nyet processed each one.\n\nNow what happens when we look at the next commit?\n\n $ git ls-tree v1.8.4^ | wc -l\n 361\n $ git diff-tree --abbrev v1.8.4 v1.8.4^\n :040000 040000 f3aec4c... a6e780e... M Documentation\n :100755 100755 06026ea... 572dfeb... M GIT-VERSION-GEN\n\nStill 361 entries, but only two are changed. Yet we still have\nto go through all 361 to figure out _which_ were changed.\n\nWe can do that by going linearly through the tree and checking each sha1\nagainst a \"have we seen this?\" data structure. Or we could diff\non-the-fly between adjacent trees, and only process those that we know\nwe didn't just see.\n\nThe current code uses the \"seen this\" strategy with a hash table. I've\ntried the diff strategy, but I couldn't make it any faster than using\nthe hash table. If we had a tree storage format that made diffs cheap\n(like packv4), then traversing via diffs would probably be a win.\n\nNote also that the cost of traversing is dependent on the shape of the\ntree. Putting all of your files in the root directory does not perform\nas well as having a nicely balanced tree structure, because we can't\nweed out as many entries by noticing the whole sub-tree is unchanged.\n\n-Peff\n"},{"id":"227930","messageId":"20130920092715.GG14259@raven.wolf.lan","threadId":"34898","inReplyTo":"20130916215536.GB5477@sigill.intra.peff.net","subject":"Re: Re-Transmission of blobs?","fromName":"Josef Wolf","fromEmail":"jw@raven.inka.de","sentAt":"2013-09-20T09:27:15Z","receivedAt":"2013-09-20T09:27:15Z","isPatch":false,"sender":{"key":"jw@raven.inka.de","avatar":null},"body":"On Mon, Sep 16, 2013 at 05:55:36PM -0400, Jeff King wrote:\n> On Fri, Sep 13, 2013 at 12:09:35PM +0200, Josef Wolf wrote:\n> \n> > > > I'm not sure I understand correctly. I see that bitmaps can be used to\n> > > > implement set operations. But how comes that walking the graph requires a lot\n> > > > of CPU? Isn't it O(n)?\n> > > \n> > > Yes and no. Your \"n\" there is the entirety of history.\n> > \n> > Is this really true?\n> \n> Yes. If you know that the receiver has commit X, and you want to know if\n> it has some blob Y, the only way to know for sure is to look at every\n> tree of every commit reachable from X, and see whether any of them\n> references Y.\n\nJeff, in my original example, I did a cherry-pick from origin/somebranch.\nEven without asking, we can assume with great probability that\norigin/somebranch is available at origin. And the file in question happens to\nreside in the tree at the very tip of origin/somebranch, not in some of its\nancestors. In this case, there's no need to search the history at all. And\neven in this pretty simple case, the algorithm seems to fail for some reason.\n\n> Yes, you do not have to recurse into sub-trees (or commits) you have\n> already seen. And we already do that optimization.\n\nWhy is the file re-transmitted, then?\n\n\nWith a little change in the protocol, a very simple optimization could be\nimplemented, avoiding the complicated bitmap strategy you were talking about:\n\nPlease consider Junio's description of the dialog:\n\n[ Junio wrote: ]\n> Consider this simple history with only a handful of commits (as\n> usual, time flows from left to right):\n>\n> E\n> / \n> A---B---C---D\n>\n> where D is at the tip of the sending side, E is at the tip of the\n> receiving side. The exchange goes roughly like this:\n>\n> (receiving side): what do you have?\n>\n> (sending side): my tip is at D.\n>\n> (receiving side): D? I've never heard of it --- please give it\n> to me. I have E.\n>\n> (sending side): E? I don't know about it; must be something you\n> created since you forked from me. Tell me about\n> its ancestors.\n>\n> (receiving side): OK, I have C.\n>\n> (sending side): Oh, C I know about. You do not have to tell me\n> anything more. A packfile to bring you up to\n> date will follow.\n\nIn the last step, instead of sending a packfile, the sending side should send\na list of the SHA's which would be included in this packfile. The receiving\nside would then be able to request all the objects it needs to get up-to-date.\n\nI think this change would be considerably simpler than the reachability bitmap\nyou are talking about. And it would avoid all those time consuming traversals\nthrough the history and the tree. And it would omit _all_ redundant\nretransmissions. Even in the case when sender and receiver do not have _any_\ncommon heads at all, _no_ files at all would be retransmitted unnecessarily.\n\n-- \nJosef Wolf\njw@raven.inka.de\n"},{"id":"228141","messageId":"20130924073613.GC7257@sigill.intra.peff.net","threadId":"34898","inReplyTo":"20130920092715.GG14259@raven.wolf.lan","subject":"Re: Re-Transmission of blobs?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-09-24T07:36:13Z","receivedAt":"2013-09-24T07:36:13Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Sep 20, 2013 at 11:27:15AM +0200, Josef Wolf wrote:\n\n> > Yes. If you know that the receiver has commit X, and you want to know if\n> > it has some blob Y, the only way to know for sure is to look at every\n> > tree of every commit reachable from X, and see whether any of them\n> > references Y.\n> \n> Jeff, in my original example, I did a cherry-pick from origin/somebranch.\n\nSorry, I thought we were talking about the general case, not your\nspecific example.\n\n> Even without asking, we can assume with great probability that\n> origin/somebranch is available at origin.\n\nBear in mind that the transfer process does not know about\ncherry-picking at all. It only sees the other side's tips and traverses.\n\n> And the file in question happens to reside in the tree at the very tip\n> of origin/somebranch, not in some of its ancestors. In this case,\n> there's no need to search the history at all. And even in this pretty\n> simple case, the algorithm seems to fail for some reason.\n\nCorrect. And in the current code, we should be looking at the tip tree\nfor your case. However, the usual reason to do so is to mark those\nobjects as a \"preferred base\" in pack-objects for doing deltas. I wonder\nif we are not correctly noticing the case that an object is both\nrequested to be sent and marked as a preferred base (in which case we\nshould drop it from our sending list).\n\nIf that's the problem, it should be easy to fix cheaply. It would not\nwork in the general case, but it would for your specific example. But\nsince it costs nothing, there's no reason not to.\n\nI'll see if I can investigate using the example script you posted.\n\n> > Yes, you do not have to recurse into sub-trees (or commits) you have\n> > already seen. And we already do that optimization.\n> \n> Why is the file re-transmitted, then?\n\nI meant \"we do the optimization during history traversal that avoids\ngoing into sub-trees we have already seen\". We do _not_ do the full\nhistory traversal for a partial push.\n\n> With a little change in the protocol, a very simple optimization could be\n> implemented, avoiding the complicated bitmap strategy you were talking about:\n> [...]\n> In the last step, instead of sending a packfile, the sending side should send\n> a list of the SHA's which would be included in this packfile. The receiving\n> side would then be able to request all the objects it needs to get up-to-date.\n\nI think you have a mis-impression of the problem bitmaps are trying to\nsolve, mostly because it is not the problem you presented in your\nthread (but your problem is one that bitmaps can help).\n\nConsider what the sending side has to do to come up with that list of\nobjects to send. It has to traverse history to do it, looking at each\ntree of each commit that is going to be sent. That effort is\nproportional to the amount of history we are going to send. For a small\npush or fetch, it is not much. For a clone, it can be quite a lot (tens\nof seconds of CPU time per clone). Bitmaps drastically reduce the amount\nof CPU required.\n\nBitmaps can _also_ solve other problems, like letting us be more\nthorough in realizing which objects the other side has (without spending\neffort on an expensive traversal). If that were the only thing they did,\nit might not be worth it. But we basically get that for \"free\" by\nsolving the other problem.\n\nSo I do not think such a protocol extension is an argument against\npack bitmaps; you would want them with or without the protocol change.\n\n> I think this change would be considerably simpler than the reachability bitmap\n> you are talking about. And it would avoid all those time consuming traversals\n> through the history and the tree. And it would omit _all_ redundant\n> retransmissions. Even in the case when sender and receiver do not have _any_\n> common heads at all, _no_ files at all would be retransmitted unnecessarily.\n\nYes, that would be nice. However, in the common cases it would make\nthings much worse. A clone of linux.git has ~3.5M objects. That's 70MB\nof sha1s that the server tells the client \"tell me which of these you\nneed\", and then another 70MB for the client to say \"yep, I need all of\nthem\". You could have the client instead say \"here are the few I\n_don't_ need\", which would save the second half in the common cases.\n\nAnd of course it would be smaller for a smaller fetch/push. Just looking\nat \"git rev-list --objects --all --since=1.week.ago\" in the kernel,\nthere are ~77K new objects. So over the course of a week, we use an\nextra 1.5MB of bandwidth. How many objects did we save ourselves from\nsending, and how big were they (keep in mind they will typically be\ndeltas against object you already have anyway)?\n\nThe answer would depend on your cherry-picking and reverting habits. But\nI would guess in a normal workflow that you would not come close to\nbreaking even.\n\nThere are, of course, cases where the user _knows_ there is a huge\nobject that the other side has, and they do not want to have to send it\nagain. For that case, it would be useful to have something like the\nprotocol you described as an optional extension to turn on. Of course,\nsomebody has to implement it. :)\n\n-Peff\n"},{"id":"228175","messageId":"20130924203651.GH14259@raven.wolf.lan","threadId":"34898","inReplyTo":"20130924073613.GC7257@sigill.intra.peff.net","subject":"Re: Re-Transmission of blobs?","fromName":"Josef Wolf","fromEmail":"jw@raven.inka.de","sentAt":"2013-09-24T20:36:51Z","receivedAt":"2013-09-24T20:36:51Z","isPatch":false,"sender":{"key":"jw@raven.inka.de","avatar":null},"body":"On Tue, Sep 24, 2013 at 03:36:13AM -0400, Jeff King wrote:\n> On Fri, Sep 20, 2013 at 11:27:15AM +0200, Josef Wolf wrote:\n\n> > Even without asking, we can assume with great probability that\n> > origin/somebranch is available at origin.\n> Bear in mind that the transfer process does not know about\n> cherry-picking at all.\n\nIt dosn't need to know.\n\n> It only sees the other side's tips and traverses.\n\nThe sender side knows with high probability that origin/somebranch is avalable\nat the receivig side (unless it was deleted). And since the file in question\nis part of the tree at the tip of origin/somebranch, we can deduce that the\nfile is available on the other side (unless it was deleted).\n\n> > And the file in question happens to reside in the tree at the very tip\n> > of origin/somebranch, not in some of its ancestors. In this case,\n> > there's no need to search the history at all. And even in this pretty\n> > simple case, the algorithm seems to fail for some reason.\n> \n> Correct. And in the current code, we should be looking at the tip tree\n> for your case. However, the usual reason to do so is to mark those\n> objects as a \"preferred base\" in pack-objects for doing deltas. I wonder\n> if we are not correctly noticing the case that an object is both\n> requested to be sent and marked as a preferred base (in which case we\n> should drop it from our sending list).\n\nFurther, it seems that the marking as preferred base had no effect, since the\ndelta should have been zero in this case. Or is this mechanism deactivated for\nbinary data (/dev/zero in this case)?\n\n> If that's the problem, it should be easy to fix cheaply. It would not\n> work in the general case, but it would for your specific example. But\n> since it costs nothing, there's no reason not to.\n> \n> I'll see if I can investigate using the example script you posted.\n\nThanks!\n\n> I meant \"we do the optimization during history traversal that avoids\n> going into sub-trees we have already seen\". We do _not_ do the full\n> history traversal for a partial push.\n\nOK. I see. Maybe a config option to request a full traversal would be a\nreasonable compromise? That way CPU could be traded against bandwidth for\nrepositories that happen to have slow/unreliable/expensive connections.\n\n> Yes, that would be nice. However, in the common cases it would make\n> things much worse. A clone of linux.git has ~3.5M objects.\n\nOf course, if there's nothing you can drop, any attempt to drop objects will\nadd to overhead. That's similar to compressing compressed files. This will\nenlarge the original file. Would that be a reasonable argument to get rid of\nall attempts to compress files?\n\n-- \nJosef Wolf\njw@raven.inka.de\n"}]}