[PATCH v2 0/7] speed up pack-objects counting with many packs

[Jeff King <peff@peff.net>]

This is a follow-up to the patches in

  http://public-inbox.org/git/20160725184938.GA12871@sigill.intra.peff.net/

that are currently queued in jk/pack-objects-optim-skimming. Roughly,
they try to optimize a loop that is O(nr_objects * nr_packs) by breaking
out early in some cases.

I had written those patches a while ago and confirmed that they did
speed up a particular nasty case I had. But when I tried to write a
t/perf test to show off the improvement, I found that they didn't help!
The reason is that the optimizations are heavily dependent on the order
of the packs, and which objects go in which pack. The loop has the same
worst-case complexity as it always did, but we rely on getting lucky to
break out early.

I think the perf test I've included here is more representative of a
real-world workloads, and with an extra optimization, I was able to show
good numbers with it.

The general strategy is to order the pack lookups in most-recently-used
order. This replaces an existing 1-element MRU cache in the normal pack
lookup code, and replaces a straight reverse-chronological iteration in
pack-objects.

All credit for thinking of this scheme goes to Michael Haggerty, who
suggested the idea to me about six months ago. It seemed like a lot of
work at the time, so I didn't do it. :) But as I started to implement
the same 1-element cache in pack-objects, I found that the code actually
gets rather awkward. The MRU solution makes the callers easier to read,
and of course it turns out to be faster, to boot.

Anyway, enough chit-chat. The patches are:

  [1/7]: t/perf: add tests for many-pack scenarios
  [2/7]: sha1_file: drop free_pack_by_name
  [3/7]: add generic most-recently-used list
  [4/7]: find_pack_entry: replace last_found_pack with MRU cache
  [5/7]: pack-objects: break out of want_object loop early
  [6/7]: pack-objects: compute local/ignore_pack_keep early
  [7/7]: pack-objects: use mru list when iterating over packs

The actual optimizations are in patches 4 and 7, which have their own
numbers. But here are end-to-end numbers for the series against the tip
of master (for the meanings, see the discussion in patch 1, and the
analysis in 4 and 7):

[p5303, linux.git]
Test                      origin                HEAD
-------------------------------------------------------------------------
5303.3: rev-list (1)      31.48(31.20+0.27)     31.18(30.95+0.22) -1.0%
5303.4: repack (1)        40.74(39.27+2.56)     40.30(38.96+2.47) -1.1%
5303.6: rev-list (50)     31.65(31.38+0.26)     31.26(31.02+0.23) -1.2%
5303.7: repack (50)       60.90(71.03+2.13)     46.95(57.46+1.85) -22.9%
5303.9: rev-list (1000)   38.63(38.25+0.37)     31.91(31.61+0.28) -17.4%
5303.10: repack (1000)    392.52(467.09+5.05)   87.38(159.98+2.92) -77.7%

[p5303, git.git]
Test                      origin              HEAD
---------------------------------------------------------------------
5303.3: rev-list (1)      1.55(1.54+0.00)     1.56(1.54+0.01) +0.6%
5303.4: repack (1)        1.83(1.82+0.06)     1.82(1.82+0.05) -0.5%
5303.6: rev-list (50)     1.58(1.56+0.02)     1.58(1.57+0.00) +0.0%
5303.7: repack (50)       2.50(3.16+0.04)     2.32(2.92+0.09) -7.2%
5303.9: rev-list (1000)   2.64(2.61+0.02)     2.23(2.21+0.01) -15.5%
5303.10: repack (1000)    12.68(19.07+0.30)   7.51(13.86+0.20) -40.8%

For curiosity, I also ran the git.git case with 10,000 packs. This is
even more silly, but it shows that the problem does get worse and worse
as the number grows, but that the patches do continue to help:

Test                        origin               HEAD
-------------------------------------------------------------------------
5303.12: rev-list (10,000)  26.00(25.86+0.13)    15.76(15.62+0.13) -39.4%
5303.13: repack (10,000)   164.11(175.30+1.34)   51.48(62.96+1.18) -68.6%

-Peff