{"action":"created","issue":{"url":"https://api.github.com/repos/gitgitgadget/git/issues/89","repository_url":"https://api.github.com/repos/gitgitgadget/git","labels_url":"https://api.github.com/repos/gitgitgadget/git/issues/89/labels{/name}","comments_url":"https://api.github.com/repos/gitgitgadget/git/issues/89/comments","events_url":"https://api.github.com/repos/gitgitgadget/git/issues/89/events","html_url":"https://github.com/gitgitgadget/git/pull/89","id":385467003,"node_id":"MDExOlB1bGxSZXF1ZXN0MjM0NDMyMDM2","number":89,"title":"Add a new \"sparse\" tree walk algorithm","user":{"login":"derrickstolee","id":570044,"node_id":"MDQ6VXNlcjU3MDA0NA==","avatar_url":"https://avatars0.githubusercontent.com/u/570044?v=4","gravatar_id":"","url":"https://api.github.com/users/derrickstolee","html_url":"https://github.com/derrickstolee","followers_url":"https://api.github.com/users/derrickstolee/followers","following_url":"https://api.github.com/users/derrickstolee/following{/other_user}","gists_url":"https://api.github.com/users/derrickstolee/gists{/gist_id}","starred_url":"https://api.github.com/users/derrickstolee/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/derrickstolee/subscriptions","organizations_url":"https://api.github.com/users/derrickstolee/orgs","repos_url":"https://api.github.com/users/derrickstolee/repos","events_url":"https://api.github.com/users/derrickstolee/events{/privacy}","received_events_url":"https://api.github.com/users/derrickstolee/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":5,"created_at":"2018-11-28T21:36:11Z","updated_at":"2018-12-10T16:43:45Z","closed_at":null,"author_association":"NONE","pull_request":{"url":"https://api.github.com/repos/gitgitgadget/git/pulls/89","html_url":"https://github.com/gitgitgadget/git/pull/89","diff_url":"https://github.com/gitgitgadget/git/pull/89.diff","patch_url":"https://github.com/gitgitgadget/git/pull/89.patch"},"body":"One of the biggest remaining pain points for users of very large repositories is the time it takes to run 'git push'. We inspected some slow pushes by our developers and found that the \"Enumerating Objects\" phase of a push was very slow. This is unsurprising, because this is why reachability bitmaps exist. However, reachability bitmaps are not available to us because of the single pack-file requirement. The bitmap approach is intended for servers anyway, and clients have a much different behavior pattern.\r\n\r\nSpecifically, clients are normally pushing a very small number of objects compared to the entire working directory. A typical user changes only a small cone of the working directory, so let's use that to our benefit.\r\n\r\nCreate a new \"sparse\" mode for 'git pack-objects' that uses the paths that introduce new objects to direct our search into the reachable trees. By collecting trees at each path, we can then recurse into a path only when there are uninteresting _and_ interesting trees at that path. This gains a significant performance boost for small topics while presenting a possibility of packing extra objects.\r\n\r\nThe main algorithm change is in patch 4, but is set up a little bit in patches 1 and 2.\r\n\r\nAs demonstrated in the included test script, we see that the existing algorithm can send extra objects due to the way we specify the \"frontier\". But we can send even more objects if a user copies objects from one folder to another. I say \"copy\" because a rename would (usually) change the original folder and trigger a walk into that path, discovering the objects.\r\n\r\nIn order to benefit from this approach, the user can opt-in using the pack.useSparse config setting. This setting can be overridden using the '--no-sparse' option.\r\n\r\nUpdate in V2: \r\n* Added `GIT_TEST_PACK_SPARSE` test option.\r\n* Fixed test breakages when `GIT_TEST_PACK_SPARSE` is enabled by adding null checks.\r\n\r\nUpdate in V3:\r\n* Change documentation around 'pack.useSparse' config setting to better advertise to users.\r\n*  Mostly a ping now that v2.20.0 is out.\r\n\r\nCc: peff@peff.net, avarab@gmail.com, jrnieder@gmail.com"},"comment":{"url":"https://api.github.com/repos/gitgitgadget/git/issues/comments/445884108","html_url":"https://github.com/gitgitgadget/git/pull/89#issuecomment-445884108","issue_url":"https://api.github.com/repos/gitgitgadget/git/issues/89","id":445884108,"node_id":"MDEyOklzc3VlQ29tbWVudDQ0NTg4NDEwOA==","user":{"login":"gitgitgadget[bot]","id":39766333,"node_id":"MDM6Qm90Mzk3NjYzMzM=","avatar_url":"https://avatars3.githubusercontent.com/in/12836?v=4","gravatar_id":"","url":"https://api.github.com/users/gitgitgadget%5Bbot%5D","html_url":"https://github.com/apps/gitgitgadget","followers_url":"https://api.github.com/users/gitgitgadget%5Bbot%5D/followers","following_url":"https://api.github.com/users/gitgitgadget%5Bbot%5D/following{/other_user}","gists_url":"https://api.github.com/users/gitgitgadget%5Bbot%5D/gists{/gist_id}","starred_url":"https://api.github.com/users/gitgitgadget%5Bbot%5D/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gitgitgadget%5Bbot%5D/subscriptions","organizations_url":"https://api.github.com/users/gitgitgadget%5Bbot%5D/orgs","repos_url":"https://api.github.com/users/gitgitgadget%5Bbot%5D/repos","events_url":"https://api.github.com/users/gitgitgadget%5Bbot%5D/events{/privacy}","received_events_url":"https://api.github.com/users/gitgitgadget%5Bbot%5D/received_events","type":"Bot","site_admin":false},"created_at":"2018-12-10T16:43:45Z","updated_at":"2018-12-10T16:43:45Z","author_association":"NONE","body":"Submitted as [pull.89.v3.git.gitgitgadget@gmail.com](https://public-inbox.org/git/pull.89.v3.git.gitgitgadget@gmail.com)"}}
{"actor":{"display_login":"gitgitgadget"}}