{"thread":{"id":"6773","subject":"[RFC] Speeding up a null fetch","startedAt":"2007-02-11T23:32:13Z","lastAt":"2007-02-12T00:18:29Z","messageCount":5,"participants":["Julian Phillips","Johannes Schindelin","Shawn O. Pearce"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"34211","messageId":"200702112332.14698.julian@quantumfyre.co.uk","threadId":"6773","inReplyTo":null,"subject":"[RFC] Speeding up a null fetch","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2007-02-11T23:32:13Z","receivedAt":"2007-02-11T23:32:13Z","isPatch":false,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"I was investigating replacing an existing subversion setup with git, and\nwas mostly pleased with the results - until it came to trying to update a\nclone ... which took very much longer than the original clone.\n\nAn artifical test repository that has similar features (~25000 commits,\n~8000 tags, ~900 branches and a 2.5Gb packfile) when running locally\ntakes ~20m to clone and ~48m to fetch (with no new commits in the\noriginal repository - i.e. the fetch does not update anything) with a\ncurrent code base (i.e. newer than 1.5.0-rc4). As a side note,\nperformance was actually better with an older version - packed refs\nmakes things quite a bit worse (clone was only ~30m with 1.4 IIRC).\n\nInvestigation showed that the main culprit seemed to be show-ref\nhaving to build a sorted list of all refs for every ref that was being\nchecked. So I used the patch below to reduce this to a single call to\nshow-ref (unless the ref had been updated). With this patch the fetch\ntimed dropped to just under 1m - obviously quite a lot faster (better\nthan I expected in fact).\n\nHowever, this seems more band-aid than fix, and I wondered if someone\nmore familiar with the git internals could point me in the right\ndirection for a better fix, e.g. should I look at rewriting fetch in C?\n\ndiff --git a/Makefile b/Makefile\nindex 5d31e6d..6baf043 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -120,7 +120,7 @@ ALL_CFLAGS = $(CFLAGS)\n ALL_LDFLAGS = $(LDFLAGS)\n STRIP ?= strip\n \n-prefix = $(HOME)\n+prefix = $(HOME)/git\n bindir = $(prefix)/bin\n gitexecdir = $(bindir)\n template_dir = $(prefix)/share/git-core/templates/\n@@ -188,7 +188,7 @@ SCRIPT_PERL = \\\n \n SCRIPTS = $(patsubst %.sh,%,$(SCRIPT_SH)) \\\n \t $(patsubst %.perl,%,$(SCRIPT_PERL)) \\\n-\t git-cherry-pick git-status git-instaweb\n+\t git-cherry-pick git-status git-instaweb git-ref-diff.py\n \n # ... and all the rest that could be moved out of bindir to gitexecdir\n PROGRAMS = \\\ndiff --git a/git-fetch.sh b/git-fetch.sh\nindex 357cac2..ce135a5 100755\n--- a/git-fetch.sh\n+++ b/git-fetch.sh\n@@ -108,11 +108,12 @@ ls_remote_result=$(git ls-remote $exec \"$remote\") ||\n \n append_fetch_head () {\n head_=\"$1\"\n- remote_=\"$2\"\n- remote_name_=\"$3\"\n- remote_nick_=\"$4\"\n- local_name_=\"$5\"\n- case \"$6\" in\n+ local_head_=\"$2\"\n+ remote_=\"$3\"\n+ remote_name_=\"$4\"\n+ remote_nick_=\"$5\"\n+ local_name_=\"$6\"\n+ case \"$7\" in\n t) not_for_merge_='not-for-merge' ;;\n '') not_for_merge_= ;;\n esac\n@@ -151,10 +152,15 @@ append_fetch_head () {\n \techo \"$head_\tnot-for-merge\t$note_\" >>\"$GIT_DIR/FETCH_HEAD\"\n fi\n \n- update_local_ref \"$local_name_\" \"$head_\" \"$note_\"\n+ update_local_ref \"$local_name_\" \"$head_\" \"$note_\" \"$local_head_\"\n }\n \n update_local_ref () {\n+ if [ \"$2\" == \"$4\" ]; then\n+\t[ \"$verbose\" ] && echo >&2 \"* $1: same as $3\"\n+\treturn 0\n+ fi\n+\n # If we are storing the head locally make sure that it is\n # a fast forward (aka \"reverse push\").\n \n@@ -392,7 +398,7 @@ fetch_main () {\n (\n \t git-fetch-pack --thin $exec $keep $shallow_depth \"$remote\" $rref ||\n \t echo failed \"$remote\"\n- ) |\n+ ) | git-ref-diff.py \"$reflist\" |\n (\n \ttrap '\n \t\tif test -n \"$keepfile\" && test -f \"$keepfile\"\n@@ -402,7 +408,7 @@ fetch_main () {\n \t' 0\n \n keepfile=\n-\twhile read sha1 remote_name\n+\twhile read sha1 remote_name local_sha1\n \tdo\n \t case \"$sha1\" in\n \t failed)\n@@ -441,7 +447,7 @@ fetch_main () {\n \t esac\n \t done\n \t local_name=$(expr \"z$found\" : 'z[^:]*:\\(.*\\)')\n-\t append_fetch_head \"$sha1\" \"$remote\" \\\n+\t append_fetch_head \"$sha1\" \"$local_sha1\" \"$remote\" \\\n \t\t \"$remote_name\" \"$remote_nick\" \"$local_name\" \\\n \t\t \"$not_for_merge\" || exit\n done\ndiff --git a/git-ref-diff.py b/git-ref-diff.py\nnew file mode 100755\nindex 0000000..2b30e4c\n--- /dev/null\n+++ b/git-ref-diff.py\n@@ -0,0 +1,33 @@\n+#!/usr/bin/python\n+\n+import os\n+import re\n+import sys\n+\n+ref_map_re = re.compile(\"^\\.?\\+?(?P.*?):(?P.*)$\")\n+\n+refs = {}\n+refsp = os.popen(\"git-show-ref\")\n+for ref in refsp.readlines():\n+ (sha, ref) = ref.strip().split(' ')\n+ refs[ref] = sha\n+refsp.close()\n+\n+ref_map = {}\n+for line in sys.argv[1].split('\\n'):\n+ ref_map_m = ref_map_re.search(line)\n+ if ref_map_m:\n+ remote = ref_map_m.group('remote')\n+ local = ref_map_m.group('local')\n+ ref_map[remote] = local\n+\n+while True:\n+ try:\n+ (sha, ref) = raw_input().split(' ')\n+ except EOFError:\n+ sys.exit(0)\n+ lref = ref_map.get(ref, None)\n+ if refs.has_key(lref):\n+ print \"%s %s %s\" % (sha, ref, refs[lref])\n+ else:\n+ print \"%s %s -\" % (sha, ref)\n\n-- \nJulian\n\n --- \nWhy bother building any more nuclear warheads until we use the ones we have?\n"},{"id":"34216","messageId":"Pine.LNX.4.63.0702120045320.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"6773","inReplyTo":"200702112332.14698.julian@quantumfyre.co.uk","subject":"Re: [RFC] Speeding up a null fetch","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-02-11T23:49:56Z","receivedAt":"2007-02-11T23:49:56Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 11 Feb 2007, Julian Phillips wrote:\n\n> An artifical test repository that has similar features (~25000 commits,\n> ~8000 tags, ~900 branches and a 2.5Gb packfile) when running locally\n> takes ~20m to clone and ~48m to fetch (with no new commits in the\n> original repository - i.e. the fetch does not update anything) with a\n> current code base (i.e. newer than 1.5.0-rc4).\n\nOuch.\n\nI hope you packed the refs?\n\nBTW your patch\n- was not minimal (and therefore it takes longer than necessary to find \n what you actually fixed),\n- it does not show where and how the call to show-ref is avoided (I \n eventually understand that you avoid calling update_local_ref early, but \n you sure could have made that easier), and\n- it uses Pythong.\n\nAlso, it touches a quite core part of git, which will hopefully be \nreplaced by a builtin _after_ 1.5.0.\n\n> However, this seems more band-aid than fix, and I wondered if someone \n> more familiar with the git internals could point me in the right \n> direction for a better fix, e.g. should I look at rewriting fetch in C?\n\nLook into the \"pu\" branch of git. There are the beginnings of a builtin \n(written in C) fetch.\n\nBut this _will_ have to wait until after 1.5.0.\n\nCiao,\nDscho\n"},{"id":"34218","messageId":"20070211235218.GH31488@spearce.org","threadId":"6773","inReplyTo":"200702112332.14698.julian@quantumfyre.co.uk","subject":"Re: [RFC] Speeding up a null fetch","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-02-11T23:52:18Z","receivedAt":"2007-02-11T23:52:18Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Julian Phillips wrote:\n> Investigation showed that the main culprit seemed to be show-ref\n> having to build a sorted list of all refs for every ref that was being\n> checked. So I used the patch below to reduce this to a single call to\n> show-ref (unless the ref had been updated). With this patch the fetch\n> timed dropped to just under 1m - obviously quite a lot faster (better\n> than I expected in fact).\n\nHave a look at the `pu` branch in git.git. Junio has done some\nwork in this area to handle 1000 refs better:\n\n ...\n commit 58fef67cb067b6dee8f94b7b0e0c1a2d324e3505\n Author: Junio C Hamano \n Date: Tue Jan 16 02:31:36 2007 -0800\n\n git-fetch: rewrite another shell loop in C\n \n Move another shell loop that canonicalizes the list of refs for\n underlying git-fetch-pack and fetch-native-store into C.\n \n This seems to shave the runtime for the same 1000 branch\n repository from 30 seconds down to 15 seconds (it used to be 2\n and half minutes with the original version).\n \n Signed-off-by: Junio C Hamano \n\n commit 3fc3729cd08e9d40dad54ccdd4db53900eca197b\n Author: Junio C Hamano \n Date: Tue Jan 16 01:53:29 2007 -0800\n\n git-fetch: move more code into C.\n \n This adds \"native-store\" subcommand to git-fetch--tool to\n move a huge loop implemented in shell into C. This shaves about\n 70% of the runtime to fetch and update 1000 tracking branches\n with a single fetch.\n \n Signed-off-by: Junio C Hamano \n ...\n\n> However, this seems more band-aid than fix, and I wondered if someone\n> more familiar with the git internals could point me in the right\n> direction for a better fix, e.g. should I look at rewriting fetch in C?\n\nRewriting fetch in C is a lot of work, not just in developing it,\nbut in testing that all existing functionality is preserved and no\nnew bugs are introduced. Rewriting some of the performance critical\nparts perhaps makes sense. Rewriting them in Python doesn't, as\nwe no longer have any Python dependency, and would like to keep it\nthat way (actuallly, some folks are also trying to remove the Perl\ndependency from some of our critical tools).\n\n-- \nShawn.\n"},{"id":"34223","messageId":"Pine.LNX.4.64.0702120005530.5695@beast.quantumfyre.co.uk","threadId":"6773","inReplyTo":"Pine.LNX.4.63.0702120045320.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [RFC] Speeding up a null fetch","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2007-02-12T00:14:12Z","receivedAt":"2007-02-12T00:14:12Z","isPatch":false,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"On Mon, 12 Feb 2007, Johannes Schindelin wrote:\n\n> Hi,\n>\n> On Sun, 11 Feb 2007, Julian Phillips wrote:\n>\n>> An artifical test repository that has similar features (~25000 commits,\n>> ~8000 tags, ~900 branches and a 2.5Gb packfile) when running locally\n>> takes ~20m to clone and ~48m to fetch (with no new commits in the\n>> original repository - i.e. the fetch does not update anything) with a\n>> current code base (i.e. newer than 1.5.0-rc4).\n>\n> Ouch.\n>\n> I hope you packed the refs?\n\nUnfortunately packing only makes things slower ... as it then becomes \nimpossible to directly access a particular ref directly, which some of the \ncalls to show-ref do.\n\n>\n> BTW your patch\n> - was not minimal (and therefore it takes longer than necessary to find\n> what you actually fixed),\n> - it does not show where and how the call to show-ref is avoided (I\n> eventually understand that you avoid calling update_local_ref early, but\n> you sure could have made that easier), and\n\nAh yes, sorry. I seem to have managed to forget to include the paragraph \nexplaining what I had done ... :$\n\n(That'll teach me to trying doing too many things at once.)\n\n> - it uses Pythong.\n>\n> Also, it touches a quite core part of git, which will hopefully be\n> replaced by a builtin _after_ 1.5.0.\n\nIndeed, I would never propose what I have done so far as a fix. I am \ndefinitely still in the investigation phase.\n\n>\n>> However, this seems more band-aid than fix, and I wondered if someone\n>> more familiar with the git internals could point me in the right\n>> direction for a better fix, e.g. should I look at rewriting fetch in C?\n>\n> Look into the \"pu\" branch of git. There are the beginnings of a builtin\n> (written in C) fetch.\n\nAh - this I didn't know. I shall have to have a play with that, I did \nnotice that there is internal caching of the ref list that might magically \nsolve the problem if fetch was a builtin (but I have a feeling that it \nwon't be that simple).\n\n>\n> But this _will_ have to wait until after 1.5.0.\n\nI hope so. 1.5 is looking very nice, and I really don't think that many \npeople have such a stuipdly large repository ...\n\n>\n> Ciao,\n> Dscho\n>\n\n-- \nJulian\n\n ---\nYou are in a maze of little twisting passages, all alike.\n"},{"id":"34225","messageId":"Pine.LNX.4.64.0702120014510.5695@beast.quantumfyre.co.uk","threadId":"6773","inReplyTo":"20070211235218.GH31488@spearce.org","subject":"Re: [RFC] Speeding up a null fetch","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2007-02-12T00:18:29Z","receivedAt":"2007-02-12T00:18:29Z","isPatch":false,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"On Sun, 11 Feb 2007, Shawn O. Pearce wrote:\n\n> Julian Phillips wrote:\n>> Investigation showed that the main culprit seemed to be show-ref\n>> having to build a sorted list of all refs for every ref that was being\n>> checked. So I used the patch below to reduce this to a single call to\n>> show-ref (unless the ref had been updated). With this patch the fetch\n>> timed dropped to just under 1m - obviously quite a lot faster (better\n>> than I expected in fact).\n>\n> Have a look at the `pu` branch in git.git. Junio has done some\n> work in this area to handle 1000 refs better:\n>\n> ...\n> commit 58fef67cb067b6dee8f94b7b0e0c1a2d324e3505\n> Author: Junio C Hamano \n> Date: Tue Jan 16 02:31:36 2007 -0800\n>\n> git-fetch: rewrite another shell loop in C\n>\n> Move another shell loop that canonicalizes the list of refs for\n> underlying git-fetch-pack and fetch-native-store into C.\n>\n> This seems to shave the runtime for the same 1000 branch\n> repository from 30 seconds down to 15 seconds (it used to be 2\n> and half minutes with the original version).\n>\n> Signed-off-by: Junio C Hamano \n>\n> commit 3fc3729cd08e9d40dad54ccdd4db53900eca197b\n> Author: Junio C Hamano \n> Date: Tue Jan 16 01:53:29 2007 -0800\n>\n> git-fetch: move more code into C.\n>\n> This adds \"native-store\" subcommand to git-fetch--tool to\n> move a huge loop implemented in shell into C. This shaves about\n> 70% of the runtime to fetch and update 1000 tracking branches\n> with a single fetch.\n>\n> Signed-off-by: Junio C Hamano \n> ...\n>\n\nI shall have to see how this work fares with ~9000 refs ... but it \ncertainly sounds good.\n\n>> However, this seems more band-aid than fix, and I wondered if someone\n>> more familiar with the git internals could point me in the right\n>> direction for a better fix, e.g. should I look at rewriting fetch in C?\n>\n> Rewriting fetch in C is a lot of work, not just in developing it,\n> but in testing that all existing functionality is preserved and no\n> new bugs are introduced. Rewriting some of the performance critical\n> parts perhaps makes sense.\n\nIndeed - this is why I asked rather than just diving in.\n\n> Rewriting them in Python doesn't, as\n> we no longer have any Python dependency, and would like to keep it\n> that way (actuallly, some folks are also trying to remove the Perl\n> dependency from some of our critical tools).\n\nI only used python for speed of development, I was simply trying to verify \nmy suspicions. I certainly wouldn't expect a python script to get added \n(having seen all the python scripts get replaced).\n\n-- \nJulian\n\n ---\nThere are no accidents whatsoever in the universe.\n \t\t-- Baba Ram Dass\n"}]}