From 733780e8a158b7bc45b8b687ac353ecadc905a63 Mon Sep 17 00:00:00 2001 From: "Shawn O. Pearce" Date: Wed, 16 Feb 2011 17:41:35 -0800 Subject: [PATCH] PackWriter: Sort commits by parse order to improve locality RevWalk in JGit and the revision code in C Git both parse commits out of the pack file in an order that differs from strict timestamp and topological sorting. Both implementations pop a commit from the head of a date queue, and then immediately parse all of its parents in order to insert those into the date queue at the proper positions as determined by their committer timestamp field. This implies that the parents are parsed when their most recent child is popped from the queue, and not where they are popped during traversal. Hoisting a parent commit to be immediately behind its child improves locality by making sure all parents of a merge are clustered together, and thus can be paged into the parser by the pack file buffering system (aka WindowCache in JGit) together. Change-Id: I80f9e64cafa2e8f082776b43845edf23065386a2 Signed-off-by: Shawn O. Pearce --- .../eclipse/jgit/storage/pack/PackWriter.java | 41 ++++++++++++++----- 1 file changed, 31 insertions(+), 10 deletions(-) diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java index b8b2767677..f28f222c0f 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/pack/PackWriter.java @@ -1116,6 +1116,7 @@ public class PackWriter { final Map tipToPack = new HashMap(); final RevFlag inCachedPack = walker.newFlag("inCachedPack"); final RevFlag include = walker.newFlag("include"); + final RevFlag added = walker.newFlag("added"); final RevFlagSet keepOnRestart = new RevFlagSet(); keepOnRestart.add(inCachedPack); @@ -1177,13 +1178,15 @@ public class PackWriter { int typesToPrune = 0; final int maxBases = config.getDeltaSearchWindowSize(); Set baseTrees = new HashSet(); - RevObject o; - while ((o = walker.next()) != null) { - if (o.has(inCachedPack)) { - CachedPack pack = tipToPack.get(o); + List commits = new ArrayList(); + RevCommit c; + while ((c = walker.next()) != null) { + if (c.has(inCachedPack)) { + CachedPack pack = tipToPack.get(c); if (includesAllTips(pack, include, walker)) { useCachedPack(walker, keepOnRestart, // wantObjs, haveObjs, pack); + commits = new ArrayList(); countingMonitor.endTask(); countingMonitor.beginTask(JGitText.get().countingObjects, @@ -1192,16 +1195,36 @@ public class PackWriter { } } - if (o.has(RevFlag.UNINTERESTING)) { + if (c.has(RevFlag.UNINTERESTING)) { if (baseTrees.size() <= maxBases) - baseTrees.add(((RevCommit) o).getTree()); + baseTrees.add(c.getTree()); continue; } - addObject(o, 0); + commits.add(c); countingMonitor.update(1); } + if (objectsLists[Constants.OBJ_COMMIT] instanceof ArrayList) { + ArrayList list = (ArrayList) objectsLists[Constants.OBJ_COMMIT]; + list.ensureCapacity(list.size() + commits.size()); + } + for (RevCommit cmit : commits) { + if (!cmit.has(added)) { + cmit.add(added); + addObject(cmit, 0); + } + + for (int i = 0; i < cmit.getParentCount(); i++) { + RevCommit p = cmit.getParent(i); + if (!p.has(added) && !p.has(RevFlag.UNINTERESTING)) { + p.add(added); + addObject(p, 0); + } + } + } + commits = null; + for (CachedPack p : cachedPacks) { for (ObjectId d : p.hasObject(objectsLists[Constants.OBJ_COMMIT])) { if (baseTrees.size() <= maxBases) @@ -1213,6 +1236,7 @@ public class PackWriter { BaseSearch bases = new BaseSearch(countingMonitor, baseTrees, // objectsMap, edgeObjects, reader); + RevObject o; while ((o = walker.nextObject()) != null) { if (o.has(RevFlag.UNINTERESTING)) continue; @@ -1284,9 +1308,6 @@ public class PackWriter { for (ObjectId id : pack.getTips()) baseObj.add(walker.lookupOrNull(id)); - objectsMap.clear(); - objectsLists[Constants.OBJ_COMMIT] = new ArrayList(); - setThin(true); walker.resetRetain(keepOnRestart); walker.sort(RevSort.TOPO); -- 2.39.5