Fix a GC scalability issue when selecting commit bitmaps
The previous algorithm selected commits by creating bitmaps at
each branch tip, doing a revwalk to populate each bitmap, and
looping in this way:
1) Select the remaining branch with the most commits (the branch
whose bitmap has the highest cardinality)
2) Select well-spaced bitmaps in that branch
3) Remove commits in the selected branch from the remaining
branch-tip bitmaps
4) Repeat at #1
This algorithm gave good commit selection on all branches but
a more uniform selection on "important" branches, where branch
length is the proxy for "important". However the algorithm
required N bitmaps of size M solely for the purpose of commit
selection, where N is the number of branch tips in the primary
GC pack, and M is the number of objects in the pack.
This new algorithm uses branch modification date as the proxy for
"important" branches, replacing the N*M memory allocation with a
single M-sized bitmap and N revwalks from new branch tips to
shared history (which will be short when there is a lot of shared
history).
GcCommitSelectionTest.testDistributionOnMultipleBranches verifies
that this algorithm still yields good coverage on all branches.
Change-Id: Ib6019b102b67eabb379e6b85623e4b5549590e6e Signed-off-by: Terry Parker <tparker@google.com>