[JGIT PATCH 00/18] Misc. performance tweaks

[JGIT PATCH 00/18] Misc. performance tweaks

[Shawn O. Pearce]

Cloning linux-2.6.git through JGit was painful at best.  I found
and fixed some small bottlenecks after a day of profiling and
experimentation, but we're still slower than C git.

With this series I managed to drop the time for "git clone --bare"
over git:// using "jgit daemon" server and "C git" client.
Any difference between jgit and "C git" is in the server side.

  before:  7m42.488s
  after :  2m33.882s
  C git :  1m26.158s     ("git daemon" server)


So I'm still seeing a major bottleneck that I can't quite fix.

Object enumeration (aka "Counting ...") takes too long, because we
spend a huge amount of time unpacking delta chains for trees so we
can enumerate their referenced items.

Our UnpackedObjectCache gets <4% hit ratio when doing the trees
for linux-2.6.git.  Increasing the cache doesn't have a noticable
improvement on performance.

I tried rewriting UnpackedObjectCache to permit multiple objects
per hash bucket.  Even with that (and the maximum chain length
per bucket not exceeding 4 items) our hit ratio was still <5%,
so I tossed that implementation out.

"jgit rev-list --objects" vs. "git rev-list --objects" is a huge
difference, about 1m difference.  That's most of the time difference
I noted above between jgit and C git on the server side.

So with this series, we're better.  Its actually almost tolerable
to clone linux-2.6 through a jgit backed server.


Shawn O. Pearce (23):
  Improve hit performance on the UnpackedObjectCache
  Add MutableObjectId.clear() to set the id to zeroId
  Allow TreeWalk callers to pass a MutableObjectId to get the current
    id
  Switch ObjectWalk to use the new MutableObjectId form in TreeWalk
  Change walker based fetch to use TreeWalk's MutableObjectId accessor
  Reduce garbage allocation when using TreeWalk
  Switch ObjectWalk to use a naked CanonicalTreeParser because its
    faster
  Remove the unused PackFile.get(ObjectId) form
  Remove getId from ObjectLoader API as its unnecessary overhead
  Make mmap mode more reliable by forcing GC at the correct spot
  Rewrite WindowCache to use a hash table
  Change ByteArrayWindow to read content outside of WindowCache's lock
  Dispose of RevCommit buffers when they aren't used in PackWriter
  Don't unpack delta chains while writing a pack from a pack v1 index
  Don't unpack delta chains while converting delta to whole object
  Defer parsing of the ObjectId while walking a PackIndex Iterator
  Only do one getCachedBytes per whole object written
  Correctly use a long for the offsets within a generated pack
  Allow more direct access to determine isWritten
  Move "wantWrite" field of ObjectToPack into the flags field
  Use an ArrayList for the reuseLoader collection in PackWriter
  Don't cut off existing delta chains if we are reusing deltas
  Correctly honor the thin parameter to PackWriter.writePack

 .../jgit/pgm/opt/AbstractTreeIteratorHandler.java  |    6 +-
 .../tst/org/spearce/jgit/lib/PackIndexTest.java    |    4 +-
 .../tst/org/spearce/jgit/lib/PackWriterTest.java   |   14 +-
 .../tst/org/spearce/jgit/lib/T0004_PackReader.java |    4 +-
 .../jgit/errors/CorruptObjectException.java        |   12 +
 .../src/org/spearce/jgit/lib/ByteArrayWindow.java  |   31 ++
 .../src/org/spearce/jgit/lib/ByteBufferWindow.java |   17 +
 .../src/org/spearce/jgit/lib/ByteWindow.java       |   20 ++-
 .../src/org/spearce/jgit/lib/Constants.java        |    2 +-
 .../spearce/jgit/lib/DeltaPackedObjectLoader.java  |    3 +-
 .../src/org/spearce/jgit/lib/MutableObjectId.java  |    9 +
 .../src/org/spearce/jgit/lib/ObjectLoader.java     |   38 ---
 .../src/org/spearce/jgit/lib/PackFile.java         |   49 +---
 .../src/org/spearce/jgit/lib/PackIndex.java        |   48 ++--
 .../src/org/spearce/jgit/lib/PackIndexV1.java      |   20 +-
 .../src/org/spearce/jgit/lib/PackIndexV2.java      |   27 +-
 .../src/org/spearce/jgit/lib/PackWriter.java       |   63 +++--
 .../src/org/spearce/jgit/lib/Repository.java       |   29 +--
 .../org/spearce/jgit/lib/UnpackedObjectCache.java  |   21 +-
 .../org/spearce/jgit/lib/UnpackedObjectLoader.java |   12 +-
 .../spearce/jgit/lib/WholePackedObjectLoader.java  |    3 +-
 .../src/org/spearce/jgit/lib/WindowCache.java      |  323 ++++++++++++--------
 .../src/org/spearce/jgit/lib/WindowCursor.java     |   16 +
 .../src/org/spearce/jgit/lib/WindowedFile.java     |   61 +++--
 .../src/org/spearce/jgit/revwalk/ObjectWalk.java   |   51 ++--
 .../src/org/spearce/jgit/revwalk/RevWalk.java      |    8 +-
 .../spearce/jgit/transport/PackedObjectInfo.java   |    2 +-
 .../src/org/spearce/jgit/transport/UploadPack.java |    1 +
 .../jgit/transport/WalkFetchConnection.java        |   48 ++-
 .../jgit/treewalk/AbstractTreeIterator.java        |   48 +++
 .../spearce/jgit/treewalk/CanonicalTreeParser.java |   85 +++++-
 .../src/org/spearce/jgit/treewalk/TreeWalk.java    |   88 +++++-
 .../spearce/jgit/util/CountingOutputStream.java    |    5 +-
 33 files changed, 752 insertions(+), 416 deletions(-)

[JGIT PATCH 01/23] Improve hit performance on the UnpackedObjectCache

[Shawn O. Pearce]

If the JVM cleared one of our SoftReferences we "leaked" the space in
the cache that the entry occupied.  Over time this meant we lost room
in the cache and didn't have a way to recover that when we replaced
the evicted entry.

The hash function was also too complex for the hit ratio we were
getting.  The old function on one of my linux-2.6 clones was giving
us <7% hit ratio; this new function is a little simpler to compute
and is getting ~11%.  Increasing the size of the hash table helps
matters considerably.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../org/spearce/jgit/lib/UnpackedObjectCache.java  |   21 +++++++++----------
 1 files changed, 10 insertions(+), 11 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectCache.java b/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectCache.java
index ee6a680..677b3a7 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectCache.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectCache.java
@@ -40,17 +40,14 @@
 import java.lang.ref.SoftReference;
 
 class UnpackedObjectCache {
-	private static final int CACHE_SZ = 256;
+	private static final int CACHE_SZ = 1024;
 
 	private static final int MB = 1024 * 1024;
 
 	private static final SoftReference<Entry> DEAD;
 
-	private static int hash(final WindowedFile pack, final long position) {
-		int h = pack.hash + (int) position;
-		h += h >>> 16;
-		h += h >>> 8;
-		return h & (CACHE_SZ - 1);
+	private static int hash(final long position) {
+		return (((int) position) << 22) >>> 22;
 	}
 
 	private static int maxByteCount;
@@ -80,7 +77,7 @@ static synchronized void reconfigure(final int dbLimit) {
 	}
 
 	static synchronized Entry get(final WindowedFile pack, final long position) {
-		final Slot e = cache[hash(pack, position)];
+		final Slot e = cache[hash(position)];
 		if (e.provider == pack && e.position == position) {
 			final Entry buf = e.data.get();
 			if (buf != null) {
@@ -96,7 +93,7 @@ static synchronized void store(final WindowedFile pack,
 		if (data.length > maxByteCount)
 			return; // Too large to cache.
 
-		final Slot e = cache[hash(pack, position)];
+		final Slot e = cache[hash(position)];
 		clearEntry(e);
 
 		openByteCount += data.length;
@@ -104,6 +101,7 @@ static synchronized void store(final WindowedFile pack,
 
 		e.provider = pack;
 		e.position = position;
+		e.sz = data.length;
 		e.data = new SoftReference<Entry>(new Entry(data, objectType));
 		moveToHead(e);
 	}
@@ -155,11 +153,10 @@ private static void unlink(final Slot e) {
 	}
 
 	private static void clearEntry(final Slot e) {
-		final Entry old = e.data.get();
-		if (old != null)
-			openByteCount -= old.data.length;
+		openByteCount -= e.sz;
 		e.provider = null;
 		e.data = DEAD;
+		e.sz = 0;
 	}
 
 	private UnpackedObjectCache() {
@@ -186,6 +183,8 @@ Entry(final byte[] aData, final int aType) {
 
 		long position;
 
+		int sz;
+
 		SoftReference<Entry> data = DEAD;
 	}
 }
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 02/23] Add MutableObjectId.clear() to set the id to zeroId

[Shawn O. Pearce]

This makes it easier to set any MutableObjectId to the same value
as the zeroId.  Its logical to ask for a ".clear()" invocation when
you are writing application code, and its more efficient for the
JIT if we do 5 zero writes then to perform a copy from the zeroId
singleton.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/lib/MutableObjectId.java  |    9 +++++++++
 1 files changed, 9 insertions(+), 0 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/MutableObjectId.java b/org.spearce.jgit/src/org/spearce/jgit/lib/MutableObjectId.java
index 5b16345..fadebab 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/MutableObjectId.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/MutableObjectId.java
@@ -66,6 +66,15 @@ MutableObjectId(MutableObjectId src) {
 		this.w5 = src.w5;
 	}
 
+	/** Make this id match {@link ObjectId#zeroId()}. */
+	public void clear() {
+		w1 = 0;
+		w2 = 0;
+		w3 = 0;
+		w4 = 0;
+		w5 = 0;
+	}
+
 	/**
 	 * Convert an ObjectId from raw binary representation.
 	 * 
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 03/23] Allow TreeWalk callers to pass a MutableObjectId to get the current id

[Shawn O. Pearce]

This avoids a memory allocation associated with getting the entry
object for each name.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/treewalk/TreeWalk.java    |   28 +++++++++++++++++++-
 1 files changed, 27 insertions(+), 1 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
index 26544b5..38a726b 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
@@ -46,6 +46,7 @@
 import org.spearce.jgit.errors.StopWalkException;
 import org.spearce.jgit.lib.Constants;
 import org.spearce.jgit.lib.FileMode;
+import org.spearce.jgit.lib.MutableObjectId;
 import org.spearce.jgit.lib.ObjectId;
 import org.spearce.jgit.lib.Repository;
 import org.spearce.jgit.revwalk.RevTree;
@@ -513,7 +514,8 @@ public FileMode getFileMode(final int nth) {
 	 * <p>
 	 * Using this method to compare ObjectId values between trees of this walker
 	 * is very inefficient. Applications should try to use
-	 * {@link #idEqual(int, int)} whenever possible.
+	 * {@link #idEqual(int, int)} or {@link #getObjectId(MutableObjectId, int)}
+	 * whenever possible.
 	 * <p>
 	 * Every tree supplies an object id, even if the tree does not contain the
 	 * current entry. In the latter case {@link ObjectId#zeroId()} is returned.
@@ -521,6 +523,7 @@ public FileMode getFileMode(final int nth) {
 	 * @param nth
 	 *            tree to obtain the object identifier from.
 	 * @return object identifier for the current tree entry.
+	 * @see #getObjectId(MutableObjectId, int)
 	 * @see #idEqual(int, int)
 	 */
 	public ObjectId getObjectId(final int nth) {
@@ -530,6 +533,29 @@ public ObjectId getObjectId(final int nth) {
 	}
 
 	/**
+	 * Obtain the ObjectId for the current entry.
+	 * <p>
+	 * Every tree supplies an object id, even if the tree does not contain the
+	 * current entry. In the latter case {@link ObjectId#zeroId()} is supplied.
+	 * <p>
+	 * Applications should try to use {@link #idEqual(int, int)} when possible
+	 * as it avoids conversion overheads.
+	 * 
+	 * @param out
+	 *            buffer to copy the object id into.
+	 * @param nth
+	 *            tree to obtain the object identifier from.
+	 * @see #idEqual(int, int)
+	 */
+	public void getObjectId(final MutableObjectId out, final int nth) {
+		final AbstractTreeIterator t = trees[nth];
+		if (t.matches == currentHead)
+			out.fromRaw(t.idBuffer(), t.idOffset());
+		else
+			out.clear();
+	}
+
+	/**
 	 * Compare two tree's current ObjectId values for equality.
 	 * 
 	 * @param nthA
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 04/23] Switch ObjectWalk to use the new MutableObjectId form in TreeWalk

[Shawn O. Pearce]

RevWalk already has an idBuffer field available, which is used by
the commit and tree parsers to hold an id they need to probe for
in the hash table.  We should be using that buffer during tree
entry iteration as it avoids object allocation.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/revwalk/ObjectWalk.java   |   20 ++++++++++++--------
 1 files changed, 12 insertions(+), 8 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java
index 69a20aa..454cb4a 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java
@@ -251,7 +251,8 @@ public RevObject nextObject() throws MissingObjectException,
 
 			switch (sType) {
 			case Constants.OBJ_BLOB: {
-				final RevObject o = lookupAny(treeWalk.getObjectId(0), sType);
+				treeWalk.getObjectId(idBuffer, 0);
+				final RevObject o = lookupAny(idBuffer, sType);
 				if ((o.flags & SEEN) != 0)
 					continue;
 				o.flags |= SEEN;
@@ -262,7 +263,8 @@ public RevObject nextObject() throws MissingObjectException,
 				return o;
 			}
 			case Constants.OBJ_TREE: {
-				final RevObject o = lookupAny(treeWalk.getObjectId(0), sType);
+				treeWalk.getObjectId(idBuffer, 0);
+				final RevObject o = lookupAny(idBuffer, sType);
 				if ((o.flags & SEEN) != 0)
 					continue;
 				o.flags |= SEEN;
@@ -276,8 +278,9 @@ public RevObject nextObject() throws MissingObjectException,
 			default:
 				if (FileMode.GITLINK.equals(mode))
 					continue;
+				treeWalk.getObjectId(idBuffer, 0);
 				throw new CorruptObjectException("Invalid mode " + mode
-						+ " for " + treeWalk.getObjectId(0).name() + " "
+						+ " for " + idBuffer.name() + " "
 						+ treeWalk.getPathString() + " in " + currentTree + ".");
 			}
 		}
@@ -390,13 +393,13 @@ private void markTreeUninteresting(final RevTree tree)
 
 			switch (sType) {
 			case Constants.OBJ_BLOB: {
-				final ObjectId sid = treeWalk.getObjectId(0);
-				lookupAny(sid, sType).flags |= UNINTERESTING;
+				treeWalk.getObjectId(idBuffer, 0);
+				lookupAny(idBuffer, sType).flags |= UNINTERESTING;
 				continue;
 			}
 			case Constants.OBJ_TREE: {
-				final ObjectId sid = treeWalk.getObjectId(0);
-				final RevObject subtree = lookupAny(sid, sType);
+				treeWalk.getObjectId(idBuffer, 0);
+				final RevObject subtree = lookupAny(idBuffer, sType);
 				if ((subtree.flags & UNINTERESTING) == 0) {
 					subtree.flags |= UNINTERESTING;
 					treeWalk.enterSubtree();
@@ -406,8 +409,9 @@ private void markTreeUninteresting(final RevTree tree)
 			default:
 				if (FileMode.GITLINK.equals(mode))
 					continue;
+				treeWalk.getObjectId(idBuffer, 0);
 				throw new CorruptObjectException("Invalid mode " + mode
-						+ " for " + treeWalk.getObjectId(0).name() + " "
+						+ " for " + idBuffer.name() + " "
 						+ treeWalk.getPathString() + " in " + tree + ".");
 			}
 		}
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 05/23] Change walker based fetch to use TreeWalk's MutableObjectId accessor

[Shawn O. Pearce]

Fetch time is usually dominated by network traffic, but while marking
objects reachable locally we can still benefit from the reduction in
object allocations this variant of getObjectId offers.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../jgit/transport/WalkFetchConnection.java        |   29 +++++++++++--------
 1 files changed, 17 insertions(+), 12 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java b/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java
index 91c5ea8..6300f10 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java
@@ -59,6 +59,7 @@
 import org.spearce.jgit.lib.AnyObjectId;
 import org.spearce.jgit.lib.Constants;
 import org.spearce.jgit.lib.FileMode;
+import org.spearce.jgit.lib.MutableObjectId;
 import org.spearce.jgit.lib.ObjectChecker;
 import org.spearce.jgit.lib.ObjectId;
 import org.spearce.jgit.lib.PackIndex;
@@ -152,6 +153,8 @@
 	 */
 	private final Set<String> packsConsidered;
 
+	private final MutableObjectId idBuffer = new MutableObjectId();
+
 	/**
 	 * Errors received while trying to obtain an object.
 	 * <p>
@@ -300,16 +303,17 @@ private void processTree(final RevObject obj) throws TransportException {
 
 				switch (sType) {
 				case Constants.OBJ_BLOB:
-				case Constants.OBJ_TREE: {
-					final ObjectId sId = treeWalk.getObjectId(0);
-					needs(revWalk.lookupAny(sId, sType));
+				case Constants.OBJ_TREE:
+					treeWalk.getObjectId(idBuffer, 0);
+					needs(revWalk.lookupAny(idBuffer, sType));
 					continue;
-				}
+
 				default:
 					if (FileMode.GITLINK.equals(mode))
 						continue;
+					treeWalk.getObjectId(idBuffer, 0);
 					throw new CorruptObjectException("Invalid mode " + mode
-							+ " for " + treeWalk.getObjectId(0).name() + " "
+							+ " for " + idBuffer.name() + " "
 							+ treeWalk.getPathString() + " in "
 							+ obj.getId().name() + ".");
 				}
@@ -722,14 +726,14 @@ private void markTreeComplete(final RevTree tree) throws IOException {
 			final int sType = mode.getObjectType();
 
 			switch (sType) {
-			case Constants.OBJ_BLOB: {
-				final ObjectId sid = treeWalk.getObjectId(0);
-				revWalk.lookupAny(sid, sType).add(COMPLETE);
+			case Constants.OBJ_BLOB:
+				treeWalk.getObjectId(idBuffer, 0);
+				revWalk.lookupAny(idBuffer, sType).add(COMPLETE);
 				continue;
-			}
+
 			case Constants.OBJ_TREE: {
-				final ObjectId sid = treeWalk.getObjectId(0);
-				final RevObject o = revWalk.lookupAny(sid, sType);
+				treeWalk.getObjectId(idBuffer, 0);
+				final RevObject o = revWalk.lookupAny(idBuffer, sType);
 				if (!o.has(COMPLETE)) {
 					o.add(COMPLETE);
 					treeWalk.enterSubtree();
@@ -739,8 +743,9 @@ private void markTreeComplete(final RevTree tree) throws IOException {
 			default:
 				if (FileMode.GITLINK.equals(mode))
 					continue;
+				treeWalk.getObjectId(idBuffer, 0);
 				throw new CorruptObjectException("Invalid mode " + mode
-						+ " for " + treeWalk.getObjectId(0).name() + " "
+						+ " for " + idBuffer.name() + " "
 						+ treeWalk.getPathString() + " in " + tree.name() + ".");
 			}
 		}
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 06/23] Reduce garbage allocation when using TreeWalk

[Shawn O. Pearce]

We now support more efficiently resetting a TreeWalk when the
walker is using a single tree traversal from the repository.
This is very common during an ObjectWalk for a PackWriter, so
optimizing the code path is worth while.  By using a special
form of reset we can avoid unnecessary temporary arrays and
also skip some loop conditional instructions.

When diving into a subtree iterator (which is also quite a
common operation in ObjectWalk) we want to reuse an idBuffer
and a WindowCursor as much as possible, ensuring that these
aren't created temporarily on the stack.  This should help
to reduce the stress on the Inflater cache by allowing it
to reuse the same Inflater on each tree construction.  We
also can avoid creating a temporary ObjectId by filling out
the mutable idBuffer during the repository lookup.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../jgit/pgm/opt/AbstractTreeIteratorHandler.java  |    6 ++-
 .../src/org/spearce/jgit/revwalk/ObjectWalk.java   |    5 +-
 .../jgit/transport/WalkFetchConnection.java        |    4 +-
 .../jgit/treewalk/AbstractTreeIterator.java        |   28 ++++++++++
 .../spearce/jgit/treewalk/CanonicalTreeParser.java |   46 ++++++++++++----
 .../src/org/spearce/jgit/treewalk/TreeWalk.java    |   58 ++++++++++++++++++--
 6 files changed, 124 insertions(+), 23 deletions(-)

diff --git a/org.spearce.jgit.pgm/src/org/spearce/jgit/pgm/opt/AbstractTreeIteratorHandler.java b/org.spearce.jgit.pgm/src/org/spearce/jgit/pgm/opt/AbstractTreeIteratorHandler.java
index 9432d5f..12d4191 100644
--- a/org.spearce.jgit.pgm/src/org/spearce/jgit/pgm/opt/AbstractTreeIteratorHandler.java
+++ b/org.spearce.jgit.pgm/src/org/spearce/jgit/pgm/opt/AbstractTreeIteratorHandler.java
@@ -51,6 +51,7 @@
 import org.spearce.jgit.errors.IncorrectObjectTypeException;
 import org.spearce.jgit.errors.MissingObjectException;
 import org.spearce.jgit.lib.ObjectId;
+import org.spearce.jgit.lib.WindowCursor;
 import org.spearce.jgit.treewalk.AbstractTreeIterator;
 import org.spearce.jgit.treewalk.CanonicalTreeParser;
 import org.spearce.jgit.treewalk.FileTreeIterator;
@@ -110,8 +111,9 @@ public int parseArguments(final Parameters params) throws CmdLineException {
 			throw new CmdLineException(name + " is not a tree");
 
 		final CanonicalTreeParser p = new CanonicalTreeParser();
+		final WindowCursor curs = new WindowCursor();
 		try {
-			p.reset(clp.getRepository(), clp.getRevWalk().parseTree(id));
+			p.reset(clp.getRepository(), clp.getRevWalk().parseTree(id), curs);
 		} catch (MissingObjectException e) {
 			throw new CmdLineException(name + " is not a tree");
 		} catch (IncorrectObjectTypeException e) {
@@ -119,6 +121,8 @@ public int parseArguments(final Parameters params) throws CmdLineException {
 		} catch (IOException e) {
 			throw new CmdLineException("cannot read " + name + ": "
 					+ e.getMessage());
+		} finally {
+			curs.release();
 		}
 
 		setter.addValue(p);
diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java
index 454cb4a..cfdbe18 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java
@@ -45,7 +45,6 @@
 import org.spearce.jgit.lib.AnyObjectId;
 import org.spearce.jgit.lib.Constants;
 import org.spearce.jgit.lib.FileMode;
-import org.spearce.jgit.lib.ObjectId;
 import org.spearce.jgit.lib.Repository;
 import org.spearce.jgit.treewalk.TreeWalk;
 
@@ -296,7 +295,7 @@ public RevObject nextObject() throws MissingObjectException,
 				continue;
 			if (o instanceof RevTree) {
 				currentTree = (RevTree) o;
-				treeWalk.reset(new ObjectId[] { currentTree });
+				treeWalk.reset(currentTree);
 			}
 			return o;
 		}
@@ -386,7 +385,7 @@ private void markTreeUninteresting(final RevTree tree)
 			return;
 		tree.flags |= UNINTERESTING;
 
-		treeWalk.reset(new ObjectId[] { tree });
+		treeWalk.reset(tree);
 		while (treeWalk.next()) {
 			final FileMode mode = treeWalk.getFileMode(0);
 			final int sType = mode.getObjectType();
diff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java b/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java
index 6300f10..5d0c6bc 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java
@@ -296,7 +296,7 @@ private void processBlob(final RevObject obj) throws TransportException {
 
 	private void processTree(final RevObject obj) throws TransportException {
 		try {
-			treeWalk.reset(new ObjectId[] { obj });
+			treeWalk.reset(obj);
 			while (treeWalk.next()) {
 				final FileMode mode = treeWalk.getFileMode(0);
 				final int sType = mode.getObjectType();
@@ -720,7 +720,7 @@ private void markTreeComplete(final RevTree tree) throws IOException {
 		if (tree.has(COMPLETE))
 			return;
 		tree.add(COMPLETE);
-		treeWalk.reset(new ObjectId[] { tree });
+		treeWalk.reset(tree);
 		while (treeWalk.next()) {
 			final FileMode mode = treeWalk.getFileMode(0);
 			final int sType = mode.getObjectType();
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
index 5226ab6..c404cdc 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
@@ -46,8 +46,10 @@
 import org.spearce.jgit.errors.IncorrectObjectTypeException;
 import org.spearce.jgit.lib.Constants;
 import org.spearce.jgit.lib.FileMode;
+import org.spearce.jgit.lib.MutableObjectId;
 import org.spearce.jgit.lib.ObjectId;
 import org.spearce.jgit.lib.Repository;
+import org.spearce.jgit.lib.WindowCursor;
 import org.spearce.jgit.treewalk.filter.TreeFilter;
 
 /**
@@ -347,6 +349,32 @@ public abstract AbstractTreeIterator createSubtreeIterator(Repository repo)
 			throws IncorrectObjectTypeException, IOException;
 
 	/**
+	 * Create a new iterator for the current entry's subtree.
+	 * <p>
+	 * The parent reference of the iterator must be <code>this</code>, otherwise
+	 * the caller would not be able to exit out of the subtree iterator
+	 * correctly and return to continue walking <code>this</code>.
+	 * 
+	 * @param repo
+	 *            repository to load the tree data from.
+	 * @param idBuffer
+	 *            temporary ObjectId buffer for use by this method.
+	 * @param curs
+	 *            window cursor to use during repository access.
+	 * @return a new parser that walks over the current subtree.
+	 * @throws IncorrectObjectTypeException
+	 *             the current entry is not actually a tree and cannot be parsed
+	 *             as though it were a tree.
+	 * @throws IOException
+	 *             a loose object or pack file could not be read.
+	 */
+	public AbstractTreeIterator createSubtreeIterator(final Repository repo,
+			final MutableObjectId idBuffer, final WindowCursor curs)
+			throws IncorrectObjectTypeException, IOException {
+		return createSubtreeIterator(repo);
+	}
+
+	/**
 	 * Is this tree iterator positioned on its first entry?
 	 * <p>
 	 * An iterator is positioned on the first entry if <code>back(1)</code>
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
index dcc53cd..df3384d 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
@@ -41,11 +41,14 @@
 
 import org.spearce.jgit.errors.IncorrectObjectTypeException;
 import org.spearce.jgit.errors.MissingObjectException;
+import org.spearce.jgit.lib.AnyObjectId;
 import org.spearce.jgit.lib.Constants;
 import org.spearce.jgit.lib.FileMode;
+import org.spearce.jgit.lib.MutableObjectId;
 import org.spearce.jgit.lib.ObjectId;
 import org.spearce.jgit.lib.ObjectLoader;
 import org.spearce.jgit.lib.Repository;
+import org.spearce.jgit.lib.WindowCursor;
 
 /** Parses raw Git trees from the canonical semi-text/semi-binary format. */
 public class CanonicalTreeParser extends AbstractTreeIterator {
@@ -87,6 +90,8 @@ public void reset(final byte[] treeData) {
 	 * @param id
 	 *            identity of the tree being parsed; used only in exception
 	 *            messages if data corruption is found.
+	 * @param curs
+	 *            window cursor to use during repository access.
 	 * @throws MissingObjectException
 	 *             the object supplied is not available from the repository.
 	 * @throws IncorrectObjectTypeException
@@ -95,27 +100,46 @@ public void reset(final byte[] treeData) {
 	 * @throws IOException
 	 *             a loose object or pack file could not be read.
 	 */
-	public void reset(final Repository repo, final ObjectId id)
+	public void reset(final Repository repo, final AnyObjectId id,
+			final WindowCursor curs)
 			throws IncorrectObjectTypeException, IOException {
-		final ObjectLoader ldr = repo.openObject(id);
-		if (ldr == null)
-			throw new MissingObjectException(id, Constants.TYPE_TREE);
+		final ObjectLoader ldr = repo.openObject(curs, id);
+		if (ldr == null) {
+			final ObjectId me = id.toObjectId();
+			throw new MissingObjectException(me, Constants.TYPE_TREE);
+		}
 		final byte[] subtreeData = ldr.getCachedBytes();
-		if (ldr.getType() != Constants.OBJ_TREE)
-			throw new IncorrectObjectTypeException(id, Constants.TYPE_TREE);
+		if (ldr.getType() != Constants.OBJ_TREE) {
+			final ObjectId me = id.toObjectId();
+			throw new IncorrectObjectTypeException(me, Constants.TYPE_TREE);
+		}
 		reset(subtreeData);
 	}
 
-	public CanonicalTreeParser createSubtreeIterator(final Repository repo)
+	@Override
+	public CanonicalTreeParser createSubtreeIterator(final Repository repo,
+			final MutableObjectId idBuffer, final WindowCursor curs)
 			throws IncorrectObjectTypeException, IOException {
-		final ObjectId id = getEntryObjectId();
-		if (!FileMode.TREE.equals(mode))
-			throw new IncorrectObjectTypeException(id, Constants.TYPE_TREE);
+		idBuffer.fromRaw(idBuffer(), idOffset());
+		if (!FileMode.TREE.equals(mode)) {
+			final ObjectId me = idBuffer.toObjectId();
+			throw new IncorrectObjectTypeException(me, Constants.TYPE_TREE);
+		}
 		final CanonicalTreeParser p = new CanonicalTreeParser(this);
-		p.reset(repo, id);
+		p.reset(repo, idBuffer, curs);
 		return p;
 	}
 
+	public CanonicalTreeParser createSubtreeIterator(final Repository repo)
+			throws IncorrectObjectTypeException, IOException {
+		final WindowCursor curs = new WindowCursor();
+		try {
+			return createSubtreeIterator(repo, new MutableObjectId(), curs);
+		} finally {
+			curs.release();
+		}
+	}
+
 	@Override
 	public byte[] idBuffer() {
 		return raw;
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
index 38a726b..cf66bf4 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
@@ -44,11 +44,13 @@
 import org.spearce.jgit.errors.IncorrectObjectTypeException;
 import org.spearce.jgit.errors.MissingObjectException;
 import org.spearce.jgit.errors.StopWalkException;
+import org.spearce.jgit.lib.AnyObjectId;
 import org.spearce.jgit.lib.Constants;
 import org.spearce.jgit.lib.FileMode;
 import org.spearce.jgit.lib.MutableObjectId;
 import org.spearce.jgit.lib.ObjectId;
 import org.spearce.jgit.lib.Repository;
+import org.spearce.jgit.lib.WindowCursor;
 import org.spearce.jgit.revwalk.RevTree;
 import org.spearce.jgit.treewalk.filter.PathFilterGroup;
 import org.spearce.jgit.treewalk.filter.TreeFilter;
@@ -99,7 +101,7 @@
 	 *             a tree object was not found.
 	 */
 	public static TreeWalk forPath(final Repository db, final String path,
-			final ObjectId[] trees) throws MissingObjectException,
+			final AnyObjectId[] trees) throws MissingObjectException,
 			IncorrectObjectTypeException, CorruptObjectException, IOException {
 		final TreeWalk r = new TreeWalk(db);
 		r.setFilter(PathFilterGroup.createFromStrings(Collections
@@ -142,6 +144,10 @@ public static TreeWalk forPath(final Repository db, final String path,
 
 	private final Repository db;
 
+	private final MutableObjectId idBuffer = new MutableObjectId();
+
+	private final WindowCursor curs = new WindowCursor();
+
 	private TreeFilter filter;
 
 	AbstractTreeIterator[] trees;
@@ -278,6 +284,46 @@ public void reset() {
 	}
 
 	/**
+	 * Reset this walker to run over a single existing tree.
+	 * 
+	 * @param id
+	 *            the tree we need to parse. The walker will execute over this
+	 *            single tree if the reset is successful.
+	 * @throws MissingObjectException
+	 *             the given tree object does not exist in this repository.
+	 * @throws IncorrectObjectTypeException
+	 *             the given object id does not denote a tree, but instead names
+	 *             some other non-tree type of object. Note that commits are not
+	 *             trees, even if they are sometimes called a "tree-ish".
+	 * @throws CorruptObjectException
+	 *             the object claimed to be a tree, but its contents did not
+	 *             appear to be a tree. The repository may have data corruption.
+	 * @throws IOException
+	 *             a loose object or pack file could not be read.
+	 */
+	public void reset(final AnyObjectId id) throws MissingObjectException,
+			IncorrectObjectTypeException, CorruptObjectException, IOException {
+		if (trees.length == 1) {
+			AbstractTreeIterator o = trees[0];
+			while (o.parent != null)
+				o = o.parent;
+			if (o instanceof CanonicalTreeParser) {
+				o.matches = null;
+				o.matchShift = 0;
+				((CanonicalTreeParser) o).reset(db, id, curs);
+				trees[0] = o;
+			} else {
+				trees[0] = parserFor(id);
+			}
+		} else {
+			trees = new AbstractTreeIterator[] { parserFor(id) };
+		}
+
+		advance = false;
+		depth = 0;
+	}
+
+	/**
 	 * Reset this walker to run over a set of existing trees.
 	 * 
 	 * @param ids
@@ -295,7 +341,7 @@ public void reset() {
 	 * @throws IOException
 	 *             a loose object or pack file could not be read.
 	 */
-	public void reset(final ObjectId[] ids) throws MissingObjectException,
+	public void reset(final AnyObjectId[] ids) throws MissingObjectException,
 			IncorrectObjectTypeException, CorruptObjectException, IOException {
 		final int oldLen = trees.length;
 		final int newLen = ids.length;
@@ -311,7 +357,7 @@ public void reset(final ObjectId[] ids) throws MissingObjectException,
 				if (o instanceof CanonicalTreeParser) {
 					o.matches = null;
 					o.matchShift = 0;
-					((CanonicalTreeParser) o).reset(db, ids[i]);
+					((CanonicalTreeParser) o).reset(db, ids[i], curs);
 					r[i] = o;
 					continue;
 				}
@@ -709,7 +755,7 @@ public void enterSubtree() throws MissingObjectException,
 			final AbstractTreeIterator t = trees[i];
 			final AbstractTreeIterator n;
 			if (t.matches == ch && !t.eof() && FileMode.TREE.equals(t.mode))
-				n = t.createSubtreeIterator(db);
+				n = t.createSubtreeIterator(db, idBuffer, curs);
 			else
 				n = new EmptyTreeIterator(t);
 			tmp[i] = n;
@@ -781,10 +827,10 @@ private void exitSubtree() {
 		currentHead = minRef;
 	}
 
-	private CanonicalTreeParser parserFor(final ObjectId id)
+	private CanonicalTreeParser parserFor(final AnyObjectId id)
 			throws IncorrectObjectTypeException, IOException {
 		final CanonicalTreeParser p = new CanonicalTreeParser();
-		p.reset(db, id);
+		p.reset(db, id, curs);
 		return p;
 	}
 
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 07/23] Switch ObjectWalk to use a naked CanonicalTreeParser because its faster

[Shawn O. Pearce]

Removing the indirection of the TreeWalk during an ObjectWalk's loop
over the trees saves us 20 seconds on one of my linux-2.6 clones.  On
average we went from 1m37s for "jgit rev-list --objects" down to 1m17s.

C git still does the same operation in 0m20s, so we're a long way from
matching C git's performance, but this is a worthwhile improvement, even
though the code has become slightly more complex.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/revwalk/ObjectWalk.java   |   42 ++++++++++---------
 .../jgit/treewalk/AbstractTreeIterator.java        |   20 +++++++++
 .../spearce/jgit/treewalk/CanonicalTreeParser.java |   39 ++++++++++++++++++-
 .../src/org/spearce/jgit/treewalk/TreeWalk.java    |    4 +-
 4 files changed, 82 insertions(+), 23 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java
index cfdbe18..0d67a38 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java
@@ -46,7 +46,7 @@
 import org.spearce.jgit.lib.Constants;
 import org.spearce.jgit.lib.FileMode;
 import org.spearce.jgit.lib.Repository;
-import org.spearce.jgit.treewalk.TreeWalk;
+import org.spearce.jgit.treewalk.CanonicalTreeParser;
 
 /**
  * Specialized subclass of RevWalk to include trees, blobs and tags.
@@ -74,7 +74,7 @@
 	 */
 	private static final int IN_PENDING = RevWalk.REWRITE;
 
-	private final TreeWalk treeWalk;
+	private CanonicalTreeParser treeWalk;
 
 	private BlockObjQueue pendingObjects;
 
@@ -92,8 +92,8 @@
 	 */
 	public ObjectWalk(final Repository repo) {
 		super(repo);
-		treeWalk = new TreeWalk(repo);
 		pendingObjects = new BlockObjQueue();
+		treeWalk = new CanonicalTreeParser();
 	}
 
 	/**
@@ -240,17 +240,17 @@ public RevObject nextObject() throws MissingObjectException,
 		fromTreeWalk = false;
 
 		if (enterSubtree) {
-			treeWalk.enterSubtree();
+			treeWalk = treeWalk.createSubtreeIterator(db, idBuffer, curs);
 			enterSubtree = false;
 		}
 
-		while (treeWalk.next()) {
-			final FileMode mode = treeWalk.getFileMode(0);
+		for (; !treeWalk.eof(); treeWalk = treeWalk.next()) {
+			final FileMode mode = treeWalk.getEntryFileMode();
 			final int sType = mode.getObjectType();
 
 			switch (sType) {
 			case Constants.OBJ_BLOB: {
-				treeWalk.getObjectId(idBuffer, 0);
+				treeWalk.getEntryObjectId(idBuffer);
 				final RevObject o = lookupAny(idBuffer, sType);
 				if ((o.flags & SEEN) != 0)
 					continue;
@@ -262,7 +262,7 @@ public RevObject nextObject() throws MissingObjectException,
 				return o;
 			}
 			case Constants.OBJ_TREE: {
-				treeWalk.getObjectId(idBuffer, 0);
+				treeWalk.getEntryObjectId(idBuffer);
 				final RevObject o = lookupAny(idBuffer, sType);
 				if ((o.flags & SEEN) != 0)
 					continue;
@@ -277,10 +277,11 @@ public RevObject nextObject() throws MissingObjectException,
 			default:
 				if (FileMode.GITLINK.equals(mode))
 					continue;
-				treeWalk.getObjectId(idBuffer, 0);
+				treeWalk.getEntryObjectId(idBuffer);
 				throw new CorruptObjectException("Invalid mode " + mode
 						+ " for " + idBuffer.name() + " "
-						+ treeWalk.getPathString() + " in " + currentTree + ".");
+						+ treeWalk.getEntryPathString() + " in " + currentTree
+						+ ".");
 			}
 		}
 
@@ -295,7 +296,7 @@ public RevObject nextObject() throws MissingObjectException,
 				continue;
 			if (o instanceof RevTree) {
 				currentTree = (RevTree) o;
-				treeWalk.reset(currentTree);
+				treeWalk = treeWalk.resetRoot(db, currentTree, curs);
 			}
 			return o;
 		}
@@ -353,7 +354,7 @@ public void checkConnectivity() throws MissingObjectException,
 	 *         has no path, such as for annotated tags or root level trees.
 	 */
 	public String getPathString() {
-		return fromTreeWalk ? treeWalk.getPathString() : null;
+		return fromTreeWalk ? treeWalk.getEntryPathString() : null;
 	}
 
 	@Override
@@ -385,33 +386,34 @@ private void markTreeUninteresting(final RevTree tree)
 			return;
 		tree.flags |= UNINTERESTING;
 
-		treeWalk.reset(tree);
-		while (treeWalk.next()) {
-			final FileMode mode = treeWalk.getFileMode(0);
+		treeWalk = treeWalk.resetRoot(db, tree, curs);
+		for (;!treeWalk.eof(); treeWalk = treeWalk.next()) {
+			final FileMode mode = treeWalk.getEntryFileMode();
 			final int sType = mode.getObjectType();
 
 			switch (sType) {
 			case Constants.OBJ_BLOB: {
-				treeWalk.getObjectId(idBuffer, 0);
+				treeWalk.getEntryObjectId(idBuffer);
 				lookupAny(idBuffer, sType).flags |= UNINTERESTING;
 				continue;
 			}
 			case Constants.OBJ_TREE: {
-				treeWalk.getObjectId(idBuffer, 0);
+				treeWalk.getEntryObjectId(idBuffer);
 				final RevObject subtree = lookupAny(idBuffer, sType);
 				if ((subtree.flags & UNINTERESTING) == 0) {
 					subtree.flags |= UNINTERESTING;
-					treeWalk.enterSubtree();
+					treeWalk = treeWalk.createSubtreeIterator(db, idBuffer,
+							curs);
 				}
 				continue;
 			}
 			default:
 				if (FileMode.GITLINK.equals(mode))
 					continue;
-				treeWalk.getObjectId(idBuffer, 0);
+				treeWalk.getEntryObjectId(idBuffer);
 				throw new CorruptObjectException("Invalid mode " + mode
 						+ " for " + idBuffer.name() + " "
-						+ treeWalk.getPathString() + " in " + tree + ".");
+						+ treeWalk.getEntryPathString() + " in " + tree + ".");
 			}
 		}
 	}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
index c404cdc..0229582 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
@@ -308,6 +308,26 @@ public ObjectId getEntryObjectId() {
 	}
 
 	/**
+	 * Obtain the ObjectId for the current entry.
+	 * 
+	 * @param out
+	 *            buffer to copy the object id into.
+	 */
+	public void getEntryObjectId(final MutableObjectId out) {
+		out.fromRaw(idBuffer(), idOffset());
+	}
+
+	/** @return the file mode of the current entry. */
+	public FileMode getEntryFileMode() {
+		return FileMode.fromBits(mode);
+	}
+
+	/** @return path of the current entry, as a string. */
+	public String getEntryPathString() {
+		return TreeWalk.pathOf(this);
+	}
+
+	/**
 	 * Get the byte array buffer object IDs must be copied out of.
 	 * <p>
 	 * The id buffer contains the bytes necessary to construct an ObjectId for
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
index df3384d..6a5bada 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
@@ -52,6 +52,8 @@
 
 /** Parses raw Git trees from the canonical semi-text/semi-binary format. */
 public class CanonicalTreeParser extends AbstractTreeIterator {
+	private static final byte[] EMPTY = {};
+
 	private byte[] raw;
 
 	/** First offset within {@link #raw} of the current entry's data. */
@@ -62,7 +64,7 @@
 
 	/** Create a new parser. */
 	public CanonicalTreeParser() {
-		// Nothing necessary.
+		raw = EMPTY;
 	}
 
 	private CanonicalTreeParser(final CanonicalTreeParser p) {
@@ -92,6 +94,41 @@ public void reset(final byte[] treeData) {
 	 *            messages if data corruption is found.
 	 * @param curs
 	 *            window cursor to use during repository access.
+	 * @return the root level parser.
+	 * @throws MissingObjectException
+	 *             the object supplied is not available from the repository.
+	 * @throws IncorrectObjectTypeException
+	 *             the object supplied as an argument is not actually a tree and
+	 *             cannot be parsed as though it were a tree.
+	 * @throws IOException
+	 *             a loose object or pack file could not be read.
+	 */
+	public CanonicalTreeParser resetRoot(final Repository repo,
+			final AnyObjectId id, final WindowCursor curs)
+			throws IncorrectObjectTypeException, IOException {
+		CanonicalTreeParser p = this;
+		while (p.parent != null)
+			p = (CanonicalTreeParser) p.parent;
+		p.reset(repo, id, curs);
+		return p;
+	}
+
+	/** @return this iterator, or its parent, if the tree is at eof. */
+	public CanonicalTreeParser next() {
+		next(1);
+		return eof() && parent != null ? (CanonicalTreeParser) parent : this;
+	}
+
+	/**
+	 * Reset this parser to walk through the given tree.
+	 * 
+	 * @param repo
+	 *            repository to load the tree data from.
+	 * @param id
+	 *            identity of the tree being parsed; used only in exception
+	 *            messages if data corruption is found.
+	 * @param curs
+	 *            window cursor to use during repository access.
 	 * @throws MissingObjectException
 	 *             the object supplied is not available from the repository.
 	 * @throws IncorrectObjectTypeException
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
index cf66bf4..d1841b3 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
@@ -596,7 +596,7 @@ public ObjectId getObjectId(final int nth) {
 	public void getObjectId(final MutableObjectId out, final int nth) {
 		final AbstractTreeIterator t = trees[nth];
 		if (t.matches == currentHead)
-			out.fromRaw(t.idBuffer(), t.idOffset());
+			t.getEntryObjectId(out);
 		else
 			out.clear();
 	}
@@ -834,7 +834,7 @@ private CanonicalTreeParser parserFor(final AnyObjectId id)
 		return p;
 	}
 
-	private static String pathOf(final AbstractTreeIterator t) {
+	static String pathOf(final AbstractTreeIterator t) {
 		return RawParseUtils.decode(Constants.CHARSET, t.path, 0, t.pathLen);
 	}
 }
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 08/23] Remove the unused PackFile.get(ObjectId) form

[Shawn O. Pearce]

Everyone passes in a WindowCursor, except this one test case.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../tst/org/spearce/jgit/lib/T0004_PackReader.java |    2 +-
 .../src/org/spearce/jgit/lib/PackFile.java         |   19 -------------------
 2 files changed, 1 insertions(+), 20 deletions(-)

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/T0004_PackReader.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/T0004_PackReader.java
index 8288e56..f6fff52 100644
--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/T0004_PackReader.java
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/T0004_PackReader.java
@@ -55,7 +55,7 @@ public void test003_lookupCompressedObject() throws IOException {
 
 		id = ObjectId.fromString("902d5476fa249b7abc9d84c611577a81381f0327");
 		pr = new PackFile(db, TEST_IDX, TEST_PACK);
-		or = pr.get(id);
+		or = pr.get(new WindowCursor(), id);
 		assertNotNull(or);
 		assertEquals(id, or.getId());
 		assertEquals(Constants.OBJ_TREE, or.getType());
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java
index fc1b6ea..cd17bd4 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java
@@ -117,25 +117,6 @@ public boolean hasObject(final AnyObjectId id) {
 	/**
 	 * Get an object from this pack.
 	 * 
-	 * @param id
-	 *            the object to obtain from the pack. Must not be null.
-	 * @return the object loader for the requested object if it is contained in
-	 *         this pack; null if the object was not found.
-	 * @throws IOException
-	 *             the pack file or the index could not be read.
-	 */
-	public PackedObjectLoader get(final AnyObjectId id) throws IOException {
-		final WindowCursor wc = new WindowCursor();
-		try {
-			return get(wc, id);
-		} finally {
-			wc.release();
-		}
-	}
-
-	/**
-	 * Get an object from this pack.
-	 * 
 	 * @param curs
 	 *            temporary working space associated with the calling thread.
 	 * @param id
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 09/23] Remove getId from ObjectLoader API as its unnecessary overhead

[Shawn O. Pearce]

Apparently nobody actually requires the getId() method on an ObjectLoader.
In every single location where the getId() is being used the caller has
an AnyObjectId wich the proper value already in-scope, typically the value
they passed into Repository.openObject().  Avoiding having the id in the
loader API means PackFile doesn't have to copy a MutableObjectId into an
immutable ObjectId, saving an object allocation per object lookup.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../tst/org/spearce/jgit/lib/T0004_PackReader.java |    2 -
 .../jgit/errors/CorruptObjectException.java        |   12 ++++++
 .../src/org/spearce/jgit/lib/Constants.java        |    2 +-
 .../spearce/jgit/lib/DeltaPackedObjectLoader.java  |    3 +-
 .../src/org/spearce/jgit/lib/ObjectLoader.java     |   38 --------------------
 .../src/org/spearce/jgit/lib/PackFile.java         |   12 +-----
 .../src/org/spearce/jgit/lib/Repository.java       |    2 +-
 .../org/spearce/jgit/lib/UnpackedObjectLoader.java |   12 +++----
 .../spearce/jgit/lib/WholePackedObjectLoader.java  |    3 +-
 .../src/org/spearce/jgit/revwalk/RevWalk.java      |    8 ++--
 .../jgit/transport/WalkFetchConnection.java        |   15 +++++++-
 11 files changed, 42 insertions(+), 67 deletions(-)

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/T0004_PackReader.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/T0004_PackReader.java
index f6fff52..6ffb904 100644
--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/T0004_PackReader.java
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/T0004_PackReader.java
@@ -57,7 +57,6 @@ public void test003_lookupCompressedObject() throws IOException {
 		pr = new PackFile(db, TEST_IDX, TEST_PACK);
 		or = pr.get(new WindowCursor(), id);
 		assertNotNull(or);
-		assertEquals(id, or.getId());
 		assertEquals(Constants.OBJ_TREE, or.getType());
 		assertEquals(35, or.getSize());
 		assertEquals(7738, or.getDataOffset());
@@ -72,7 +71,6 @@ public void test004_lookupDeltifiedObject() throws IOException {
 		or = db.openObject(id);
 		assertNotNull(or);
 		assertTrue(or instanceof PackedObjectLoader);
-		assertEquals(id, or.getId());
 		assertEquals(Constants.OBJ_BLOB, or.getType());
 		assertEquals(18009, or.getSize());
 		assertEquals(537, ((PackedObjectLoader) or).getDataOffset());
diff --git a/org.spearce.jgit/src/org/spearce/jgit/errors/CorruptObjectException.java b/org.spearce.jgit/src/org/spearce/jgit/errors/CorruptObjectException.java
index 4eb7aa6..2b0e287 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/errors/CorruptObjectException.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/errors/CorruptObjectException.java
@@ -40,6 +40,7 @@
 
 import java.io.IOException;
 
+import org.spearce.jgit.lib.AnyObjectId;
 import org.spearce.jgit.lib.ObjectId;
 
 /**
@@ -55,6 +56,17 @@
 	 * @param id
 	 * @param why
 	 */
+	public CorruptObjectException(final AnyObjectId id, final String why) {
+		this(id.toObjectId(), why);
+	}
+
+	/**
+	 * Construct a CorruptObjectException for reporting a problem specified
+	 * object id
+	 *
+	 * @param id
+	 * @param why
+	 */
 	public CorruptObjectException(final ObjectId id, final String why) {
 		super("Object " + id.name() + " is corrupt: " + why);
 	}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/Constants.java b/org.spearce.jgit/src/org/spearce/jgit/lib/Constants.java
index 9613d07..8f093d6 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/Constants.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/Constants.java
@@ -311,7 +311,7 @@ public static String typeString(final int typeCode) {
 	 * @throws CorruptObjectException
 	 *             there is no valid type identified by <code>typeString</code>.
 	 */
-	public static int decodeTypeString(final ObjectId id,
+	public static int decodeTypeString(final AnyObjectId id,
 			final byte[] typeString, final byte endMark,
 			final MutableInteger offset) throws CorruptObjectException {
 		try {
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaPackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaPackedObjectLoader.java
index e73f8e5..85f2bda 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaPackedObjectLoader.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaPackedObjectLoader.java
@@ -92,7 +92,8 @@ public long getSize() throws IOException {
 			return data;
 		} catch (DataFormatException dfe) {
 			final CorruptObjectException coe;
-			coe = new CorruptObjectException(getId(), "bad stream");
+			coe = new CorruptObjectException("Object at " + dataOffset + " in "
+					+ pack.getPackFile() + " has bad zlib stream");
 			coe.initCause(dfe);
 			throw coe;
 		}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectLoader.java
index 8d745dd..5485d8d 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectLoader.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectLoader.java
@@ -39,50 +39,12 @@
 package org.spearce.jgit.lib;
 
 import java.io.IOException;
-import java.security.MessageDigest;
 
 /**
  * Base class for a set of loaders for different representations of Git objects.
  * New loaders are constructed for every object.
  */
 public abstract class ObjectLoader {
-	private ObjectId objectId;
-
-	/**
-	 * @return the id of this object, possibly computed on demand
-	 * @throws IOException
-	 */
-	public ObjectId getId() throws IOException {
-		if (objectId == null) {
-			final MessageDigest md = Constants.newMessageDigest();
-			md.update(Constants.encodedTypeString(getType()));
-			md.update((byte) ' ');
-			md.update(Constants.encodeASCII(getSize()));
-			md.update((byte) 0);
-			md.update(getCachedBytes());
-			objectId = ObjectId.fromRaw(md.digest());
-		}
-		return objectId;
-	}
-
-	/**
-	 * @return true if id of loaded object is already known, false otherwise.
-	 */
-	protected boolean hasComputedId() {
-		return objectId != null;
-	}
-
-	/**
-	 * Set the SHA-1 id of the object handled by this loader
-	 * 
-	 * @param id
-	 */
-	protected void setId(final ObjectId id) {
-		if (objectId != null)
-			throw new IllegalStateException("Id already set.");
-		objectId = id;
-	}
-
 	/**
 	 * @return Git in pack object type, see {@link Constants}.
 	 * @throws IOException
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java
index cd17bd4..3cdca8f 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java
@@ -129,11 +129,7 @@ public boolean hasObject(final AnyObjectId id) {
 	public PackedObjectLoader get(final WindowCursor curs, final AnyObjectId id)
 			throws IOException {
 		final long offset = idx.findOffset(id);
-		if (offset == -1)
-			return null;
-		final PackedObjectLoader objReader = reader(curs, offset);
-		objReader.setId(id.toObjectId());
-		return objReader;
+		return 0 < offset ? reader(curs, offset) : null;
 	}
 
 	/**
@@ -219,11 +215,7 @@ final void copyRawData(final PackedObjectLoader loader,
 			pack.copyToStream(dataOffset, buf, cnt, crcOut, curs);
 			final long computed = crc.getValue();
 
-			ObjectId id;
-			if (loader.hasComputedId())
-				id = loader.getId();
-			else
-				id = findObjectForOffset(objectOffset);
+			final ObjectId id = findObjectForOffset(objectOffset);
 			final long expected = idx.findCRC32(id);
 			if (computed != expected)
 				throw new CorruptObjectException(id,
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java b/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java
index 8f6e96e..02f8103 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java
@@ -317,7 +317,7 @@ public ObjectLoader openObject(final WindowCursor curs, final AnyObjectId id)
 			} while (k > 0);
 		}
 		try {
-			return new UnpackedObjectLoader(this, id.toObjectId());
+			return new UnpackedObjectLoader(this, id);
 		} catch (FileNotFoundException fnfe) {
 			return null;
 		}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectLoader.java
index 3ad273f..0560c3a 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectLoader.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectLoader.java
@@ -67,13 +67,13 @@
 	 *            SHA-1
 	 * @throws IOException
 	 */
-	public UnpackedObjectLoader(final Repository db, final ObjectId id)
+	public UnpackedObjectLoader(final Repository db, final AnyObjectId id)
 			throws IOException {
 		this(readCompressed(db, id), id);
 	}
 
-	private static byte[] readCompressed(final Repository db, final ObjectId id)
-			throws FileNotFoundException, IOException {
+	private static byte[] readCompressed(final Repository db,
+			final AnyObjectId id) throws FileNotFoundException, IOException {
 		final FileInputStream objStream = new FileInputStream(db.toFile(id));
 		final byte[] compressed;
 		try {
@@ -101,10 +101,8 @@ public UnpackedObjectLoader(final byte[] compressed)
 		this(compressed, null);
 	}
 
-	private UnpackedObjectLoader(final byte[] compressed, final ObjectId id)
+	private UnpackedObjectLoader(final byte[] compressed, final AnyObjectId id)
 			throws CorruptObjectException {
-		setId(id);
-
 		// Try to determine if this is a legacy format loose object or
 		// a new style loose object. The legacy format was completely
 		// compressed with zlib so the first byte must be 0x78 (15-bit
@@ -177,7 +175,7 @@ private UnpackedObjectLoader(final byte[] compressed, final ObjectId id)
 		}
 	}
 
-	private void decompress(final ObjectId id, final Inflater inf, int p)
+	private void decompress(final AnyObjectId id, final Inflater inf, int p)
 			throws CorruptObjectException {
 		try {
 			while (!inf.finished())
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WholePackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WholePackedObjectLoader.java
index 7185df5..3b4f90d 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WholePackedObjectLoader.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WholePackedObjectLoader.java
@@ -72,7 +72,8 @@ WholePackedObjectLoader(final WindowCursor curs, final PackFile pr,
 			return data;
 		} catch (DataFormatException dfe) {
 			final CorruptObjectException coe;
-			coe = new CorruptObjectException(getId(), "bad stream");
+			coe = new CorruptObjectException("Object at " + dataOffset + " in "
+					+ pack.getPackFile() + " has bad zlib stream");
 			coe.initCause(dfe);
 			throw coe;
 		}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java
index b1571ab..dfb34d9 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java
@@ -687,23 +687,23 @@ public RevObject parseAny(final AnyObjectId id)
 			final int type = ldr.getType();
 			switch (type) {
 			case Constants.OBJ_COMMIT: {
-				final RevCommit c = createCommit(ldr.getId());
+				final RevCommit c = createCommit(id);
 				c.parseCanonical(this, data);
 				r = c;
 				break;
 			}
 			case Constants.OBJ_TREE: {
-				r = new RevTree(ldr.getId());
+				r = new RevTree(id);
 				r.flags |= PARSED;
 				break;
 			}
 			case Constants.OBJ_BLOB: {
-				r = new RevBlob(ldr.getId());
+				r = new RevBlob(id);
 				r.flags |= PARSED;
 				break;
 			}
 			case Constants.OBJ_TAG: {
-				final RevTag t = new RevTag(ldr.getId());
+				final RevTag t = new RevTag(id);
 				t.parseCanonical(this, data);
 				r = t;
 				break;
diff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java b/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java
index 5d0c6bc..93b5bd2 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java
@@ -42,6 +42,7 @@
 import java.io.FileNotFoundException;
 import java.io.FileOutputStream;
 import java.io.IOException;
+import java.security.MessageDigest;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.HashMap;
@@ -155,6 +156,8 @@
 
 	private final MutableObjectId idBuffer = new MutableObjectId();
 
+	private final MessageDigest objectDigest = Constants.newMessageDigest();
+
 	/**
 	 * Errors received while trying to obtain an object.
 	 * <p>
@@ -573,9 +576,17 @@ private void verifyLooseObject(final AnyObjectId id, final byte[] compressed)
 			throw e;
 		}
 
-		if (!AnyObjectId.equals(id, uol.getId())) {
+		objectDigest.reset();
+		objectDigest.update(Constants.encodedTypeString(uol.getType()));
+		objectDigest.update((byte) ' ');
+		objectDigest.update(Constants.encodeASCII(uol.getSize()));
+		objectDigest.update((byte) 0);
+		objectDigest.update(uol.getCachedBytes());
+		idBuffer.fromRaw(objectDigest.digest(), 0);
+
+		if (!AnyObjectId.equals(id, idBuffer)) {
 			throw new TransportException("Incorrect hash for " + id.name()
-					+ "; computed " + uol.getId().name() + " as a "
+					+ "; computed " + idBuffer.name() + " as a "
 					+ Constants.encodedTypeString(uol.getType()) + " from "
 					+ compressed.length + " bytes.");
 		}
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 10/23] Make mmap mode more reliable by forcing GC at the correct spot

[Shawn O. Pearce]

ObjectLoaders can defer the bulk of their data access to the
getCachedBytes() method invocation, rather than at the time
of their construction.  That means there's code paths into
the mmap allocator which aren't protected by the "try GC and
try again" within openObject, resulting in some random crashes
due to mmap failures.

The right place to check for mmap failure and retry is within
WindowedFile.loadWindow, where we actually invoke the mmap call.
If the call fails, we need can immediately retry it, and if it
fails again, we can temporarily degrade to the byte[] variant
until the JVM is able to evict and GC enough space.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/lib/Repository.java       |   27 +-----------
 .../src/org/spearce/jgit/lib/WindowedFile.java     |   43 ++++++++++++++-----
 2 files changed, 34 insertions(+), 36 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java b/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java
index 02f8103..e1c4049 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java
@@ -290,30 +290,9 @@ public ObjectLoader openObject(final WindowCursor curs, final AnyObjectId id)
 		int k = packs.length;
 		if (k > 0) {
 			do {
-				try {
-					final ObjectLoader ol = packs[--k].get(curs, id);
-					if (ol != null)
-						return ol;
-				} catch (IOException ioe) {
-					// This shouldn't happen unless the pack was corrupted
-					// after we opened it or the VM runs out of memory. This is
-					// a know problem with memory mapped I/O in java and have
-					// been noticed with JDK < 1.6. Tell the gc that now is a good
-					// time to collect and try once more.
-					try {
-						curs.release();
-						System.gc();
-						final ObjectLoader ol = packs[k].get(curs, id);
-						if (ol != null)
-							return ol;
-					} catch (IOException ioe2) {
-						ioe2.printStackTrace();
-						ioe.printStackTrace();
-						// Still fails.. that's BAD, maybe the pack has
-						// been corrupted after all, or the gc didn't manage
-						// to release enough previously mmaped areas.
-					}
-				}
+				final ObjectLoader ol = packs[--k].get(curs, id);
+				if (ol != null)
+					return ol;
 			} while (k > 0);
 		}
 		try {
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java
index f640c42..dd94f24 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java
@@ -299,22 +299,41 @@ void cacheClose() {
 	}
 
 	void loadWindow(final WindowCursor curs, final int windowId,
-			final long pos, final int windowSize) throws IOException {
+			final long pos, final int size) throws IOException {
 		if (WindowCache.mmap) {
-			final MappedByteBuffer map = fd.getChannel().map(MapMode.READ_ONLY,
-					pos, windowSize);
-			if (map.hasArray()) {
-				final byte[] b = map.array();
-				curs.window = new ByteArrayWindow(this, pos, windowId, b);
-				curs.handle = b;
-			} else {
-				curs.window = new ByteBufferWindow(this, pos, windowId, map);
-				curs.handle = map;
+			MappedByteBuffer map;
+			try {
+				map = fd.getChannel().map(MapMode.READ_ONLY, pos, size);
+			} catch (IOException e) {
+				// The most likely reason this failed is the JVM has run out
+				// of virtual memory. We need to discard quickly, and try to
+				// force the GC to finalize and release any existing mappings.
+				try {
+					curs.release();
+					System.gc();
+					System.runFinalization();
+					map = fd.getChannel().map(MapMode.READ_ONLY, pos, size);
+				} catch (IOException ioe2) {
+					// Temporarily disable mmap and do buffered disk IO.
+					//
+					map = null;
+					System.err.println("warning: mmap failure: "+ioe2);
+				}
+			}
+			if (map != null) {
+				if (map.hasArray()) {
+					final byte[] b = map.array();
+					curs.window = new ByteArrayWindow(this, pos, windowId, b);
+					curs.handle = b;
+				} else {
+					curs.window = new ByteBufferWindow(this, pos, windowId, map);
+					curs.handle = map;
+				}
+				return;
 			}
-			return;
 		}
 
-		final byte[] b = new byte[windowSize];
+		final byte[] b = new byte[size];
 		synchronized (fd) {
 			fd.seek(pos);
 			fd.readFully(b);
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 11/23] Rewrite WindowCache to use a hash table

[Shawn O. Pearce]

This shaved 10s off my linux-2.6 "jgit rev-list --objects" test.
We're also getting slightly better cache hit ratios, approaching
95% during commit access and 80% during tree access on the same
repository.  Its a significant win.

The cache is also a bit better about memory usage.  We now make
sure the byte[] or ByteBuffer handle is cleared out of the soft
reference when we push the reference into the queue manually. A
small change, but it makes a marked difference with the overall
JVM memory usage.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/lib/ByteWindow.java       |   10 +-
 .../src/org/spearce/jgit/lib/WindowCache.java      |  323 ++++++++++++--------
 .../src/org/spearce/jgit/lib/WindowedFile.java     |    2 +-
 3 files changed, 199 insertions(+), 136 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java
index 1f6beb8..8d37de7 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java
@@ -56,14 +56,20 @@
  *            type of object reference used to manage the window data.
  */
 abstract class ByteWindow<T> extends SoftReference<T> {
+	boolean sizeActive = true;
+
+	ByteWindow<?> chainNext;
+
+	ByteWindow<?> lruPrev;
+
+	ByteWindow<?> lruNext;
+
 	final WindowedFile provider;
 
 	final int id;
 
 	final int size;
 
-	int lastAccessed;
-
 	final long start;
 
 	final long end;
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java
index f617845..f478f04 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2007, Robin Rosenberg <robin.rosenberg@dewire.com>
+ * Copyright (C) 2008, Google Inc.
  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
  *
  * All rights reserved.
@@ -41,11 +41,7 @@
 import java.io.IOException;
 import java.lang.ref.ReferenceQueue;
 
-/**
- * The WindowCache manages reusable <code>Windows</code> and inflaters used by
- * the other windowed file access classes.
- */
-public class WindowCache {
+class WindowCache {
 	private static final int KB = 1024;
 
 	private static final int MB = 1024 * KB;
@@ -68,23 +64,51 @@ private static final int bits(int newSize) {
 
 	static final ReferenceQueue<?> clearedWindowQueue;
 
-	private static ByteWindow[] windows;
+	private static ByteWindow[] cache;
+
+	private static ByteWindow lruHead;
 
-	private static int openWindowCount;
+	private static ByteWindow lruTail;
 
 	private static int openByteCount;
 
-	private static int accessClock;
+	private static int hits;
+
+	private static int reqs;
+
+	private static int opens;
+
+	private static int closes;
 
 	static {
 		maxByteCount = 10 * MB;
 		windowSizeShift = bits(8 * KB);
 		windowSize = 1 << windowSizeShift;
 		mmap = false;
-		windows = new ByteWindow[maxByteCount / windowSize];
+		cache = new ByteWindow[cacheTableSize()];
 		clearedWindowQueue = new ReferenceQueue<Object>();
 	}
 
+	static synchronized String statString() {
+		int maxChain = 0, tot = 0;
+		for (ByteWindow<?> e : cache) {
+			int n = 0;
+			for (; e != null; e = e.chainNext) {
+				n++;
+				tot++;
+			}
+			maxChain = Math.max(maxChain, n);
+		}
+		return "WindowCache[ hits: " + (hits * 100 / reqs) + "%"
+				+ "; windows: " + tot + " maxChain: " + maxChain + "; kb:"
+				+ (openByteCount / KB) + "; cache: " + cache.length + " fds: "
+				+ (opens - closes) + "," + opens + "," + closes + " ]";
+	}
+
+	private static int cacheTableSize() {
+		return 5 * (maxByteCount / windowSize) / 2;
+	}
+
 	/**
 	 * Modify the configuration of the window cache.
 	 * <p>
@@ -135,27 +159,36 @@ private static synchronized void reconfigureImpl(final int packedGitLimit,
 			// We have to throw away every window we have. None
 			// of them are suitable for the new configuration.
 			//
-			for (int i = 0; i < openWindowCount; i++) {
-				final ByteWindow win = windows[i];
-				if (--win.provider.openCount == 0)
-					win.provider.cacheClose();
-				windows[i] = null;
+			for (ByteWindow<?> e : cache) {
+				for (; e != null; e = e.chainNext)
+					clear(e);
+			}
+			runClearedWindowQueue();
+			cache = new ByteWindow[cacheTableSize()];
+
+		} else {
+			if (prune) {
+				// We should decrease our memory usage.
+				//
+				releaseMemory();
+				runClearedWindowQueue();
 			}
-			windows = new ByteWindow[maxByteCount / windowSize];
-			openWindowCount = 0;
-			openByteCount = 0;
-		} else if (prune) {
-			// Our memory limit was decreased so we should try
-			// to drop windows to ensure we meet the new lower
-			// limit we were just given.
-			//
-			final int wincnt = maxByteCount / windowSize;
-			releaseMemory(wincnt, null, 0, 0);
 
-			if (wincnt != windows.length) {
-				final ByteWindow[] n = new ByteWindow[wincnt];
-				System.arraycopy(windows, 0, n, 0, openWindowCount);
-				windows = n;
+			if (cache.length != cacheTableSize()) {
+				// The cache table should be resized.
+				// Rehash every entry.
+				//
+				final ByteWindow[] priorTable = cache;
+
+				cache = new ByteWindow[cacheTableSize()];
+				for (ByteWindow<?> e : priorTable) {
+					for (ByteWindow<?> n; e != null; e = n) {
+						n = e.chainNext;
+						final int idx = hash(e.provider, e.id);
+						e.chainNext = cache[idx];
+						cache[idx] = e;
+					}
+				}
 			}
 		}
 	}
@@ -178,19 +211,27 @@ private static synchronized void reconfigureImpl(final int packedGitLimit,
 	 */
 	public static synchronized final void get(final WindowCursor curs,
 			final WindowedFile wp, final long position) throws IOException {
+		reqs++;
 		final int id = (int) (position >> windowSizeShift);
-		int idx = binarySearch(wp, id);
-		if (0 <= idx) {
-			final ByteWindow<?> w = windows[idx];
-			if ((curs.handle = w.get()) != null) {
-				w.lastAccessed = ++accessClock;
-				curs.window = w;
-				return;
+		final int idx = hash(wp, id);
+		for (ByteWindow<?> e = cache[idx]; e != null; e = e.chainNext) {
+			if (e.provider == wp && e.id == id) {
+				if ((curs.handle = e.get()) != null) {
+					curs.window = e;
+					makeMostRecent(e);
+					hits++;
+					return;
+				}
+
+				clear(e);
+				break;
 			}
 		}
 
-		if (++wp.openCount == 1) {
+		if (wp.openCount == 0) {
 			try {
+				opens++;
+				wp.openCount = 1;
 				wp.cacheOpen();
 			} catch (IOException ioe) {
 				wp.openCount = 0;
@@ -201,106 +242,55 @@ public static synchronized final void get(final WindowCursor curs,
 			} catch (Error ioe) {
 				wp.openCount = 0;
 				throw ioe;
+			} finally {
+				wp.openCount--;
 			}
 
 			// The cacheOpen may have mapped the window we are trying to
 			// map ourselves. Retrying the search ensures that does not
 			// happen to us.
 			//
-			idx = binarySearch(wp, id);
-			if (0 <= idx) {
-				final ByteWindow<?> w = windows[idx];
-				if ((curs.handle = w.get()) != null) {
-					w.lastAccessed = ++accessClock;
-					curs.window = w;
-					return;
+			for (ByteWindow<?> e = cache[idx]; e != null; e = e.chainNext) {
+				if (e.provider == wp && e.id == id) {
+					if ((curs.handle = e.get()) != null) {
+						curs.window = e;
+						makeMostRecent(e);
+						return;
+					}
+
+					clear(e);
+					break;
 				}
 			}
 		}
 
-		idx = -(idx + 1);
-		final int wSz = windowSize(wp, id);
-		idx = releaseMemory(windows.length, wp, idx, wSz);
-
-		if (idx < 0)
-			idx = 0;
-		final int toMove = openWindowCount - idx;
-		if (toMove > 0)
-			System.arraycopy(windows, idx, windows, idx + 1, toMove);
-		wp.loadWindow(curs, id, id << windowSizeShift, wSz);
-		windows[idx] = curs.window;
-		openWindowCount++;
-		openByteCount += curs.window.size;
+		final int wsz = windowSize(wp, id);
+		wp.openCount++;
+		openByteCount += wsz;
+		releaseMemory();
+		runClearedWindowQueue();
+
+		wp.loadWindow(curs, id, id << windowSizeShift, wsz);
+		final ByteWindow<?> e = curs.window;
+		e.chainNext = cache[idx];
+		cache[idx] = e;
+		insertLRU(e);
 	}
 
-	private static int releaseMemory(final int maxWindowCount,
-			final WindowedFile willRead, int insertionIndex, final int willAdd) {
-		for (;;) {
-			final ByteWindow<?> w = (ByteWindow<?>) clearedWindowQueue.poll();
-			if (w == null)
-				break;
-			final int oldest = binarySearch(w.provider, w.id);
-			if (oldest < 0 || windows[oldest] != w)
-				continue; // Must have been evicted by our other controls.
-
-			final WindowedFile p = w.provider;
-			if (--p.openCount == 0 && p != willRead)
-				p.cacheClose();
-
-			openByteCount -= w.size;
-			final int toMove = openWindowCount - oldest - 1;
-			if (toMove > 0)
-				System.arraycopy(windows, oldest + 1, windows, oldest, toMove);
-			windows[--openWindowCount] = null;
-			if (oldest < insertionIndex)
-				insertionIndex--;
-		}
-
-		while (openWindowCount >= maxWindowCount
-				|| (openWindowCount > 0 && openByteCount + willAdd > maxByteCount)) {
-			int oldest = 0;
-			for (int k = openWindowCount - 1; k > 0; k--) {
-				if (windows[k].lastAccessed < windows[oldest].lastAccessed)
-					oldest = k;
-			}
-
-			final ByteWindow w = windows[oldest];
-			final WindowedFile p = w.provider;
-			if (--p.openCount == 0 && p != willRead)
-				p.cacheClose();
-
-			openByteCount -= w.size;
-			final int toMove = openWindowCount - oldest - 1;
-			if (toMove > 0)
-				System.arraycopy(windows, oldest + 1, windows, oldest, toMove);
-			windows[--openWindowCount] = null;
-			w.enqueue();
-			if (oldest < insertionIndex)
-				insertionIndex--;
+	private static void makeMostRecent(ByteWindow<?> e) {
+		if (lruHead != e) {
+			unlinkLRU(e);
+			insertLRU(e);
 		}
-
-		return insertionIndex;
 	}
 
-	private static final int binarySearch(final WindowedFile sprov,
-			final int sid) {
-		if (openWindowCount == 0)
-			return -1;
-		final int shc = sprov.hash;
-		int high = openWindowCount;
-		int low = 0;
-		do {
-			final int mid = (low + high) / 2;
-			final ByteWindow mw = windows[mid];
-			if (mw.provider == sprov && mw.id == sid)
-				return mid;
-			final int mhc = mw.provider.hash;
-			if (mhc < shc || (shc == mhc && mw.id < sid))
-				low = mid + 1;
-			else
-				high = mid;
-		} while (low < high);
-		return -(low + 1);
+	private static void releaseMemory() {
+		ByteWindow<?> e = lruTail;
+		while (openByteCount > maxByteCount && e != null) {
+			final ByteWindow<?> p = e.lruPrev;
+			clear(e);
+			e = p;
+		}
 	}
 
 	/**
@@ -316,22 +306,89 @@ private static final int binarySearch(final WindowedFile sprov,
 	 *            cache.
 	 */
 	public static synchronized final void purge(final WindowedFile wp) {
-		int d = 0;
-		for (int s = 0; s < openWindowCount; s++) {
-			final ByteWindow win = windows[s];
-			if (win.provider != wp)
-				windows[d++] = win;
-			else
-				openByteCount -= win.size;
+		for (ByteWindow e : cache) {
+			for (; e != null; e = e.chainNext) {
+				if (e.provider == wp)
+					clear(e);
+			}
+		}
+		runClearedWindowQueue();
+	}
+
+	private static void runClearedWindowQueue() {
+		ByteWindow<?> e;
+		while ((e = (ByteWindow) clearedWindowQueue.poll()) != null) {
+			unlinkSize(e);
+			unlinkLRU(e);
+			unlinkCache(e);
+			e.chainNext = null;
+			e.lruNext = null;
+			e.lruPrev = null;
 		}
-		openWindowCount = d;
+	}
+
+	private static void clear(final ByteWindow<?> e) {
+		unlinkSize(e);
+		e.clear();
+		e.enqueue();
+	}
 
-		if (wp.openCount > 0) {
-			wp.openCount = 0;
-			wp.cacheClose();
+	private static void unlinkSize(final ByteWindow<?> e) {
+		if (e.sizeActive) {
+			if (--e.provider.openCount == 0) {
+				closes++;
+				e.provider.cacheClose();
+			}
+			openByteCount -= e.size;
+			e.sizeActive = false;
 		}
 	}
 
+	private static void unlinkCache(final ByteWindow dead) {
+		final int idx = hash(dead.provider, dead.id);
+		ByteWindow<?> e = cache[idx], p = null, n;
+		for (; e != null; p = e, e = n) {
+			n = e.chainNext;
+			if (e == dead) {
+				if (p == null)
+					cache[idx] = n;
+				else
+					p.chainNext = n;
+				break;
+			}
+		}
+	}
+
+	private static void unlinkLRU(final ByteWindow e) {
+		final ByteWindow<?> prev = e.lruPrev;
+		final ByteWindow<?> next = e.lruNext;
+
+		if (prev != null)
+			prev.lruNext = next;
+		else
+			lruHead = next;
+
+		if (next != null)
+			next.lruPrev = prev;
+		else
+			lruTail = prev;
+	}
+
+	private static void insertLRU(final ByteWindow<?> e) {
+		final ByteWindow h = lruHead;
+		e.lruPrev = null;
+		e.lruNext = h;
+		if (h != null)
+			h.lruPrev = e;
+		else
+			lruTail = e;
+		lruHead = e;
+	}
+
+	private static int hash(final WindowedFile wp, final int id) {
+		return ((wp.hash + id) >>> 1) % cache.length;
+	}
+
 	private static int windowSize(final WindowedFile file, final int id) {
 		final long len = file.length();
 		final long pos = id << windowSizeShift;
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java
index dd94f24..9c5cf1e 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java
@@ -88,7 +88,7 @@
 	 */
 	public WindowedFile(final File file) {
 		fPath = file;
-		hash = System.identityHashCode(this);
+		hash = System.identityHashCode(this) * 31;
 		length = Long.MAX_VALUE;
 	}
 
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 12/23] Change ByteArrayWindow to read content outside of WindowCache's lock

[Shawn O. Pearce]

This improves the concurrency limit of WindowCache by allowing the
individual windows to be paged in outside of the cache lock.  By
moving it out multiple threads can read in different windows of
the same (or different) pack files concurrently, but we still do
only one read per window.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/lib/ByteArrayWindow.java  |   17 +++++++++++++++++
 .../src/org/spearce/jgit/lib/WindowCache.java      |    2 +-
 .../src/org/spearce/jgit/lib/WindowedFile.java     |   15 +++++++--------
 3 files changed, 25 insertions(+), 9 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java
index cea71be..b32d4f8 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java
@@ -38,6 +38,8 @@
 
 package org.spearce.jgit.lib;
 
+import java.io.IOException;
+import java.nio.ByteBuffer;
 import java.util.zip.DataFormatException;
 import java.util.zip.Inflater;
 
@@ -45,6 +47,8 @@
  * A {@link ByteWindow} with an underlying byte array for storage.
  */
 final class ByteArrayWindow extends ByteWindow<byte[]> {
+	boolean loaded;
+
 	/**
 	 * Constructor for ByteWindow.
 	 * 
@@ -64,6 +68,7 @@ ByteArrayWindow(final WindowedFile o, final long p, final int d,
 	}
 
 	int copy(final byte[] array, final int p, final byte[] b, final int o, int n) {
+		ensureLoaded(array);
 		n = Math.min(array.length - p, n);
 		System.arraycopy(array, p, b, o, n);
 		return n;
@@ -71,6 +76,7 @@ int copy(final byte[] array, final int p, final byte[] b, final int o, int n) {
 
 	int inflate(final byte[] array, final int pos, final byte[] b, int o,
 			final Inflater inf) throws DataFormatException {
+		ensureLoaded(array);
 		while (!inf.finished()) {
 			if (inf.needsInput()) {
 				inf.setInput(array, pos, array.length - pos);
@@ -82,4 +88,15 @@ int inflate(final byte[] array, final int pos, final byte[] b, int o,
 			o += inf.inflate(b, o, b.length - o);
 		return o;
 	}
+
+	private synchronized void ensureLoaded(final byte[] array) {
+		if (!loaded) {
+			try {
+				provider.fd.getChannel().read(ByteBuffer.wrap(array), start);
+			} catch (IOException e) {
+				throw new RuntimeException("Cannot fault in window", e);
+			}
+			loaded = true;
+		}
+	}
 }
\ No newline at end of file
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java
index f478f04..649567b 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java
@@ -270,7 +270,7 @@ public static synchronized final void get(final WindowCursor curs,
 		releaseMemory();
 		runClearedWindowQueue();
 
-		wp.loadWindow(curs, id, id << windowSizeShift, wsz);
+		wp.allocWindow(curs, id, id << windowSizeShift, wsz);
 		final ByteWindow<?> e = curs.window;
 		e.chainNext = cache[idx];
 		cache[idx] = e;
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java
index 9c5cf1e..7626693 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java
@@ -73,7 +73,7 @@
 
 	final int hash;
 
-	private RandomAccessFile fd;
+	RandomAccessFile fd;
 
 	private long length;
 
@@ -298,8 +298,8 @@ void cacheClose() {
 		fd = null;
 	}
 
-	void loadWindow(final WindowCursor curs, final int windowId,
-			final long pos, final int size) throws IOException {
+	void allocWindow(final WindowCursor curs, final int windowId,
+			final long pos, final int size) {
 		if (WindowCache.mmap) {
 			MappedByteBuffer map;
 			try {
@@ -323,7 +323,10 @@ void loadWindow(final WindowCursor curs, final int windowId,
 			if (map != null) {
 				if (map.hasArray()) {
 					final byte[] b = map.array();
-					curs.window = new ByteArrayWindow(this, pos, windowId, b);
+					final ByteArrayWindow w;
+					w = new ByteArrayWindow(this, pos, windowId, b);
+					w.loaded = true;
+					curs.window = w;
 					curs.handle = b;
 				} else {
 					curs.window = new ByteBufferWindow(this, pos, windowId, map);
@@ -334,10 +337,6 @@ void loadWindow(final WindowCursor curs, final int windowId,
 		}
 
 		final byte[] b = new byte[size];
-		synchronized (fd) {
-			fd.seek(pos);
-			fd.readFully(b);
-		}
 		curs.window = new ByteArrayWindow(this, pos, windowId, b);
 		curs.handle = b;
 	}
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 13/23] Dispose of RevCommit buffers when they aren't used in PackWriter

[Shawn O. Pearce]

We don't need the commit buffer, so we might as well throw it
away immediately to reduce the total memory usage within the
writer process.

The same goes for the buffers within UploadPack when its doing
a check to see if it has a complete base.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/lib/PackWriter.java       |    2 ++
 .../src/org/spearce/jgit/transport/UploadPack.java |    1 +
 2 files changed, 3 insertions(+), 0 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
index 89460f2..88b2b1f 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
@@ -802,10 +802,12 @@ private void findObjectsToPack(final ObjectWalk walker)
 
 		while ((o = walker.next()) != null) {
 			addObject(o);
+			o.dispose();
 			initMonitor.update(1);
 		}
 		while ((o = walker.nextObject()) != null) {
 			addObject(o);
+			o.dispose();
 			initMonitor.update(1);
 		}
 		initMonitor.endTask();
diff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/UploadPack.java b/org.spearce.jgit/src/org/spearce/jgit/transport/UploadPack.java
index 4401951..d57df03 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/transport/UploadPack.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/UploadPack.java
@@ -434,6 +434,7 @@ private boolean wantSatisfied(final RevCommit want) throws IOException {
 				}
 				return true;
 			}
+			c.dispose();
 		}
 		return false;
 	}
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 14/23] Don't unpack delta chains while writing a pack from a pack v1 index

[Shawn O. Pearce]

We only need to inflate the delta to verify the content is sane;
going all the way through the delta chain by getCachedBytes is
a massive expensive that we just cannot afford to pay.  This
simple change improves clone time for the Linux kernel from
14m50s to 3m20s, due to the improved throughput in our write
objects phase.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/lib/ByteArrayWindow.java  |   14 ++++++++++++++
 .../src/org/spearce/jgit/lib/ByteBufferWindow.java |   17 +++++++++++++++++
 .../src/org/spearce/jgit/lib/ByteWindow.java       |   10 ++++++++++
 .../src/org/spearce/jgit/lib/PackFile.java         |   18 +++++++++++-------
 .../src/org/spearce/jgit/lib/WindowCursor.java     |   16 ++++++++++++++++
 .../src/org/spearce/jgit/lib/WindowedFile.java     |    5 +++++
 6 files changed, 73 insertions(+), 7 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java
index b32d4f8..7b7c7a4 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java
@@ -89,6 +89,20 @@ int inflate(final byte[] array, final int pos, final byte[] b, int o,
 		return o;
 	}
 
+	void inflateVerify(final byte[] array, final int pos, final Inflater inf)
+			throws DataFormatException {
+		ensureLoaded(array);
+		while (!inf.finished()) {
+			if (inf.needsInput()) {
+				inf.setInput(array, pos, array.length - pos);
+				break;
+			}
+			inf.inflate(verifyGarbageBuffer, 0, verifyGarbageBuffer.length);
+		}
+		while (!inf.finished() && !inf.needsInput())
+			inf.inflate(verifyGarbageBuffer, 0, verifyGarbageBuffer.length);
+	}
+
 	private synchronized void ensureLoaded(final byte[] array) {
 		if (!loaded) {
 			try {
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteBufferWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteBufferWindow.java
index 03bafb1..a6757e8 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteBufferWindow.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteBufferWindow.java
@@ -90,4 +90,21 @@ int inflate(final ByteBuffer buffer, final int pos, final byte[] b, int o,
 			o += inf.inflate(b, o, b.length - o);
 		return o;
 	}
+
+	void inflateVerify(final ByteBuffer buffer, final int pos,
+			final Inflater inf) throws DataFormatException {
+		final byte[] tmp = new byte[512];
+		final ByteBuffer s = buffer.slice();
+		s.position(pos);
+		while (s.remaining() > 0 && !inf.finished()) {
+			if (inf.needsInput()) {
+				final int n = Math.min(s.remaining(), tmp.length);
+				s.get(tmp, 0, n);
+				inf.setInput(tmp, 0, n);
+			}
+			inf.inflate(verifyGarbageBuffer, 0, verifyGarbageBuffer.length);
+		}
+		while (!inf.finished() && !inf.needsInput())
+			inf.inflate(verifyGarbageBuffer, 0, verifyGarbageBuffer.length);
+	}
 }
\ No newline at end of file
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java
index 8d37de7..732664b 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java
@@ -207,4 +207,14 @@ final int inflate(T ref, long pos, byte[] dstbuf, int dstoff, Inflater inf)
 	 */
 	abstract int inflate(T ref, int pos, byte[] dstbuf, int dstoff, Inflater inf)
 			throws DataFormatException;
+
+	protected static final byte[] verifyGarbageBuffer = new byte[2048];
+
+	final void inflateVerify(T ref, long pos, Inflater inf)
+			throws DataFormatException {
+		inflateVerify(ref, (int) (pos - start), inf);
+	}
+
+	abstract void inflateVerify(T ref, int pos, Inflater inf)
+			throws DataFormatException;
 }
\ No newline at end of file
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java
index 3cdca8f..0de4c55 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java
@@ -218,15 +218,19 @@ final void copyRawData(final PackedObjectLoader loader,
 			final ObjectId id = findObjectForOffset(objectOffset);
 			final long expected = idx.findCRC32(id);
 			if (computed != expected)
-				throw new CorruptObjectException(id,
-						"Possible data corruption - CRC32 of raw pack data (object offset "
-								+ objectOffset
-								+ ") mismatch CRC32 from pack index");
+				throw new CorruptObjectException("Object at " + dataOffset
+						+ " in " + getPackFile() + " has bad zlib stream");
 		} else {
+			try {
+				pack.verifyCompressed(dataOffset, curs);
+			} catch (DataFormatException dfe) {
+				final CorruptObjectException coe;
+				coe = new CorruptObjectException("Object at " + dataOffset
+						+ " in " + getPackFile() + " has bad zlib stream");
+				coe.initCause(dfe);
+				throw coe;
+			}
 			pack.copyToStream(dataOffset, buf, cnt, out, curs);
-
-			// read to verify against Adler32 zlib checksum
-			loader.getCachedBytes();
 		}
 	}
 
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCursor.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCursor.java
index 7aad081..5c8bec5 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCursor.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCursor.java
@@ -125,6 +125,22 @@ int inflate(final WindowedFile provider, long position,
 		}
 	}
 
+	void inflateVerify(final WindowedFile provider, long position)
+			throws IOException, DataFormatException {
+		if (inf == null)
+			inf = InflaterCache.get();
+		else
+			inf.reset();
+		for (;;) {
+			pin(provider, position);
+			window.inflateVerify(handle, position, inf);
+			if (inf.finished())
+				return;
+			position = window.end;
+		}
+	}
+
+	
 	private void pin(final WindowedFile provider, final long position)
 			throws IOException {
 		final ByteWindow w = window;
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java
index 7626693..5eb8465 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java
@@ -248,6 +248,11 @@ void readCompressed(final long position, final byte[] dstbuf,
 			throw new EOFException("Short compressed stream at " + position);
 	}
 
+	void verifyCompressed(final long position, final WindowCursor curs)
+			throws IOException, DataFormatException {
+		curs.inflateVerify(this, position);
+	}
+
 	/**
 	 * Overridable hook called after the file is opened.
 	 * <p>
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 15/23] Don't unpack delta chains while converting delta to whole object

[Shawn O. Pearce]

If an object is currently a delta but we need to convert it into
a whole object we shouldn't be chasing the delta chain to get its
real type code.  We had the type code at the time we made the list
of objects to pack; so we save it in the ObjectToPack structure.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/lib/PackWriter.java       |   28 ++++++++++++++-----
 1 files changed, 20 insertions(+), 8 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
index 88b2b1f..a0823c7 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
@@ -705,14 +705,14 @@ private void writeObject(final ObjectToPack otp) throws IOException {
 	private void writeWholeObject(final ObjectToPack otp) throws IOException {
 		if (otp.hasReuseLoader()) {
 			final PackedObjectLoader loader = otp.getReuseLoader();
-			writeObjectHeader(loader.getType(), loader.getSize());
+			writeObjectHeader(otp.getType(), loader.getSize());
 			loader.copyRawData(out, buf);
 			otp.disposeLoader();
 		} else {
 			final ObjectLoader loader = db.openObject(windowCursor, otp);
 			final DeflaterOutputStream deflaterOut = new DeflaterOutputStream(
 					out, deflater);
-			writeObjectHeader(loader.getType(), loader.getSize());
+			writeObjectHeader(otp.getType(), loader.getSize());
 			deflaterOut.write(loader.getCachedBytes());
 			deflaterOut.finish();
 			deflater.reset();
@@ -833,7 +833,7 @@ public void addObject(final RevObject object)
 			return;
 		}
 
-		final ObjectToPack otp = new ObjectToPack(object);
+		final ObjectToPack otp = new ObjectToPack(object, object.getType());
 		try {
 			objectsLists[object.getType()].add(otp);
 		} catch (ArrayIndexOutOfBoundsException x) {
@@ -858,7 +858,8 @@ public void addObject(final RevObject object)
 
 		private PackedObjectLoader reuseLoader;
 
-		private int deltaDepth;
+		/** Low bits contain the objectType; higher bits the deltaDepth */
+		private int flags;
 
 		private boolean wantWrite;
 
@@ -868,9 +869,12 @@ public void addObject(final RevObject object)
 		 *
 		 * @param src
 		 *            object id of object for packing
+		 * @param type
+		 *            real type code of the object, not its in-pack type.
 		 */
-		ObjectToPack(AnyObjectId src) {
+		ObjectToPack(AnyObjectId src, final int type) {
 			super(src);
+			flags |= type;
 		}
 
 		/**
@@ -946,15 +950,23 @@ void disposeLoader() {
 			this.reuseLoader = null;
 		}
 
+		int getType() {
+			return flags & 0x7;
+		}
+
 		int getDeltaDepth() {
-			return deltaDepth;
+			return flags >>> 3;
 		}
 
 		void updateDeltaDepth() {
+			final int d;
 			if (deltaBase instanceof ObjectToPack)
-				deltaDepth = ((ObjectToPack) deltaBase).deltaDepth + 1;
+				d = ((ObjectToPack) deltaBase).getDeltaDepth() + 1;
 			else if (deltaBase != null)
-				deltaDepth = 1;
+				d = 1;
+			else
+				d = 0;
+			flags = (d << 3) | getType();
 		}
 
 		boolean wantWrite() {
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 16/23] Defer parsing of the ObjectId while walking a PackIndex Iterator

[Shawn O. Pearce]

This is a slight performance improvement for the PackReverseIndex
construction.  The only code that really cares about the ObjectId
from a PackIndex entry is test cases.  By avoiding construction
we can save some CPU time during the several passes we do to make
the reverse index data structure within PackWriter.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../tst/org/spearce/jgit/lib/PackIndexTest.java    |    4 +-
 .../tst/org/spearce/jgit/lib/PackWriterTest.java   |    2 +-
 .../src/org/spearce/jgit/lib/PackIndex.java        |   48 +++++++++++--------
 .../src/org/spearce/jgit/lib/PackIndexV1.java      |   20 +++++---
 .../src/org/spearce/jgit/lib/PackIndexV2.java      |   27 +++++++----
 5 files changed, 61 insertions(+), 40 deletions(-)

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexTest.java
index 8ab380e..7163718 100644
--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexTest.java
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexTest.java
@@ -134,10 +134,10 @@ assertEquals("c59759f143fb1fe21c197981df75a7ee00290799", iter.next()
 	 */
 	public void testCompareEntriesOffsetsWithFindOffsets() {
 		for (MutableEntry me : smallIdx) {
-			assertEquals(smallIdx.findOffset(me), me.getOffset());
+			assertEquals(smallIdx.findOffset(me.toObjectId()), me.getOffset());
 		}
 		for (MutableEntry me : denseIdx) {
-			assertEquals(denseIdx.findOffset(me), me.getOffset());
+			assertEquals(denseIdx.findOffset(me.toObjectId()), me.getOffset());
 		}
 	}
 
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackWriterTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackWriterTest.java
index 3c02955..ec138a0 100644
--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackWriterTest.java
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackWriterTest.java
@@ -487,7 +487,7 @@ public int compare(MutableEntry o1, MutableEntry o2) {
 
 		int i = 0;
 		for (MutableEntry me : entries) {
-			assertEquals(objectsOrder[i++], me.copy());
+			assertEquals(objectsOrder[i++].toObjectId(), me.toObjectId());
 		}
 	}
 }
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java
index 5fb41b1..5b7a62d 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java
@@ -239,15 +239,10 @@ abstract long findCRC32(AnyObjectId objId) throws MissingObjectException,
 	 * in pack (both mutable).
 	 * 
 	 */
-	public static class MutableEntry extends MutableObjectId {
-		private long offset;
+	public static class MutableEntry {
+		protected final MutableObjectId idBuffer = new MutableObjectId();
 
-		/**
-		 * Empty constructor. Object fields should be filled in later.
-		 */
-		public MutableEntry() {
-			super();
-		}
+		long offset;
 
 		/**
 		 * Returns offset for this index object entry
@@ -258,30 +253,43 @@ public long getOffset() {
 			return offset;
 		}
 
-		void setOffset(long offset) {
-			this.offset = offset;
+		/** @return hex string describing the object id of this entry. */
+		public String name() {
+			ensureId();
+			return idBuffer.name();
 		}
 
-		private MutableEntry(MutableEntry src) {
-			super(src);
-			this.offset = src.offset;
+		/** @return a copy of the object id. */
+		public ObjectId toObjectId() {
+			ensureId();
+			return idBuffer.toObjectId();
 		}
 
-		/**
-		 * Returns mutable copy of this mutable entry.
-		 * 
-		 * @return copy of this mutable entry
-		 */
+		/** @return a complete copy of this entry, that won't modify */
 		public MutableEntry cloneEntry() {
-			return new MutableEntry(this);
+			final MutableEntry r = new MutableEntry();
+			ensureId();
+			r.idBuffer.w1 = idBuffer.w1;
+			r.idBuffer.w2 = idBuffer.w2;
+			r.idBuffer.w3 = idBuffer.w3;
+			r.idBuffer.w4 = idBuffer.w4;
+			r.idBuffer.w5 = idBuffer.w5;
+			r.offset = offset;
+			return r;
+		}
+		
+		protected void ensureId() {
+			// Override in implementations.
 		}
 	}
 
 	protected abstract class EntriesIterator implements Iterator<MutableEntry> {
-		protected MutableEntry objectId = new MutableEntry();
+		protected final MutableEntry entry = initEntry();
 
 		protected long returnedNumber = 0;
 
+		protected abstract MutableEntry initEntry();
+
 		public boolean hasNext() {
 			return returnedNumber < getObjectCount();
 		}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java
index 02465f6..90b5f6f 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java
@@ -162,21 +162,27 @@ boolean hasCRC32Support() {
 
 		private int levelTwo;
 
+		@Override
+		protected MutableEntry initEntry() {
+			return new MutableEntry() {
+				protected void ensureId() {
+					idBuffer.fromRaw(idxdata[levelOne], levelTwo
+							- Constants.OBJECT_ID_LENGTH);
+				}
+			};
+		}
+
 		public MutableEntry next() {
 			for (; levelOne < idxdata.length; levelOne++) {
 				if (idxdata[levelOne] == null)
 					continue;
-
 				if (levelTwo < idxdata[levelOne].length) {
-					long offset = NB.decodeUInt32(idxdata[levelOne], levelTwo);
-					objectId.setOffset(offset);
-					objectId.fromRaw(idxdata[levelOne], levelTwo + 4);
+					entry.offset = NB.decodeUInt32(idxdata[levelOne], levelTwo);
 					levelTwo += Constants.OBJECT_ID_LENGTH + 4;
 					returnedNumber++;
-					return objectId;
-				} else {
-					levelTwo = 0;
+					return entry;
 				}
+				levelTwo = 0;
 			}
 			throw new NoSuchElementException();
 		}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java
index cc3ad65..48a5206 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java
@@ -234,25 +234,32 @@ else if (cmp == 0) {
 
 		private int levelTwo;
 
+		@Override
+		protected MutableEntry initEntry() {
+			return new MutableEntry() {
+				protected void ensureId() {
+					idBuffer.fromRaw(names[levelOne], levelTwo
+							- Constants.OBJECT_ID_LENGTH / 4);
+				}
+			};
+		}
+
 		public MutableEntry next() {
 			for (; levelOne < names.length; levelOne++) {
 				if (levelTwo < names[levelOne].length) {
-					objectId.fromRaw(names[levelOne], levelTwo);
-					int arrayIdx = levelTwo / (Constants.OBJECT_ID_LENGTH / 4)
-							* 4;
-					long offset = NB.decodeUInt32(offset32[levelOne], arrayIdx);
+					int idx = levelTwo / (Constants.OBJECT_ID_LENGTH / 4) * 4;
+					long offset = NB.decodeUInt32(offset32[levelOne], idx);
 					if ((offset & IS_O64) != 0) {
-						arrayIdx = (8 * (int) (offset & ~IS_O64));
-						offset = NB.decodeUInt64(offset64, arrayIdx);
+						idx = (8 * (int) (offset & ~IS_O64));
+						offset = NB.decodeUInt64(offset64, idx);
 					}
-					objectId.setOffset(offset);
+					entry.offset = offset;
 
 					levelTwo += Constants.OBJECT_ID_LENGTH / 4;
 					returnedNumber++;
-					return objectId;
-				} else {
-					levelTwo = 0;
+					return entry;
 				}
+				levelTwo = 0;
 			}
 			throw new NoSuchElementException();
 		}
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 17/23] Only do one getCachedBytes per whole object written

[Shawn O. Pearce]

Getting the size of an object may cause getCachedBytes to be invoked,
and then have its result discarded.  To save time we should make the
call to getCachedBytes first, hold onto the byte[], then obtain the
size off the byte[], and finally write from the byte[].

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/lib/PackWriter.java       |    5 +++--
 1 files changed, 3 insertions(+), 2 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
index a0823c7..bb889e8 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
@@ -710,10 +710,11 @@ private void writeWholeObject(final ObjectToPack otp) throws IOException {
 			otp.disposeLoader();
 		} else {
 			final ObjectLoader loader = db.openObject(windowCursor, otp);
+			final byte[] data = loader.getCachedBytes();
 			final DeflaterOutputStream deflaterOut = new DeflaterOutputStream(
 					out, deflater);
-			writeObjectHeader(otp.getType(), loader.getSize());
-			deflaterOut.write(loader.getCachedBytes());
+			writeObjectHeader(otp.getType(), data.length);
+			deflaterOut.write(data);
 			deflaterOut.finish();
 			deflater.reset();
 		}
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 18/23] Correctly use a long for the offsets within a generated pack

[Shawn O. Pearce]

Pack files can be larger than 2 GiB, especially if the PackIndexV2
format is being used.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../tst/org/spearce/jgit/lib/PackWriterTest.java   |   12 ++++++------
 .../spearce/jgit/util/CountingOutputStream.java    |    5 ++---
 2 files changed, 8 insertions(+), 9 deletions(-)

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackWriterTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackWriterTest.java
index ec138a0..98e0d3a 100644
--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackWriterTest.java
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackWriterTest.java
@@ -308,11 +308,11 @@ public void testWritePack4ThinPack() throws IOException {
 	 */
 	public void testWritePack2SizeDeltasVsNoDeltas() throws Exception {
 		testWritePack2();
-		final int sizePack2NoDeltas = cos.getCount();
+		final long sizePack2NoDeltas = cos.getCount();
 		tearDown();
 		setUp();
 		testWritePack2DeltasReuseRefs();
-		final int sizePack2DeltasRefs = cos.getCount();
+		final long sizePack2DeltasRefs = cos.getCount();
 
 		assertTrue(sizePack2NoDeltas > sizePack2DeltasRefs);
 	}
@@ -327,11 +327,11 @@ public void testWritePack2SizeDeltasVsNoDeltas() throws Exception {
 	 */
 	public void testWritePack2SizeOffsetsVsRefs() throws Exception {
 		testWritePack2DeltasReuseRefs();
-		final int sizePack2DeltasRefs = cos.getCount();
+		final long sizePack2DeltasRefs = cos.getCount();
 		tearDown();
 		setUp();
 		testWritePack2DeltasReuseOffsets();
-		final int sizePack2DeltasOffsets = cos.getCount();
+		final long sizePack2DeltasOffsets = cos.getCount();
 
 		assertTrue(sizePack2DeltasRefs > sizePack2DeltasOffsets);
 	}
@@ -345,11 +345,11 @@ public void testWritePack2SizeOffsetsVsRefs() throws Exception {
 	 */
 	public void testWritePack4SizeThinVsNoThin() throws Exception {
 		testWritePack4();
-		final int sizePack4 = cos.getCount();
+		final long sizePack4 = cos.getCount();
 		tearDown();
 		setUp();
 		testWritePack4ThinPack();
-		final int sizePack4Thin = cos.getCount();
+		final long sizePack4Thin = cos.getCount();
 
 		assertTrue(sizePack4 > sizePack4Thin);
 	}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/util/CountingOutputStream.java b/org.spearce.jgit/src/org/spearce/jgit/util/CountingOutputStream.java
index 53935dc..b0b5f7d 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/util/CountingOutputStream.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/util/CountingOutputStream.java
@@ -45,8 +45,7 @@
  * Counting output stream decoration. Counts bytes written to stream.
  */
 public class CountingOutputStream extends FilterOutputStream {
-
-	private int count;
+	private long count;
 
 	/**
 	 * Create counting stream being decorated to provided real output stream.
@@ -76,7 +75,7 @@ public void write(byte[] b, int off, int len) throws IOException {
 	 * @return number of written bytes since last reset (object is reset upon
 	 *         creation)
 	 */
-	public int getCount() {
+	public long getCount() {
 		return count;
 	}
 
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 19/23] Allow more direct access to determine isWritten

[Shawn O. Pearce]

This gives the JVM a better chance to inline the isWritten method
when writing a pack file out.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/lib/PackWriter.java       |    2 +-
 .../spearce/jgit/transport/PackedObjectInfo.java   |    2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
index bb889e8..50d06c2 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
@@ -932,7 +932,7 @@ boolean isDeltaRepresentation() {
 		 * @return true if object is already written; false otherwise.
 		 */
 		boolean isWritten() {
-			return getOffset() != 0;
+			return offset != 0;
 		}
 
 		PackedObjectLoader getReuseLoader() {
diff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/PackedObjectInfo.java b/org.spearce.jgit/src/org/spearce/jgit/transport/PackedObjectInfo.java
index f37f421..045b795 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/transport/PackedObjectInfo.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/PackedObjectInfo.java
@@ -49,7 +49,7 @@
  * objects from the pack. This extension of ObjectId includes the offset.
  */
 public class PackedObjectInfo extends ObjectId {
-	private long offset;
+	protected long offset;
 
 	private int crc;
 
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 20/23] Move "wantWrite" field of ObjectToPack into the flags field

[Shawn O. Pearce]

This reduces the ObjectToPack structure by 4 bytes, saving us 4 MB
on the linux kernel repository.  Its only a single bit value, so
keeping it in a full boolean is rather wasteful given how many of
these objects we need in to pack a large project.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/lib/PackWriter.java       |   23 ++++++++++++-------
 1 files changed, 14 insertions(+), 9 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
index 50d06c2..3ef9154 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
@@ -859,11 +859,16 @@ public void addObject(final RevObject object)
 
 		private PackedObjectLoader reuseLoader;
 
-		/** Low bits contain the objectType; higher bits the deltaDepth */
+		/**
+		 * Bit field, from bit 0 to bit 31:
+		 * <ul>
+		 * <li>1 bit: wantWrite</li>
+		 * <li>3 bits: type</li>
+		 * <li>28 bits: deltaDepth</li>
+		 * </ul>
+		 */
 		private int flags;
 
-		private boolean wantWrite;
-
 		/**
 		 * Construct object for specified object id. <br/> By default object is
 		 * marked as not written and non-delta packed (as a whole object).
@@ -875,7 +880,7 @@ public void addObject(final RevObject object)
 		 */
 		ObjectToPack(AnyObjectId src, final int type) {
 			super(src);
-			flags |= type;
+			flags |= type << 1;
 		}
 
 		/**
@@ -952,11 +957,11 @@ void disposeLoader() {
 		}
 
 		int getType() {
-			return flags & 0x7;
+			return (flags>>1) & 0x7;
 		}
 
 		int getDeltaDepth() {
-			return flags >>> 3;
+			return flags >>> 4;
 		}
 
 		void updateDeltaDepth() {
@@ -967,15 +972,15 @@ else if (deltaBase != null)
 				d = 1;
 			else
 				d = 0;
-			flags = (d << 3) | getType();
+			flags = (d << 4) | flags & 0x15;
 		}
 
 		boolean wantWrite() {
-			return wantWrite;
+			return (flags & 1) == 1;
 		}
 
 		void markWantWrite() {
-			this.wantWrite = true;
+			flags |= 1;
 		}
 	}
 }
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 21/23] Use an ArrayList for the reuseLoader collection in PackWriter

[Shawn O. Pearce]

Nulling out the elements of the array is quicker than deallocating
LinkedList nodes and allocating new ones for the next use.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/lib/PackWriter.java       |    4 +---
 1 files changed, 1 insertions(+), 3 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
index 3ef9154..69b4294 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
@@ -46,7 +46,6 @@
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Iterator;
-import java.util.LinkedList;
 import java.util.List;
 import java.util.zip.Deflater;
 import java.util.zip.DeflaterOutputStream;
@@ -577,8 +576,7 @@ public void writePack(OutputStream packStream) throws IOException {
 
 	private void searchForReuse() throws IOException {
 		initMonitor.beginTask(SEARCHING_REUSE_PROGRESS, getObjectsNumber());
-		final Collection<PackedObjectLoader> reuseLoaders = new LinkedList<PackedObjectLoader>();
-
+		final Collection<PackedObjectLoader> reuseLoaders = new ArrayList<PackedObjectLoader>();
 		for (List<ObjectToPack> list : objectsLists) {
 			for (ObjectToPack otp : list) {
 				if (initMonitor.isCancelled())
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 22/23] Don't cut off existing delta chains if we are reusing deltas

[Shawn O. Pearce]

The existing pack file may have chains longer than our current max
depth, such as if it is a historical pack and was generated with a
maximum chain depth >100.  Cutting off the chains would create a
bigger pack file that we need to transmit, and it costs a lot more
CPU time to expand the delta object in order to recompress it whole,
because we couldn't copy it directly from the pack file.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/lib/PackWriter.java       |    6 ------
 1 files changed, 0 insertions(+), 6 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
index 69b4294..4c01b6e 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
@@ -681,12 +681,6 @@ private void writeObject(final ObjectToPack otp) throws IOException {
 					writeObject(deltaBase);
 				}
 			}
-
-			otp.updateDeltaDepth();
-			if (otp.getDeltaDepth() > maxDeltaDepth) {
-				otp.clearDeltaBase();
-				otp.disposeLoader();
-			}
 		}
 
 		assert !otp.isWritten();
-- 
1.6.1.rc4.301.g5497a

[JGIT PATCH 23/23] Correctly honor the thin parameter to PackWriter.writePack

[Shawn O. Pearce]

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/lib/PackWriter.java       |    5 +++--
 1 files changed, 3 insertions(+), 2 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
index 4c01b6e..b2d0227 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java
@@ -465,8 +465,9 @@ public void preparePack(
 			final Collection<? extends ObjectId> uninterestingObjects,
 			final boolean thin, final boolean ignoreMissingUninteresting)
 			throws IOException {
+		this.thin = thin;
 		ObjectWalk walker = setUpWalker(interestingObjects,
-				uninterestingObjects, thin, ignoreMissingUninteresting);
+				uninterestingObjects, ignoreMissingUninteresting);
 		findObjectsToPack(walker);
 	}
 
@@ -759,7 +760,7 @@ private void writeChecksum() throws IOException {
 	private ObjectWalk setUpWalker(
 			final Collection<? extends ObjectId> interestingObjects,
 			final Collection<? extends ObjectId> uninterestingObjects,
-			final boolean thin, final boolean ignoreMissingUninteresting)
+			final boolean ignoreMissingUninteresting)
 			throws MissingObjectException, IOException,
 			IncorrectObjectTypeException {
 		final ObjectWalk walker = new ObjectWalk(db);
-- 
1.6.1.rc4.301.g5497a

Re: [JGIT PATCH 11/23] Rewrite WindowCache to use a hash table

[Robin Rosenberg]

torsdag 25 december 2008 03:11:07 skrev Shawn O. Pearce:
> diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java
> index f617845..f478f04 100644
> --- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java
> +++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java
> @@ -41,11 +41,7 @@
>  import java.io.IOException;
>  import java.lang.ref.ReferenceQueue;
>  
> -/**
> - * The WindowCache manages reusable <code>Windows</code> and inflaters used by
> - * the other windowed file access classes.
> - */
> -public class WindowCache {
> +class WindowCache {

This breaks the Eclipse plugin which want to call WindowCache.reconfigure. Package level
class can also have javadocs. Even though we do not require it, I still thinks it's a good idea. Not
sure how useful that one was.

-- robin

[JGIT PATCH 11/23 v2] Rewrite WindowCache to use a hash table

[Shawn O. Pearce]

This shaved 10s off my linux-2.6 "jgit rev-list --objects" test.
We're also getting slightly better cache hit ratios, approaching
95% during commit access and 80% during tree access on the same
repository.  Its a significant win.

The cache is also a bit better about memory usage.  We now make
sure the byte[] or ByteBuffer handle is cleared out of the soft
reference when we push the reference into the queue manually. A
small change, but it makes a marked difference with the overall
JVM memory usage.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
  Robin Rosenberg <robin.rosenberg.lists@dewire.com> wrote:
  > > -/**
  > > - * The WindowCache manages reusable <code>Windows</code> and inflaters used by
  > > - * the other windowed file access classes.
  > > - */
  > > -public class WindowCache {
  > > +class WindowCache {
  > 
  > This breaks the Eclipse plugin which want to call WindowCache.reconfigure. Package level
  > class can also have javadocs. Even though we do not require it, I still thinks it's a good idea. Not
  > sure how useful that one was.

  Dammit, good catch.  I was working on this in the context of only
  having the JGit code in my workspace, so I missed the impact on
  the Eclipse plugin, and possibly on the NetBeans one as well.

  Corrected patch follows.

  
 .../src/org/spearce/jgit/lib/ByteWindow.java       |   10 +-
 .../src/org/spearce/jgit/lib/WindowCache.java      |  317 ++++++++++++--------
 .../src/org/spearce/jgit/lib/WindowedFile.java     |    2 +-
 3 files changed, 198 insertions(+), 131 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java
index 1f6beb8..8d37de7 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java
@@ -56,14 +56,20 @@
  *            type of object reference used to manage the window data.
  */
 abstract class ByteWindow<T> extends SoftReference<T> {
+	boolean sizeActive = true;
+
+	ByteWindow<?> chainNext;
+
+	ByteWindow<?> lruPrev;
+
+	ByteWindow<?> lruNext;
+
 	final WindowedFile provider;
 
 	final int id;
 
 	final int size;
 
-	int lastAccessed;
-
 	final long start;
 
 	final long end;
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java
index f617845..e71ca73 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2007, Robin Rosenberg <robin.rosenberg@dewire.com>
+ * Copyright (C) 2008, Google Inc.
  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
  *
  * All rights reserved.
@@ -68,23 +68,51 @@ private static final int bits(int newSize) {
 
 	static final ReferenceQueue<?> clearedWindowQueue;
 
-	private static ByteWindow[] windows;
+	private static ByteWindow[] cache;
 
-	private static int openWindowCount;
+	private static ByteWindow lruHead;
+
+	private static ByteWindow lruTail;
 
 	private static int openByteCount;
 
-	private static int accessClock;
+	private static int hits;
+
+	private static int reqs;
+
+	private static int opens;
+
+	private static int closes;
 
 	static {
 		maxByteCount = 10 * MB;
 		windowSizeShift = bits(8 * KB);
 		windowSize = 1 << windowSizeShift;
 		mmap = false;
-		windows = new ByteWindow[maxByteCount / windowSize];
+		cache = new ByteWindow[cacheTableSize()];
 		clearedWindowQueue = new ReferenceQueue<Object>();
 	}
 
+	static synchronized String statString() {
+		int maxChain = 0, tot = 0;
+		for (ByteWindow<?> e : cache) {
+			int n = 0;
+			for (; e != null; e = e.chainNext) {
+				n++;
+				tot++;
+			}
+			maxChain = Math.max(maxChain, n);
+		}
+		return "WindowCache[ hits: " + (hits * 100 / reqs) + "%"
+				+ "; windows: " + tot + " maxChain: " + maxChain + "; kb:"
+				+ (openByteCount / KB) + "; cache: " + cache.length + " fds: "
+				+ (opens - closes) + "," + opens + "," + closes + " ]";
+	}
+
+	private static int cacheTableSize() {
+		return 5 * (maxByteCount / windowSize) / 2;
+	}
+
 	/**
 	 * Modify the configuration of the window cache.
 	 * <p>
@@ -135,27 +163,36 @@ private static synchronized void reconfigureImpl(final int packedGitLimit,
 			// We have to throw away every window we have. None
 			// of them are suitable for the new configuration.
 			//
-			for (int i = 0; i < openWindowCount; i++) {
-				final ByteWindow win = windows[i];
-				if (--win.provider.openCount == 0)
-					win.provider.cacheClose();
-				windows[i] = null;
+			for (ByteWindow<?> e : cache) {
+				for (; e != null; e = e.chainNext)
+					clear(e);
+			}
+			runClearedWindowQueue();
+			cache = new ByteWindow[cacheTableSize()];
+
+		} else {
+			if (prune) {
+				// We should decrease our memory usage.
+				//
+				releaseMemory();
+				runClearedWindowQueue();
 			}
-			windows = new ByteWindow[maxByteCount / windowSize];
-			openWindowCount = 0;
-			openByteCount = 0;
-		} else if (prune) {
-			// Our memory limit was decreased so we should try
-			// to drop windows to ensure we meet the new lower
-			// limit we were just given.
-			//
-			final int wincnt = maxByteCount / windowSize;
-			releaseMemory(wincnt, null, 0, 0);
 
-			if (wincnt != windows.length) {
-				final ByteWindow[] n = new ByteWindow[wincnt];
-				System.arraycopy(windows, 0, n, 0, openWindowCount);
-				windows = n;
+			if (cache.length != cacheTableSize()) {
+				// The cache table should be resized.
+				// Rehash every entry.
+				//
+				final ByteWindow[] priorTable = cache;
+
+				cache = new ByteWindow[cacheTableSize()];
+				for (ByteWindow<?> e : priorTable) {
+					for (ByteWindow<?> n; e != null; e = n) {
+						n = e.chainNext;
+						final int idx = hash(e.provider, e.id);
+						e.chainNext = cache[idx];
+						cache[idx] = e;
+					}
+				}
 			}
 		}
 	}
@@ -178,19 +215,27 @@ private static synchronized void reconfigureImpl(final int packedGitLimit,
 	 */
 	public static synchronized final void get(final WindowCursor curs,
 			final WindowedFile wp, final long position) throws IOException {
+		reqs++;
 		final int id = (int) (position >> windowSizeShift);
-		int idx = binarySearch(wp, id);
-		if (0 <= idx) {
-			final ByteWindow<?> w = windows[idx];
-			if ((curs.handle = w.get()) != null) {
-				w.lastAccessed = ++accessClock;
-				curs.window = w;
-				return;
+		final int idx = hash(wp, id);
+		for (ByteWindow<?> e = cache[idx]; e != null; e = e.chainNext) {
+			if (e.provider == wp && e.id == id) {
+				if ((curs.handle = e.get()) != null) {
+					curs.window = e;
+					makeMostRecent(e);
+					hits++;
+					return;
+				}
+
+				clear(e);
+				break;
 			}
 		}
 
-		if (++wp.openCount == 1) {
+		if (wp.openCount == 0) {
 			try {
+				opens++;
+				wp.openCount = 1;
 				wp.cacheOpen();
 			} catch (IOException ioe) {
 				wp.openCount = 0;
@@ -201,106 +246,55 @@ public static synchronized final void get(final WindowCursor curs,
 			} catch (Error ioe) {
 				wp.openCount = 0;
 				throw ioe;
+			} finally {
+				wp.openCount--;
 			}
 
 			// The cacheOpen may have mapped the window we are trying to
 			// map ourselves. Retrying the search ensures that does not
 			// happen to us.
 			//
-			idx = binarySearch(wp, id);
-			if (0 <= idx) {
-				final ByteWindow<?> w = windows[idx];
-				if ((curs.handle = w.get()) != null) {
-					w.lastAccessed = ++accessClock;
-					curs.window = w;
-					return;
+			for (ByteWindow<?> e = cache[idx]; e != null; e = e.chainNext) {
+				if (e.provider == wp && e.id == id) {
+					if ((curs.handle = e.get()) != null) {
+						curs.window = e;
+						makeMostRecent(e);
+						return;
+					}
+
+					clear(e);
+					break;
 				}
 			}
 		}
 
-		idx = -(idx + 1);
-		final int wSz = windowSize(wp, id);
-		idx = releaseMemory(windows.length, wp, idx, wSz);
-
-		if (idx < 0)
-			idx = 0;
-		final int toMove = openWindowCount - idx;
-		if (toMove > 0)
-			System.arraycopy(windows, idx, windows, idx + 1, toMove);
-		wp.loadWindow(curs, id, id << windowSizeShift, wSz);
-		windows[idx] = curs.window;
-		openWindowCount++;
-		openByteCount += curs.window.size;
+		final int wsz = windowSize(wp, id);
+		wp.openCount++;
+		openByteCount += wsz;
+		releaseMemory();
+		runClearedWindowQueue();
+
+		wp.loadWindow(curs, id, id << windowSizeShift, wsz);
+		final ByteWindow<?> e = curs.window;
+		e.chainNext = cache[idx];
+		cache[idx] = e;
+		insertLRU(e);
 	}
 
-	private static int releaseMemory(final int maxWindowCount,
-			final WindowedFile willRead, int insertionIndex, final int willAdd) {
-		for (;;) {
-			final ByteWindow<?> w = (ByteWindow<?>) clearedWindowQueue.poll();
-			if (w == null)
-				break;
-			final int oldest = binarySearch(w.provider, w.id);
-			if (oldest < 0 || windows[oldest] != w)
-				continue; // Must have been evicted by our other controls.
-
-			final WindowedFile p = w.provider;
-			if (--p.openCount == 0 && p != willRead)
-				p.cacheClose();
-
-			openByteCount -= w.size;
-			final int toMove = openWindowCount - oldest - 1;
-			if (toMove > 0)
-				System.arraycopy(windows, oldest + 1, windows, oldest, toMove);
-			windows[--openWindowCount] = null;
-			if (oldest < insertionIndex)
-				insertionIndex--;
-		}
-
-		while (openWindowCount >= maxWindowCount
-				|| (openWindowCount > 0 && openByteCount + willAdd > maxByteCount)) {
-			int oldest = 0;
-			for (int k = openWindowCount - 1; k > 0; k--) {
-				if (windows[k].lastAccessed < windows[oldest].lastAccessed)
-					oldest = k;
-			}
-
-			final ByteWindow w = windows[oldest];
-			final WindowedFile p = w.provider;
-			if (--p.openCount == 0 && p != willRead)
-				p.cacheClose();
-
-			openByteCount -= w.size;
-			final int toMove = openWindowCount - oldest - 1;
-			if (toMove > 0)
-				System.arraycopy(windows, oldest + 1, windows, oldest, toMove);
-			windows[--openWindowCount] = null;
-			w.enqueue();
-			if (oldest < insertionIndex)
-				insertionIndex--;
+	private static void makeMostRecent(ByteWindow<?> e) {
+		if (lruHead != e) {
+			unlinkLRU(e);
+			insertLRU(e);
 		}
-
-		return insertionIndex;
 	}
 
-	private static final int binarySearch(final WindowedFile sprov,
-			final int sid) {
-		if (openWindowCount == 0)
-			return -1;
-		final int shc = sprov.hash;
-		int high = openWindowCount;
-		int low = 0;
-		do {
-			final int mid = (low + high) / 2;
-			final ByteWindow mw = windows[mid];
-			if (mw.provider == sprov && mw.id == sid)
-				return mid;
-			final int mhc = mw.provider.hash;
-			if (mhc < shc || (shc == mhc && mw.id < sid))
-				low = mid + 1;
-			else
-				high = mid;
-		} while (low < high);
-		return -(low + 1);
+	private static void releaseMemory() {
+		ByteWindow<?> e = lruTail;
+		while (openByteCount > maxByteCount && e != null) {
+			final ByteWindow<?> p = e.lruPrev;
+			clear(e);
+			e = p;
+		}
 	}
 
 	/**
@@ -316,22 +310,89 @@ private static final int binarySearch(final WindowedFile sprov,
 	 *            cache.
 	 */
 	public static synchronized final void purge(final WindowedFile wp) {
-		int d = 0;
-		for (int s = 0; s < openWindowCount; s++) {
-			final ByteWindow win = windows[s];
-			if (win.provider != wp)
-				windows[d++] = win;
-			else
-				openByteCount -= win.size;
+		for (ByteWindow e : cache) {
+			for (; e != null; e = e.chainNext) {
+				if (e.provider == wp)
+					clear(e);
+			}
+		}
+		runClearedWindowQueue();
+	}
+
+	private static void runClearedWindowQueue() {
+		ByteWindow<?> e;
+		while ((e = (ByteWindow) clearedWindowQueue.poll()) != null) {
+			unlinkSize(e);
+			unlinkLRU(e);
+			unlinkCache(e);
+			e.chainNext = null;
+			e.lruNext = null;
+			e.lruPrev = null;
 		}
-		openWindowCount = d;
+	}
+
+	private static void clear(final ByteWindow<?> e) {
+		unlinkSize(e);
+		e.clear();
+		e.enqueue();
+	}
 
-		if (wp.openCount > 0) {
-			wp.openCount = 0;
-			wp.cacheClose();
+	private static void unlinkSize(final ByteWindow<?> e) {
+		if (e.sizeActive) {
+			if (--e.provider.openCount == 0) {
+				closes++;
+				e.provider.cacheClose();
+			}
+			openByteCount -= e.size;
+			e.sizeActive = false;
 		}
 	}
 
+	private static void unlinkCache(final ByteWindow dead) {
+		final int idx = hash(dead.provider, dead.id);
+		ByteWindow<?> e = cache[idx], p = null, n;
+		for (; e != null; p = e, e = n) {
+			n = e.chainNext;
+			if (e == dead) {
+				if (p == null)
+					cache[idx] = n;
+				else
+					p.chainNext = n;
+				break;
+			}
+		}
+	}
+
+	private static void unlinkLRU(final ByteWindow e) {
+		final ByteWindow<?> prev = e.lruPrev;
+		final ByteWindow<?> next = e.lruNext;
+
+		if (prev != null)
+			prev.lruNext = next;
+		else
+			lruHead = next;
+
+		if (next != null)
+			next.lruPrev = prev;
+		else
+			lruTail = prev;
+	}
+
+	private static void insertLRU(final ByteWindow<?> e) {
+		final ByteWindow h = lruHead;
+		e.lruPrev = null;
+		e.lruNext = h;
+		if (h != null)
+			h.lruPrev = e;
+		else
+			lruTail = e;
+		lruHead = e;
+	}
+
+	private static int hash(final WindowedFile wp, final int id) {
+		return ((wp.hash + id) >>> 1) % cache.length;
+	}
+
 	private static int windowSize(final WindowedFile file, final int id) {
 		final long len = file.length();
 		final long pos = id << windowSizeShift;
diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java
index dd94f24..9c5cf1e 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java
@@ -88,7 +88,7 @@
 	 */
 	public WindowedFile(final File file) {
 		fPath = file;
-		hash = System.identityHashCode(this);
+		hash = System.identityHashCode(this) * 31;
 		length = Long.MAX_VALUE;
 	}
 
-- 
1.6.1.302.gccd4d