{"thread":{"id":"60504","subject":"rev-list default order sometimes very slow (size and metadata dependent)","startedAt":"2023-11-11T16:46:38Z","lastAt":"2023-11-13T20:39:46Z","messageCount":2,"participants":["Kevin Lyles","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"484762","messageId":"DM6PR17MB247594CF3A0511EF95893935AEADA@DM6PR17MB2475.namprd17.prod.outlook.com","threadId":"60504","inReplyTo":null,"subject":"rev-list default order sometimes very slow (size and metadata dependent)","fromName":"Kevin Lyles","fromEmail":"klyles@epic.com","sentAt":"2023-11-11T16:17:17Z","receivedAt":"2023-11-11T16:46:38Z","isPatch":false,"sender":{"key":"klyles@epic.com","avatar":null},"body":"Hello,\n\n \n\nAs part of my company's migration from SVN to git, we discovered a\n\nperformance issue in rev-list with large repositories.  The issue appears to\n\nbe metadata-dependent; we were able to work around it (completely avoiding\n\nany performance penalty) by changing the date of certain commits.\n\n \n\nThe general structure of our repository is I think fairly normal (if large\n\n-- we have >5.5 million commits total).  We have a handful of trunk\n\nbranches, and ~10k total refs.  To reduce the ref count (we hit other\n\nperformance issues when we had significantly more refs), we remove refs as\n\nwe're done with them.  Any code that doesn't make it into a trunk is\n\npreserved in an archive branch.  The archive branch has no content, and\n\nconsists entirely of octopus merges with 50-500 parents.\n\n \n\nIf the archive branch is created with author/commit dates older than the\n\nrest of the repository, we're able to run:\n\n  $ git rev-list --count --all\n\nin ~9-10 seconds on a mirror clone with a commit-graph.  However, if the\n\narchive branch is instead created with author/commit dates newer than the\n\nrest of the repository, it takes 4-5 minutes.\n\n \n\nUsing any order other than the default or --reverse removes the disparity.\n\nAll orders except --author-date-order bring things much closer to the ~9-10\n\nseconds we see with the workaround, and --author-date-order is still under a\n\nminute (though not by much).\n\n \n\nSystem info from git bugreport:\n\n  [System Info]\n\n  git version:\n\n  git version 2.42.0.windows.2\n\n  cpu: x86_64\n\n  built from commit: 2f819d1670fff9a1818f63b6722e9959405378e3\n\n  sizeof-long: 4\n\n  sizeof-size_t: 8\n\n  shell-path: /bin/sh\n\n  feature: fsmonitor--daemon\n\n  uname: Windows 10.0 19044\n\n  compiler info: gnuc: 13.2\n\n  libc info: no libc information available\n\n  $SHELL (typically, interactive shell): C:\\Program Files\\Git\\usr\\bin\\bash.exe\n\n \n\n  (no enabled hooks)\n\n \n\nNote that we first realized this was an issue on our GitLab instance, which\n\nruns on Linux, so this is not a Windows-specific bug.\n\n \n\nI created a bash script to create very similar repositories that are/are not\n\naffected by the issue; it follows.  The issue starts to become visible at 1\n\nmillion commits (the default), where the difference is ~2x.  5 million\n\ncommits is roughly equivalent performance-wise to what we saw in our\n\nrepository, with a difference of ~33x.  Note that with 5 million commits,\n\neach repository is ~1.2 GB and takes 7-8 minutes to create on an i9-9900\n\nwith NVMe storage.\n\n \n\nOnce you create a fast and a slow repo with the script, try the following\n\ncommands in each one:\n\n  # Shows the performance difference\n\n  $ time git rev-list --count –all\n\n  # Shows very similar performance across both repos\n\n  $ time git rev-list --count --all --topo-order\n\n \n\nThank you,\n\nKevin Lyles\n\nklyles@epic.com <mailto:klyles@epic.com> \n\n----------------------------------------\n\n \n\n#!/bin/bash\n\n \n\nusage=\"Usage: $0 <destination folder> <--fast|--slow> [Number of commits (default: 1000000)]\"\n\ndestinationFolder=${1:?$usage}\n\n \n\noldTimestamp=315554400 # 1980-01-01 midnight\n\nnewTimestamp=1672552800 # 2023-01-01 midnight\n\nif [ \"$2\" == \"--fast\" ]\n\nthen\n\n    archiveTimestamp=$oldTimestamp\n\nelif [ \"$2\" == \"--slow\" ]\n\nthen\n\n    archiveTimestamp=$newTimestamp\n\nelse\n\n    echo \"$usage\" >&2\n\n    exit 1\n\nfi\n\n \n\nnumberOfCommits=${3:-1000000}\n\nif ! [[ \"$numberOfCommits\" =~ ^[0-9]+$ ]]\n\nthen\n\n    echo \"$usage\" >&2\n\n    exit 1\n\nfi\n\n \n\nincrement=$(( (newTimestamp - oldTimestamp) / (numberOfCommits + 2) ))\n\n \n\ntimestamp=$oldTimestamp\n\n \n\nrm -rf \"$destinationFolder\"\n\ngit init \"$destinationFolder\"\n\n \n\necho \"Fast-importing repo, please wait...\"\n\n{\n\n    echo \"feature done\"\n\n    echo \"reset refs/heads/main\"\n\n    echo \"\"\n\n \n\n    for count in $(seq \"$numberOfCommits\")\n\n    do\n\n        timestamp=$(( timestamp + increment ))\n\n        echo \"commit refs/heads/main\"\n\n        echo \"mark :$count\"\n\n        echo \"committer Test Test <test@test.com <mailto:test@test.com> > $timestamp -0500\"\n\n        echo \"data <<|\"\n\n        echo \"Main branch commit #$count\"\n\n        echo \"|\"\n\n        echo \"\"\n\n    done\n\n \n\n    parentMark=0\n\n    echo \"reset refs/archive\"\n\n    for count in $(seq $(( numberOfCommits / 1000 )))\n\n    do\n\n        echo \"commit refs/archive\"\n\n        echo \"committer Test Test <test@test.com <mailto:test@test.com> > $archiveTimestamp -0500\"\n\n        echo \"data <<|\"\n\n        echo \"Archive branch commit #$count\"\n\n        echo \"|\"\n\n        for parentCount in {1..50}\n\n        do\n\n            parentMark=$(( (parentMark + 99991) % numberOfCommits + 1 ))\n\n            echo \"merge :$parentMark\"\n\n        done\n\n        echo \"\"\n\n    done\n\n \n\n    echo \"done\"\n\n} | git -C \"$destinationFolder\" fast-import\n\n \n\ngit -C \"$destinationFolder\" commit-graph write\n\n"},{"id":"484813","messageId":"20231113203943.GD3838361@coredump.intra.peff.net","threadId":"60504","inReplyTo":"DM6PR17MB247594CF3A0511EF95893935AEADA@DM6PR17MB2475.namprd17.prod.outlook.com","subject":"Re: rev-list default order sometimes very slow (size and metadata dependent)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2023-11-13T20:39:43Z","receivedAt":"2023-11-13T20:39:46Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Nov 11, 2023 at 04:17:17PM +0000, Kevin Lyles wrote:\n\n> If the archive branch is created with author/commit dates older than the\n> rest of the repository, we're able to run:\n> \n>   $ git rev-list --count --all\n> \n> in ~9-10 seconds on a mirror clone with a commit-graph.  However, if the\n> archive branch is instead created with author/commit dates newer than the\n> rest of the repository, it takes 4-5 minutes.\n\nThanks for providing a reproduction script. I had trouble following the\ntext explanation, but I can easily reproduce the issue using your\nscript.\n\nRunning the slow case under perf, it looks like we are spending most of\nthe time in commit_list_insert_by_date(). Which makes sense. The queue\nof commits to visit during the traversal is kept as an ordered linked\nlist that uses linear search for the insertion. So the worst case to\ninsert N commits is quadratic.\n\nIn practice, it tends not to be a big problem because we visit commits\nin roughly reverse-timestamp order as we traverse. So it's more like\nO(N*width), where \"width\" is the average number of simultaneous lines of\nhistory. And your archive graph is...very wide.\n\nPlaying with the commit timestamps helps your case because it just\nhappens to reorder the queue in such a way that we put off looking at\nthose huge archive merges until much later in the traversal, when our\nremaining \"N\" is much smaller.\n\nThe right solution is obviously to switch to a better data structure.\nAnd some of the infrastructure is in place from the last time we dealt\nwith a similar case:\n\n  https://lore.kernel.org/git/HE1PR0702MB3788FCDAB764252D9CBB42E5B0560@HE1PR0702MB3788.eurprd07.prod.outlook.com/\n\nThere we started using a priority queue instead of the linked list.\nThat patch stopped shorting of replacing the main revs->commits\ntraversal list, though, as it's referenced in a ton of places (some of\nwhich really care about its list-like nature). Here's a hacky patch that\ntries to lazily convert the list to a queue. It makes your case much\nfaster, but it also causes a few failures in the test suite (related to\ncommit ordering), so obviously it's violating some assumptions\nsomewhere. I'm not sure if it's a fruitful direction or not.\n\nAnd as you noticed, using --topo-order does not suffer from the same\nproblem. It follows a completely different path, which...you guessed it,\nuses a priority queue. I'm not sure what the current state of things is,\nbut one of the promises of commit-graphs is that with stored generation\nnumbers, we could compute topo-order incrementally and efficiently. So\nanother possible route is that we'd simply enable it by default. But I'm\nnot sure if there's more work that needs to be done to get there, or if\nthere are other downsides.\n\ndiff --git a/revision.c b/revision.c\nindex 00d5c29bfc..62d33dbfee 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -3119,6 +3119,7 @@ void release_revisions(struct rev_info *revs)\n \tclear_decoration(&revs->treesame, free);\n \tline_log_free(revs);\n \toidset_clear(&revs->missing_commits);\n+\tclear_prio_queue(&revs->commitq);\n }\n \n static void add_child(struct rev_info *revs, struct commit *parent, struct commit *child)\n@@ -4161,6 +4162,36 @@ static void track_linear(struct rev_info *revs, struct commit *commit)\n \n static struct commit *get_revision_1(struct rev_info *revs)\n {\n+\t/*\n+\t * This is kind of hacky. We'll dynamically move commits from the\n+\t * linear list over to our priority queue, which has better worst-case\n+\t * behavior. Doing it here serves two purposes:\n+\t *\n+\t *   - we'll let all of the setup code still operate on the \"commits\"\n+\t *     list, and then just move it over to the queue lazily. This\n+\t *     probably could be done in prepare_revision_walk() or similar,\n+\t *     but by doing it here we know we're catching all code paths.\n+\t *\n+\t *   - we'll likewise catch any code which tries to add new commits to\n+\t *     the list _during_ the traversal. The main one would be\n+\t *     process_parents() below, which we've taught to use the queue\n+\t *     directly. But this will catch any other random bits of code,\n+\t *     including callers of the revision API, which add to the\n+\t *     traversal as they go.\n+\t *\n+\t * A cleaner solution would probably be to get rid of the \"commits\"\n+\t * list entirely, but that's a much bigger task.\n+\t */\n+\tif (revs->commits && !revs->topo_order) {\n+\t\tstruct commit_list *p;\n+\t\tif (!revs->unsorted_input)\n+\t\t\trevs->commitq.compare = compare_commits_by_commit_date;\n+\t\tfor (p = revs->commits; p; p = p->next)\n+\t\t\tprio_queue_put(&revs->commitq, p->item);\n+\t\tfree_commit_list(revs->commits);\n+\t\trevs->commits = NULL;\n+\t}\n+\n \twhile (1) {\n \t\tstruct commit *commit;\n \n@@ -4169,7 +4200,7 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\telse if (revs->topo_walk_info)\n \t\t\tcommit = next_topo_commit(revs);\n \t\telse\n-\t\t\tcommit = pop_commit(&revs->commits);\n+\t\t\tcommit = prio_queue_get(&revs->commitq);\n \n \t\tif (!commit)\n \t\t\treturn NULL;\n@@ -4191,7 +4222,7 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\t\t\ttry_to_simplify_commit(revs, commit);\n \t\t\telse if (revs->topo_walk_info)\n \t\t\t\texpand_topo_walk(revs, commit);\n-\t\t\telse if (process_parents(revs, commit, &revs->commits, NULL) < 0) {\n+\t\t\telse if (process_parents(revs, commit, NULL, &revs->commitq) < 0) {\n \t\t\t\tif (!revs->ignore_missing_links)\n \t\t\t\t\tdie(\"Failed to traverse parents of commit %s\",\n \t\t\t\t\t\toid_to_hex(&commit->object.oid));\ndiff --git a/revision.h b/revision.h\nindex 94c43138bc..4301b825a0 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -12,6 +12,7 @@\n #include \"ident.h\"\n #include \"list-objects-filter-options.h\"\n #include \"strvec.h\"\n+#include \"prio-queue.h\"\n \n /**\n  * The revision walking API offers functions to build a list of revisions\n@@ -124,6 +125,12 @@ struct rev_info {\n \tstruct object_array pending;\n \tstruct repository *repo;\n \n+\t/*\n+\t * We'll use this queue during the actual traversal, rather than\n+\t * adding and popping from the \"commits\" list.\n+\t */\n+\tstruct prio_queue commitq;\n+\n \t/* Parents of shown commits */\n \tstruct object_array boundary_commits;\n \n"}]}