{"thread":{"id":"14394","subject":"git pull is slow","startedAt":"2008-07-10T14:40:17Z","lastAt":"2008-07-17T23:45:03Z","messageCount":51,"participants":["Stephan Hennig","Martin Langhoff","Petr Baudis","Johannes Sixt","Andreas Ericsson","Johannes Schindelin","Shawn O. Pearce","Nicolas Pitre","Jakub Narebski","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"82816","messageId":"g5570s$d5m$1@ger.gmane.org","threadId":"14394","inReplyTo":null,"subject":"git pull is slow","fromName":"Stephan Hennig","fromEmail":"mailing_list@arcor.de","sentAt":"2008-07-10T14:40:17Z","receivedAt":"2008-07-10T14:40:17Z","isPatch":false,"sender":{"key":"mailing_list@arcor.de","avatar":null},"body":"Hi,\n\nI am observing very large data transfers when pulling from the\nrepository at . This repository\ncontains one 13 MB text file that compressed is roughly 3 MB large.\n\nWhile I'd expect pulling commits that change only a few lines of the\nlarge text file to result in a download of less than, say 10kB, git pull\nseems to transfer the complete, compressed file. I have observed this\nseveral times for different commits. On the other hand, pushing my own\ncommits to the repository is fast (with git+ssh access method). Any\nideas what's going on and how to make pulling faster?\n\nBest regards,\nStephan Hennig\n\n> $ git version\n> git version 1.5.6.1.1071.g76fb\n"},{"id":"82817","messageId":"46a038f90807100813s82e1e54l1d8ac6851015a500@mail.gmail.com","threadId":"14394","inReplyTo":"g5570s$d5m$1@ger.gmane.org","subject":"Re: git pull is slow","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2008-07-10T15:13:28Z","receivedAt":"2008-07-10T15:13:28Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On Thu, Jul 10, 2008 at 11:40 AM, Stephan Hennig wrote:\n> commits to the repository is fast (with git+ssh access method). Any\n> ideas what's going on and how to make pulling faster?\n\nWhen pushing you can use --thin to get a \"thin pack\" transfer, where\nthe delta-base is not transferred. Not sure how you request this from\ngit fetch these days though :-/ Search the list for \"thin packs\"\nperhaps?\n\ncheers,\n\n\nm\n--\n martin.langhoff@gmail.com\n martin@laptop.org -- School Server Architect\n - ask interesting questions\n - don't get distracted with shiny stuff - working code first\n - http://wiki.laptop.org/go/User:Martinlanghoff\n"},{"id":"82819","messageId":"20080710152846.GB32184@machine.or.cz","threadId":"14394","inReplyTo":"g5570s$d5m$1@ger.gmane.org","subject":"Re: git pull is slow","fromName":"Petr Baudis","fromEmail":"pasky@suse.cz","sentAt":"2008-07-10T15:28:46Z","receivedAt":"2008-07-10T15:28:46Z","isPatch":false,"sender":{"key":"pasky@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/18439?v=4"},"body":" Hi,\n\nOn Thu, Jul 10, 2008 at 04:40:17PM +0200, Stephan Hennig wrote:\n> I am observing very large data transfers when pulling from the\n> repository at . This repository\n> contains one 13 MB text file that compressed is roughly 3 MB large.\n> \n> While I'd expect pulling commits that change only a few lines of the\n> large text file to result in a download of less than, say 10kB, git pull\n> seems to transfer the complete, compressed file. I have observed this\n> several times for different commits. On the other hand, pushing my own\n> commits to the repository is fast (with git+ssh access method). Any\n> ideas what's going on and how to make pulling faster?\n\n do you use HTTP or native Git protocol for pulling? If HTTP, you have\nto live with this, sorry - the automatic repacks will create a new pack\nevery time and you will have to redownload the whole history; I tried to\navoid this problem but in the end I had to bow down to the agressive\nrepacking strategy because the number of packs was getting out of hand.\nIt is technically possible to implement some alternative more\nHTTP-friendly packing strategy, but this has always stayed only in idea\nstage. If you want to implement something, repo.or.cz will become a glad\nuser. :-)\n\n-- \n\t\t\t\tPetr \"Pasky\" Baudis\nThe last good thing written in C++ was the Pachelbel Canon. -- J. Olson\n"},{"id":"82822","messageId":"48762B27.90004@viscovery.net","threadId":"14394","inReplyTo":"g5570s$d5m$1@ger.gmane.org","subject":"Re: git pull is slow","fromName":"Johannes Sixt","fromEmail":"j.sixt@viscovery.net","sentAt":"2008-07-10T15:30:47Z","receivedAt":"2008-07-10T15:30:47Z","isPatch":false,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Stephan Hennig schrieb:\n> I am observing very large data transfers when pulling from the\n> repository at . This repository\n> contains one 13 MB text file that compressed is roughly 3 MB large.\n> \n> While I'd expect pulling commits that change only a few lines of the\n> large text file to result in a download of less than, say 10kB, git pull\n> seems to transfer the complete, compressed file. I have observed this\n> several times for different commits. On the other hand, pushing my own\n> commits to the repository is fast (with git+ssh access method). Any\n> ideas what's going on and how to make pulling faster?\n\nDo you by any chance use a http URL to pull? Don't do that. Use git protocol.\n\n-- Hannes\n"},{"id":"82823","messageId":"48762E8A.7070203@arcor.de","threadId":"14394","inReplyTo":"48762B27.90004@viscovery.net","subject":"Re: git pull is slow","fromName":"Stephan Hennig","fromEmail":"mailing_list@arcor.de","sentAt":"2008-07-10T15:45:14Z","receivedAt":"2008-07-10T15:45:14Z","isPatch":false,"sender":{"key":"mailing_list@arcor.de","avatar":null},"body":"Johannes Sixt schrieb:\n> Stephan Hennig schrieb:\n>> I am observing very large data transfers when pulling from the \n>> repository at . This\n>> repository contains one 13 MB text file that compressed is roughly\n>> 3 MB large.\n> \n> Do you by any chance use a http URL to pull? Don't do that. Use git\n> protocol.\n\nNo, I'm already using git+ssh.\n\nBest regards,\nStephan Hennig\n"},{"id":"82824","messageId":"20080710155016.GC32184@machine.or.cz","threadId":"14394","inReplyTo":"48762E8A.7070203@arcor.de","subject":"Re: git pull is slow","fromName":"Petr Baudis","fromEmail":"pasky@suse.cz","sentAt":"2008-07-10T15:50:16Z","receivedAt":"2008-07-10T15:50:16Z","isPatch":false,"sender":{"key":"pasky@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/18439?v=4"},"body":"On Thu, Jul 10, 2008 at 05:45:14PM +0200, Stephan Hennig wrote:\n> Johannes Sixt schrieb:\n> > Stephan Hennig schrieb:\n> >> I am observing very large data transfers when pulling from the \n> >> repository at . This\n> >> repository contains one 13 MB text file that compressed is roughly\n> >> 3 MB large.\n> > \n> > Do you by any chance use a http URL to pull? Don't do that. Use git\n> > protocol.\n> \n> No, I'm already using git+ssh.\n\nOh, ok. By the way, how long are you hitting this issue? Just today,\nI have upgraded the chroot Git from some anonymous 2007-12-08 version\nto the almost-latest #next.\n\n-- \n\t\t\t\tPetr \"Pasky\" Baudis\nThe last good thing written in C++ was the Pachelbel Canon. -- J. Olson\n"},{"id":"82831","messageId":"48764A63.9070705@arcor.de","threadId":"14394","inReplyTo":"20080710155016.GC32184@machine.or.cz","subject":"Re: git pull is slow","fromName":"Stephan Hennig","fromEmail":"mailing_list@arcor.de","sentAt":"2008-07-10T17:44:03Z","receivedAt":"2008-07-10T17:44:03Z","isPatch":false,"sender":{"key":"mailing_list@arcor.de","avatar":null},"body":"Petr Baudis schrieb:\n> On Thu, Jul 10, 2008 at 05:45:14PM +0200, Stephan Hennig wrote:\n>> \n>> No, I'm already using git+ssh.\n> \n> Oh, ok. By the way, how long are you hitting this issue? Just today,\n> I have upgraded the chroot Git from some anonymous 2007-12-08 version\n> to the almost-latest #next.\n\nI don't know for sure. But I think I've had the issue since I started\naccessing that repository in October 2007 (then with WinGit-0.2-alpha).\n\nBest regards,\nStephan Hennig\n\nPS: Attached is my .git/config. Could the repositoryformatversion line\ntrigger some sort of dumb transfer protocol?\n\n\n> [core]\n> \trepositoryformatversion = 0\n> \tfilemode = false\n> \tbare = false\n> \tlogallrefupdates = true\n> \tsymlinks = false\n> autocrlf = false\n> [remote \"origin\"]\n> \turl = git+ssh://xxx@repo.or.cz/srv/git/wortliste.git\n> \tfetch = +refs/heads/*:refs/remotes/origin/*\n> [branch \"master\"]\n> \tremote = origin\n> \tmerge = refs/heads/master\n"},{"id":"82950","messageId":"g57jkp$ekm$1@ger.gmane.org","threadId":"14394","inReplyTo":"g5570s$d5m$1@ger.gmane.org","subject":"Re: git pull is slow","fromName":"Stephan Hennig","fromEmail":"mailing_list@arcor.de","sentAt":"2008-07-11T12:25:58Z","receivedAt":"2008-07-11T12:25:58Z","isPatch":false,"sender":{"key":"mailing_list@arcor.de","avatar":null},"body":"Stephan Hennig schrieb:\n\n> I am observing very large data transfers when pulling from the\n> repository at .\n\nHere's the output of a recent pull:\n\n> unknown@COMMODORE ~/Themen/trennmuster/repository/wortliste (master)\n> $ git pull\n> Enter passphrase for key '/x/home/.ssh/id_rsa':\n> remote: Counting objects: 15, done.←[K\n> remote: Compressing objects: 100% (7/7), done.←[K) ←[Kts: 8% (1/12)\n> remote: Total 12 (delta 5), reused 12 (delta 5)←[K\n> Unpacking objects: 100% (12/12), done.\n> From git+ssh://xxx@repo.or.cz/srv/git/wortliste\n> d905095..d0c6a33 master -> origin/master\n> * [new tag] dehyph-exptl-v0.13 -> dehyph-exptl-v0.13\n> Updating d905095..d0c6a33\n> Fast forward\n> wortliste←[m | 19 ←[32m+++++++++++←[m←[31m--------←[m\n> 1 files changed, 11 insertions(+), 8 deletions(-)←[m\n\nAfter the line containing \"remote: Compressing objects:\" had been\nprinted several MB have been transferred.\n\nDoes it matter that the original clone has been performed with plain git\nprotocol? I have only later changed the url in .git/config to use git+ssh.\n\nBest regards,\nStephan Hennig\n"},{"id":"82955","messageId":"g57mu1$q3v$1@ger.gmane.org","threadId":"14394","inReplyTo":"g5570s$d5m$1@ger.gmane.org","subject":"Re: git pull is slow","fromName":"Stephan Hennig","fromEmail":"mailing_list@arcor.de","sentAt":"2008-07-11T12:55:25Z","receivedAt":"2008-07-11T12:55:25Z","isPatch":false,"sender":{"key":"mailing_list@arcor.de","avatar":null},"body":"Stephan Hennig schrieb:\n\n> Does it matter that the original clone has been performed with plain git\n> protocol? I have only later changed the url in .git/config to use git+ssh.\n\nTo be precise, the original pull has been done via\n\n\turl = git://repo.or.cz/wortliste.git\n\nwhich is a read-only URL. I changed .git/config manually to point to\n\n\turl = git+ssh://xxx@repo.or.cz/srv/git/wortliste.git\n\nlater, which is the push URL.\n\nBest regards,\nStephan Hennig\n"},{"id":"82956","messageId":"48776169.20705@op5.se","threadId":"14394","inReplyTo":"g57jkp$ekm$1@ger.gmane.org","subject":"Re: git pull is slow","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2008-07-11T13:34:33Z","receivedAt":"2008-07-11T13:34:33Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Stephan Hennig wrote:\n> Stephan Hennig schrieb:\n> \n>> I am observing very large data transfers when pulling from the\n>> repository at .\n> \n> Here's the output of a recent pull:\n> \n>> unknown@COMMODORE ~/Themen/trennmuster/repository/wortliste (master)\n>> $ git pull\n>> Enter passphrase for key '/x/home/.ssh/id_rsa':\n>> remote: Counting objects: 15, done.←[K\n>> remote: Compressing objects: 100% (7/7), done.←[K) ←[Kts: 8% (1/12)\n>> remote: Total 12 (delta 5), reused 12 (delta 5)←[K\n>> Unpacking objects: 100% (12/12), done.\n>> From git+ssh://xxx@repo.or.cz/srv/git/wortliste\n>> d905095..d0c6a33 master -> origin/master\n>> * [new tag] dehyph-exptl-v0.13 -> dehyph-exptl-v0.13\n>> Updating d905095..d0c6a33\n>> Fast forward\n>> wortliste←[m | 19 ←[32m+++++++++++←[m←[31m--------←[m\n>> 1 files changed, 11 insertions(+), 8 deletions(-)←[m\n> \n> After the line containing \"remote: Compressing objects:\" had been\n> printed several MB have been transferred.\n> \n\nSeems like you're being bitten by a bug we had some months back,\nwhere the client requested full history for new tag objects.\n\nDoes this bug still show up if you use the latest git from\nmaster of git.git?\n\nI *think* v1.5.4.3-440-g41fa7d2 fixed the issue, but I'm\nnot 100% certain as the commit message doesn't mention anything\nabout any bugs being solved. Otoh, I vaguely remember the first\nbug-reporter being told to try 'next', and afair, that solved it\nfor him/her.\n\n> Does it matter that the original clone has been performed with plain git\n> protocol? I have only later changed the url in .git/config to use git+ssh.\n> \n\nNo, that doesn't matter in the slightest.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"82958","messageId":"alpine.DEB.1.00.0807111443280.8950@racer","threadId":"14394","inReplyTo":"48776169.20705@op5.se","subject":"Re: git pull is slow","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-11T14:04:21Z","receivedAt":"2008-07-11T14:04:21Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Fri, 11 Jul 2008, Andreas Ericsson wrote:\n\n> Stephan Hennig wrote:\n> > Stephan Hennig schrieb:\n> > \n> > > I am observing very large data transfers when pulling from the\n> > > repository at .\n> > \n> > Here's the output of a recent pull:\n> > \n> > > unknown@COMMODORE ~/Themen/trennmuster/repository/wortliste (master)\n> > > $ git pull\n> > > Enter passphrase for key '/x/home/.ssh/id_rsa':\n> > > remote: Counting objects: 15, done.←[K\n> > > remote: Compressing objects: 100% (7/7), done.←[K) ←[Kts: 8% (1/12)\n> > > remote: Total 12 (delta 5), reused 12 (delta 5)←[K\n> > > Unpacking objects: 100% (12/12), done.\n> > > From git+ssh://xxx@repo.or.cz/srv/git/wortliste\n> > > d905095..d0c6a33 master -> origin/master\n> > > * [new tag] dehyph-exptl-v0.13 -> dehyph-exptl-v0.13\n> > > Updating d905095..d0c6a33\n> > > Fast forward\n> > > wortliste←[m | 19 ←[32m+++++++++++←[m←[31m--------←[m\n> > > 1 files changed, 11 insertions(+), 8 deletions(-)←[m\n> > \n> > After the line containing \"remote: Compressing objects:\" had been\n> > printed several MB have been transferred.\n> > \n> \n> Seems like you're being bitten by a bug we had some months back,\n> where the client requested full history for new tag objects.\n\nI do not think so. I think it is a problem with the pack. The slowness \nis already there in the clone, in the resolving phase.\n\nJudging from the output of \"verify-pack -v\", it seems that the delta \nchains are quite long.\n\nI saw memory usage go up pretty quickly. I thought that maybe \neac12e2(Correct pack memory leak causing git gc to try to exceed ulimit)\nwould help things, since it fixes a place where memory usage grows out of \nbounds, but it did not.\n\nUnfortunately, I do not have time to look into this further.\n\nBTW there is a nasty usability bug when \"Compressing objects:\" and \n\"Receiving objects:\" messages \n\nCiao,\nDscho"},{"id":"83075","messageId":"4878A442.6020405@arcor.de","threadId":"14394","inReplyTo":"alpine.DEB.1.00.0807111443280.8950@racer","subject":"Re: git pull is slow","fromName":"Stephan Hennig","fromEmail":"mailing_list@arcor.de","sentAt":"2008-07-12T12:32:02Z","receivedAt":"2008-07-12T12:32:02Z","isPatch":false,"sender":{"key":"mailing_list@arcor.de","avatar":null},"body":"Hi,\n\nJohannes Schindelin schrieb:\n> On Fri, 11 Jul 2008, Andreas Ericsson wrote:\n> \n>> Seems like you're being bitten by a bug we had some months back,\n>> where the client requested full history for new tag objects.\n> \n> I do not think so. I think it is a problem with the pack. The slowness \n> is already there in the clone, in the resolving phase.\n\nThanks for having a look at this! What does \"problem with the pack\"\nmean? Do you think it is a Git problem (client or server side?) or just\na misconfiguration?\n\nBest regards,\nStephan Hennig\n"},{"id":"83094","messageId":"alpine.DEB.1.00.0807121546590.8950@racer","threadId":"14394","inReplyTo":"4878A442.6020405@arcor.de","subject":"Re: git pull is slow","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-12T17:05:14Z","receivedAt":"2008-07-12T17:05:14Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sat, 12 Jul 2008, Stephan Hennig wrote:\n\n> Johannes Schindelin schrieb:\n> > On Fri, 11 Jul 2008, Andreas Ericsson wrote:\n> > \n> >> Seems like you're being bitten by a bug we had some months back, \n> >> where the client requested full history for new tag objects.\n> > \n> > I do not think so. I think it is a problem with the pack. The \n> > slowness is already there in the clone, in the resolving phase.\n> \n> Thanks for having a look at this! What does \"problem with the pack\" \n> mean? Do you think it is a Git problem (client or server side?) or just \n> a misconfiguration?\n\nI thought that the blobs in the pack are just too similar. That makes for \na good compression, since you get many relatively small deltas. But it \nalso makes for a lot of work to reconstruct the blobs.\n\nI suspected that you run out of space for the cache holding some \nreconstructed blobs (to prevent reconstructing all of them from scratch).\n\nTo see what I mean, just look at\n\n$ git -p verify-pack -v \\\n .git/objects/pack/pack-563c2d83940c7e2d8c20a35206a390e2e567282f.pack\n\n(or whatever pack you have there). It has this:\n\n-- snip --\nchain length = 40: 7 objects\nchain length = 41: 8 objects\nchain length = 42: 4 objects\nchain length = 43: 8 objects\nchain length = 44: 6 objects\nchain length = 45: 2 objects\nchain length = 46: 6 objects\nchain length = 47: 2 objects\nchain length = 48: 2 objects\nchain length = 49: 2 objects\nchain length = 50: 2 objects\n-- snap --\n\n... but that could not be the reason, as my current git.git's pack shows \nthis:\n\n-- snip --\nchain length = 40: 122 objects\nchain length = 41: 99 objects\nchain length = 42: 77 objects\nchain length = 43: 76 objects\nchain length = 44: 69 objects\nchain length = 45: 72 objects\nchain length = 46: 66 objects\nchain length = 47: 103 objects\nchain length = 48: 77 objects\nchain length = 49: 111 objects\nchain length = 50: 86 objects\nchain length > 50: 60 objects\n-- snap --\n\n... which is much worse.\n\nSo I tried this:\n\n-- snip --\nwortliste$ /usr/bin/time git index-pack -o /dev/null \n.git/objects/pack/pack-563c2d83940c7e2d8c20a35206a390e2e567282f.pack\nfatal: unable to create /dev/null: File exists\nCommand exited with non-zero status 128\n27.12user 11.21system 2:51.02elapsed 22%CPU (0avgtext+0avgdata \n0maxresident)k\n81848inputs+0outputs (1134major+2042348minor)pagefaults 0swaps\n-- snap --\n\nCompare that to git.git:\n\n-- snip --\ngit$ /usr/bin/time git index-pack -o /dev/null \n.git/objects/pack/pack-355b54f45778b56c00099bf45369f8a4f2704a51.pack\nfatal: unable to create /dev/null: File exists\nCommand exited with non-zero status 128\n16.13user 0.38system 0:17.80elapsed 92%CPU (0avgtext+0avgdata \n0maxresident)k\n81288inputs+0outputs (38major+51917minor)pagefaults 0swaps\n-- snap --\n\nSo it seems that the major faults (requiring I/O) occur substantially more \noften with your repository.\n\nBTW the RAM numbers here are obviously bogus, the program trashed the disk \nlike there was no tomorrow.\n\nOkay, \"valgrind --tool=massif\" to the rescue:\n\n-- snip --\nMB\n555.9^ , #\n| @..#\n| @. :@::#\n| , @@: :@::#\n| ,@. @:. .:: @: : @@: :@::#\n| @: .@@::@:: :::: @: : @@: :@::#\n| , .@: :@@::@:: :::: @: : @@: :@::#\n| . .@ :@: :@@::@:: :::: @: : @@: :@::#\n| . :: : :: :@ :@: :@@::@:: :::: @: : @@: :@::#\n| . : :: : :: :@ :@: :@@::@:: :::: @: : @@: :@::#\n| . ,.: : : :: : :: :@ :@: :@@::@:: :::: @: : @@: :@::# :\n| .: @:: : : :: : :: :@ :@: :@@::@:: :::: @: : @@: :@::# :\n| ::: @:: : : :: : :: :@ :@: :@@::@:: :::: @: : @@: :@::# :\n| :::: @:: : : :: : :: :@ :@: :@@::@:: :::: @: : @@: :@::# :\n| . ::::: @:: : : :: : :: :@ :@: :@@::@:: :::: @: : @@: :@::# :.\n| .: ::::: @:: : : :: : :: :@ :@: :@@::@:: :::: @: : @@: :@::# ::\n| ::: ::::: @:: : : :: : :: :@ :@: :@@::@:: :::: @: : @@: :@::# ::\n| : ::: ::::: @:: : : :: : :: :@ :@: :@@::@:: :::: @: : @@: :@::# ::\n| .:: ::: ::::: @:: : : :: : :: :@ :@: :@@::@:: :::: @: : @@: :@::# ::\n| . :::: ::: ::::: @:: : : :: : :: :@ :@: :@@::@:: :::: @: : @@: :@::# ::\n0----------------------------------------------------------------------->Gi\n 32.83\n-- snap --\n\nWhoa. As you can see, your puny little 3.3 megabyte pack is blown to a \nfull 555 megabyte in RAM.\n\nThat is bad.\n\nOkay, so what is the reason?\n\nYou have a pretty large file there, \"wortliste\", weighing in with 13 \nmegabyte. This file is part of at least one of those 50-strong delta \nchains.\n\nTo reconstruct the blobs, we have to store all intermediate versions in \nRAM (since index-pack is called with \"--stdin\" from receive-pack, which is \ncalled by clone). Now, the file was big from the beginning, so you end up \nwith ~13*50 megabyte (actually, even 100 megabyte less) while indexing \none single delta chain.\n\nMy tests were performed on a puny little laptop (512MB RAM, to be precise, \nas I am a strong believer that developers with too powerful machines just \nlose touch to reality and write programs that are only useful to \nthemselves, but useless for everyone else), where this hurt big time.\n\nNow, I do not know the internals of index-pack enough to know if there is \na way to cut the memory usage (by throwing out earlier reconstructed \nblobs, for example, and reconstructing them _again_ if need be), so I \nCc:ed Nico and hand the problem off to him.\n\nI expect this to touch the resolve_delta() function of index-pack.c in a \nmajor way, though.\n\nCiao,\nDscho\n\nP.S.: It seems that \"git verify-pack -v\" only shows the sizes of the \ndeltas. Might be interesting to some to show the unpacked _full_ size, \ntoo.\n"},{"id":"83117","messageId":"20080713011512.GB31050@spearce.org","threadId":"14394","inReplyTo":"alpine.DEB.1.00.0807121546590.8950@racer","subject":"Re: git pull is slow","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-13T01:15:12Z","receivedAt":"2008-07-13T01:15:12Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Johannes Schindelin wrote:\n> On Sat, 12 Jul 2008, Stephan Hennig wrote:\n> > \n> > Thanks for having a look at this! What does \"problem with the pack\" \n> > mean? Do you think it is a Git problem (client or server side?) or just \n> > a misconfiguration?\n> \n> I thought that the blobs in the pack are just too similar. That makes for \n> a good compression, since you get many relatively small deltas. But it \n> also makes for a lot of work to reconstruct the blobs.\n> \n> I suspected that you run out of space for the cache holding some \n> reconstructed blobs (to prevent reconstructing all of them from scratch).\n...\n> Whoa. As you can see, your puny little 3.3 megabyte pack is blown to a \n> full 555 megabyte in RAM.\n...\n> I expect this to touch the resolve_delta() function of index-pack.c in a \n> major way, though.\n\nYea, that's going to be ugly. The \"cache\" you speak of above is held\non the call stack as resolv_delta() recurses through the delta chain\nto reconstruct objects and generate their SHA-1s. There isn't a way to\nrelease these objects when memory gets low so your worst case scenario\nis a 100M+ blob with a delta chain of 50 or more - that will take you\n5G of memory to pass through index-pack.\n\njgit isn't any better here.\n\nWhat we need to do is maintain a list of the objects we are holding\non the call stack, and reduce ones up near the top when memory\ngets low. Then upon recursing back up we can just recreate the\nobject if we had to throw it out. The higher up on the stack the\nobject is, the less likely we are to need it in the near future.\n\nThe more that I think about this, the easier it sounds to implement.\nI may try to look at it a little later this evening.\n \n> P.S.: It seems that \"git verify-pack -v\" only shows the sizes of the \n> deltas. Might be interesting to some to show the unpacked _full_ size, \n> too.\n\nIt wouldn't be very difficult to get that unpacked size. We just have\nto deflate enough of the delta to see the delta header and obtain the\ninflated object size from that. Unfortunately there is not an API in\nsha1_file.c to offer that information to callers.\n\n-- \nShawn.\n"},{"id":"83132","messageId":"4879C469.4080101@arcor.de","threadId":"14394","inReplyTo":"alpine.DEB.1.00.0807121546590.8950@racer","subject":"Re: git pull is slow","fromName":"Stephan Hennig","fromEmail":"mailing_list@arcor.de","sentAt":"2008-07-13T09:01:29Z","receivedAt":"2008-07-13T09:01:29Z","isPatch":false,"sender":{"key":"mailing_list@arcor.de","avatar":null},"body":"Johannes Schindelin schrieb:\n\n> I suspected that you run out of space for the cache holding some \n> reconstructed blobs (to prevent reconstructing all of them from scratch).\n> \n> [...]\n> \n> Okay, \"valgrind --tool=massif\" to the rescue:\n> \n> -- snip --\n> MB\n> 555.9^ , #\n> | @..#\n> ~\n> | . :::: ::: ::::: @:: : : :: : :: :@ :@: :@@::@:: :::: @: : @@: :@::# ::\n> 0----------------------------------------------------------------------->Gi\n> 32.83\n> -- snap --\n> \n> [...]\n> \n> Now, I do not know the internals of index-pack enough to know if there is \n> a way to cut the memory usage (by throwing out earlier reconstructed \n> blobs, for example, and reconstructing them _again_ if need be), so I \n> Cc:ed Nico and hand the problem off to him.\n> \n> I expect this to touch the resolve_delta() function of index-pack.c in a \n> major way, though.\n\nThank you for the analysis! As a workaround, I think about splitting\nthe file. Can you suggest a proper file size?\n\nBest regards,\nStephan Hennig\n"},{"id":"83152","messageId":"alpine.DEB.1.00.0807131555560.4816@eeepc-johanness","threadId":"14394","inReplyTo":"20080713011512.GB31050@spearce.org","subject":"Re: git pull is slow","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-13T13:59:00Z","receivedAt":"2008-07-13T13:59:00Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 13 Jul 2008, Shawn O. Pearce wrote:\n\n> Johannes Schindelin wrote:\n> > On Sat, 12 Jul 2008, Stephan Hennig wrote:\n> > > \n> > > Thanks for having a look at this! What does \"problem with the pack\" \n> > > mean? Do you think it is a Git problem (client or server side?) or just \n> > > a misconfiguration?\n> > \n> > I thought that the blobs in the pack are just too similar. That makes for \n> > a good compression, since you get many relatively small deltas. But it \n> > also makes for a lot of work to reconstruct the blobs.\n> > \n> > I suspected that you run out of space for the cache holding some \n> > reconstructed blobs (to prevent reconstructing all of them from scratch).\n> ...\n> > Whoa. As you can see, your puny little 3.3 megabyte pack is blown to a \n> > full 555 megabyte in RAM.\n> ...\n> > I expect this to touch the resolve_delta() function of index-pack.c in a \n> > major way, though.\n> \n> Yea, that's going to be ugly. The \"cache\" you speak of above is held on \n> the call stack as resolv_delta() recurses through the delta chain to \n> reconstruct objects and generate their SHA-1s. There isn't a way to \n> release these objects when memory gets low so your worst case scenario \n> is a 100M+ blob with a delta chain of 50 or more - that will take you 5G \n> of memory to pass through index-pack.\n\nActually, there is...\n\nYou would only need to tap into the \"release_pack_memory()\" mechanism, \nadding a sort of a \"smart pointer\" that knows how to reconstruct its \ncontents.\n\nCiao,\nDscho\n"},{"id":"83189","messageId":"20080713221141.GC12708@spearce.org","threadId":"14394","inReplyTo":"alpine.DEB.1.00.0807131555560.4816@eeepc-johanness","subject":"Re: git pull is slow","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-13T22:11:41Z","receivedAt":"2008-07-13T22:11:41Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Johannes Schindelin wrote:\n> On Sun, 13 Jul 2008, Shawn O. Pearce wrote:\n> > Johannes Schindelin wrote:\n> > ...\n> > > I expect this to touch the resolve_delta() function of index-pack.c in a \n> > > major way, though.\n> > \n> > Yea, that's going to be ugly. The \"cache\" you speak of above is held on \n> > the call stack as resolv_delta() recurses through the delta chain to \n> > reconstruct objects and generate their SHA-1s. There isn't a way to \n> > release these objects when memory gets low so your worst case scenario \n> > is a 100M+ blob with a delta chain of 50 or more - that will take you 5G \n> > of memory to pass through index-pack.\n> \n> Actually, there is...\n> \n> You would only need to tap into the \"release_pack_memory()\" mechanism, \n> adding a sort of a \"smart pointer\" that knows how to reconstruct its \n> contents.\n\nI guess you don't really know how index-pack is organized than.\nIt is not quite that simple.\n\nI think we want to use the core.deltabasecachelimit parameter inside\nof index-pack to limit the size of the cache, but evict based on\nthe callstack depth. Objects deeper back in the callstack should\nevict before objects closer to the top of the stack.\n\nReconstruction is a bit complex as we don't have the machinary in\nsha1_file.c available to us, as the index is not available, as we\nare still in the process of creating the damn thing.\n\nI'm working up a patch series to resolve this. I'm going to shutup\nnow and just try to post working code sometime this evening.\n\n-- \nShawn.\n"},{"id":"299052","messageId":"1216001267-33235-1-git-send-email-spearce@spearce.org","threadId":"14394","inReplyTo":"20080713011512.GB31050@spearce.org","subject":"[PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-14T02:07:43Z","receivedAt":"2008-07-14T02:07:43Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"This should resolve the obscene memory usage of index-pack when\nresolving deltas for very large files.\n\nShawn O. Pearce (4):\n index-pack: Refactor base arguments of resolve_delta into a struct\n index-pack: Chain the struct base_data on the stack for traversal\n index-pack: Track the object_entry that creates each base_data\n index-pack: Honor core.deltaBaseCacheLimit when resolving deltas\n\n index-pack.c | 137 +++++++++++++++++++++++++++++++++++++++++++++------------\n 1 files changed, 108 insertions(+), 29 deletions(-)\n\n"},{"id":"299053","messageId":"1216001267-33235-2-git-send-email-spearce@spearce.org","threadId":"14394","inReplyTo":"1216001267-33235-1-git-send-email-spearce@spearce.org","subject":"[PATCH 1/4] index-pack: Refactor base arguments of resolve_delta into a struct","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-14T02:07:44Z","receivedAt":"2008-07-14T02:07:44Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"We need to discard base objects which are not recently used if our\nmemory gets low, such as when we are unpacking a long delta chain\nof a very large object.\n\nTo support tracking the available base objects we combine the\npointer and size into a struct. Future changes would allow the\ndata pointer to be free'd and marked NULL if memory gets low.\n\nSigned-off-by: Shawn O. Pearce \n---\n index-pack.c | 60 +++++++++++++++++++++++++++++++--------------------------\n 1 files changed, 33 insertions(+), 27 deletions(-)\n\ndiff --git a/index-pack.c b/index-pack.c\nindex 25db5db..db03478 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -26,6 +26,11 @@ union delta_base {\n \toff_t offset;\n };\n \n+struct base_data {\n+\tvoid *data;\n+\tunsigned long size;\n+};\n+\n /*\n * Even if sizeof(union delta_base) == 24 on 64-bit archs, we really want\n * to memcmp() only the first 20 bytes.\n@@ -426,25 +431,25 @@ static void sha1_object(const void *data, unsigned long size,\n \t}\n }\n \n-static void resolve_delta(struct object_entry *delta_obj, void *base_data,\n-\t\t\t unsigned long base_size, enum object_type type)\n+static void resolve_delta(struct object_entry *delta_obj,\n+\t\t\t struct base_data *base_obj, enum object_type type)\n {\n \tvoid *delta_data;\n \tunsigned long delta_size;\n-\tvoid *result;\n-\tunsigned long result_size;\n \tunion delta_base delta_base;\n \tint j, first, last;\n+\tstruct base_data result;\n \n \tdelta_obj->real_type = type;\n \tdelta_data = get_data_from_pack(delta_obj);\n \tdelta_size = delta_obj->size;\n-\tresult = patch_delta(base_data, base_size, delta_data, delta_size,\n-\t\t\t &result_size);\n+\tresult.data = patch_delta(base_obj->data, base_obj->size,\n+\t\t\t delta_data, delta_size,\n+\t\t\t &result.size);\n \tfree(delta_data);\n-\tif (!result)\n+\tif (!result.data)\n \t\tbad_object(delta_obj->idx.offset, \"failed to apply delta\");\n-\tsha1_object(result, result_size, type, delta_obj->idx.sha1);\n+\tsha1_object(result.data, result.size, type, delta_obj->idx.sha1);\n \tnr_resolved_deltas++;\n \n \thashcpy(delta_base.sha1, delta_obj->idx.sha1);\n@@ -452,7 +457,7 @@ static void resolve_delta(struct object_entry *delta_obj, void *base_data,\n \t\tfor (j = first; j <= last; j++) {\n \t\t\tstruct object_entry *child = objects + deltas[j].obj_no;\n \t\t\tif (child->real_type == OBJ_REF_DELTA)\n-\t\t\t\tresolve_delta(child, result, result_size, type);\n+\t\t\t\tresolve_delta(child, &result, type);\n \t\t}\n \t}\n \n@@ -462,11 +467,11 @@ static void resolve_delta(struct object_entry *delta_obj, void *base_data,\n \t\tfor (j = first; j <= last; j++) {\n \t\t\tstruct object_entry *child = objects + deltas[j].obj_no;\n \t\t\tif (child->real_type == OBJ_OFS_DELTA)\n-\t\t\t\tresolve_delta(child, result, result_size, type);\n+\t\t\t\tresolve_delta(child, &result, type);\n \t\t}\n \t}\n \n-\tfree(result);\n+\tfree(result.data);\n }\n \n static int compare_delta_entry(const void *a, const void *b)\n@@ -481,7 +486,6 @@ static void parse_pack_objects(unsigned char *sha1)\n {\n \tint i;\n \tstruct delta_entry *delta = deltas;\n-\tvoid *data;\n \tstruct stat st;\n \n \t/*\n@@ -496,7 +500,7 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\t\t\tnr_objects);\n \tfor (i = 0; i < nr_objects; i++) {\n \t\tstruct object_entry *obj = &objects[i];\n-\t\tdata = unpack_raw_entry(obj, &delta->base);\n+\t\tvoid *data = unpack_raw_entry(obj, &delta->base);\n \t\tobj->real_type = obj->type;\n \t\tif (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA) {\n \t\t\tnr_deltas++;\n@@ -545,6 +549,7 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\tstruct object_entry *obj = &objects[i];\n \t\tunion delta_base base;\n \t\tint j, ref, ref_first, ref_last, ofs, ofs_first, ofs_last;\n+\t\tstruct base_data base_obj;\n \n \t\tif (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA)\n \t\t\tcontinue;\n@@ -555,22 +560,22 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\tofs = !find_delta_children(&base, &ofs_first, &ofs_last);\n \t\tif (!ref && !ofs)\n \t\t\tcontinue;\n-\t\tdata = get_data_from_pack(obj);\n+\t\tbase_obj.data = get_data_from_pack(obj);\n+\t\tbase_obj.size = obj->size;\n+\n \t\tif (ref)\n \t\t\tfor (j = ref_first; j <= ref_last; j++) {\n \t\t\t\tstruct object_entry *child = objects + deltas[j].obj_no;\n \t\t\t\tif (child->real_type == OBJ_REF_DELTA)\n-\t\t\t\t\tresolve_delta(child, data,\n-\t\t\t\t\t\t obj->size, obj->type);\n+\t\t\t\t\tresolve_delta(child, &base_obj, obj->type);\n \t\t\t}\n \t\tif (ofs)\n \t\t\tfor (j = ofs_first; j <= ofs_last; j++) {\n \t\t\t\tstruct object_entry *child = objects + deltas[j].obj_no;\n \t\t\t\tif (child->real_type == OBJ_OFS_DELTA)\n-\t\t\t\t\tresolve_delta(child, data,\n-\t\t\t\t\t\t obj->size, obj->type);\n+\t\t\t\t\tresolve_delta(child, &base_obj, obj->type);\n \t\t\t}\n-\t\tfree(data);\n+\t\tfree(base_obj.data);\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n \t}\n }\n@@ -656,28 +661,29 @@ static void fix_unresolved_deltas(int nr_unresolved)\n \n \tfor (i = 0; i < n; i++) {\n \t\tstruct delta_entry *d = sorted_by_pos[i];\n-\t\tvoid *data;\n-\t\tunsigned long size;\n \t\tenum object_type type;\n \t\tint j, first, last;\n+\t\tstruct base_data base_obj;\n \n \t\tif (objects[d->obj_no].real_type != OBJ_REF_DELTA)\n \t\t\tcontinue;\n-\t\tdata = read_sha1_file(d->base.sha1, &type, &size);\n-\t\tif (!data)\n+\t\tbase_obj.data = read_sha1_file(d->base.sha1, &type, &base_obj.size);\n+\t\tif (!base_obj.data)\n \t\t\tcontinue;\n \n \t\tfind_delta_children(&d->base, &first, &last);\n \t\tfor (j = first; j <= last; j++) {\n \t\t\tstruct object_entry *child = objects + deltas[j].obj_no;\n \t\t\tif (child->real_type == OBJ_REF_DELTA)\n-\t\t\t\tresolve_delta(child, data, size, type);\n+\t\t\t\tresolve_delta(child, &base_obj, type);\n \t\t}\n \n-\t\tif (check_sha1_signature(d->base.sha1, data, size, typename(type)))\n+\t\tif (check_sha1_signature(d->base.sha1, base_obj.data,\n+\t\t\t\tbase_obj.size, typename(type)))\n \t\t\tdie(\"local object %s is corrupt\", sha1_to_hex(d->base.sha1));\n-\t\tappend_obj_to_pack(d->base.sha1, data, size, type);\n-\t\tfree(data);\n+\t\tappend_obj_to_pack(d->base.sha1, base_obj.data,\n+\t\t\tbase_obj.size, type);\n+\t\tfree(base_obj.data);\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n \t}\n \tfree(sorted_by_pos);\n-- \n1.5.6.2.393.g45096\n\n"},{"id":"299054","messageId":"1216001267-33235-3-git-send-email-spearce@spearce.org","threadId":"14394","inReplyTo":"1216001267-33235-2-git-send-email-spearce@spearce.org","subject":"[PATCH 2/4] index-pack: Chain the struct base_data on the stack for traversal","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-14T02:07:45Z","receivedAt":"2008-07-14T02:07:45Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"We need to release earlier inflated base objects when memory gets\nlow, which means we need to be able to walk up or down the stack\nto locate the objects we want to release, and free their data.\n\nThe new link/unlink routines allow inserting and removing the struct\nbase_data during recursion inside resolve_delta, and the global\nbase_cache gives us the head of the chain (bottom of the stack)\nso we can traverse it.\n\nSigned-off-by: Shawn O. Pearce \n---\n index-pack.c | 34 +++++++++++++++++++++++++++++++---\n 1 files changed, 31 insertions(+), 3 deletions(-)\n\ndiff --git a/index-pack.c b/index-pack.c\nindex db03478..6c59fd3 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -27,6 +27,8 @@ union delta_base {\n };\n \n struct base_data {\n+\tstruct base_data *base;\n+\tstruct base_data *child;\n \tvoid *data;\n \tunsigned long size;\n };\n@@ -48,6 +50,7 @@ struct delta_entry\n \n static struct object_entry *objects;\n static struct delta_entry *deltas;\n+static struct base_data *base_cache;\n static int nr_objects;\n static int nr_deltas;\n static int nr_resolved_deltas;\n@@ -216,6 +219,27 @@ static void bad_object(unsigned long offset, const char *format, ...)\n \tdie(\"pack has bad object at offset %lu: %s\", offset, buf);\n }\n \n+static void link_base_data(struct base_data *base, struct base_data *c)\n+{\n+\tif (base)\n+\t\tbase->child = c;\n+\telse\n+\t\tbase_cache = c;\n+\n+\tc->base = base;\n+\tc->child = NULL;\n+}\n+\n+static void unlink_base_data(struct base_data *c)\n+{\n+\tstruct base_data *base = c->base;\n+\tif (base)\n+\t\tbase->child = NULL;\n+\telse\n+\t\tbase_cache = NULL;\n+\tfree(c->data);\n+}\n+\n static void *unpack_entry_data(unsigned long offset, unsigned long size)\n {\n \tz_stream stream;\n@@ -452,6 +476,8 @@ static void resolve_delta(struct object_entry *delta_obj,\n \tsha1_object(result.data, result.size, type, delta_obj->idx.sha1);\n \tnr_resolved_deltas++;\n \n+\tlink_base_data(base_obj, &result);\n+\n \thashcpy(delta_base.sha1, delta_obj->idx.sha1);\n \tif (!find_delta_children(&delta_base, &first, &last)) {\n \t\tfor (j = first; j <= last; j++) {\n@@ -471,7 +497,7 @@ static void resolve_delta(struct object_entry *delta_obj,\n \t\t}\n \t}\n \n-\tfree(result.data);\n+\tunlink_base_data(&result);\n }\n \n static int compare_delta_entry(const void *a, const void *b)\n@@ -562,6 +588,7 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\t\tcontinue;\n \t\tbase_obj.data = get_data_from_pack(obj);\n \t\tbase_obj.size = obj->size;\n+\t\tlink_base_data(NULL, &base_obj);\n \n \t\tif (ref)\n \t\t\tfor (j = ref_first; j <= ref_last; j++) {\n@@ -575,7 +602,7 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\t\t\tif (child->real_type == OBJ_OFS_DELTA)\n \t\t\t\t\tresolve_delta(child, &base_obj, obj->type);\n \t\t\t}\n-\t\tfree(base_obj.data);\n+\t\tunlink_base_data(&base_obj);\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n \t}\n }\n@@ -670,6 +697,7 @@ static void fix_unresolved_deltas(int nr_unresolved)\n \t\tbase_obj.data = read_sha1_file(d->base.sha1, &type, &base_obj.size);\n \t\tif (!base_obj.data)\n \t\t\tcontinue;\n+\t\tlink_base_data(NULL, &base_obj);\n \n \t\tfind_delta_children(&d->base, &first, &last);\n \t\tfor (j = first; j <= last; j++) {\n@@ -683,7 +711,7 @@ static void fix_unresolved_deltas(int nr_unresolved)\n \t\t\tdie(\"local object %s is corrupt\", sha1_to_hex(d->base.sha1));\n \t\tappend_obj_to_pack(d->base.sha1, base_obj.data,\n \t\t\tbase_obj.size, type);\n-\t\tfree(base_obj.data);\n+\t\tunlink_base_data(&base_obj);\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n \t}\n \tfree(sorted_by_pos);\n-- \n1.5.6.2.393.g45096\n\n"},{"id":"299055","messageId":"1216001267-33235-4-git-send-email-spearce@spearce.org","threadId":"14394","inReplyTo":"1216001267-33235-3-git-send-email-spearce@spearce.org","subject":"[PATCH 3/4] index-pack: Track the object_entry that creates each base_data","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-14T02:07:46Z","receivedAt":"2008-07-14T02:07:46Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"If we free the data stored within a base_data we need the struct\nobject_entry to get the data back again for use with another\ndependent delta. Storing the object_entry* makes it simple to call\nget_data_from_pack() to recover the compressed information.\n\nThis however means we must add the missing baes object to the end\nof our packfile prior to calling resolve_delta() on each of the\ndependent deltas. Adding the base first ensures we can read the\nbase back from the pack we indexing, as if it had been included by\nthe remote side.\n\nSigned-off-by: Shawn O. Pearce \n---\n index-pack.c | 18 ++++++++++++------\n 1 files changed, 12 insertions(+), 6 deletions(-)\n\ndiff --git a/index-pack.c b/index-pack.c\nindex 6c59fd3..7239e89 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -29,6 +29,7 @@ union delta_base {\n struct base_data {\n \tstruct base_data *base;\n \tstruct base_data *child;\n+\tstruct object_entry *obj;\n \tvoid *data;\n \tunsigned long size;\n };\n@@ -476,6 +477,7 @@ static void resolve_delta(struct object_entry *delta_obj,\n \tsha1_object(result.data, result.size, type, delta_obj->idx.sha1);\n \tnr_resolved_deltas++;\n \n+\tresult.obj = delta_obj;\n \tlink_base_data(base_obj, &result);\n \n \thashcpy(delta_base.sha1, delta_obj->idx.sha1);\n@@ -588,6 +590,7 @@ static void parse_pack_objects(unsigned char *sha1)\n \t\t\tcontinue;\n \t\tbase_obj.data = get_data_from_pack(obj);\n \t\tbase_obj.size = obj->size;\n+\t\tbase_obj.obj = obj;\n \t\tlink_base_data(NULL, &base_obj);\n \n \t\tif (ref)\n@@ -633,7 +636,8 @@ static int write_compressed(int fd, void *in, unsigned int size, uint32_t *obj_c\n \treturn size;\n }\n \n-static void append_obj_to_pack(const unsigned char *sha1, void *buf,\n+static struct object_entry *append_obj_to_pack(\n+\t\t\t const unsigned char *sha1, void *buf,\n \t\t\t unsigned long size, enum object_type type)\n {\n \tstruct object_entry *obj = &objects[nr_objects++];\n@@ -654,6 +658,7 @@ static void append_obj_to_pack(const unsigned char *sha1, void *buf,\n \tobj[1].idx.offset = obj[0].idx.offset + n;\n \tobj[1].idx.offset += write_compressed(output_fd, buf, size, &obj[0].idx.crc32);\n \thashcpy(obj->idx.sha1, sha1);\n+\treturn obj;\n }\n \n static int delta_pos_compare(const void *_a, const void *_b)\n@@ -697,6 +702,12 @@ static void fix_unresolved_deltas(int nr_unresolved)\n \t\tbase_obj.data = read_sha1_file(d->base.sha1, &type, &base_obj.size);\n \t\tif (!base_obj.data)\n \t\t\tcontinue;\n+\n+\t\tif (check_sha1_signature(d->base.sha1, base_obj.data,\n+\t\t\t\tbase_obj.size, typename(type)))\n+\t\t\tdie(\"local object %s is corrupt\", sha1_to_hex(d->base.sha1));\n+\t\tbase_obj.obj = append_obj_to_pack(d->base.sha1, base_obj.data,\n+\t\t\tbase_obj.size, type);\n \t\tlink_base_data(NULL, &base_obj);\n \n \t\tfind_delta_children(&d->base, &first, &last);\n@@ -706,11 +717,6 @@ static void fix_unresolved_deltas(int nr_unresolved)\n \t\t\t\tresolve_delta(child, &base_obj, type);\n \t\t}\n \n-\t\tif (check_sha1_signature(d->base.sha1, base_obj.data,\n-\t\t\t\tbase_obj.size, typename(type)))\n-\t\t\tdie(\"local object %s is corrupt\", sha1_to_hex(d->base.sha1));\n-\t\tappend_obj_to_pack(d->base.sha1, base_obj.data,\n-\t\t\tbase_obj.size, type);\n \t\tunlink_base_data(&base_obj);\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n \t}\n-- \n1.5.6.2.393.g45096\n\n"},{"id":"299056","messageId":"1216001267-33235-5-git-send-email-spearce@spearce.org","threadId":"14394","inReplyTo":"1216001267-33235-4-git-send-email-spearce@spearce.org","subject":"[PATCH 4/4] index-pack: Honor core.deltaBaseCacheLimit when resolving deltas","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-14T02:07:47Z","receivedAt":"2008-07-14T02:07:47Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"If we are trying to resolve deltas for a long delta chain composed\nof multi-megabyte objects we can easily run into requiring 500M+\nof memory to hold each object in the chain on the call stack while\nwe recurse into the dependent objects and resolve them.\n\nWe now use a simple delta cache that discards objects near the\nbottom of the call stack first, as they are the most least recently\nused objects in this current delta chain. If we recurse out of a\nchain we may find the base object is no longer available, as it was\nfree'd to keep memory under the deltaBaseCacheLimit. In such cases\nwe must unpack the base object again, which will require recursing\nback to the root of the top of the delta chain as we released that\nroot first.\n\nSigned-off-by: Shawn O. Pearce \n---\n index-pack.c | 43 +++++++++++++++++++++++++++++++++++++++++--\n 1 files changed, 41 insertions(+), 2 deletions(-)\n\ndiff --git a/index-pack.c b/index-pack.c\nindex 7239e89..84c9fc1 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -52,6 +52,7 @@ struct delta_entry\n static struct object_entry *objects;\n static struct delta_entry *deltas;\n static struct base_data *base_cache;\n+static size_t base_cache_used;\n static int nr_objects;\n static int nr_deltas;\n static int nr_resolved_deltas;\n@@ -220,6 +221,20 @@ static void bad_object(unsigned long offset, const char *format, ...)\n \tdie(\"pack has bad object at offset %lu: %s\", offset, buf);\n }\n \n+static void prune_base_data(void)\n+{\n+\tstruct base_data *b = base_cache;\n+\tfor (b = base_cache;\n+\t base_cache_used > delta_base_cache_limit && b && b->child;\n+\t b = b->child) {\n+\t\tif (b->data) {\n+\t\t\tfree(b->data);\n+\t\t\tb->data = NULL;\n+\t\t\tbase_cache_used -= b->size;\n+\t\t}\n+\t}\n+}\n+\n static void link_base_data(struct base_data *base, struct base_data *c)\n {\n \tif (base)\n@@ -229,6 +244,8 @@ static void link_base_data(struct base_data *base, struct base_data *c)\n \n \tc->base = base;\n \tc->child = NULL;\n+\tbase_cache_used += c->size;\n+\tprune_base_data();\n }\n \n static void unlink_base_data(struct base_data *c)\n@@ -238,7 +255,10 @@ static void unlink_base_data(struct base_data *c)\n \t\tbase->child = NULL;\n \telse\n \t\tbase_cache = NULL;\n-\tfree(c->data);\n+\tif (c->data) {\n+\t\tfree(c->data);\n+\t\tbase_cache_used -= c->size;\n+\t}\n }\n \n static void *unpack_entry_data(unsigned long offset, unsigned long size)\n@@ -456,6 +476,25 @@ static void sha1_object(const void *data, unsigned long size,\n \t}\n }\n \n+static void *get_base_data(struct base_data *c)\n+{\n+\tif (!c->data) {\n+\t\tstruct object_entry *obj = c->obj;\n+\t\tvoid *raw = get_data_from_pack(obj);\n+\t\tif (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA) {\n+\t\t\tc->data = patch_delta(\n+\t\t\t\tget_base_data(c->base), c->base->size,\n+\t\t\t\traw, obj->size,\n+\t\t\t\t&c->size);\n+\t\t\tfree(raw);\n+\t\t\tif (!c->data)\n+\t\t\t\tbad_object(obj->idx.offset, \"failed to apply delta\");\n+\t\t} else\n+\t\t\tc->data = raw;\n+\t}\n+\treturn c->data;\n+}\n+\n static void resolve_delta(struct object_entry *delta_obj,\n \t\t\t struct base_data *base_obj, enum object_type type)\n {\n@@ -468,7 +507,7 @@ static void resolve_delta(struct object_entry *delta_obj,\n \tdelta_obj->real_type = type;\n \tdelta_data = get_data_from_pack(delta_obj);\n \tdelta_size = delta_obj->size;\n-\tresult.data = patch_delta(base_obj->data, base_obj->size,\n+\tresult.data = patch_delta(get_base_data(base_obj), base_obj->size,\n \t\t\t delta_data, delta_size,\n \t\t\t &result.size);\n \tfree(delta_data);\n-- \n1.5.6.2.393.g45096\n\n"},{"id":"83205","messageId":"alpine.LFD.1.10.0807132220570.12484@xanadu.home","threadId":"14394","inReplyTo":"1216001267-33235-1-git-send-email-spearce@spearce.org","subject":"Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-07-14T02:27:18Z","receivedAt":"2008-07-14T02:27:18Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 13 Jul 2008, Shawn O. Pearce wrote:\n\n> This should resolve the obscene memory usage of index-pack when\n> resolving deltas for very large files.\n> \n> Shawn O. Pearce (4):\n> index-pack: Refactor base arguments of resolve_delta into a struct\n> index-pack: Chain the struct base_data on the stack for traversal\n> index-pack: Track the object_entry that creates each base_data\n> index-pack: Honor core.deltaBaseCacheLimit when resolving deltas\n\nWell... \n\nI don't like this. Not your patch, but rather the direction this whole \nthing took in the first place, and now we have to bolt extra complexity \non top.\n\nI have the feeling this is not the best approach, especially since many \nlong delta chains are going deep and all those intermediate objects are \nsimply useless once the _only_ delta child has been resolved and \ntherefore could be freed right away instead.\n\nBut I have to sleep on it first.\n\n\nNicolas\n"},{"id":"83208","messageId":"20080714031242.GA14542@spearce.org","threadId":"14394","inReplyTo":"alpine.LFD.1.10.0807132220570.12484@xanadu.home","subject":"Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-14T03:12:42Z","receivedAt":"2008-07-14T03:12:42Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> On Sun, 13 Jul 2008, Shawn O. Pearce wrote:\n> \n> > This should resolve the obscene memory usage of index-pack when\n> > resolving deltas for very large files.\n> \n> I don't like this. Not your patch, but rather the direction this whole \n> thing took in the first place, and now we have to bolt extra complexity \n> on top.\n> \n> I have the feeling this is not the best approach, especially since many \n> long delta chains are going deep and all those intermediate objects are \n> simply useless once the _only_ delta child has been resolved and \n> therefore could be freed right away instead.\n\nI thought about trying to free a base object if this is the last\nresolve_delta() call which would require that data, but I realized\nthis is just a \"tail-call optimization\" and doesn't work in the\nmore general case. This patch series is the best solution I could\ncome up with to handle even the general case.\n\nThe only other alternative I can come up with is to change\npack-objects (or at least its defaults) so we don't generate these\nmassive delta chains. But there are already packs in the wild that\nuse these chains, resulting in performance problems for clients.\n\n-- \nShawn.\n"},{"id":"83246","messageId":"alpine.LSU.1.00.0807141214260.32392@wbgn129.biozentrum.uni-wuerzburg.de","threadId":"14394","inReplyTo":"1216001267-33235-4-git-send-email-spearce@spearce.org","subject":"Re: [PATCH 3/4] index-pack: Track the object_entry that creates each base_data","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-14T10:15:06Z","receivedAt":"2008-07-14T10:15:06Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 13 Jul 2008, Shawn O. Pearce wrote:\n\n> This however means we must add the missing baes object to the end\n> of our packfile prior to calling resolve_delta() on each of the\n> dependent deltas. Adding the base first ensures we can read the\n> base back from the pack we indexing, as if it had been included by\n> the remote side.\n\ns/baes/base/\n\nOtherwise very clear.\n\nThanks,\nDscho\n"},{"id":"83249","messageId":"alpine.LSU.1.00.0807141216390.32392@wbgn129.biozentrum.uni-wuerzburg.de","threadId":"14394","inReplyTo":"20080714031242.GA14542@spearce.org","subject":"Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-14T11:44:50Z","receivedAt":"2008-07-14T11:44:50Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 14 Jul 2008, Shawn O. Pearce wrote:\n\n> Nicolas Pitre wrote:\n> > On Sun, 13 Jul 2008, Shawn O. Pearce wrote:\n> > \n> > > This should resolve the obscene memory usage of index-pack when\n> > > resolving deltas for very large files.\n> > \n> > I don't like this. Not your patch, but rather the direction this whole \n> > thing took in the first place, and now we have to bolt extra complexity \n> > on top.\n> > \n> > I have the feeling this is not the best approach, especially since many \n> > long delta chains are going deep and all those intermediate objects are \n> > simply useless once the _only_ delta child has been resolved and \n> > therefore could be freed right away instead.\n> \n> I thought about trying to free a base object if this is the last \n> resolve_delta() call which would require that data, but I realized this \n> is just a \"tail-call optimization\" and doesn't work in the more general \n> case.\n\nHowever, for cases like Stephan's I assume this is the rule. If you \nthink of it, most use cases for such a big blob are one-user, \nappend-only.\n\n> The only other alternative I can come up with is to change pack-objects \n> (or at least its defaults) so we don't generate these massive delta \n> chains. But there are already packs in the wild that use these chains, \n> resulting in performance problems for clients.\n\nBut the long chains make the pack actually as efficient as it is...\n\nCiao,\nDscho\n"},{"id":"83251","messageId":"m31w1wu1hc.fsf@localhost.localdomain","threadId":"14394","inReplyTo":"alpine.LSU.1.00.0807141216390.32392@wbgn129.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2008-07-14T11:54:38Z","receivedAt":"2008-07-14T11:54:38Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Johannes Schindelin writes:\n> On Mon, 14 Jul 2008, Shawn O. Pearce wrote:\n\n> > The only other alternative I can come up with is to change pack-objects \n> > (or at least its defaults) so we don't generate these massive delta \n> > chains. But there are already packs in the wild that use these chains, \n> > resulting in performance problems for clients.\n> \n> But the long chains make the pack actually as efficient as it is...\n\nPerhaps Shawn thought here about limiting delta chain not by its\n*length*, but by its *size* (as required when unpacking last object\nin a delta chanin).\n\nWhat do you think about this idea?\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"83255","messageId":"alpine.DEB.1.00.0807141309340.8950@racer","threadId":"14394","inReplyTo":"m31w1wu1hc.fsf@localhost.localdomain","subject":"Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-14T12:10:47Z","receivedAt":"2008-07-14T12:10:47Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 14 Jul 2008, Jakub Narebski wrote:\n\n> Johannes Schindelin writes:\n> > On Mon, 14 Jul 2008, Shawn O. Pearce wrote:\n> \n> > > The only other alternative I can come up with is to change pack-objects \n> > > (or at least its defaults) so we don't generate these massive delta \n> > > chains. But there are already packs in the wild that use these chains, \n> > > resulting in performance problems for clients.\n> > \n> > But the long chains make the pack actually as efficient as it is...\n> \n> Perhaps Shawn thought here about limiting delta chain not by its\n> *length*, but by its *size* (as required when unpacking last object\n> in a delta chanin).\n\nSo you mean once the sizes of the reconstructed objects are too big, i.e. \nwhen the delta chain is actually _most useful_, we should not do it? \nDon't think so.\n\nCiao,\nDscho\n"},{"id":"83257","messageId":"487B439F.8040902@op5.se","threadId":"14394","inReplyTo":"m31w1wu1hc.fsf@localhost.localdomain","subject":"Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2008-07-14T12:16:31Z","receivedAt":"2008-07-14T12:16:31Z","isPatch":true,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Jakub Narebski wrote:\n> Johannes Schindelin writes:\n>> On Mon, 14 Jul 2008, Shawn O. Pearce wrote:\n> \n>>> The only other alternative I can come up with is to change pack-objects \n>>> (or at least its defaults) so we don't generate these massive delta \n>>> chains. But there are already packs in the wild that use these chains, \n>>> resulting in performance problems for clients.\n>> But the long chains make the pack actually as efficient as it is...\n> \n> Perhaps Shawn thought here about limiting delta chain not by its\n> *length*, but by its *size* (as required when unpacking last object\n> in a delta chanin).\n> \n> What do you think about this idea?\n\nSorry for being clueless here, but why does the older versions need\nto be kept in-memory anyway? Aren't we applying the delta each time\nwe find one, repeatedly creating a new base-object in-memory for\neach delta? If we aren't doing that, why do we need more than just\na small amount of memory just for keeping the delta?\n\nFeel free to tell me to go away if I'm being stupid. I'm just\ncurious and probably won't be able to hack up any patches anyway.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"83259","messageId":"alpine.DEB.1.00.0807141322140.8950@racer","threadId":"14394","inReplyTo":"487B439F.8040902@op5.se","subject":"Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-14T12:25:54Z","receivedAt":"2008-07-14T12:25:54Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 14 Jul 2008, Andreas Ericsson wrote:\n\n> Sorry for being clueless here, but why does the older versions need\n> to be kept in-memory anyway? Aren't we applying the delta each time\n> we find one, repeatedly creating a new base-object in-memory for\n> each delta? If we aren't doing that, why do we need more than just\n> a small amount of memory just for keeping the delta?\n\nThink of a delta chain of 49 delta objects, 1 base object. Now \nreconstruct all of the objects.\n\nIf you do it one by one, not storing the intermediate results, you end up \napplying 1 delta for the first, 2 for the second (first the first, then \nthe second), and so on, in total 1 + 2 + 3 + ... + 49 = 49 * 50 / 2 = 1225 \ntimes.\n\nCompare that to the 49 times when reusing the intermediate results.\n\nCiao,\nDscho\n"},{"id":"83263","messageId":"487B4BD8.5030208@op5.se","threadId":"14394","inReplyTo":"alpine.DEB.1.00.0807141322140.8950@racer","subject":"Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2008-07-14T12:51:36Z","receivedAt":"2008-07-14T12:51:36Z","isPatch":true,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Johannes Schindelin wrote:\n> Hi,\n> \n> On Mon, 14 Jul 2008, Andreas Ericsson wrote:\n> \n>> Sorry for being clueless here, but why does the older versions need\n>> to be kept in-memory anyway? Aren't we applying the delta each time\n>> we find one, repeatedly creating a new base-object in-memory for\n>> each delta? If we aren't doing that, why do we need more than just\n>> a small amount of memory just for keeping the delta?\n> \n> Think of a delta chain of 49 delta objects, 1 base object. Now \n> reconstruct all of the objects.\n> \n> If you do it one by one, not storing the intermediate results, you end up \n> applying 1 delta for the first, 2 for the second (first the first, then \n> the second), and so on, in total 1 + 2 + 3 + ... + 49 = 49 * 50 / 2 = 1225 \n> times.\n> \n> Compare that to the 49 times when reusing the intermediate results.\n> \n\nThat's only true if you discard the result of applying D1 to DB though.\nWhat I'm wondering is; Why isn't it done like this (pseudo-code):\n\nwhile (delta = find_earlier_delta(sha1)) {\n\tif (is_base_object(delta)) {\n\t\tbase_object = delta;\n\t\tbreak;\n\t}\n\tpush_delta(delta, patch_stack);\n}\n\nwhile (pop_delta(patch_stack))\n\tapply_delta(base_object, delta);\n\n\n\nwhere \"apply_delta\" replaces the base_object->blob with the delta\napplied, releasing the previously used memory?\n\nThat way, you'll never use more memory than the largest ever size\nof the object + 1 delta at a time and still not apply the delta\nmore than delta_chain_length-1 times.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"83265","messageId":"alpine.DEB.1.00.0807141357430.8950@racer","threadId":"14394","inReplyTo":"487B4BD8.5030208@op5.se","subject":"Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2008-07-14T12:58:34Z","receivedAt":"2008-07-14T12:58:34Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 14 Jul 2008, Andreas Ericsson wrote:\n\n> Johannes Schindelin wrote:\n> \n> > On Mon, 14 Jul 2008, Andreas Ericsson wrote:\n> > \n> > > Sorry for being clueless here, but why does the older versions need\n> > > to be kept in-memory anyway? Aren't we applying the delta each time\n> > > we find one, repeatedly creating a new base-object in-memory for\n> > > each delta? If we aren't doing that, why do we need more than just\n> > > a small amount of memory just for keeping the delta?\n> > \n> > Think of a delta chain of 49 delta objects, 1 base object. Now reconstruct\n> > all of the objects.\n> > \n> > If you do it one by one, not storing the intermediate results, you end up\n> > applying 1 delta for the first, 2 for the second (first the first, then the\n> > second), and so on, in total 1 + 2 + 3 + ... + 49 = 49 * 50 / 2 = 1225\n> > times.\n> > \n> > Compare that to the 49 times when reusing the intermediate results.\n> > \n> \n> [...]\n>\n> while (pop_delta(patch_stack))\n> \tapply_delta(base_object, delta);\n> \n> where \"apply_delta\" replaces the base_object->blob with the delta \n> applied, releasing the previously used memory?\n\nDelta chains are not (necessarily) independent.\n\nCiao,\nDscho\n"},{"id":"83337","messageId":"alpine.LFD.1.10.0807142203530.12484@xanadu.home","threadId":"14394","inReplyTo":"487B4BD8.5030208@op5.se","subject":"Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-07-15T02:21:41Z","receivedAt":"2008-07-15T02:21:41Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 14 Jul 2008, Andreas Ericsson wrote:\n\n> Johannes Schindelin wrote:\n> > Hi,\n> > \n> > On Mon, 14 Jul 2008, Andreas Ericsson wrote:\n> > \n> > > Sorry for being clueless here, but why does the older versions need\n> > > to be kept in-memory anyway? Aren't we applying the delta each time\n> > > we find one, repeatedly creating a new base-object in-memory for\n> > > each delta? If we aren't doing that, why do we need more than just\n> > > a small amount of memory just for keeping the delta?\n> > \n> > Think of a delta chain of 49 delta objects, 1 base object. Now reconstruct\n> > all of the objects.\n> > \n> > If you do it one by one, not storing the intermediate results, you end up\n> > applying 1 delta for the first, 2 for the second (first the first, then the\n> > second), and so on, in total 1 + 2 + 3 + ... + 49 = 49 * 50 / 2 = 1225\n> > times.\n> > \n> > Compare that to the 49 times when reusing the intermediate results.\n> > \n> \n> That's only true if you discard the result of applying D1 to DB though.\n> What I'm wondering is; Why isn't it done like this (pseudo-code):\n> \n> while (delta = find_earlier_delta(sha1)) {\n> \tif (is_base_object(delta)) {\n> \t\tbase_object = delta;\n> \t\tbreak;\n> \t}\n> \tpush_delta(delta, patch_stack);\n> }\n> \n> while (pop_delta(patch_stack))\n> \tapply_delta(base_object, delta);\n> \n> \n> \n> where \"apply_delta\" replaces the base_object->blob with the delta\n> applied, releasing the previously used memory?\n> \n> That way, you'll never use more memory than the largest ever size\n> of the object + 1 delta at a time and still not apply the delta\n> more than delta_chain_length-1 times.\n\nThose delta chains aren't simple chained lists. They are trees of \ndeltas where one object might be the base for an unlimited number of \ndeltas of depth 1, and in turn each of those deltas might constitute the \nbase for an unlimited number of deltas of depth 2, and so on.\n\nSo what the code does is to find out which objects are not deltas but \nare the base for a delta. Then, for each of them, all deltas having \ngiven object for base are found and they are recursively resolved so \neach resolved delta is then considered a possible base for more deltas, \netc. In other words, those deltas are resolved by walking the delta \ntree in a \"depth first\" fashion.\n\nIf we discard previous delta bases, we will have to recreate them each \ntime a delta sibling is processed. And if those delta bases are \nthemselves deltas then you have an explosion of delta results to \nre-compute.\n\n\nNicolas\n"},{"id":"83338","messageId":"alpine.LFD.1.10.0807142239390.12484@xanadu.home","threadId":"14394","inReplyTo":"1216001267-33235-2-git-send-email-spearce@spearce.org","subject":"Re: [PATCH 1/4] index-pack: Refactor base arguments of resolve_delta into a struct","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-07-15T02:40:28Z","receivedAt":"2008-07-15T02:40:28Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 13 Jul 2008, Shawn O. Pearce wrote:\n\n> We need to discard base objects which are not recently used if our\n> memory gets low, such as when we are unpacking a long delta chain\n> of a very large object.\n> \n> To support tracking the available base objects we combine the\n> pointer and size into a struct. Future changes would allow the\n> data pointer to be free'd and marked NULL if memory gets low.\n> \n> Signed-off-by: Shawn O. Pearce \n\nACK\n\n\n> ---\n> index-pack.c | 60 +++++++++++++++++++++++++++++++--------------------------\n> 1 files changed, 33 insertions(+), 27 deletions(-)\n> \n> diff --git a/index-pack.c b/index-pack.c\n> index 25db5db..db03478 100644\n> --- a/index-pack.c\n> +++ b/index-pack.c\n> @@ -26,6 +26,11 @@ union delta_base {\n> \toff_t offset;\n> };\n> \n> +struct base_data {\n> +\tvoid *data;\n> +\tunsigned long size;\n> +};\n> +\n> /*\n> * Even if sizeof(union delta_base) == 24 on 64-bit archs, we really want\n> * to memcmp() only the first 20 bytes.\n> @@ -426,25 +431,25 @@ static void sha1_object(const void *data, unsigned long size,\n> \t}\n> }\n> \n> -static void resolve_delta(struct object_entry *delta_obj, void *base_data,\n> -\t\t\t unsigned long base_size, enum object_type type)\n> +static void resolve_delta(struct object_entry *delta_obj,\n> +\t\t\t struct base_data *base_obj, enum object_type type)\n> {\n> \tvoid *delta_data;\n> \tunsigned long delta_size;\n> -\tvoid *result;\n> -\tunsigned long result_size;\n> \tunion delta_base delta_base;\n> \tint j, first, last;\n> +\tstruct base_data result;\n> \n> \tdelta_obj->real_type = type;\n> \tdelta_data = get_data_from_pack(delta_obj);\n> \tdelta_size = delta_obj->size;\n> -\tresult = patch_delta(base_data, base_size, delta_data, delta_size,\n> -\t\t\t &result_size);\n> +\tresult.data = patch_delta(base_obj->data, base_obj->size,\n> +\t\t\t delta_data, delta_size,\n> +\t\t\t &result.size);\n> \tfree(delta_data);\n> -\tif (!result)\n> +\tif (!result.data)\n> \t\tbad_object(delta_obj->idx.offset, \"failed to apply delta\");\n> -\tsha1_object(result, result_size, type, delta_obj->idx.sha1);\n> +\tsha1_object(result.data, result.size, type, delta_obj->idx.sha1);\n> \tnr_resolved_deltas++;\n> \n> \thashcpy(delta_base.sha1, delta_obj->idx.sha1);\n> @@ -452,7 +457,7 @@ static void resolve_delta(struct object_entry *delta_obj, void *base_data,\n> \t\tfor (j = first; j <= last; j++) {\n> \t\t\tstruct object_entry *child = objects + deltas[j].obj_no;\n> \t\t\tif (child->real_type == OBJ_REF_DELTA)\n> -\t\t\t\tresolve_delta(child, result, result_size, type);\n> +\t\t\t\tresolve_delta(child, &result, type);\n> \t\t}\n> \t}\n> \n> @@ -462,11 +467,11 @@ static void resolve_delta(struct object_entry *delta_obj, void *base_data,\n> \t\tfor (j = first; j <= last; j++) {\n> \t\t\tstruct object_entry *child = objects + deltas[j].obj_no;\n> \t\t\tif (child->real_type == OBJ_OFS_DELTA)\n> -\t\t\t\tresolve_delta(child, result, result_size, type);\n> +\t\t\t\tresolve_delta(child, &result, type);\n> \t\t}\n> \t}\n> \n> -\tfree(result);\n> +\tfree(result.data);\n> }\n> \n> static int compare_delta_entry(const void *a, const void *b)\n> @@ -481,7 +486,6 @@ static void parse_pack_objects(unsigned char *sha1)\n> {\n> \tint i;\n> \tstruct delta_entry *delta = deltas;\n> -\tvoid *data;\n> \tstruct stat st;\n> \n> \t/*\n> @@ -496,7 +500,7 @@ static void parse_pack_objects(unsigned char *sha1)\n> \t\t\t\tnr_objects);\n> \tfor (i = 0; i < nr_objects; i++) {\n> \t\tstruct object_entry *obj = &objects[i];\n> -\t\tdata = unpack_raw_entry(obj, &delta->base);\n> +\t\tvoid *data = unpack_raw_entry(obj, &delta->base);\n> \t\tobj->real_type = obj->type;\n> \t\tif (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA) {\n> \t\t\tnr_deltas++;\n> @@ -545,6 +549,7 @@ static void parse_pack_objects(unsigned char *sha1)\n> \t\tstruct object_entry *obj = &objects[i];\n> \t\tunion delta_base base;\n> \t\tint j, ref, ref_first, ref_last, ofs, ofs_first, ofs_last;\n> +\t\tstruct base_data base_obj;\n> \n> \t\tif (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA)\n> \t\t\tcontinue;\n> @@ -555,22 +560,22 @@ static void parse_pack_objects(unsigned char *sha1)\n> \t\tofs = !find_delta_children(&base, &ofs_first, &ofs_last);\n> \t\tif (!ref && !ofs)\n> \t\t\tcontinue;\n> -\t\tdata = get_data_from_pack(obj);\n> +\t\tbase_obj.data = get_data_from_pack(obj);\n> +\t\tbase_obj.size = obj->size;\n> +\n> \t\tif (ref)\n> \t\t\tfor (j = ref_first; j <= ref_last; j++) {\n> \t\t\t\tstruct object_entry *child = objects + deltas[j].obj_no;\n> \t\t\t\tif (child->real_type == OBJ_REF_DELTA)\n> -\t\t\t\t\tresolve_delta(child, data,\n> -\t\t\t\t\t\t obj->size, obj->type);\n> +\t\t\t\t\tresolve_delta(child, &base_obj, obj->type);\n> \t\t\t}\n> \t\tif (ofs)\n> \t\t\tfor (j = ofs_first; j <= ofs_last; j++) {\n> \t\t\t\tstruct object_entry *child = objects + deltas[j].obj_no;\n> \t\t\t\tif (child->real_type == OBJ_OFS_DELTA)\n> -\t\t\t\t\tresolve_delta(child, data,\n> -\t\t\t\t\t\t obj->size, obj->type);\n> +\t\t\t\t\tresolve_delta(child, &base_obj, obj->type);\n> \t\t\t}\n> -\t\tfree(data);\n> +\t\tfree(base_obj.data);\n> \t\tdisplay_progress(progress, nr_resolved_deltas);\n> \t}\n> }\n> @@ -656,28 +661,29 @@ static void fix_unresolved_deltas(int nr_unresolved)\n> \n> \tfor (i = 0; i < n; i++) {\n> \t\tstruct delta_entry *d = sorted_by_pos[i];\n> -\t\tvoid *data;\n> -\t\tunsigned long size;\n> \t\tenum object_type type;\n> \t\tint j, first, last;\n> +\t\tstruct base_data base_obj;\n> \n> \t\tif (objects[d->obj_no].real_type != OBJ_REF_DELTA)\n> \t\t\tcontinue;\n> -\t\tdata = read_sha1_file(d->base.sha1, &type, &size);\n> -\t\tif (!data)\n> +\t\tbase_obj.data = read_sha1_file(d->base.sha1, &type, &base_obj.size);\n> +\t\tif (!base_obj.data)\n> \t\t\tcontinue;\n> \n> \t\tfind_delta_children(&d->base, &first, &last);\n> \t\tfor (j = first; j <= last; j++) {\n> \t\t\tstruct object_entry *child = objects + deltas[j].obj_no;\n> \t\t\tif (child->real_type == OBJ_REF_DELTA)\n> -\t\t\t\tresolve_delta(child, data, size, type);\n> +\t\t\t\tresolve_delta(child, &base_obj, type);\n> \t\t}\n> \n> -\t\tif (check_sha1_signature(d->base.sha1, data, size, typename(type)))\n> +\t\tif (check_sha1_signature(d->base.sha1, base_obj.data,\n> +\t\t\t\tbase_obj.size, typename(type)))\n> \t\t\tdie(\"local object %s is corrupt\", sha1_to_hex(d->base.sha1));\n> -\t\tappend_obj_to_pack(d->base.sha1, data, size, type);\n> -\t\tfree(data);\n> +\t\tappend_obj_to_pack(d->base.sha1, base_obj.data,\n> +\t\t\tbase_obj.size, type);\n> +\t\tfree(base_obj.data);\n> \t\tdisplay_progress(progress, nr_resolved_deltas);\n> \t}\n> \tfree(sorted_by_pos);\n> -- \n> 1.5.6.2.393.g45096\n> \n\n\nNicolas\n"},{"id":"83339","messageId":"20080715024741.GB1700@spearce.org","threadId":"14394","inReplyTo":"alpine.LFD.1.10.0807142203530.12484@xanadu.home","subject":"Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-15T02:47:41Z","receivedAt":"2008-07-15T02:47:41Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> \n> Those delta chains aren't simple chained lists. They are trees of \n> deltas where one object might be the base for an unlimited number of \n> deltas of depth 1, and in turn each of those deltas might constitute the \n> base for an unlimited number of deltas of depth 2, and so on.\n> \n> So what the code does is to find out which objects are not deltas but \n> are the base for a delta. Then, for each of them, all deltas having \n> given object for base are found and they are recursively resolved so \n> each resolved delta is then considered a possible base for more deltas, \n> etc. In other words, those deltas are resolved by walking the delta \n> tree in a \"depth first\" fashion.\n> \n> If we discard previous delta bases, we will have to recreate them each \n> time a delta sibling is processed. And if those delta bases are \n> themselves deltas then you have an explosion of delta results to \n> re-compute.\n\nYes, it would be horrible if we had to recompute 10 deltas in order\nto recover a previously discarded delta base in order to visit new\nsiblings.\n\nBut its even more horrible that we use 512M of memory in our working\nset size on a 256M machine to process a pack that is only 300M in\nsize, due to long delta chains on large objects. In such a case\nthe system will swap and perform fairly poorly due to the huge disk\nIO necessary to keep moving the working set around.\n\nWe're better off keeping our memory usage low and recomputing\nthe delta base when we need to return to it to process a sibling.\n\nPlease. Remember that index-pack, unlike unpack-objects, does not\nhold the unresolved deltas in memory while processing the input.\nIt assumes the total size of the unresolved deltas may exceed\nthe available memory for our working set and writes them to disk,\nto be read back in later during the resolving phase.\n\nAt some point it is possible for the completely inflated delta\nchain to exceed the physical memory of the system. As soon as you\ndo that you are committed to some form of swapping. We can probably\ndo that better from the packfile by reinflating the super compressed\ndeltas than letting the OS page in huge tracts of the virtual address\nspace off the swap device. Plus the OS does not need to expend disk\nIO to swap out the pages, we have already spent that cost when we\nwrote the pack file down to disk as part of our normal operation.\n\nI don't like adding code either. But I think I'm right. We really\nneed to not allow index-pack to create these massive working sets\nand assume the operating system is going to be able to handle\nit magically. Memory is not infinite, even if the Turing machine\ntheory claims it is.\n\n-- \nShawn.\n"},{"id":"83340","messageId":"alpine.LFD.1.10.0807142240460.12484@xanadu.home","threadId":"14394","inReplyTo":"1216001267-33235-3-git-send-email-spearce@spearce.org","subject":"Re: [PATCH 2/4] index-pack: Chain the struct base_data on the stack for traversal","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-07-15T02:48:35Z","receivedAt":"2008-07-15T02:48:35Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 13 Jul 2008, Shawn O. Pearce wrote:\n\n> We need to release earlier inflated base objects when memory gets\n> low, which means we need to be able to walk up or down the stack\n> to locate the objects we want to release, and free their data.\n> \n> The new link/unlink routines allow inserting and removing the struct\n> base_data during recursion inside resolve_delta, and the global\n> base_cache gives us the head of the chain (bottom of the stack)\n> so we can traverse it.\n> \n> Signed-off-by: Shawn O. Pearce \n\nYou don't really need that 'base' pointer, do you? When linking a new \nchild, then the 'child' pointer simply has to be overwritten. there is \na window where that 'child' pointer would be invalid after the child \nstructure has been discarded, but no walking of the list should occur at \nthat point anyway.\n\n> ---\n> index-pack.c | 34 +++++++++++++++++++++++++++++++---\n> 1 files changed, 31 insertions(+), 3 deletions(-)\n> \n> diff --git a/index-pack.c b/index-pack.c\n> index db03478..6c59fd3 100644\n> --- a/index-pack.c\n> +++ b/index-pack.c\n> @@ -27,6 +27,8 @@ union delta_base {\n> };\n> \n> struct base_data {\n> +\tstruct base_data *base;\n> +\tstruct base_data *child;\n> \tvoid *data;\n> \tunsigned long size;\n> };\n> @@ -48,6 +50,7 @@ struct delta_entry\n> \n> static struct object_entry *objects;\n> static struct delta_entry *deltas;\n> +static struct base_data *base_cache;\n> static int nr_objects;\n> static int nr_deltas;\n> static int nr_resolved_deltas;\n> @@ -216,6 +219,27 @@ static void bad_object(unsigned long offset, const char *format, ...)\n> \tdie(\"pack has bad object at offset %lu: %s\", offset, buf);\n> }\n> \n> +static void link_base_data(struct base_data *base, struct base_data *c)\n> +{\n> +\tif (base)\n> +\t\tbase->child = c;\n> +\telse\n> +\t\tbase_cache = c;\n> +\n> +\tc->base = base;\n> +\tc->child = NULL;\n> +}\n> +\n> +static void unlink_base_data(struct base_data *c)\n> +{\n> +\tstruct base_data *base = c->base;\n> +\tif (base)\n> +\t\tbase->child = NULL;\n> +\telse\n> +\t\tbase_cache = NULL;\n> +\tfree(c->data);\n> +}\n> +\n> static void *unpack_entry_data(unsigned long offset, unsigned long size)\n> {\n> \tz_stream stream;\n> @@ -452,6 +476,8 @@ static void resolve_delta(struct object_entry *delta_obj,\n> \tsha1_object(result.data, result.size, type, delta_obj->idx.sha1);\n> \tnr_resolved_deltas++;\n> \n> +\tlink_base_data(base_obj, &result);\n> +\n> \thashcpy(delta_base.sha1, delta_obj->idx.sha1);\n> \tif (!find_delta_children(&delta_base, &first, &last)) {\n> \t\tfor (j = first; j <= last; j++) {\n> @@ -471,7 +497,7 @@ static void resolve_delta(struct object_entry *delta_obj,\n> \t\t}\n> \t}\n> \n> -\tfree(result.data);\n> +\tunlink_base_data(&result);\n> }\n> \n> static int compare_delta_entry(const void *a, const void *b)\n> @@ -562,6 +588,7 @@ static void parse_pack_objects(unsigned char *sha1)\n> \t\t\tcontinue;\n> \t\tbase_obj.data = get_data_from_pack(obj);\n> \t\tbase_obj.size = obj->size;\n> +\t\tlink_base_data(NULL, &base_obj);\n> \n> \t\tif (ref)\n> \t\t\tfor (j = ref_first; j <= ref_last; j++) {\n> @@ -575,7 +602,7 @@ static void parse_pack_objects(unsigned char *sha1)\n> \t\t\t\tif (child->real_type == OBJ_OFS_DELTA)\n> \t\t\t\t\tresolve_delta(child, &base_obj, obj->type);\n> \t\t\t}\n> -\t\tfree(base_obj.data);\n> +\t\tunlink_base_data(&base_obj);\n> \t\tdisplay_progress(progress, nr_resolved_deltas);\n> \t}\n> }\n> @@ -670,6 +697,7 @@ static void fix_unresolved_deltas(int nr_unresolved)\n> \t\tbase_obj.data = read_sha1_file(d->base.sha1, &type, &base_obj.size);\n> \t\tif (!base_obj.data)\n> \t\t\tcontinue;\n> +\t\tlink_base_data(NULL, &base_obj);\n> \n> \t\tfind_delta_children(&d->base, &first, &last);\n> \t\tfor (j = first; j <= last; j++) {\n> @@ -683,7 +711,7 @@ static void fix_unresolved_deltas(int nr_unresolved)\n> \t\t\tdie(\"local object %s is corrupt\", sha1_to_hex(d->base.sha1));\n> \t\tappend_obj_to_pack(d->base.sha1, base_obj.data,\n> \t\t\tbase_obj.size, type);\n> -\t\tfree(base_obj.data);\n> +\t\tunlink_base_data(&base_obj);\n> \t\tdisplay_progress(progress, nr_resolved_deltas);\n> \t}\n> \tfree(sorted_by_pos);\n> -- \n> 1.5.6.2.393.g45096\n> \n\n\nNicolas\n"},{"id":"83341","messageId":"alpine.LFD.1.10.0807142249100.12484@xanadu.home","threadId":"14394","inReplyTo":"1216001267-33235-4-git-send-email-spearce@spearce.org","subject":"Re: [PATCH 3/4] index-pack: Track the object_entry that creates each base_data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-07-15T02:50:01Z","receivedAt":"2008-07-15T02:50:01Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 13 Jul 2008, Shawn O. Pearce wrote:\n\n> If we free the data stored within a base_data we need the struct\n> object_entry to get the data back again for use with another\n> dependent delta. Storing the object_entry* makes it simple to call\n> get_data_from_pack() to recover the compressed information.\n> \n> This however means we must add the missing baes object to the end\n\nTypo?\n\n> of our packfile prior to calling resolve_delta() on each of the\n> dependent deltas. Adding the base first ensures we can read the\n> base back from the pack we indexing, as if it had been included by\n> the remote side.\n> \n> Signed-off-by: Shawn O. Pearce \n\nACK\n\n> ---\n> index-pack.c | 18 ++++++++++++------\n> 1 files changed, 12 insertions(+), 6 deletions(-)\n> \n> diff --git a/index-pack.c b/index-pack.c\n> index 6c59fd3..7239e89 100644\n> --- a/index-pack.c\n> +++ b/index-pack.c\n> @@ -29,6 +29,7 @@ union delta_base {\n> struct base_data {\n> \tstruct base_data *base;\n> \tstruct base_data *child;\n> +\tstruct object_entry *obj;\n> \tvoid *data;\n> \tunsigned long size;\n> };\n> @@ -476,6 +477,7 @@ static void resolve_delta(struct object_entry *delta_obj,\n> \tsha1_object(result.data, result.size, type, delta_obj->idx.sha1);\n> \tnr_resolved_deltas++;\n> \n> +\tresult.obj = delta_obj;\n> \tlink_base_data(base_obj, &result);\n> \n> \thashcpy(delta_base.sha1, delta_obj->idx.sha1);\n> @@ -588,6 +590,7 @@ static void parse_pack_objects(unsigned char *sha1)\n> \t\t\tcontinue;\n> \t\tbase_obj.data = get_data_from_pack(obj);\n> \t\tbase_obj.size = obj->size;\n> +\t\tbase_obj.obj = obj;\n> \t\tlink_base_data(NULL, &base_obj);\n> \n> \t\tif (ref)\n> @@ -633,7 +636,8 @@ static int write_compressed(int fd, void *in, unsigned int size, uint32_t *obj_c\n> \treturn size;\n> }\n> \n> -static void append_obj_to_pack(const unsigned char *sha1, void *buf,\n> +static struct object_entry *append_obj_to_pack(\n> +\t\t\t const unsigned char *sha1, void *buf,\n> \t\t\t unsigned long size, enum object_type type)\n> {\n> \tstruct object_entry *obj = &objects[nr_objects++];\n> @@ -654,6 +658,7 @@ static void append_obj_to_pack(const unsigned char *sha1, void *buf,\n> \tobj[1].idx.offset = obj[0].idx.offset + n;\n> \tobj[1].idx.offset += write_compressed(output_fd, buf, size, &obj[0].idx.crc32);\n> \thashcpy(obj->idx.sha1, sha1);\n> +\treturn obj;\n> }\n> \n> static int delta_pos_compare(const void *_a, const void *_b)\n> @@ -697,6 +702,12 @@ static void fix_unresolved_deltas(int nr_unresolved)\n> \t\tbase_obj.data = read_sha1_file(d->base.sha1, &type, &base_obj.size);\n> \t\tif (!base_obj.data)\n> \t\t\tcontinue;\n> +\n> +\t\tif (check_sha1_signature(d->base.sha1, base_obj.data,\n> +\t\t\t\tbase_obj.size, typename(type)))\n> +\t\t\tdie(\"local object %s is corrupt\", sha1_to_hex(d->base.sha1));\n> +\t\tbase_obj.obj = append_obj_to_pack(d->base.sha1, base_obj.data,\n> +\t\t\tbase_obj.size, type);\n> \t\tlink_base_data(NULL, &base_obj);\n> \n> \t\tfind_delta_children(&d->base, &first, &last);\n> @@ -706,11 +717,6 @@ static void fix_unresolved_deltas(int nr_unresolved)\n> \t\t\t\tresolve_delta(child, &base_obj, type);\n> \t\t}\n> \n> -\t\tif (check_sha1_signature(d->base.sha1, base_obj.data,\n> -\t\t\t\tbase_obj.size, typename(type)))\n> -\t\t\tdie(\"local object %s is corrupt\", sha1_to_hex(d->base.sha1));\n> -\t\tappend_obj_to_pack(d->base.sha1, base_obj.data,\n> -\t\t\tbase_obj.size, type);\n> \t\tunlink_base_data(&base_obj);\n> \t\tdisplay_progress(progress, nr_resolved_deltas);\n> \t}\n> -- \n> 1.5.6.2.393.g45096\n> \n\n\nNicolas\n"},{"id":"83344","messageId":"alpine.LFD.1.10.0807142255240.12484@xanadu.home","threadId":"14394","inReplyTo":"1216001267-33235-5-git-send-email-spearce@spearce.org","subject":"Re: [PATCH 4/4] index-pack: Honor core.deltaBaseCacheLimit when resolving deltas","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-07-15T03:05:24Z","receivedAt":"2008-07-15T03:05:24Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 13 Jul 2008, Shawn O. Pearce wrote:\n\n> If we are trying to resolve deltas for a long delta chain composed\n> of multi-megabyte objects we can easily run into requiring 500M+\n> of memory to hold each object in the chain on the call stack while\n> we recurse into the dependent objects and resolve them.\n> \n> We now use a simple delta cache that discards objects near the\n> bottom of the call stack first, as they are the most least recently\n> used objects in this current delta chain. If we recurse out of a\n> chain we may find the base object is no longer available, as it was\n> free'd to keep memory under the deltaBaseCacheLimit. In such cases\n> we must unpack the base object again, which will require recursing\n> back to the root of the top of the delta chain as we released that\n> root first.\n> \n> Signed-off-by: Shawn O. Pearce \n\nOK now I see what the 'base' pointer I previously dismissed is really \nneeded for.\n\nBut this patch is suboptimal as it actually recreate the same memory \npressure, to a lesser degree, this series is meant to solve. If you do:\n\n> +\t\tstruct object_entry *obj = c->obj;\n> +\t\tvoid *raw = get_data_from_pack(obj);\n> +\t\tif (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA) {\n> +\t\t\tc->data = patch_delta(\n> +\t\t\t\tget_base_data(c->base), c->base->size,\n> +\t\t\t\traw, obj->size,\n> +\t\t\t\t&c->size);\n> +\t\t\tfree(raw);\n\nWhat you actually do is to read the delta data in memory, then recurse \ndown to read more delta data, then recurse down to read the base which \nmight be yet more delta data in memory, etc. etc. Only when you reach \nthe bottom of the stack will you start resolving all those deltas in \nmemory. Instead, the check for a delta object should be done first, and \nif so then recursion for the base object be performed _before_ reading \nthe currently wanted object data. This way you won't have more than one \ndelta buffer at any time in memory.\n\n\nNicolas\n"},{"id":"83345","messageId":"alpine.LFD.1.10.0807142306130.12484@xanadu.home","threadId":"14394","inReplyTo":"20080715024741.GB1700@spearce.org","subject":"Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-07-15T03:06:57Z","receivedAt":"2008-07-15T03:06:57Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 15 Jul 2008, Shawn O. Pearce wrote:\n\n> Nicolas Pitre wrote:\n> > \n> > Those delta chains aren't simple chained lists. They are trees of \n> > deltas where one object might be the base for an unlimited number of \n> > deltas of depth 1, and in turn each of those deltas might constitute the \n> > base for an unlimited number of deltas of depth 2, and so on.\n> > \n> > So what the code does is to find out which objects are not deltas but \n> > are the base for a delta. Then, for each of them, all deltas having \n> > given object for base are found and they are recursively resolved so \n> > each resolved delta is then considered a possible base for more deltas, \n> > etc. In other words, those deltas are resolved by walking the delta \n> > tree in a \"depth first\" fashion.\n> > \n> > If we discard previous delta bases, we will have to recreate them each \n> > time a delta sibling is processed. And if those delta bases are \n> > themselves deltas then you have an explosion of delta results to \n> > re-compute.\n> \n> Yes, it would be horrible if we had to recompute 10 deltas in order\n> to recover a previously discarded delta base in order to visit new\n> siblings.\n> \n> But its even more horrible that we use 512M of memory in our working\n> set size on a 256M machine to process a pack that is only 300M in\n> size, due to long delta chains on large objects. In such a case\n> the system will swap and perform fairly poorly due to the huge disk\n> IO necessary to keep moving the working set around.\n> \n> We're better off keeping our memory usage low and recomputing\n> the delta base when we need to return to it to process a sibling.\n\nPlease relax! ;-)\n\nAnd have a look in your mbox.\n\n\nNicolas\n"},{"id":"83348","messageId":"20080715031800.GD1700@spearce.org","threadId":"14394","inReplyTo":"alpine.LFD.1.10.0807142255240.12484@xanadu.home","subject":"Re: [PATCH 4/4] index-pack: Honor core.deltaBaseCacheLimit when resolving deltas","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-15T03:18:00Z","receivedAt":"2008-07-15T03:18:00Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> On Sun, 13 Jul 2008, Shawn O. Pearce wrote:\n> \n> But this patch is suboptimal as it actually recreate the same memory \n> pressure, to a lesser degree, this series is meant to solve. If you do:\n\nArrgh. Good catch on review. I'll post a replacement patch shortly\nthat doesn't suffer from this problem. Thanks!\n \n> > +\t\tstruct object_entry *obj = c->obj;\n> > +\t\tvoid *raw = get_data_from_pack(obj);\n> > +\t\tif (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA) {\n> > +\t\t\tc->data = patch_delta(\n> > +\t\t\t\tget_base_data(c->base), c->base->size,\n> > +\t\t\t\traw, obj->size,\n> > +\t\t\t\t&c->size);\n> > +\t\t\tfree(raw);\n\n-- \nShawn.\n"},{"id":"83349","messageId":"20080715032008.GE1700@spearce.org","threadId":"14394","inReplyTo":"alpine.LFD.1.10.0807142249100.12484@xanadu.home","subject":"Re: [PATCH 3/4] index-pack: Track the object_entry that creates each base_data","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-15T03:20:08Z","receivedAt":"2008-07-15T03:20:08Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> On Sun, 13 Jul 2008, Shawn O. Pearce wrote:\n> \n> > If we free the data stored within a base_data we need the struct\n> > object_entry to get the data back again for use with another\n> > dependent delta. Storing the object_entry* makes it simple to call\n> > get_data_from_pack() to recover the compressed information.\n> > \n> > This however means we must add the missing baes object to the end\n> \n> Typo?\n\nYea, Dscho also pointed it out.\n\nJunio, if you can, please fix this typo in the commit message.\n\nIts not really a big deal. I have no plans on posting a replacement\npatch just for this one small typo. Plenty of my current commits\nin git.git have typos too. I'm not that good of a typist. And gcc\ndoesn't check my commit messages. ;-)\n \n-- \nShawn.\n"},{"id":"83352","messageId":"alpine.LFD.1.10.0807142340030.12484@xanadu.home","threadId":"14394","inReplyTo":"20080715032008.GE1700@spearce.org","subject":"Re: [PATCH 3/4] index-pack: Track the object_entry that creates each base_data","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-07-15T03:42:30Z","receivedAt":"2008-07-15T03:42:30Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 15 Jul 2008, Shawn O. Pearce wrote:\n\n> Nicolas Pitre wrote:\n> > On Sun, 13 Jul 2008, Shawn O. Pearce wrote:\n> > \n> > > If we free the data stored within a base_data we need the struct\n> > > object_entry to get the data back again for use with another\n> > > dependent delta. Storing the object_entry* makes it simple to call\n> > > get_data_from_pack() to recover the compressed information.\n> > > \n> > > This however means we must add the missing baes object to the end\n> > \n> > Typo?\n> \n> Yea, Dscho also pointed it out.\n> \n> Junio, if you can, please fix this typo in the commit message.\n> \n> Its not really a big deal. I have no plans on posting a replacement\n> patch just for this one small typo.\n\nNo, it is not a big deal. I do write crappy english myself. I \ninitially had some comments on the patch itself which whould have \nwarranted another patch and then changed my mind.\n\n\nNicolas\n"},{"id":"83353","messageId":"20080715041929.GC2432@spearce.org","threadId":"14394","inReplyTo":"m31w1wu1hc.fsf@localhost.localdomain","subject":"Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-15T04:19:29Z","receivedAt":"2008-07-15T04:19:29Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Jakub Narebski wrote:\n> Johannes Schindelin writes:\n> > On Mon, 14 Jul 2008, Shawn O. Pearce wrote:\n> \n> > > The only other alternative I can come up with is to change pack-objects \n> > > (or at least its defaults) so we don't generate these massive delta \n> > > chains. But there are already packs in the wild that use these chains, \n> > > resulting in performance problems for clients.\n> > \n> > But the long chains make the pack actually as efficient as it is...\n> \n> Perhaps Shawn thought here about limiting delta chain not by its\n> *length*, but by its *size* (as required when unpacking last object\n> in a delta chanin).\n> \n> What do you think about this idea?\n\nI was talking about that. Or at least thinking it. But its not a\ngood solution, as Dscho points out those long chains is what makes\nthe pack file such a powerful source code compressor.\n\nIMHO the right solution is to continue to allow these long chains,\nespecially since they are typically used for the older, less often\naccessed objects, and use bounded caching where necessary in the\nreaders to avoid unpacking costs. We already have a bounded cache\nfor the random access case used by most programs. What we missed\nwas the bounded cache in index-pack, and my 4 patch series is an\nattempt to define that.\n\n-- \nShawn.\n"},{"id":"83357","messageId":"20080715044534.GA2794@spearce.org","threadId":"14394","inReplyTo":"20080715031800.GD1700@spearce.org","subject":"[PATCH v2] index-pack: Honor core.deltaBaseCacheLimit when resolving deltas","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-15T04:45:34Z","receivedAt":"2008-07-15T04:45:34Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"If we are trying to resolve deltas for a long delta chain composed\nof multi-megabyte objects we can easily run into requiring 500M+\nof memory to hold each object in the chain on the call stack while\nwe recurse into the dependent objects and resolve them.\n\nWe now use a simple delta cache that discards objects near the\nbottom of the call stack first, as they are the most least recently\nused objects in this current delta chain. If we recurse out of a\nchain we may find the base object is no longer available, as it was\nfree'd to keep memory under the deltaBaseCacheLimit. In such cases\nwe must unpack the base object again, which will require recursing\nback to the root of the top of the delta chain as we released that\nroot first.\n\nThe astute reader will probably realize that we can still exceed\nthe delta base cache limit, but this happens only if the most\nrecent base plus the delta plus the inflated dependent sum up to\nmore than the base cache limit. Due to the way patch_delta is\ncurrently implemented we cannot operate in less memory anyway.\n\nSigned-off-by: Shawn O. Pearce \n---\n\n Version 2 plugs the case Nico noticed, where the patch was causing\n the exact behavior it was trying to prevent while recovering from\n what it did to avoid the excessive memory usage in the first place.\n\n The change was in get_base_data() where we now unpack the delta\n after we have unpacked the base. Nico and I both missed that we\n must also bump base_cache_used when we restore the base, and we\n must also prune the bases in case this base has caused us to go\n over the limit.\n\n :-)\n\n index-pack.c | 48 ++++++++++++++++++++++++++++++++++++++++++++++--\n 1 files changed, 46 insertions(+), 2 deletions(-)\n\ndiff --git a/index-pack.c b/index-pack.c\nindex 7239e89..b4ec736 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -52,6 +52,7 @@ struct delta_entry\n static struct object_entry *objects;\n static struct delta_entry *deltas;\n static struct base_data *base_cache;\n+static size_t base_cache_used;\n static int nr_objects;\n static int nr_deltas;\n static int nr_resolved_deltas;\n@@ -220,6 +221,20 @@ static void bad_object(unsigned long offset, const char *format, ...)\n \tdie(\"pack has bad object at offset %lu: %s\", offset, buf);\n }\n \n+static void prune_base_data(struct base_data *retain)\n+{\n+\tstruct base_data *b = base_cache;\n+\tfor (b = base_cache;\n+\t base_cache_used > delta_base_cache_limit && b;\n+\t b = b->child) {\n+\t\tif (b->data && b != retain) {\n+\t\t\tfree(b->data);\n+\t\t\tb->data = NULL;\n+\t\t\tbase_cache_used -= b->size;\n+\t\t}\n+\t}\n+}\n+\n static void link_base_data(struct base_data *base, struct base_data *c)\n {\n \tif (base)\n@@ -229,6 +244,8 @@ static void link_base_data(struct base_data *base, struct base_data *c)\n \n \tc->base = base;\n \tc->child = NULL;\n+\tbase_cache_used += c->size;\n+\tprune_base_data(c);\n }\n \n static void unlink_base_data(struct base_data *c)\n@@ -238,7 +255,10 @@ static void unlink_base_data(struct base_data *c)\n \t\tbase->child = NULL;\n \telse\n \t\tbase_cache = NULL;\n-\tfree(c->data);\n+\tif (c->data) {\n+\t\tfree(c->data);\n+\t\tbase_cache_used -= c->size;\n+\t}\n }\n \n static void *unpack_entry_data(unsigned long offset, unsigned long size)\n@@ -456,6 +476,30 @@ static void sha1_object(const void *data, unsigned long size,\n \t}\n }\n \n+static void *get_base_data(struct base_data *c)\n+{\n+\tif (!c->data) {\n+\t\tstruct object_entry *obj = c->obj;\n+\n+\t\tif (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA) {\n+\t\t\tvoid *base = get_base_data(c->base);\n+\t\t\tvoid *raw = get_data_from_pack(obj);\n+\t\t\tc->data = patch_delta(\n+\t\t\t\tbase, c->base->size,\n+\t\t\t\traw, obj->size,\n+\t\t\t\t&c->size);\n+\t\t\tfree(raw);\n+\t\t\tif (!c->data)\n+\t\t\t\tbad_object(obj->idx.offset, \"failed to apply delta\");\n+\t\t} else\n+\t\t\tc->data = get_data_from_pack(obj);\n+\n+\t\tbase_cache_used += c->size;\n+\t\tprune_base_data(c);\n+\t}\n+\treturn c->data;\n+}\n+\n static void resolve_delta(struct object_entry *delta_obj,\n \t\t\t struct base_data *base_obj, enum object_type type)\n {\n@@ -468,7 +512,7 @@ static void resolve_delta(struct object_entry *delta_obj,\n \tdelta_obj->real_type = type;\n \tdelta_data = get_data_from_pack(delta_obj);\n \tdelta_size = delta_obj->size;\n-\tresult.data = patch_delta(base_obj->data, base_obj->size,\n+\tresult.data = patch_delta(get_base_data(base_obj), base_obj->size,\n \t\t\t delta_data, delta_size,\n \t\t\t &result.size);\n \tfree(delta_data);\n-- \n1.5.6.2.393.g45096\n"},{"id":"83360","messageId":"alpine.LFD.1.10.0807150100470.12484@xanadu.home","threadId":"14394","inReplyTo":"20080715044534.GA2794@spearce.org","subject":"Re: [PATCH v2] index-pack: Honor core.deltaBaseCacheLimit when resolving deltas","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-07-15T05:05:32Z","receivedAt":"2008-07-15T05:05:32Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 15 Jul 2008, Shawn O. Pearce wrote:\n\n> If we are trying to resolve deltas for a long delta chain composed\n> of multi-megabyte objects we can easily run into requiring 500M+\n> of memory to hold each object in the chain on the call stack while\n> we recurse into the dependent objects and resolve them.\n> \n> We now use a simple delta cache that discards objects near the\n> bottom of the call stack first, as they are the most least recently\n> used objects in this current delta chain. If we recurse out of a\n> chain we may find the base object is no longer available, as it was\n> free'd to keep memory under the deltaBaseCacheLimit. In such cases\n> we must unpack the base object again, which will require recursing\n> back to the root of the top of the delta chain as we released that\n> root first.\n> \n> The astute reader will probably realize that we can still exceed\n> the delta base cache limit, but this happens only if the most\n> recent base plus the delta plus the inflated dependent sum up to\n> more than the base cache limit. Due to the way patch_delta is\n> currently implemented we cannot operate in less memory anyway.\n\nYou may also set the limit lower than the size of the largest object \nwhich is going to bust it too. Same goes for the cache in sha1_file.c. \nThere is simply a limit to how tight we can sanely make memory usage.\n\n> Signed-off-by: Shawn O. Pearce \n\nACK\n\n> ---\n> \n> Version 2 plugs the case Nico noticed, where the patch was causing\n> the exact behavior it was trying to prevent while recovering from\n> what it did to avoid the excessive memory usage in the first place.\n> \n> The change was in get_base_data() where we now unpack the delta\n> after we have unpacked the base. Nico and I both missed that we\n> must also bump base_cache_used when we restore the base, and we\n> must also prune the bases in case this base has caused us to go\n> over the limit.\n> \n> :-)\n> \n> index-pack.c | 48 ++++++++++++++++++++++++++++++++++++++++++++++--\n> 1 files changed, 46 insertions(+), 2 deletions(-)\n> \n> diff --git a/index-pack.c b/index-pack.c\n> index 7239e89..b4ec736 100644\n> --- a/index-pack.c\n> +++ b/index-pack.c\n> @@ -52,6 +52,7 @@ struct delta_entry\n> static struct object_entry *objects;\n> static struct delta_entry *deltas;\n> static struct base_data *base_cache;\n> +static size_t base_cache_used;\n> static int nr_objects;\n> static int nr_deltas;\n> static int nr_resolved_deltas;\n> @@ -220,6 +221,20 @@ static void bad_object(unsigned long offset, const char *format, ...)\n> \tdie(\"pack has bad object at offset %lu: %s\", offset, buf);\n> }\n> \n> +static void prune_base_data(struct base_data *retain)\n> +{\n> +\tstruct base_data *b = base_cache;\n> +\tfor (b = base_cache;\n> +\t base_cache_used > delta_base_cache_limit && b;\n> +\t b = b->child) {\n> +\t\tif (b->data && b != retain) {\n> +\t\t\tfree(b->data);\n> +\t\t\tb->data = NULL;\n> +\t\t\tbase_cache_used -= b->size;\n> +\t\t}\n> +\t}\n> +}\n> +\n> static void link_base_data(struct base_data *base, struct base_data *c)\n> {\n> \tif (base)\n> @@ -229,6 +244,8 @@ static void link_base_data(struct base_data *base, struct base_data *c)\n> \n> \tc->base = base;\n> \tc->child = NULL;\n> +\tbase_cache_used += c->size;\n> +\tprune_base_data(c);\n> }\n> \n> static void unlink_base_data(struct base_data *c)\n> @@ -238,7 +255,10 @@ static void unlink_base_data(struct base_data *c)\n> \t\tbase->child = NULL;\n> \telse\n> \t\tbase_cache = NULL;\n> -\tfree(c->data);\n> +\tif (c->data) {\n> +\t\tfree(c->data);\n> +\t\tbase_cache_used -= c->size;\n> +\t}\n> }\n> \n> static void *unpack_entry_data(unsigned long offset, unsigned long size)\n> @@ -456,6 +476,30 @@ static void sha1_object(const void *data, unsigned long size,\n> \t}\n> }\n> \n> +static void *get_base_data(struct base_data *c)\n> +{\n> +\tif (!c->data) {\n> +\t\tstruct object_entry *obj = c->obj;\n> +\n> +\t\tif (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA) {\n> +\t\t\tvoid *base = get_base_data(c->base);\n> +\t\t\tvoid *raw = get_data_from_pack(obj);\n> +\t\t\tc->data = patch_delta(\n> +\t\t\t\tbase, c->base->size,\n> +\t\t\t\traw, obj->size,\n> +\t\t\t\t&c->size);\n> +\t\t\tfree(raw);\n> +\t\t\tif (!c->data)\n> +\t\t\t\tbad_object(obj->idx.offset, \"failed to apply delta\");\n> +\t\t} else\n> +\t\t\tc->data = get_data_from_pack(obj);\n> +\n> +\t\tbase_cache_used += c->size;\n> +\t\tprune_base_data(c);\n> +\t}\n> +\treturn c->data;\n> +}\n> +\n> static void resolve_delta(struct object_entry *delta_obj,\n> \t\t\t struct base_data *base_obj, enum object_type type)\n> {\n> @@ -468,7 +512,7 @@ static void resolve_delta(struct object_entry *delta_obj,\n> \tdelta_obj->real_type = type;\n> \tdelta_data = get_data_from_pack(delta_obj);\n> \tdelta_size = delta_obj->size;\n> -\tresult.data = patch_delta(base_obj->data, base_obj->size,\n> +\tresult.data = patch_delta(get_base_data(base_obj), base_obj->size,\n> \t\t\t delta_data, delta_size,\n> \t\t\t &result.size);\n> \tfree(delta_data);\n> -- \n> 1.5.6.2.393.g45096\n> \n\n\nNicolas\n"},{"id":"83422","messageId":"7vabgj0yrv.fsf@gitster.siamese.dyndns.org","threadId":"14394","inReplyTo":"20080715044534.GA2794@spearce.org","subject":"Re: [PATCH v2] index-pack: Honor core.deltaBaseCacheLimit when resolving deltas","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-15T18:48:20Z","receivedAt":"2008-07-15T18:48:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" writes:\n\n> Version 2 plugs the case Nico noticed, where the patch was causing\n> the exact behavior it was trying to prevent while recovering from\n> what it did to avoid the excessive memory usage in the first place.\n\nThanks both; it makes sense.\n"},{"id":"83707","messageId":"487F6E04.9050106@arcor.de","threadId":"14394","inReplyTo":"20080715024741.GB1700@spearce.org","subject":"Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack","fromName":"Stephan Hennig","fromEmail":"mailing_list@arcor.de","sentAt":"2008-07-17T16:06:28Z","receivedAt":"2008-07-17T16:06:28Z","isPatch":true,"sender":{"key":"mailing_list@arcor.de","avatar":null},"body":"Shawn O. Pearce schrieb:\n\n> We're better off keeping our memory usage low and recomputing\n> the delta base when we need to return to it to process a sibling.\n\nThanks to all who have had a look at this issue! From a user's\nperspective I have one more suggestions and a question:\n\nFirst, it would have helped me to bring this issue onto the list if I\nhad earlier known that this was no misconfiguration, but a memory\nproblem. Even though Git now makes some efforts to substitute runtime\nfor memory to be able to operate with low(er) memory, I think it would\nstill be informative for a user that repository and hardware, resp.\ncore.deltaBaseCacheLimit, are, say, incompatible. If valuable objects\nhave to be discarded due to memory restrictions a warning could be\nissued to make the user aware of this fact, e.g.,\n\n Warning! Low memory. Git might be slowing down.\n\n\nSecond, while there have been some changes to Git now, as a poor user,\nhow can I make use of that changes? I think, updating my client should\nonly help with pushing. For pulling, I have to wait for repo.or.cz to\nupdate to Git 1.6.0, right?\n\nBest regards,\nStephan Hennig\n"},{"id":"83711","messageId":"alpine.LFD.1.10.0807171215020.3110@xanadu.home","threadId":"14394","inReplyTo":"487F6E04.9050106@arcor.de","subject":"Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-07-17T16:25:36Z","receivedAt":"2008-07-17T16:25:36Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 17 Jul 2008, Stephan Hennig wrote:\n\n> Shawn O. Pearce schrieb:\n> \n> > We're better off keeping our memory usage low and recomputing\n> > the delta base when we need to return to it to process a sibling.\n> \n> Thanks to all who have had a look at this issue! From a user's\n> perspective I have one more suggestions and a question:\n> \n> First, it would have helped me to bring this issue onto the list if I\n> had earlier known that this was no misconfiguration, but a memory\n> problem.\n\nWell, if we had known before that this could be a problem, we'd have \nfixed it earlier. In other words, sh*t happens.\n\n> Even though Git now makes some efforts to substitute runtime\n> for memory to be able to operate with low(er) memory, I think it would\n> still be informative for a user that repository and hardware, resp.\n> core.deltaBaseCacheLimit, are, say, incompatible. If valuable objects\n> have to be discarded due to memory restrictions a warning could be\n> issued to make the user aware of this fact, e.g.,\n> \n> Warning! Low memory. Git might be slowing down.\n\nWell, I disagree. First we don't know how slow git would effectively be \nsince all (my) concerns so far were totally theoretical. It will still \nwork better than, say, 'git verify-pack' nevertheless. And git should \njust do its best regardless and avoid being needlessly verbose.\n\n> Second, while there have been some changes to Git now, as a poor user,\n> how can I make use of that changes? I think, updating my client should\n> only help with pushing. For pulling, I have to wait for repo.or.cz to\n> update to Git 1.6.0, right?\n\nActually that's the other way around. This change will help the \nreceiving side of a transfer. So it should help you when pulling.\n\n\nNicolas\n"},{"id":"83759","messageId":"20080717213550.GA2798@spearce.org","threadId":"14394","inReplyTo":"alpine.LFD.1.10.0807171215020.3110@xanadu.home","subject":"Re: [PATCH 0/4] Honor core.deltaBaseCacheLimit during index-pack","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-17T21:35:50Z","receivedAt":"2008-07-17T21:35:50Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nicolas Pitre wrote:\n> On Thu, 17 Jul 2008, Stephan Hennig wrote:\n> > Even though Git now makes some efforts to substitute runtime\n> > for memory to be able to operate with low(er) memory, I think it would\n> > still be informative for a user that repository and hardware, resp.\n> > core.deltaBaseCacheLimit, are, say, incompatible. If valuable objects\n> > have to be discarded due to memory restrictions a warning could be\n> > issued to make the user aware of this fact, e.g.,\n> > \n> > Warning! Low memory. Git might be slowing down.\n> \n> Well, I disagree. First we don't know how slow git would effectively be \n> since all (my) concerns so far were totally theoretical. It will still \n> work better than, say, 'git verify-pack' nevertheless. And git should \n> just do its best regardless and avoid being needlessly verbose.\n\nActually, this warning may be a good idea. I'll post an RFC patch\nfor it in a few minutes. If people hate the idea, that's what an\nRFC is for. :)\n\n-- \nShawn.\n"},{"id":"83764","messageId":"20080717220251.GA3072@spearce.org","threadId":"14394","inReplyTo":"20080717213550.GA2798@spearce.org","subject":"[RFC PATCH] index-pack: Issue a warning if deltaBaseCacheLimit is too small","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-07-17T22:02:51Z","receivedAt":"2008-07-17T22:02:51Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Its rare that we should exceed deltaBaseCacheLimit while resolving\ndelta compressed objects. By default this limit is 16M, and most\nchains are under 50 objects in length. This affords about 327K per\nobject in the chain, which is quite large by source code standards.\n\nIf we have to recreate a prior delta base because we evicted it to\nstay within the deltaBaseCacheLimit we can warn the user that their\nconfigured limit is perhaps too low for this repository data set.\nIf the user keeps seeing the warning they can research it in the\ndocumentation, and consider setting it higher on this repository,\nor just globally on their system.\n\nSuggested-by: Stephan Hennig \nSigned-off-by: Shawn O. Pearce \n---\n index-pack.c | 8 ++++++++\n 1 files changed, 8 insertions(+), 0 deletions(-)\n\ndiff --git a/index-pack.c b/index-pack.c\nindex ac20a46..97533d6 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -53,6 +53,7 @@ static struct object_entry *objects;\n static struct delta_entry *deltas;\n static struct base_data *base_cache;\n static size_t base_cache_used;\n+static int oom_warning;\n static int nr_objects;\n static int nr_deltas;\n static int nr_resolved_deltas;\n@@ -481,6 +482,13 @@ static void *get_base_data(struct base_data *c)\n \tif (!c->data) {\n \t\tstruct object_entry *obj = c->obj;\n \n+\t\tif (!oom_warning && verbose) {\n+\t\t\tif (progress)\n+\t\t\t\tfputc('\\n', stderr);\n+\t\t\twarning(\"One or more delta chains are larger than deltaBaseCache.\");\n+\t\t\toom_warning = 1;\n+\t\t}\n+\n \t\tif (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA) {\n \t\t\tvoid *base = get_base_data(c->base);\n \t\t\tvoid *raw = get_data_from_pack(obj);\n-- \n1.5.6.3.569.ga9185\n"},{"id":"83772","messageId":"alpine.LFD.1.10.0807171914270.3213@xanadu.home","threadId":"14394","inReplyTo":"20080717220251.GA3072@spearce.org","subject":"Re: [RFC PATCH] index-pack: Issue a warning if deltaBaseCacheLimit is too small","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-07-17T23:45:03Z","receivedAt":"2008-07-17T23:45:03Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 17 Jul 2008, Shawn O. Pearce wrote:\n\n> Its rare that we should exceed deltaBaseCacheLimit while resolving\n> delta compressed objects. By default this limit is 16M, and most\n> chains are under 50 objects in length. This affords about 327K per\n> object in the chain, which is quite large by source code standards.\n> \n> If we have to recreate a prior delta base because we evicted it to\n> stay within the deltaBaseCacheLimit we can warn the user that their\n> configured limit is perhaps too low for this repository data set.\n> If the user keeps seeing the warning they can research it in the\n> documentation, and consider setting it higher on this repository,\n> or just globally on their system.\n\nAs I said earlier, I don't think this is a good idea, but I'll elaborate \na bit more.\n\nFirst, this is a really bad clue for setting deltaBaseCacheLimit. The \nlikelyhood of this warning to actually show up during an initial clone \nis relatively high, yet this doesn't mean that deltaBaseCacheLimit has \nto be changed at all. For one, the real time usage of \ndeltaBaseCacheLimit is to cap a cache of objects for multiple delta \nchains with random access, and not only one chain traversed linearly \nlike in the index-pack case, \nand that cache is \nlikely to always be full and in active eviction mode -- that's the point \nof a cap after all. In the index-pack this is only used to avoid \nexcessive memory usage for intermediate delta results and not really a \ncache. In other words, we have two rather different usages for the same \nsettings. Now don't read me wrong: I think that reusing this setting is \nsensible, but its value should not be determined by what index-pack may \nhappen to do with it, especially on a first clone. And issuing warnings \non the first clone is not the way to give new users confidence either.\n\nSecondly, on subsequent fetches, the warning is likely to never appear \nagain due to the fact that the delta chains will typically be much \nshorter. And that would be true even if in reality the runtime access \nto the repository would benefit a lot from deltaBaseCacheLimit being \nraised. And it is the runtime access which is important here, not the \noccasional fetch. Yet the full delta chains are not likely to be walked \nin their entirety very often anyway either.\n\nThirdly, if such indication is considered useful, then it should really \nbe part of some statistic/analysis tool, such as verify-pack for \nexample. Such a tool could compute the exact memory requirements for a \ngiven repository usage and possibly provide suggestions as to what the \noptimal deltaBaseCacheLimit value could be. But yet that cache has a \nhardcoded number of entries at the moment and its hash function might \nnot be optimal either, making the connection with index-pack even more \napart.\n\nAnd finally, I think that index-pack would benefit a lot from a really \nsimple optimization which is to free the resulting intermediate delta \nbase object right away when there is only one delta child to resolve, \nbefore that child is itself used as a base for further delta \ngrand-children. That is likely to cover most cases of big delta chains \nalready, making that warning an even worse indicator.\n\n> Suggested-by: Stephan Hennig \n> Signed-off-by: Shawn O. Pearce \n\nUnrecommended-by: Nicolas Pitre \n\n\nNicolas\n"}]}