Only create RoaringBitmaps for commits which are tags

Instead of creating a RoaringBitmap for every commit, we can lazily
create RoaringBitmaps when adding tags or refs. We also lazily create
a RoaringBitmap when copying bits to a parent commit that has not yet
had a RoaringBitmap created and the current commit is a tag tip.

Using this lazy approach we can save significant amounts of memory and
cache space for repositories that have many commits that are not tag or
ref tips. Most repositories likely fit this use case.

Change-Id: I51c8950e4252f1258950c2d02bd3a72f78cfbee0
Release-Notes: Reduced memory and storage needs for TagSet

1 files changed, 46 insertions, 13 deletions

diff --git a/java/com/google/gerrit/server/git/TagSet.java b/java/com/google/gerrit/server/git/TagSet.java
index a528c8fd60..9f155d0d05 100644
--- a/java/com/google/gerrit/server/git/TagSet.java
+++ b/java/com/google/gerrit/server/git/TagSet.java
@@ -14,6 +14,8 @@
 
 package com.google.gerrit.server.git;
 
+import static com.google.common.base.Preconditions.checkNotNull;
+
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.MoreObjects;
 import com.google.common.collect.ImmutableSet;
@@ -229,16 +231,37 @@ class TagSet {
         }
       }
 
-      // Traverse the complete history. Copy any flags from a commit to
-      // all of its ancestors. This automatically updates any Tag object
-      // as the TagCommit and the stored Tag object share the same
-      // underlying bit set.
+      // Traverse the complete history. Copy any flags from a commit to all of its ancestors. Do not
+      // maintain a reference to the flags on non-tag commits after copying their flags to their
+      // ancestors. The flag copying automatically updates any Tag object as the TagCommit and the
+      // stored Tag object share the same underlying RoaringBitmap.
       TagCommit c;
       while ((c = (TagCommit) rw.next()) != null) {
         RoaringBitmap mine = c.refFlags;
-        int pCnt = c.getParentCount();
-        for (int pIdx = 0; pIdx < pCnt; pIdx++) {
-          ((TagCommit) c.getParent(pIdx)).refFlags.or(mine);
+        if (mine != null) {
+          boolean isTag = tags.contains(c);
+          boolean canMoveBitmap = false;
+          if (!isTag) {
+            c.refFlags = null;
+            canMoveBitmap = true;
+          }
+          int pCnt = c.getParentCount();
+          for (int pIdx = 0; pIdx < pCnt; pIdx++) {
+            TagCommit commit = (TagCommit) c.getParent(pIdx);
+            RoaringBitmap parentFlags = commit.refFlags;
+            if (parentFlags == null) {
+              if (canMoveBitmap) {
+                // Move non-tag commit's bitmap reference to their first parent with null refFlags
+                // in order to reduce cloning overhead
+                commit.refFlags = mine;
+                canMoveBitmap = false;
+              } else {
+                commit.refFlags = mine.clone();
+              }
+            } else {
+              parentFlags.or(mine);
+            }
+          }
         }
       }
     } catch (IOException e) {
@@ -356,9 +379,7 @@ class TagSet {
     refs.putAll(old.refs);
 
     for (Tag srcTag : old.tags) {
-      RoaringBitmap mine = new RoaringBitmap();
-      mine.or(srcTag.refFlags);
-      tags.add(new Tag(srcTag, mine));
+      tags.add(new Tag(srcTag));
     }
 
     for (TagMatcher.LostRef lost : m.lostRefs) {
@@ -378,7 +399,11 @@ class TagSet {
     if (!tags.contains(id)) {
       RoaringBitmap flags;
       try {
-        flags = ((TagCommit) rw.parseCommit(id)).refFlags;
+        TagCommit commit = ((TagCommit) rw.parseCommit(id));
+        if (commit.refFlags == null) {
+          commit.refFlags = new RoaringBitmap();
+        }
+        flags = commit.refFlags;
       } catch (IncorrectObjectTypeException notCommit) {
         flags = new RoaringBitmap();
       } catch (IOException e) {
@@ -395,6 +420,9 @@ class TagSet {
       rw.markStart(commit);
 
       int flag = refs.size();
+      if (commit.refFlags == null) {
+        commit.refFlags = new RoaringBitmap();
+      }
       commit.refFlags.add(flag);
       refs.put(ref.getName(), new CachedRef(ref, flag));
     } catch (IncorrectObjectTypeException notCommit) {
@@ -432,8 +460,13 @@ class TagSet {
     // RoaringBitmap in TagCommit.refFlags.
     @VisibleForTesting final RoaringBitmap refFlags;
 
+    Tag(Tag src) {
+      this(src, src.refFlags.clone());
+    }
+
     Tag(AnyObjectId id, RoaringBitmap flags) {
       super(id);
+      checkNotNull(flags);
       this.refFlags = flags;
     }
 
@@ -485,13 +518,13 @@ class TagSet {
   }
 
   // TODO(hanwen): this would be better named as CommitWithReachability, as it also holds non-tags.
+  // However, non-tags will have a null refFlags field.
   private static final class TagCommit extends RevCommit {
     /** CachedRef.flag => isVisible, indicating if this commit is reachable from the ref. */
-    final RoaringBitmap refFlags;
+    RoaringBitmap refFlags;
 
     TagCommit(AnyObjectId id) {
       super(id);
-      refFlags = new RoaringBitmap();
     }
   }
 }