]> source.dussan.org Git - jgit.git/commit
Fix a GC scalability issue when selecting commit bitmaps 55/124955/5
authortparker <tparker@google.com>
Mon, 25 Jun 2018 03:00:55 +0000 (20:00 -0700)
committerTerry Parker <tparker@google.com>
Tue, 26 Jun 2018 16:23:46 +0000 (09:23 -0700)
commit2070d146cb5d5023d70cab6f3a8618b71e6fe5b4
tree2508ce42a8deeb0ead4147dcf79c97bb7759928f
parent34fb1d7d2156e19b6807e3d8f83f3f947fa6d3f3
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>
org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapPreparer.java