From: Derrick Stolee Date: Tue, 10 Apr 2018 19:18:20 GMT Subject: Re: [PATCH v8 03/14] commit-graph: add format document Message-ID: In-Reply-To: On 4/10/2018 3:10 PM, Stefan Beller wrote: > Hi Derrick, > > On Tue, Apr 10, 2018 at 5:55 AM, Derrick Stolee wrote: > >> + OID Fanout (ID: {'O', 'I', 'D', 'F'}) (256 * 4 bytes) >> + The ith entry, F[i], stores the number of OIDs with first >> + byte at most i. Thus F[255] stores the total >> + number of commits (N). > I was about to give this series one last read not expecting any questions > to come up (this series has had a lot of feedback already!) > Although I just did. > > What were your design considerations for the fanout table? > Did you include it as the pack index has one or did you come up with > them from first principles? > Have you measured the performance impact of the fanout table > (maybe even depending on the size of the fanout) ? > > context: > https://public-inbox.org/git/CAJo=hJsto1ik=GTC8c3+2_jBuUqcAPL0UWp-1uoYYMpgbLB+qg@mail.gmail.com/ > (side note: searching the web for fanout makes it seem > as if it is git-lingo, apparently the term is not widely used) > > I don't think we want to restart the design discussion, > I am just curious. I knew that I wanted some amount of a fanout table, and the 256-entry one was used for IDX files (and in my MIDX RFC). With the recent addition of "packfile: refactor hash search with fanout table" [1] it is probably best to keep the 256-entry table to reduce code clones. As for speed, we have the notion of 'graph_pos' which gives random access into the commit-graph after a commit is loaded as a parent of a commit from the commit-graph file. Thus, we are spending time in the binary search only for commits that do not exist in the commit-graph file and those that are first found in the file. Thus, running profilers on long commit-graph walks do not show any measurable time spent in 'bsearch_graph()'. Thanks, -Stolee [1] https://github.com/gitster/git/commit/b4e00f7306a160639f047b3421985e8f3d0c6fb1