summaryrefslogtreecommitdiff
path: root/t/perf/bisect_regression
diff options
context:
space:
mode:
authorLibravatar Derrick Stolee <dstolee@microsoft.com>2019-06-18 11:14:29 -0700
committerLibravatar Junio C Hamano <gitster@pobox.com>2019-06-19 20:46:26 -0700
commit1771be90c8e4797c2466296d1d570dbfa39d9743 (patch)
tree38e4ee534e905bd5a31cf7607eedbe48c5c6255c /t/perf/bisect_regression
parentcommit-graph: add --split option to builtin (diff)
downloadtgif-1771be90c8e4797c2466296d1d570dbfa39d9743.tar.xz
commit-graph: merge commit-graph chains
When searching for a commit in a commit-graph chain of G graphs with N commits, the search takes O(G log N) time. If we always add a new tip graph with every write, the linear G term will start to dominate and slow the lookup process. To keep lookups fast, but also keep most incremental writes fast, create a strategy for merging levels of the commit-graph chain. The strategy is detailed in the commit-graph design document, but is summarized by these two conditions: 1. If the number of commits we are adding is more than half the number of commits in the graph below, then merge with that graph. 2. If we are writing more than 64,000 commits into a single graph, then merge with all lower graphs. The numeric values in the conditions above are currently constant, but can become config options in a future update. As we merge levels of the commit-graph chain, check that the commits still exist in the repository. A garbage-collection operation may have removed those commits from the object store and we do not want to persist them in the commit-graph chain. This is a non-issue if the 'git gc' process wrote a new, single-level commit-graph file. After we merge levels, the old graph-{hash}.graph files are no longer referenced by the commit-graph-chain file. We will expire these files in a future change. Signed-off-by: Derrick Stolee <dstolee@microsoft.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 't/perf/bisect_regression')
0 files changed, 0 insertions, 0 deletions