[RFC PATCH 0/6] Better threaded delta resolution in index-pack

[Jonathan Tan <jonathantanmy@google.com>]

Quoting myself [1]:

> index-pack does parallelize delta resolution, but
> it cannot split up trees into threads: each delta base root can go into
> its own thread, but when a delta base root is processed, all deltas on
> that root (direct or indirect) is processed in the same thread.

This is a problem when a repository contains a large text file (thus,
delta-able) that is modified many times - delta resolution time during
fetching is dominated by processing the deltas corresponding to that
text file. Here are patches that teach index-pack to better divide up
the work.

As an example of the effect, when cloning using

  git -c core.deltabasecachelimit=1g clone \
    https://fuchsia.googlesource.com/third_party/vulkan-cts

on my laptop, clone time improved from 3m2s to 2m5s (using 3 threads,
which is the default).

As you can see from the diff stats, my new algorithm uses comparable
lines of code to the existing one, but I think that it is a bit more
complicated. My main point of difficulty was in handling the delta base
cache - it must be GC-able, but at the same time available to another
thread if it was being used as a base to inflate a delta. In the end,
what I did was to make individual mutex-guarded refcounts for each
inflation result, but the buffer itself is not mutex-guarded: so a
thread could increment the refcount within the mutex, inflate (and
verify) outside the mutex, and then decrement the refcount within the
mutex. (One global mutex guards all the refcounts, as well as other
things.) Any ideas for making this design less complicated is
appreciated.

If this is a good direction, let me know and I'll refine the patches. I
personally think that the improvement in performance is worth the slight
added complexity. Also, in this patch set, I did some cleanup to make
future patches clearer, but some of the cleanup is undone by the future
patches themselves; let me know if it's easier to review if I should
squash those patches.

Also CC-ing Mike Hommey because Mike brought up a repo with a similar
case [2], although that case happens during repack.

[1] https://public-inbox.org/git/20190926003300.195781-1-jonathantanmy@google.com/
[2] https://public-inbox.org/git/20190704100530.smn4rpiekwtfylhz@glandium.org/

Jonathan Tan (6):
  index-pack: unify threaded and unthreaded code
  index-pack: remove redundant parameter
  index-pack: remove redundant child field
  index-pack: calculate {ref,ofs}_{first,last} early
  index-pack: make resolve_delta() assume base data
  index-pack: make quantum of work smaller

 builtin/index-pack.c | 375 ++++++++++++++++++++-----------------------
 1 file changed, 177 insertions(+), 198 deletions(-)

-- 
2.23.0.581.g78d2f28ef7-goog