Re: [PATCH v2 09/11] commit-graph: merge commit-graph chains

2019-05-23 Thread Derrick Stolee
On 5/22/2019 8:43 PM, Ævar Arnfjörð Bjarmason wrote: > > On Wed, May 22 2019, Derrick Stolee via GitGitGadget wrote: > >> 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-

Re: [PATCH v2 09/11] commit-graph: merge commit-graph chains

2019-05-22 Thread Ævar Arnfjörð Bjarmason
On Wed, May 22 2019, Derrick Stolee via GitGitGadget wrote: > 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 condi

[PATCH v2 09/11] commit-graph: merge commit-graph chains

2019-05-22 Thread Derrick Stolee via GitGitGadget
From: Derrick Stolee 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