From 087b5051ff9f53eb7b0106568d5a9eb2d86180c4 Mon Sep 17 00:00:00 2001 From: Jonathan Nieder Date: Sat, 7 Nov 2015 11:53:25 -0800 Subject: [PATCH] Skip redundant 'OR-reuse' step in tip commit bitmap setup When creating bitmaps during gc, the bitmaps in tipCommitBitmaps are built in setupTipCommitBitmaps using the following procedure: 0. create a bitmap ('reuse') that lists all ancestors of commits whose existing bitmaps will be reused. I will call this the reused part of history. 1. initialize a bitmap for each of the pack's "want"s by taking a copy of the 'reuse' bitmap and setting the bit corresponding to the one wanted commit. 2. walk through ancestors of wants, excluding the reused part of history. Add parents of visited commits to bitmaps that have those commits. 3. AND-NOT each tipCommitBitmap against the 'reuse' bitmap 4. Sort the bitmaps and AND-NOT each against the previous so they partition the new commits. The OR against 'reuse' in step 1 and the AND-NOT against 'reuse' cancel each other out, except when commits from the reused part of history are added to a bitmap in step 2. So avoid adding commits from the reused part of history in step 2 and skip the OR and AND-NOT. Performance impact (thanks to Terry for measuring): The initial "selecting bitmaps" phase of garbage collection decreased from (83 + 81 + 85) / 3 = 83 to (56 + 57 + 56) / 3 = 56.3, meaning nearly a ~50% speedup of that phase. Tested-by: Terry Parker Change-Id: I26ea695809594347575d14a1d8e6721b8608eb9c --- .../storage/pack/PackWriterBitmapPreparer.java | 11 +++-------- 1 file changed, 3 insertions(+), 8 deletions(-) diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapPreparer.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapPreparer.java index 86669f6b39..63da518795 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapPreparer.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/PackWriterBitmapPreparer.java @@ -410,7 +410,6 @@ class PackWriterBitmapPreparer { rw.markStart(rc); BitmapBuilder bitmap = commitBitmapIndex.newBitmapBuilder(); - bitmap.or(reuse); bitmap.addObject(rc, Constants.OBJ_COMMIT); tipCommitBitmaps.add(new BitmapBuilderEntry(rc, bitmap)); } @@ -430,19 +429,15 @@ class PackWriterBitmapPreparer { continue; } for (RevCommit c : rc.getParents()) { + if (reuse.contains(c)) { + continue; + } bitmap.addObject(c, Constants.OBJ_COMMIT); } } pm.update(1); } - // Remove the reused bitmaps from the tip commit bitmaps - if (!reuseCommits.isEmpty()) { - for (BitmapBuilderEntry entry : tipCommitBitmaps) { - entry.getBuilder().andNot(reuse); - } - } - // Sort the tip commit bitmaps. Find the one containing the most // commits, remove those commits from the remaining bitmaps, resort and // repeat. -- 2.39.5