Re: [PATCH 1/1] commit-graph.c: avoid unnecessary tag dereference when merging

[Taylor Blau <me@ttaylorr.com>]

On Sun, Mar 22, 2020 at 01:36:35AM -0400, Jeff King wrote:
> On Sat, Mar 21, 2020 at 11:27:16AM -0600, Taylor Blau wrote:
>
> > > I'm not sure how to do that, though. Saying "--input=none" still puts
> > > all of those existing graphed objects into the list of oids to include.
> > > I think you'd need a case where you were legitimately only adding a few
> > > commits, but the merge rules say we need to create one big commit-graph
> > > file.
> >
> > You have to be careful, since we're taking the reachability closure over
> > any commits that you do give. So, one thing you could do to ensure that
> > you have an actually small graph is to take something from the output of
> > 'git rev-list --max-parents=0 HEAD'.
>
> I don't think you need to be that careful, though. In split-mode,
> close_reachable() will stop traversing when it finds a graphed commit.
> That's why using the tip of HEAD in my previous example worked.
>
> > To try and reproduce your results, I used '1da177e4c3', which is the
> > kernel's first commit in Git. If my interpretation of your setup is
> > faithful, it goes something like:
> >
> >   $ graphdir=.git/objects/info/commit-graphs
> >   $ git rev-parse 1da177e4c3 |
> >     git commit-graph write --split=no-merge --stdin-commits
> >   $ cp -r "$graphdir{,.bak}"
> >
> >   $ best-of-five -p "rm -rf $graphdir && cp -r $graphdir{.bak,}" \
> >     'git commit-graph write --split=merge-all'
>
> My case is the opposite, isn't it? Here it looks like you've made a very
> _tiny_ commit-graph file (with one commit), and then you're going to end
> up adding in all of the new objects. I don't think it would be improved
> much by this patch (which makes me very confused by the numbers you got
> below).
>
> I also don't think it's that interesting a real-world case.
>
> The more interesting one is where you do already have a big
> commit-graph, and want to add just a bit more to it. In the real world,
> that might look something like this:
>
>   # create a fake server repo
>   git clone --bare . dst.git
>
>   # imagine the server already has everything in a graph file
>   git -C dst.git commit-graph write --split=no-merge --reachable
>
>   # and now do a small push
>   git commit --allow-empty -m foo
>   git push dst.git
>
>   # the server might do an incremental immediately to cover the new
>   # objects; here we'll use --stdin-commits with the new data, but a
>   # real server might feed the new packfile. We'd probably just use
>   # regular --split here in practice, but let's imagine that we're
>   # starting to have a lot of graph files, and that triggers a desire to
>   # merge. We'll force that state with --split=merge-all.
>   git rev-list HEAD^..HEAD |
>   git -C dst.git commit-graph write --split=merge-all --stdin-commits
>
> Without your patch, that takes ~11s for me. With it, it takes ~2s.
>
> Another equally interesting case is if the per-push generation _doesn't_
> merge anything, and just creates a new, tiny graph file. And then later
> we want to do a real maintenance, merging them all done. I think that
> would be something like:
>
>   git -C dst.git commit-graph write --input=none --split=merge-all
>
> But that _isn't_ improved by your patch. For the simple reason that all
> of the commits will already have been parsed. The "--input=none" option
> isn't "no input"; it's actually "take all existing graphed objects as
> input" (i.e., it implies --append). So each of those objects will
> already have been examined in an earlier stage.
>
> > Where the last step is taking all commits listed in any pack, which is
> > cheap to iterate.
>
> I'm not sure it's all that cheap. It has to find the type of every
> object in every pack. And finding types involves walking delta chains.
> That's something like 7s on my machine for linux.git (compared to the 2s
> in which I can just merge down the existing graph files).
>
> > In the above setup, I get something like:
> >
> >   git version 2.26.0.rc2.221.ge327a58236
> >   Attempt 1: 16.933
> >   Attempt 2: 18.101
> >   Attempt 3: 17.603
> >   Attempt 4: 20.404
> >   Attempt 5: 18.871
> >
> >   real	0m16.933s
> >   user	0m16.440s
> >   sys	0m0.472s
> >
> > versus:
> >
> >   git version 2.26.0.rc2.222.g295e7905ee
> >   Attempt 1: 5.34
> >   Attempt 2: 4.623
> >   Attempt 3: 5.263
> >   Attempt 4: 5.268
> >   Attempt 5: 5.606
> >
> >   real	0m4.623s
> >   user	0m4.428s
> >   sys	0m0.176s
> >
> > which is a best-case savings of ~72.7%, and a savings of ~71.5%. That
> > seems much better.
>
> I'm still puzzled by this. In the setup you showed, hardly anything is
> graphed. But the change is only in the graph-merge code.

I agree with your reasoning. I tried to recreate these timings this
morning, and was unable to do so. Here's my setup (where 'git' is built
on the tip of 'next'):

  $ graphdir=".git/objects/info/commit-graphs"
  $ pack="pack-b10a98360eacb1f5a5ff67cb8d8113d8b3d0b39f.idx"
  $ rm -rf "$graphdir"
  $ git rev-list --max-parents=0 HEAD | tail -1 |
    git commit-graph write --input=stdin-commits --split=no-merge
  $ cp -r "$graphdir" "$graphdir.bak"

  $ git version
  git version 2.26.0.rc2.221.ge327a58236

  # repeat the below twice to ensure a warm cache
  $ rm -rf "$graphdir" && cp -r "$graphdir.bak" "$graphdir" &&
    echo "$pack" |
    sudo perf record -F 997 ~ttaylorr/bin/git commit-graph write \
      --split=merge-all --input=stdin-packs
  $ mv perf.data{,.base}

  $ git version
  git version 2.26.0.rc2.222.g1931b73955

  # do the above again, and mv perf.data{,.patch}

  $ sudo perf diff perf.data.base perf.data.patch
  # Event 'cpu-clock'
  #
  # Baseline    Delta  Shared Object       Symbol
  # ........  .......  ..................  ..........................................
  #
      18.42%   +0.34%  libc-2.24.so        [.] __memcmp_sse4_1
      15.50%   -0.45%  libz.so.1.2.8       [.] 0x00000000000083c9
       8.42%   -0.01%  libz.so.1.2.8       [.] inflate
       6.33%   +0.30%  libc-2.24.so        [.] __memmove_avx_unaligned_erms
       4.67%   -0.36%  git                 [.] lookup_object
       3.62%   -0.28%  git                 [.] unpack_object_header_buffer
       2.64%   +0.20%  git                 [.] commit_to_sha1
       2.41%   -0.03%  git                 [.] get_delta_base
       2.05%   -0.17%  git                 [.] sha1_compression_states
       2.00%   +0.06%  git                 [.] use_pack
       1.66%   +0.14%  git                 [.] nth_packed_object_offset
       1.63%   +0.11%  git                 [.] write_graph_chunk_extra_edges
       1.44%   +0.21%  libz.so.1.2.8       [.] adler32
       1.42%   -0.03%  git                 [.] sort_revindex
       1.42%   -0.06%  git                 [.] parse_commit_date
       1.41%   -0.15%  git                 [.] oidhash
       1.37%   +0.07%  git                 [.] commit_list_count
       1.11%   -0.02%  git                 [.] in_window
       1.08%   -0.05%  git                 [.] packed_to_object_type
       0.90%   -0.18%  git                 [.] ubc_check
       0.82%   -0.23%  git                 [.] hex2chr
       0.75%   -0.02%  git                 [.] hashcmp
       0.71%   +0.17%  libc-2.24.so        [.] msort_with_tmp.part.0
       0.70%   +0.25%  git                 [.] sha1_pos
       0.70%   +0.12%  git                 [.] repo_parse_commit_internal
       0.66%   -0.06%  git                 [.] bsearch_hash
       0.65%   -0.11%  git                 [.] compute_generation_numbers
       0.64%   +0.03%  git                 [.] unpack_object_header
       0.60%   -0.06%  git                 [.] find_entry_ptr
       0.59%   +0.09%  libc-2.24.so        [.] _int_malloc
       0.55%   -0.01%  git                 [.] hexval
       0.51%   +0.07%  git                 [.] entry_equals
       0.44%   +0.12%  git                 [.] get_sha1_hex
       0.41%   -0.13%  git                 [.] packed_object_info

...and many other functions that have a delta that can be attributed to
noise, all comfortably less than 1%.

So, I'm not sure what was going on with my original measurements, other
than that I took them around midnight, so the chance for error was
probably high. I'll go with your measurements, since they are both
closer to what we'd see in the real world, and actually representative
of the change here.

I'll wait for some of the discussion in the sub-thread about
'OBJECT_INFO_SKIP_FETCH' to settle, and then send v2 in the next couple
of days or so.

> -Peff

Thanks,
Taylor