{"thread":{"id":"27811","subject":"Strange O(N^3) behavior in \"git filter-branch\"","startedAt":"2011-07-14T07:16:19Z","lastAt":"2011-08-03T19:37:40Z","messageCount":11,"participants":["Michael Haggerty","Junio C Hamano","Jeff King","Drew Northup","Jakub Narebski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"171309","messageId":"4E1E97C3.3030306@alum.mit.edu","threadId":"27811","inReplyTo":null,"subject":"Strange O(N^3) behavior in \"git filter-branch\"","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2011-07-14T07:16:19Z","receivedAt":"2011-07-14T07:16:19Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"I have noticed that \"git filter-branch\" gets pathologically slow when it\noperates on a repository that has many references in a complicated\ndirectory hierarchy.  The time seems to go like O(N^3), where N is the\nnumber of references being rewritten.\n\nI have attached a Python program that I have been using to explore this\nbehavior.  It creates a simple linear history with hardly any content\nbut one reference to each commit, then runs \"git-filter-branch\" on all\nbranches using a trivial tree-filter.\n\nThe times were taken using the \"maint\" version of git on a notebook\ncomputer with 4Gb of RAM running Linux 2.6.32.  The RAM usage never\nseemed to expand unusually.\n\nThe part that slows down is the part near the end where it writes\n\n    Ref 'foo' was rewritten\n    Ref 'bar' was rewritten\n    etc.\n\nThese lines come at ever-greater intervals and dominate the time for\nrunning git-filter-branch for N more than 1000 or so.  The time taken\nfor each iteration of this loop increases quadratically, so the time for\nthe whole run goes like N^3.  The time that the Nth line appears goes\napproximately like\n\n    254.954 + 0.0195578*N + 3.38276e-05*N^2 + 3.45833e-08*N^3\n\n; and the N^3 term starts to dominate around N=1000.  The 1000th step\ntakes about 270 ms.\n\nTo figure out where the time is going, I instrumented git-filter-branch\nas shown below, and found the blocks between \"1\" and \"2\", \"4b\" and \"5\",\nand \"5\" and 6\" each take about 90 ms (and therefore almost all of the time).\n\nThe slowdown seems to depend crucially on having a complicated hierarchy\nof references.  The bad case is lots of subdirectories, like\n\n    refs/heads/a0/b0/c0000\n    refs/heads/a1/b0/c0001\n    refs/heads/a2/b0/c0002\n    ...\n    refs/heads/a9/b9/c0999\n\n, where I have basically sharded the references based on their last two\ndigits.  (It is just as slow if the sharding is based on the most\nsignificant digits.)\n\nOn the other hand, if the refs are all in one directory (even a\nsubdirectory) like\n\n    refs/heads/a/b/c0000\n    refs/heads/a/b/c0001\n    ...\n    refs/heads/a/b/c0999\n\n, then the times go down dramatically, and appear to go from O(N^3) to\nO(N^2) (though O(N^2) still seems too slow for this loop!).\n\nIf the \"git pack-refs\" is omitted before \"git filter-branch\", then the\ntimes become considerably worse, though I have not done systematic tests\non this variation.\n\nI tried to reproduce the slowdown in a simpler scenario using various\nloops over \"git update-ref\", but have so far been unsuccessful.\nHowever, I have also observed a serious slowdown in the context of\nmaking lots of automated fixes to a git repository converted from\nSubversion (involving lots of calls to git-update-ref).  The slowdown in\nthis case could be largely mitigated by running \"git pack-refs\"\nperiodically, so it seems that the slowdown is related to the number of\nunpacked refs in complicated directory structures.  Unfortunately it\nwould not be trivial to insert \"git pack-refs\" in the \"git\nfilter-branch\" loop because the loop relies on the presence of unpacked\nreferences to \"avoid rewriting a ref twice\".\n\nDoes anybody have an idea?\n\nMichael\n\nInstrumented git-filter-branch:\n> while read ref\n> do\n> echo 0 @@@\n> \t# avoid rewriting a ref twice\n> \ttest -f \"$orig_namespace$ref\" && continue\n> \n> echo 1 @@@\n> \tsha1=$(git rev-parse \"$ref\"^0)\n> echo 2 @@@\n> \trewritten=$(map $sha1)\n> \n> echo 3 @@@\n> \ttest $sha1 = \"$rewritten\" &&\n> \t\twarn \"WARNING: Ref '$ref' is unchanged\" &&\n> \t\tcontinue\n> \n> echo 4 @@@\n> \tcase \"$rewritten\" in\n> \t'')\n> echo 4a @@@\n> \t\techo \"Ref '$ref' was deleted\"\n> \t\tgit update-ref -m \"filter-branch: delete\" -d \"$ref\" $sha1 ||\n> \t\t\tdie \"Could not delete $ref\"\n> \t;;\n> \t$_x40)\n> echo 4b @@@\n> \t\techo \"Ref '$ref' was rewritten\"\n> \t\tif ! git update-ref -m \"filter-branch: rewrite\" \\\n> \t\t\t\t\t\"$ref\" $rewritten $sha1 2>/dev/null; then\n> \t\t\tif test $(git cat-file -t \"$ref\") = tag; then\n> \t\t\t\tif test -z \"$filter_tag_name\"; then\n> \t\t\t\t\twarn \"WARNING: You said to rewrite tagged commits, but not the corresponding tag.\"\n> \t\t\t\t\twarn \"WARNING: Perhaps use '--tag-name-filter cat' to rewrite the tag.\"\n> \t\t\t\tfi\n> \t\t\telse\n> \t\t\t\tdie \"Could not rewrite $ref\"\n> \t\t\tfi\n> \t\tfi\n> \t;;\n> \t*)\n> echo 4c @@@\n> \t\t# NEEDSWORK: possibly add -Werror, making this an error\n> \t\twarn \"WARNING: '$ref' was rewritten into multiple commits:\"\n> \t\twarn \"$rewritten\"\n> \t\twarn \"WARNING: Ref '$ref' points to the first one now.\"\n> \t\trewritten=$(echo \"$rewritten\" | head -n 1)\n> \t\tgit update-ref -m \"filter-branch: rewrite to first\" \\\n> \t\t\t\t\"$ref\" $rewritten $sha1 ||\n> \t\t\tdie \"Could not rewrite $ref\"\n> \t;;\n> \tesac\n> echo 5 @@@\n> \tgit update-ref -m \"filter-branch: backup\" \"$orig_namespace$ref\" $sha1 ||\n> \t\t exit\n> echo 6 @@@\n> done < \"$tempdir\"/heads\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n\n\n#! /usr/bin/python\n\nimport sys\nimport os\nimport subprocess\nimport shutil\nimport time\n\n\nGIT_REPO = '/tmp/git-time-test'\nFILENAME1 = os.path.join(GIT_REPO, 'a.txt')\nFILENAME2 = os.path.join(GIT_REPO, 'b.txt')\n\n\nN = 3000\n\n\ndef run(*args, **kw):\n    if True:\n        sys.stderr.write('Running %s\\n' % (repr(args),))\n    subprocess.check_call(*args, cwd=GIT_REPO, **kw)\n\n\ndef get_refnames(*patterns):\n    cmd = ['git', 'for-each-ref', '--format=%(refname)'] + list(patterns)\n    if True:\n        sys.stderr.write('Running %s\\n' % (repr(cmd),))\n    p = subprocess.Popen(\n        cmd,\n        stdout=subprocess.PIPE,\n        cwd=GIT_REPO,\n        )\n    (out, err) = p.communicate()\n    return [l.strip() for l in out.splitlines()]\n\n\ndef get_name(i):\n    name = '%04d' % (i,)\n    #return 'refs/heads/b%s' % (name,)\n    return 'refs/heads/a/b/c%s' % (name,)\n    #return 'refs/heads/a%s/b%s/c%s' % (name[-1], name[-2], name,)\n\n\ndef make_repo():\n    if os.path.exists(GIT_REPO):\n        shutil.rmtree(GIT_REPO)\n\n    subprocess.check_call(['git', 'init', GIT_REPO])\n\n    run(['git', 'config', 'user.name', 'Lou User'])\n    run(['git', 'config', 'user.email', 'luser@example.com'])\n\n    open(FILENAME1, 'w')\n    run(['git', 'add', '-N', FILENAME1])\n\n    for i in range(N):\n        open(FILENAME1, 'w').write('%d\\n' % (i,))\n        run(['git', 'commit', '-a', '-m', 'Commit %d' % (i,)])\n        #run(['git', 'update-ref', 'refs/tags/%04d' % (i,), 'HEAD'])\n        run(['git', 'update-ref', get_name(i), 'HEAD'])\n\n\ndef pack_refs():\n    run(['git', 'pack-refs', '--all', '--prune'])\n\n\ndef filter():\n    run(['git', 'filter-branch', '--tree-filter', 'cp a.txt b.txt', '--', '--all'])\n\n\ndef add_refs():\n    refnames = get_refnames('refs/tags')\n\n    for refname in refnames:\n        assert not refname.endswith('master')\n        i = int(refname.rsplit('/', 1)[-1])\n        new_refname = get_name(i)\n        run(['git', 'update-ref', '-m', 'add ref', new_refname, refname])\n\n\ndef move_refs():\n    refnames = get_refnames('refs/tags')\n\n    for refname in refnames:\n        assert not refname.endswith('master')\n        i = int(refname.rsplit('/', 1)[-1])\n        new_refname = get_name(N - 1 - i)\n        run(['git', 'update-ref', '-m', 'move ref', new_refname, refname])\n\n\ndef main(args):\n    make_repo()\n    pack_refs()\n    t = time.time()\n    filter()\n    #add_refs()\n    #move_refs()\n    print 'time to process: %.3f s' % (time.time() - t,)\n\n\nmain(sys.argv[1:])\n\n"},{"id":"171311","messageId":"4E1EB5E9.1070902@alum.mit.edu","threadId":"27811","inReplyTo":"4E1E97C3.3030306@alum.mit.edu","subject":"Re: Strange O(N^3) behavior in \"git filter-branch\"","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2011-07-14T09:24:57Z","receivedAt":"2011-07-14T09:24:57Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 07/14/2011 09:16 AM, Michael Haggerty wrote:\n> I have noticed that \"git filter-branch\" gets pathologically slow when it\n> operates on a repository that has many references in a complicated\n> directory hierarchy.  The time seems to go like O(N^3), where N is the\n> number of references being rewritten.\n\nCorrection and new information...\n\nCorrection: The test script that I attached to the last email was\nconfigured incorrectly.  [Note to self: thunderbird reads attached files\nat the moment the email is *sent*, not the moment that the attachment is\nadded in the compose window.]  The corrected script is attached.\n\nNew information: Once I have \"primed\" a git repository using the\nattached script, a command like the following takes about 90 ms:\n\n    git rev-parse refs/heads/a4/b1/c0414^0\n\nstrace reveals that it is calling stat64() then lstat64() on every\ndirectory and every file under .git/refs.  By contrast,\n\n    git rev-parse refs/heads/a4/b1/c0414\n\ngoes more or less straight to the file\n.git/refs/tags/refs/heads/a4/b1/c0414, and finishes in a few milliseconds.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n\n\n#! /usr/bin/python\n\nimport sys\nimport os\nimport subprocess\nimport shutil\nimport time\n\n\nGIT_REPO = '/tmp/git-time-test'\nFILENAME1 = os.path.join(GIT_REPO, 'a.txt')\nFILENAME2 = os.path.join(GIT_REPO, 'b.txt')\n\n\nN = 1000\n\n#REF_STYLE = 'flat'\n#REF_STYLE = 'subdir'\nREF_STYLE = 'shard'\n\nACTION = 'filter'\n#ACTION = 'add_refs'\n#ACTION = 'move_refs'\n\nPACK_REFS = True\n\n\ndef run(*args, **kw):\n    if True:\n        sys.stderr.write('Running %s\\n' % (repr(args),))\n    subprocess.check_call(*args, cwd=GIT_REPO, **kw)\n\n\ndef get_refnames(*patterns):\n    cmd = ['git', 'for-each-ref', '--format=%(refname)'] + list(patterns)\n    if True:\n        sys.stderr.write('Running %s\\n' % (repr(cmd),))\n    p = subprocess.Popen(\n        cmd,\n        stdout=subprocess.PIPE,\n        cwd=GIT_REPO,\n        )\n    (out, err) = p.communicate()\n    return [l.strip() for l in out.splitlines()]\n\n\ndef get_name(i):\n    name = '%04d' % (i,)\n    if REF_STYLE == 'flat':\n        return 'refs/heads/b%s' % (name,)\n    elif REF_STYLE == 'subdir':\n        return 'refs/heads/a/b/c%s' % (name,)\n    elif REF_STYLE == 'shard':\n        return 'refs/heads/a%s/b%s/c%s' % (name[-1], name[-2], name,)\n\n\ndef make_repo():\n    if os.path.exists(GIT_REPO):\n        shutil.rmtree(GIT_REPO)\n\n    subprocess.check_call(['git', 'init', GIT_REPO])\n\n    run(['git', 'config', 'user.name', 'Lou User'])\n    run(['git', 'config', 'user.email', 'luser@example.com'])\n\n    open(FILENAME1, 'w')\n    run(['git', 'add', '-N', FILENAME1])\n\n    for i in range(N):\n        open(FILENAME1, 'w').write('%d\\n' % (i,))\n        run(['git', 'commit', '-a', '-m', 'Commit %d' % (i,)])\n        if ACTION != 'filter':\n            run(['git', 'update-ref', 'refs/tags/%04d' % (i,), 'HEAD'])\n        run(['git', 'update-ref', get_name(i), 'HEAD'])\n\n\ndef pack_refs():\n    run(['git', 'pack-refs', '--all', '--prune'])\n\n\ndef filter():\n    run(['git', 'filter-branch', '--tree-filter', 'cp a.txt b.txt', '--', '--all'])\n\n\ndef add_refs():\n    refnames = get_refnames('refs/tags')\n\n    for refname in refnames:\n        assert not refname.endswith('master')\n        i = int(refname.rsplit('/', 1)[-1])\n        new_refname = get_name(i)\n        run(['git', 'update-ref', '-m', 'add ref', new_refname, refname])\n\n\ndef move_refs():\n    refnames = get_refnames('refs/tags')\n\n    for refname in refnames:\n        assert not refname.endswith('master')\n        i = int(refname.rsplit('/', 1)[-1])\n        new_refname = get_name(N - 1 - i)\n        run(['git', 'update-ref', '-m', 'move ref', new_refname, refname])\n\n\ndef main(args):\n    make_repo()\n\n    if PACK_REFS:\n        pack_refs()\n\n    t = time.time()\n    if ACTION == 'filter':\n        filter()\n    elif ACTION == 'add_refs':\n        add_refs()\n    elif ACTION == 'move_refs':\n        move_refs()\n    print 'time to process: %.3f s' % (time.time() - t,)\n\n\nmain(sys.argv[1:])\n\n"},{"id":"171401","messageId":"4E200611.9010005@alum.mit.edu","threadId":"27811","inReplyTo":"4E1EB5E9.1070902@alum.mit.edu","subject":"Re: Strange O(N^3) behavior in \"git filter-branch\"","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2011-07-15T09:19:13Z","receivedAt":"2011-07-15T09:19:13Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 07/14/2011 11:24 AM, Michael Haggerty wrote:\n> On 07/14/2011 09:16 AM, Michael Haggerty wrote:\n>> I have noticed that \"git filter-branch\" gets pathologically slow when it\n>> operates on a repository that has many references in a complicated\n>> directory hierarchy.  The time seems to go like O(N^3), where N is the\n>> number of references being rewritten.\n> \n> New information: Once I have \"primed\" a git repository using the\n> attached script, a command like the following takes about 90 ms:\n> \n>     git rev-parse refs/heads/a4/b1/c0414^0\n> \n> strace reveals that it is calling stat64() then lstat64() on every\n> directory and every file under .git/refs.\n\nIt looks like the time is being taken up by attempted object\nreplacement.  The --no-replace-objects option makes the lookup fast again:\n\n$ time git rev-parse\nrefs/heads/a4/b1/c0414^0c9d42cb64d465f354c1fa6eea5825ebb6d0483a7\n\nreal\t0m0.093s\nuser\t0m0.064s\nsys\t0m0.032s\n$ time git --no-replace-objects rev-parse refs/heads/a4/b1/c0414^0\nc9d42cb64d465f354c1fa6eea5825ebb6d0483a7\n\nreal\t0m0.007s\nuser\t0m0.000s\nsys\t0m0.012s\n\nThe guilty code path is here:\n\n> #0  get_ref_dir (submodule=0x0, base=0x81384dd \"refs\", list=0x0) at refs.c:260\n> #1  0x080f8a63 in get_loose_refs (submodule=0x0) at refs.c:368\n> #2  0x080f912f in do_for_each_ref (submodule=0x0, base=<value optimized out>, fn=<value optimized out>, trim=13, flags=0, cb_data=0x0) at refs.c:663\n> #3  0x080f92db in for_each_replace_ref (fn=0x80fd1c0 <register_replace_ref>, cb_data=0x0) at refs.c:782\n> #4  0x080fd174 in prepare_replace_object (sha1=0xbfffde68 \"\\311\\324,\\266MF_5L\\037\\246^\\273m\\004\\203\\247\") at replace_object.c:86\n> #5  do_lookup_replace_object (sha1=0xbfffde68 \"\\311\\324,\\266MF_5L\\037\\246^\\273m\\004\\203\\247\") at replace_object.c:103\n> #6  0x080e7920 in lookup_replace_object (sha1=0xbfffde68 \"\\311\\324,\\266MF_5L\\037\\246^\\273m\\004\\203\\247\") at cache.h:774\n> #7  parse_object (sha1=0xbfffde68 \"\\311\\324,\\266MF_5L\\037\\246^\\273m\\004\\203\\247\") at object.c:191\n> #8  0x080bcf2a in lookup_commit_reference_gently (sha1=0xbfffde68 \"\\311\\324,\\266MF_5L\\037\\246^\\273m\\004\\203\\247\", quiet=0) at commit.c:30\n> #9  0x080bcf89 in lookup_commit_reference (sha1=0xbfffde68 \"\\311\\324,\\266MF_5L\\037\\246^\\273m\\004\\203\\247\") at commit.c:39\n> #10 0x0810e2a8 in get_parent (name=<value optimized out>, len=<value optimized out>, sha1=<value optimized out>) at sha1_name.c:456\n> #11 get_sha1_1 (name=<value optimized out>, len=<value optimized out>, sha1=<value optimized out>) at sha1_name.c:663\n> #12 0x0810e9dd in get_sha1_with_context_1 (name=0xbffff48c \"refs/heads/a4/b1/c0414^0\", sha1=0xbffff098 \"\\310\\360\\377\\277\\001C\\021\\b\\300\\265䷂\\364\\377\\277\", oc=0xbfffefec, only_to_die=0, prefix=0x0) at sha1_name.c:1123\n> #13 0x0810f290 in get_sha1_with_context (name=0xbffff48c \"refs/heads/a4/b1/c0414^0\", sha1=0xbffff098 \"\\310\\360\\377\\277\\001C\\021\\b\\300\\265䷂\\364\\377\\277\") at cache.h:824\n> #14 get_sha1 (name=0xbffff48c \"refs/heads/a4/b1/c0414^0\", sha1=0xbffff098 \"\\310\\360\\377\\277\\001C\\021\\b\\300\\265䷂\\364\\377\\277\") at sha1_name.c:987\n> #15 0x080a258a in cmd_rev_parse (argc=2, argv=0xbffff2a4, prefix=0x0) at builtin/rev-parse.c:715\n> #16 0x0804b917 in run_builtin (argc=<value optimized out>, argv=<value optimized out>) at git.c:302\n> #17 handle_internal_command (argc=<value optimized out>, argv=<value optimized out>) at git.c:460\n> #18 0x0804c00a in main (argc=2, argv=0xbffff2a4) at git.c:545\n\nThe replace_object machinery is causing the whole loose reference cache\nto be populated even though it is only interested in references under\nrefs/replace (which, in this case, doesn't even exist).\n\nA many possible improvements come to mind, in increasing order of\nintrusiveness and generality:\n\n0. Individual users can use --no-replace-objects or\nGIT_NO_REPLACE_OBJECTS to reduce their pain, especially when running\ngit-filter-branch.  But this is cumbersome and error-prone.\n\n1. Change git-filter-branch (and any other long-running commands?) to do\nan initial check for the presence of replace references (packed or\nloose), and if there are none, set GIT_NO_REPLACE_OBJECTS automatically.\n This would of course fail if any of the user's scripts try to set up\nreplace references.  (Side note: perhaps the git-replace command should\ncomplain if GIT_NO_REPLACE_OBJECTS is turned on?  It would almost always\nindicate a mistake.)  It also wouldn't help in repositories that *have*\nreplace references.\n\n2. Add an option to git-filter-branch to have it pack references\noccasionally.  This could even be made the default behavior if nobody\nobjects to having their references packed without their conscious decision.\n\n3. Optimize the specific case where there is no refs/replace\ndirectory--if this directory is missing, then defer populating the loose\nrefs cache in the hope that it will never be needed.\n\n4. Optimize reading of loose refs in general--change get_loose_refs() to\ntake a \"base\" parameter, and defer populating the loose refs cache if\nthe directory corresponding to \"base\" is absent.  This would salvage the\nworst cases, but would always force the whole loose refs cache to be\nread even in cases when only part of it is needed.\n\n5. Organize the loose refs cache in memory as a tree, and only populate\nthe parts of it that are accessed.  This should also speed up iteration\nthrough a subtree by avoiding a linear search through all loose references.\n\nUnfortunately, none of these improvements would change the fact that the\npacked refs always have to be read in full, and thus that *basically\nall* git commands scale like O(total number of references).  But packed\nrefs are so much faster than loose refs that this is probably acceptable.\n\nI'd be willing to work on this problem if I get a little bit of feedback\nfrom more experienced git developers about which approach would be\nacceptable / preferred.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"171416","messageId":"7vlivz1inu.fsf@alter.siamese.dyndns.org","threadId":"27811","inReplyTo":"4E200611.9010005@alum.mit.edu","subject":"Re: Strange O(N^3) behavior in \"git filter-branch\"","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-15T18:51:49Z","receivedAt":"2011-07-15T18:51:49Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> 1. Change git-filter-branch (and any other long-running commands?) to do\n> an initial check for the presence of replace references (packed or\n> loose), and if there are none, set GIT_NO_REPLACE_OBJECTS automatically.\n>  This would of course fail if any of the user's scripts try to set up\n> replace references.  (Side note: perhaps the git-replace command should\n> complain if GIT_NO_REPLACE_OBJECTS is turned on?  It would almost always\n> indicate a mistake.)  It also wouldn't help in repositories that *have*\n> replace references.\n\nIn the short term I think this makes sense, as the whole point of using\nfilter-branch in a repository that has grafts and replacements is so that\nthe resulting history won't have to look-aside into grafts and replace\ninformation.\n\nBut I think the replace-object codepath should be optimized to realize\nthere is no funky replacement (which _is_ a rare configuration) going on\nmuch early so that it does not incur that much overhead you observed. IOW,\nI tend to agree with your 3. below.\n\n> 2. Add an option to git-filter-branch to have it pack references\n> occasionally.\n\nDoesn't the code already do this via \"git gc\" though?\n\n> 3. Optimize the specific case where there is no refs/replace\n> directory--if this directory is missing, then defer populating the loose\n> refs cache in the hope that it will never be needed.\n"},{"id":"171442","messageId":"20110715212059.GA2117@sigill.intra.peff.net","threadId":"27811","inReplyTo":"7vlivz1inu.fsf@alter.siamese.dyndns.org","subject":"Re: Strange O(N^3) behavior in \"git filter-branch\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-15T21:20:59Z","receivedAt":"2011-07-15T21:20:59Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jul 15, 2011 at 11:51:49AM -0700, Junio C Hamano wrote:\n\n> But I think the replace-object codepath should be optimized to realize\n> there is no funky replacement (which _is_ a rare configuration) going on\n> much early so that it does not incur that much overhead you observed. IOW,\n> I tend to agree with your 3. below.\n> [...]\n> > 3. Optimize the specific case where there is no refs/replace\n> > directory--if this directory is missing, then defer populating the loose\n> > refs cache in the hope that it will never be needed.\n\nIt already tries to do so. It looks like it calls:\n\n  for_each_replace_ref(...)\n\nwhich calls:\n\n  do_for_each_ref(\"refs/replace\", ...)\n\nwhich reads _every_ loose ref, regardless of the prefix we have given\nit. So the optimization should go into the for_each_ref code, which\nshould avoid looking at parts of the hierarchy that are just going to be\nculled, no?\n\nAnd then we would see immediately that there is no refs/replace at all,\nand quit early. And as a bonus, things like \"for_each_tag_ref\" would get\nfaster in a repository with many branches, too.\n\n-Peff\n"},{"id":"171456","messageId":"4E212113.6000906@alum.mit.edu","threadId":"27811","inReplyTo":"20110715212059.GA2117@sigill.intra.peff.net","subject":"Re: Strange O(N^3) behavior in \"git filter-branch\"","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2011-07-16T05:26:43Z","receivedAt":"2011-07-16T05:26:43Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 07/15/2011 11:20 PM, Jeff King wrote:\n> On Fri, Jul 15, 2011 at 11:51:49AM -0700, Junio C Hamano wrote:\n>> But I think the replace-object codepath should be optimized to realize\n>> there is no funky replacement (which _is_ a rare configuration) going on\n>> much early so that it does not incur that much overhead you observed. IOW,\n>> I tend to agree with your 3. below.\n>> [...]\n>>> 3. Optimize the specific case where there is no refs/replace\n>>> directory--if this directory is missing, then defer populating the loose\n>>> refs cache in the hope that it will never be needed.\n> \n> It already tries to do so. It looks like it calls:\n> \n>   for_each_replace_ref(...)\n> \n> which calls:\n> \n>   do_for_each_ref(\"refs/replace\", ...)\n> \n> which reads _every_ loose ref, regardless of the prefix we have given\n> it. So the optimization should go into the for_each_ref code, which\n> should avoid looking at parts of the hierarchy that are just going to be\n> culled, no?\n\nThe way to implement the deferral of reading refs if for_each_ref() is\ncalled on an empty subtree (alternative 4 or 5 from my earlier email) is\nto change get_loose_refs() to take a base argument, have it check\nwhether the directory corresponding to base is empty, and if so return\nNULL without reading anything into the cache.\n\nCurrently, the loose ref cache is stored as a single linked list, so\nthere is no easy way to populate part of it now and part of it later.\nSo with the current data structure, the loose refs cache is\nall-or-nothing.  It would be possible to avoid filling it if there are\nnot replace references, but if there is even one loose replace reference\nthen the whole refs tree would have to be crawled.  Implementing this\nvariation is alternative 4 from the early email.\n\nMore flexible would be to change the way the loose ref cache is stored\nfrom a linked list into a tree (probably mirroring the directory tree).\n If this were done, then it would be possible to populate the cache\nlazily, only crawling the part of the refs tree that is needed for a\nparticular call of for_each_ref() and reusing any part of the cache that\nis already in memory.  This (alternative \"5\") is considerably more\ninvolved because the data structure has to be changed, but also\npotentially a much bigger win because the presence of a single reference\nin refs/replace would not force all of the refs/heads and refs/tags and\n... to be read.\n\n> And then we would see immediately that there is no refs/replace at all,\n> and quit early. And as a bonus, things like \"for_each_tag_ref\" would get\n> faster in a repository with many branches, too.\n\nOnly if the data structure used to hold the loose refs cache is changed...\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"171502","messageId":"1310909091.21563.23.camel@drew-northup.unet.maine.edu","threadId":"27811","inReplyTo":"4E212113.6000906@alum.mit.edu","subject":"Re: Strange O(N^3) behavior in \"git filter-branch\"","fromName":"Drew Northup","fromEmail":"drew.northup@maine.edu","sentAt":"2011-07-17T13:24:51Z","receivedAt":"2011-07-17T13:24:51Z","isPatch":false,"sender":{"key":"drew.northup@maine.edu","avatar":"https://avatars.githubusercontent.com/u/18331571?v=4"},"body":"\nOn Sat, 2011-07-16 at 07:26 +0200, Michael Haggerty wrote:\n\n> Currently, the loose ref cache is stored as a single linked list, so\n> there is no easy way to populate part of it now and part of it later.\n> So with the current data structure, the loose refs cache is\n> all-or-nothing.  It would be possible to avoid filling it if there are\n> not replace references, but if there is even one loose replace reference\n> then the whole refs tree would have to be crawled.  Implementing this\n> variation is alternative 4 from the early email.\n> \n> More flexible would be to change the way the loose ref cache is stored\n> from a linked list into a tree (probably mirroring the directory tree).\n\nGiven the potential for high performance inherent with trees, why mix\nmetaphors like this? What would the gain be?\n\n>  If this were done, then it would be possible to populate the cache\n> lazily, only crawling the part of the refs tree that is needed for a\n> particular call of for_each_ref() and reusing any part of the cache that\n> is already in memory.  \n\nIs this the argument for directory structure mirroring?\n\n-- \n-Drew Northup\n________________________________________________\n\"As opposed to vegetable or mineral error?\"\n-John Pescatore, SANS NewsBites Vol. 12 Num. 59\n"},{"id":"171566","messageId":"m3pql8yngt.fsf@localhost.localdomain","threadId":"27811","inReplyTo":"1310909091.21563.23.camel@drew-northup.unet.maine.edu","subject":"Re: Strange O(N^3) behavior in \"git filter-branch\"","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2011-07-18T08:59:19Z","receivedAt":"2011-07-18T08:59:19Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Drew Northup <drew.northup@maine.edu> writes:\n\n> On Sat, 2011-07-16 at 07:26 +0200, Michael Haggerty wrote:\n> \n> > Currently, the loose ref cache is stored as a single linked list, so\n> > there is no easy way to populate part of it now and part of it later.\n> > So with the current data structure, the loose refs cache is\n> > all-or-nothing.  It would be possible to avoid filling it if there are\n> > not replace references, but if there is even one loose replace reference\n> > then the whole refs tree would have to be crawled.  Implementing this\n> > variation is alternative 4 from the early email.\n> > \n> > More flexible would be to change the way the loose ref cache is stored\n> > from a linked list into a tree (probably mirroring the directory tree).\n> \n> Given the potential for high performance inherent with trees, why mix\n> metaphors like this? What would the gain be?\n\nDid you mean: \"why linked list\"?  I _guess_ that it is most probably\nbecause linked list is simpler and better known data structure than\nnon-binary tree.\n\nWhat is needed I think is something like trie[1], but with path\ncomponents and not letters stored in trie nodes.\n\n[1]: http://en.wikipedia.org/wiki/Trie\n \n> >  If this were done, then it would be possible to populate the cache\n> > lazily, only crawling the part of the refs tree that is needed for a\n> > particular call of for_each_ref() and reusing any part of the cache that\n> > is already in memory.  \n> \n> Is this the argument for directory structure mirroring?\n\n-- \nJakub Narębski\n"},{"id":"171581","messageId":"1311004870.18654.21.camel@drew-northup.unet.maine.edu","threadId":"27811","inReplyTo":"m3pql8yngt.fsf@localhost.localdomain","subject":"Re: Strange O(N^3) behavior in \"git filter-branch\"","fromName":"Drew Northup","fromEmail":"drew.northup@maine.edu","sentAt":"2011-07-18T16:01:10Z","receivedAt":"2011-07-18T16:01:10Z","isPatch":false,"sender":{"key":"drew.northup@maine.edu","avatar":"https://avatars.githubusercontent.com/u/18331571?v=4"},"body":"\nOn Mon, 2011-07-18 at 01:59 -0700, Jakub Narebski wrote:\n> Drew Northup <drew.northup@maine.edu> writes:\n> \n> > On Sat, 2011-07-16 at 07:26 +0200, Michael Haggerty wrote:\n> > \n> > > Currently, the loose ref cache is stored as a single linked list, so\n> > > there is no easy way to populate part of it now and part of it later.\n> > > So with the current data structure, the loose refs cache is\n> > > all-or-nothing.  It would be possible to avoid filling it if there are\n> > > not replace references, but if there is even one loose replace reference\n> > > then the whole refs tree would have to be crawled.  Implementing this\n> > > variation is alternative 4 from the early email.\n> > > \n> > > More flexible would be to change the way the loose ref cache is stored\n> > > from a linked list into a tree (probably mirroring the directory tree).\n> > \n> > Given the potential for high performance inherent with trees, why mix\n> > metaphors like this? What would the gain be?\n> \n> Did you mean: \"why linked list\"?  I _guess_ that it is most probably\n> because linked list is simpler and better known data structure than\n> non-binary tree.\n\nNo, that I can compute. I was asking why mix tree metaphors (pure\nbinary, R/B, and 234 being probably the most common kinds for the data\nstructure; and filesystem \"trees\"). In my mind I was thinking of\nSHA1sums as the keys (for some reason that doesn't occur to me right\nnow) and thought perhaps it was worth becoming enlightened (or\nsomething). Perhaps I should have looked harder in my mail queue for the\npatch referenced.\n\n> \n> What is needed I think is something like trie[1], but with path\n> components and not letters stored in trie nodes.\n> \n> [1]: http://en.wikipedia.org/wiki/Trie\n\nObviously, there are other \"tree\" structures. That's one I probably\nshould have thought of earlier.\n\n-- \n-Drew Northup\n________________________________________________\n\"As opposed to vegetable or mineral error?\"\n-John Pescatore, SANS NewsBites Vol. 12 Num. 59\n"},{"id":"172759","messageId":"4E394E33.4060107@alum.mit.edu","threadId":"27811","inReplyTo":"4E200611.9010005@alum.mit.edu","subject":"Re: Strange O(N^3) behavior in \"git filter-branch\"","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2011-08-03T13:33:39Z","receivedAt":"2011-08-03T13:33:39Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 07/15/2011 11:19 AM, Michael Haggerty wrote:\n> On 07/14/2011 11:24 AM, Michael Haggerty wrote:\n>> On 07/14/2011 09:16 AM, Michael Haggerty wrote:\n>>> I have noticed that \"git filter-branch\" gets pathologically slow when it\n>>> operates on a repository that has many references in a complicated\n>>> directory hierarchy.  The time seems to go like O(N^3), where N is the\n>>> number of references being rewritten.\n> [...]\n> A many possible improvements come to mind, in increasing order of\n> intrusiveness and generality:\n> [...]\n> 5. Organize the loose refs cache in memory as a tree, and only populate\n> the parts of it that are accessed.  This should also speed up iteration\n> through a subtree by avoiding a linear search through all loose references.\n\nFYI: I am working on (5), namely storing a linked list of loose refs for\neach directory and only populating those directories that are accessed.\n The directories themselves will be held in a tree/trie (AFAICT the\ndistinction is primarily whether each node holds its whole key or only\nthe part of the key relative to its parent, which is an implementation\ndetail).  As a bonus, the caches for submodules will be handled\ncorrectly (they are currently never used).\n\nIt might be another week or so before I have patches ready.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"172798","messageId":"20110803193740.GA23848@sigill.intra.peff.net","threadId":"27811","inReplyTo":"4E394E33.4060107@alum.mit.edu","subject":"Re: Strange O(N^3) behavior in \"git filter-branch\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-08-03T19:37:40Z","receivedAt":"2011-08-03T19:37:40Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 03, 2011 at 03:33:39PM +0200, Michael Haggerty wrote:\n\n> On 07/15/2011 11:19 AM, Michael Haggerty wrote:\n> > On 07/14/2011 11:24 AM, Michael Haggerty wrote:\n> >> On 07/14/2011 09:16 AM, Michael Haggerty wrote:\n> >>> I have noticed that \"git filter-branch\" gets pathologically slow when it\n> >>> operates on a repository that has many references in a complicated\n> >>> directory hierarchy.  The time seems to go like O(N^3), where N is the\n> >>> number of references being rewritten.\n> > [...]\n> > A many possible improvements come to mind, in increasing order of\n> > intrusiveness and generality:\n> > [...]\n> > 5. Organize the loose refs cache in memory as a tree, and only populate\n> > the parts of it that are accessed.  This should also speed up iteration\n> > through a subtree by avoiding a linear search through all loose references.\n> \n> FYI: I am working on (5), namely storing a linked list of loose refs for\n> each directory and only populating those directories that are accessed.\n>  The directories themselves will be held in a tree/trie (AFAICT the\n> distinction is primarily whether each node holds its whole key or only\n> the part of the key relative to its parent, which is an implementation\n> detail).  As a bonus, the caches for submodules will be handled\n> correctly (they are currently never used).\n> \n> It might be another week or so before I have patches ready.\n\nGreat. That is exactly the solution I was going to pursue, as well, but\nI didn't actually start on it yet. I look forward to seeing your\npatches.\n\n-Peff\n"}]}