{"thread":{"id":"16859","subject":"[JGIT PATCH 04/23] Switch ObjectWalk to use the new MutableObjectId form in TreeWalk","startedAt":"2008-12-25T02:10:56Z","lastAt":"2008-12-27T17:32:51Z","messageCount":26,"participants":["Shawn O. Pearce","Robin Rosenberg"],"isPatch":true,"patchVersion":1,"patchTotal":23},"messages":[{"id":"98660","messageId":"1230171079-17156-1-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":null,"subject":"[JGIT PATCH 00/18] Misc. performance tweaks","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:10:56Z","receivedAt":"2008-12-25T02:10:56Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Cloning linux-2.6.git through JGit was painful at best. I found\nand fixed some small bottlenecks after a day of profiling and\nexperimentation, but we're still slower than C git.\n\nWith this series I managed to drop the time for \"git clone --bare\"\nover git:// using \"jgit daemon\" server and \"C git\" client.\nAny difference between jgit and \"C git\" is in the server side.\n\n before: 7m42.488s\n after : 2m33.882s\n C git : 1m26.158s (\"git daemon\" server)\n\n\nSo I'm still seeing a major bottleneck that I can't quite fix.\n\nObject enumeration (aka \"Counting ...\") takes too long, because we\nspend a huge amount of time unpacking delta chains for trees so we\ncan enumerate their referenced items.\n\nOur UnpackedObjectCache gets <4% hit ratio when doing the trees\nfor linux-2.6.git. Increasing the cache doesn't have a noticable\nimprovement on performance.\n\nI tried rewriting UnpackedObjectCache to permit multiple objects\nper hash bucket. Even with that (and the maximum chain length\nper bucket not exceeding 4 items) our hit ratio was still <5%,\nso I tossed that implementation out.\n\n\"jgit rev-list --objects\" vs. \"git rev-list --objects\" is a huge\ndifference, about 1m difference. That's most of the time difference\nI noted above between jgit and C git on the server side.\n\nSo with this series, we're better. Its actually almost tolerable\nto clone linux-2.6 through a jgit backed server.\n\n\nShawn O. Pearce (23):\n Improve hit performance on the UnpackedObjectCache\n Add MutableObjectId.clear() to set the id to zeroId\n Allow TreeWalk callers to pass a MutableObjectId to get the current\n id\n Switch ObjectWalk to use the new MutableObjectId form in TreeWalk\n Change walker based fetch to use TreeWalk's MutableObjectId accessor\n Reduce garbage allocation when using TreeWalk\n Switch ObjectWalk to use a naked CanonicalTreeParser because its\n faster\n Remove the unused PackFile.get(ObjectId) form\n Remove getId from ObjectLoader API as its unnecessary overhead\n Make mmap mode more reliable by forcing GC at the correct spot\n Rewrite WindowCache to use a hash table\n Change ByteArrayWindow to read content outside of WindowCache's lock\n Dispose of RevCommit buffers when they aren't used in PackWriter\n Don't unpack delta chains while writing a pack from a pack v1 index\n Don't unpack delta chains while converting delta to whole object\n Defer parsing of the ObjectId while walking a PackIndex Iterator\n Only do one getCachedBytes per whole object written\n Correctly use a long for the offsets within a generated pack\n Allow more direct access to determine isWritten\n Move \"wantWrite\" field of ObjectToPack into the flags field\n Use an ArrayList for the reuseLoader collection in PackWriter\n Don't cut off existing delta chains if we are reusing deltas\n Correctly honor the thin parameter to PackWriter.writePack\n\n .../jgit/pgm/opt/AbstractTreeIteratorHandler.java | 6 +-\n .../tst/org/spearce/jgit/lib/PackIndexTest.java | 4 +-\n .../tst/org/spearce/jgit/lib/PackWriterTest.java | 14 +-\n .../tst/org/spearce/jgit/lib/T0004_PackReader.java | 4 +-\n .../jgit/errors/CorruptObjectException.java | 12 +\n .../src/org/spearce/jgit/lib/ByteArrayWindow.java | 31 ++\n .../src/org/spearce/jgit/lib/ByteBufferWindow.java | 17 +\n .../src/org/spearce/jgit/lib/ByteWindow.java | 20 ++-\n .../src/org/spearce/jgit/lib/Constants.java | 2 +-\n .../spearce/jgit/lib/DeltaPackedObjectLoader.java | 3 +-\n .../src/org/spearce/jgit/lib/MutableObjectId.java | 9 +\n .../src/org/spearce/jgit/lib/ObjectLoader.java | 38 ---\n .../src/org/spearce/jgit/lib/PackFile.java | 49 +---\n .../src/org/spearce/jgit/lib/PackIndex.java | 48 ++--\n .../src/org/spearce/jgit/lib/PackIndexV1.java | 20 +-\n .../src/org/spearce/jgit/lib/PackIndexV2.java | 27 +-\n .../src/org/spearce/jgit/lib/PackWriter.java | 63 +++--\n .../src/org/spearce/jgit/lib/Repository.java | 29 +--\n .../org/spearce/jgit/lib/UnpackedObjectCache.java | 21 +-\n .../org/spearce/jgit/lib/UnpackedObjectLoader.java | 12 +-\n .../spearce/jgit/lib/WholePackedObjectLoader.java | 3 +-\n .../src/org/spearce/jgit/lib/WindowCache.java | 323 ++++++++++++--------\n .../src/org/spearce/jgit/lib/WindowCursor.java | 16 +\n .../src/org/spearce/jgit/lib/WindowedFile.java | 61 +++--\n .../src/org/spearce/jgit/revwalk/ObjectWalk.java | 51 ++--\n .../src/org/spearce/jgit/revwalk/RevWalk.java | 8 +-\n .../spearce/jgit/transport/PackedObjectInfo.java | 2 +-\n .../src/org/spearce/jgit/transport/UploadPack.java | 1 +\n .../jgit/transport/WalkFetchConnection.java | 48 ++-\n .../jgit/treewalk/AbstractTreeIterator.java | 48 +++\n .../spearce/jgit/treewalk/CanonicalTreeParser.java | 85 +++++-\n .../src/org/spearce/jgit/treewalk/TreeWalk.java | 88 +++++-\n .../spearce/jgit/util/CountingOutputStream.java | 5 +-\n 33 files changed, 752 insertions(+), 416 deletions(-)\n"},{"id":"98661","messageId":"1230171079-17156-2-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-1-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 01/23] Improve hit performance on the UnpackedObjectCache","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:10:57Z","receivedAt":"2008-12-25T02:10:57Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"If the JVM cleared one of our SoftReferences we \"leaked\" the space in\nthe cache that the entry occupied. Over time this meant we lost room\nin the cache and didn't have a way to recover that when we replaced\nthe evicted entry.\n\nThe hash function was also too complex for the hit ratio we were\ngetting. The old function on one of my linux-2.6 clones was giving\nus <7% hit ratio; this new function is a little simpler to compute\nand is getting ~11%. Increasing the size of the hash table helps\nmatters considerably.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../org/spearce/jgit/lib/UnpackedObjectCache.java | 21 +++++++++----------\n 1 files changed, 10 insertions(+), 11 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectCache.java b/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectCache.java\nindex ee6a680..677b3a7 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectCache.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectCache.java\n@@ -40,17 +40,14 @@\n import java.lang.ref.SoftReference;\n \n class UnpackedObjectCache {\n-\tprivate static final int CACHE_SZ = 256;\n+\tprivate static final int CACHE_SZ = 1024;\n \n \tprivate static final int MB = 1024 * 1024;\n \n \tprivate static final SoftReference DEAD;\n \n-\tprivate static int hash(final WindowedFile pack, final long position) {\n-\t\tint h = pack.hash + (int) position;\n-\t\th += h >>> 16;\n-\t\th += h >>> 8;\n-\t\treturn h & (CACHE_SZ - 1);\n+\tprivate static int hash(final long position) {\n+\t\treturn (((int) position) << 22) >>> 22;\n \t}\n \n \tprivate static int maxByteCount;\n@@ -80,7 +77,7 @@ static synchronized void reconfigure(final int dbLimit) {\n \t}\n \n \tstatic synchronized Entry get(final WindowedFile pack, final long position) {\n-\t\tfinal Slot e = cache[hash(pack, position)];\n+\t\tfinal Slot e = cache[hash(position)];\n \t\tif (e.provider == pack && e.position == position) {\n \t\t\tfinal Entry buf = e.data.get();\n \t\t\tif (buf != null) {\n@@ -96,7 +93,7 @@ static synchronized void store(final WindowedFile pack,\n \t\tif (data.length > maxByteCount)\n \t\t\treturn; // Too large to cache.\n \n-\t\tfinal Slot e = cache[hash(pack, position)];\n+\t\tfinal Slot e = cache[hash(position)];\n \t\tclearEntry(e);\n \n \t\topenByteCount += data.length;\n@@ -104,6 +101,7 @@ static synchronized void store(final WindowedFile pack,\n \n \t\te.provider = pack;\n \t\te.position = position;\n+\t\te.sz = data.length;\n \t\te.data = new SoftReference(new Entry(data, objectType));\n \t\tmoveToHead(e);\n \t}\n@@ -155,11 +153,10 @@ private static void unlink(final Slot e) {\n \t}\n \n \tprivate static void clearEntry(final Slot e) {\n-\t\tfinal Entry old = e.data.get();\n-\t\tif (old != null)\n-\t\t\topenByteCount -= old.data.length;\n+\t\topenByteCount -= e.sz;\n \t\te.provider = null;\n \t\te.data = DEAD;\n+\t\te.sz = 0;\n \t}\n \n \tprivate UnpackedObjectCache() {\n@@ -186,6 +183,8 @@ Entry(final byte[] aData, final int aType) {\n \n \t\tlong position;\n \n+\t\tint sz;\n+\n \t\tSoftReference data = DEAD;\n \t}\n }\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98656","messageId":"1230171079-17156-3-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-2-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 02/23] Add MutableObjectId.clear() to set the id to zeroId","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:10:58Z","receivedAt":"2008-12-25T02:10:58Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"This makes it easier to set any MutableObjectId to the same value\nas the zeroId. Its logical to ask for a \".clear()\" invocation when\nyou are writing application code, and its more efficient for the\nJIT if we do 5 zero writes then to perform a copy from the zeroId\nsingleton.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../src/org/spearce/jgit/lib/MutableObjectId.java | 9 +++++++++\n 1 files changed, 9 insertions(+), 0 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/MutableObjectId.java b/org.spearce.jgit/src/org/spearce/jgit/lib/MutableObjectId.java\nindex 5b16345..fadebab 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/MutableObjectId.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/MutableObjectId.java\n@@ -66,6 +66,15 @@ MutableObjectId(MutableObjectId src) {\n \t\tthis.w5 = src.w5;\n \t}\n \n+\t/** Make this id match {@link ObjectId#zeroId()}. */\n+\tpublic void clear() {\n+\t\tw1 = 0;\n+\t\tw2 = 0;\n+\t\tw3 = 0;\n+\t\tw4 = 0;\n+\t\tw5 = 0;\n+\t}\n+\n \t/**\n \t * Convert an ObjectId from raw binary representation.\n \t * \n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98662","messageId":"1230171079-17156-4-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-3-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 03/23] Allow TreeWalk callers to pass a MutableObjectId to get the current id","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:10:59Z","receivedAt":"2008-12-25T02:10:59Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"This avoids a memory allocation associated with getting the entry\nobject for each name.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../src/org/spearce/jgit/treewalk/TreeWalk.java | 28 +++++++++++++++++++-\n 1 files changed, 27 insertions(+), 1 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\nindex 26544b5..38a726b 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\n@@ -46,6 +46,7 @@\n import org.spearce.jgit.errors.StopWalkException;\n import org.spearce.jgit.lib.Constants;\n import org.spearce.jgit.lib.FileMode;\n+import org.spearce.jgit.lib.MutableObjectId;\n import org.spearce.jgit.lib.ObjectId;\n import org.spearce.jgit.lib.Repository;\n import org.spearce.jgit.revwalk.RevTree;\n@@ -513,7 +514,8 @@ public FileMode getFileMode(final int nth) {\n \t *

\n \t * Using this method to compare ObjectId values between trees of this walker\n \t * is very inefficient. Applications should try to use\n-\t * {@link #idEqual(int, int)} whenever possible.\n+\t * {@link #idEqual(int, int)} or {@link #getObjectId(MutableObjectId, int)}\n+\t * whenever possible.\n \t *

\n \t * Every tree supplies an object id, even if the tree does not contain the\n \t * current entry. In the latter case {@link ObjectId#zeroId()} is returned.\n@@ -521,6 +523,7 @@ public FileMode getFileMode(final int nth) {\n \t * @param nth\n \t * tree to obtain the object identifier from.\n \t * @return object identifier for the current tree entry.\n+\t * @see #getObjectId(MutableObjectId, int)\n \t * @see #idEqual(int, int)\n \t */\n \tpublic ObjectId getObjectId(final int nth) {\n@@ -530,6 +533,29 @@ public ObjectId getObjectId(final int nth) {\n \t}\n \n \t/**\n+\t * Obtain the ObjectId for the current entry.\n+\t *

\n+\t * Every tree supplies an object id, even if the tree does not contain the\n+\t * current entry. In the latter case {@link ObjectId#zeroId()} is supplied.\n+\t *

\n+\t * Applications should try to use {@link #idEqual(int, int)} when possible\n+\t * as it avoids conversion overheads.\n+\t * \n+\t * @param out\n+\t * buffer to copy the object id into.\n+\t * @param nth\n+\t * tree to obtain the object identifier from.\n+\t * @see #idEqual(int, int)\n+\t */\n+\tpublic void getObjectId(final MutableObjectId out, final int nth) {\n+\t\tfinal AbstractTreeIterator t = trees[nth];\n+\t\tif (t.matches == currentHead)\n+\t\t\tout.fromRaw(t.idBuffer(), t.idOffset());\n+\t\telse\n+\t\t\tout.clear();\n+\t}\n+\n+\t/**\n \t * Compare two tree's current ObjectId values for equality.\n \t * \n \t * @param nthA\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98655","messageId":"1230171079-17156-5-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-4-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 04/23] Switch ObjectWalk to use the new MutableObjectId form in TreeWalk","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:00Z","receivedAt":"2008-12-25T02:11:00Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"RevWalk already has an idBuffer field available, which is used by\nthe commit and tree parsers to hold an id they need to probe for\nin the hash table. We should be using that buffer during tree\nentry iteration as it avoids object allocation.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../src/org/spearce/jgit/revwalk/ObjectWalk.java | 20 ++++++++++++--------\n 1 files changed, 12 insertions(+), 8 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\nindex 69a20aa..454cb4a 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\n@@ -251,7 +251,8 @@ public RevObject nextObject() throws MissingObjectException,\n \n \t\t\tswitch (sType) {\n \t\t\tcase Constants.OBJ_BLOB: {\n-\t\t\t\tfinal RevObject o = lookupAny(treeWalk.getObjectId(0), sType);\n+\t\t\t\ttreeWalk.getObjectId(idBuffer, 0);\n+\t\t\t\tfinal RevObject o = lookupAny(idBuffer, sType);\n \t\t\t\tif ((o.flags & SEEN) != 0)\n \t\t\t\t\tcontinue;\n \t\t\t\to.flags |= SEEN;\n@@ -262,7 +263,8 @@ public RevObject nextObject() throws MissingObjectException,\n \t\t\t\treturn o;\n \t\t\t}\n \t\t\tcase Constants.OBJ_TREE: {\n-\t\t\t\tfinal RevObject o = lookupAny(treeWalk.getObjectId(0), sType);\n+\t\t\t\ttreeWalk.getObjectId(idBuffer, 0);\n+\t\t\t\tfinal RevObject o = lookupAny(idBuffer, sType);\n \t\t\t\tif ((o.flags & SEEN) != 0)\n \t\t\t\t\tcontinue;\n \t\t\t\to.flags |= SEEN;\n@@ -276,8 +278,9 @@ public RevObject nextObject() throws MissingObjectException,\n \t\t\tdefault:\n \t\t\t\tif (FileMode.GITLINK.equals(mode))\n \t\t\t\t\tcontinue;\n+\t\t\t\ttreeWalk.getObjectId(idBuffer, 0);\n \t\t\t\tthrow new CorruptObjectException(\"Invalid mode \" + mode\n-\t\t\t\t\t\t+ \" for \" + treeWalk.getObjectId(0).name() + \" \"\n+\t\t\t\t\t\t+ \" for \" + idBuffer.name() + \" \"\n \t\t\t\t\t\t+ treeWalk.getPathString() + \" in \" + currentTree + \".\");\n \t\t\t}\n \t\t}\n@@ -390,13 +393,13 @@ private void markTreeUninteresting(final RevTree tree)\n \n \t\t\tswitch (sType) {\n \t\t\tcase Constants.OBJ_BLOB: {\n-\t\t\t\tfinal ObjectId sid = treeWalk.getObjectId(0);\n-\t\t\t\tlookupAny(sid, sType).flags |= UNINTERESTING;\n+\t\t\t\ttreeWalk.getObjectId(idBuffer, 0);\n+\t\t\t\tlookupAny(idBuffer, sType).flags |= UNINTERESTING;\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tcase Constants.OBJ_TREE: {\n-\t\t\t\tfinal ObjectId sid = treeWalk.getObjectId(0);\n-\t\t\t\tfinal RevObject subtree = lookupAny(sid, sType);\n+\t\t\t\ttreeWalk.getObjectId(idBuffer, 0);\n+\t\t\t\tfinal RevObject subtree = lookupAny(idBuffer, sType);\n \t\t\t\tif ((subtree.flags & UNINTERESTING) == 0) {\n \t\t\t\t\tsubtree.flags |= UNINTERESTING;\n \t\t\t\t\ttreeWalk.enterSubtree();\n@@ -406,8 +409,9 @@ private void markTreeUninteresting(final RevTree tree)\n \t\t\tdefault:\n \t\t\t\tif (FileMode.GITLINK.equals(mode))\n \t\t\t\t\tcontinue;\n+\t\t\t\ttreeWalk.getObjectId(idBuffer, 0);\n \t\t\t\tthrow new CorruptObjectException(\"Invalid mode \" + mode\n-\t\t\t\t\t\t+ \" for \" + treeWalk.getObjectId(0).name() + \" \"\n+\t\t\t\t\t\t+ \" for \" + idBuffer.name() + \" \"\n \t\t\t\t\t\t+ treeWalk.getPathString() + \" in \" + tree + \".\");\n \t\t\t}\n \t\t}\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98665","messageId":"1230171079-17156-6-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-5-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 05/23] Change walker based fetch to use TreeWalk's MutableObjectId accessor","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:01Z","receivedAt":"2008-12-25T02:11:01Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Fetch time is usually dominated by network traffic, but while marking\nobjects reachable locally we can still benefit from the reduction in\nobject allocations this variant of getObjectId offers.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../jgit/transport/WalkFetchConnection.java | 29 +++++++++++--------\n 1 files changed, 17 insertions(+), 12 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java b/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java\nindex 91c5ea8..6300f10 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java\n@@ -59,6 +59,7 @@\n import org.spearce.jgit.lib.AnyObjectId;\n import org.spearce.jgit.lib.Constants;\n import org.spearce.jgit.lib.FileMode;\n+import org.spearce.jgit.lib.MutableObjectId;\n import org.spearce.jgit.lib.ObjectChecker;\n import org.spearce.jgit.lib.ObjectId;\n import org.spearce.jgit.lib.PackIndex;\n@@ -152,6 +153,8 @@\n \t */\n \tprivate final Set packsConsidered;\n \n+\tprivate final MutableObjectId idBuffer = new MutableObjectId();\n+\n \t/**\n \t * Errors received while trying to obtain an object.\n \t *

\n@@ -300,16 +303,17 @@ private void processTree(final RevObject obj) throws TransportException {\n \n \t\t\t\tswitch (sType) {\n \t\t\t\tcase Constants.OBJ_BLOB:\n-\t\t\t\tcase Constants.OBJ_TREE: {\n-\t\t\t\t\tfinal ObjectId sId = treeWalk.getObjectId(0);\n-\t\t\t\t\tneeds(revWalk.lookupAny(sId, sType));\n+\t\t\t\tcase Constants.OBJ_TREE:\n+\t\t\t\t\ttreeWalk.getObjectId(idBuffer, 0);\n+\t\t\t\t\tneeds(revWalk.lookupAny(idBuffer, sType));\n \t\t\t\t\tcontinue;\n-\t\t\t\t}\n+\n \t\t\t\tdefault:\n \t\t\t\t\tif (FileMode.GITLINK.equals(mode))\n \t\t\t\t\t\tcontinue;\n+\t\t\t\t\ttreeWalk.getObjectId(idBuffer, 0);\n \t\t\t\t\tthrow new CorruptObjectException(\"Invalid mode \" + mode\n-\t\t\t\t\t\t\t+ \" for \" + treeWalk.getObjectId(0).name() + \" \"\n+\t\t\t\t\t\t\t+ \" for \" + idBuffer.name() + \" \"\n \t\t\t\t\t\t\t+ treeWalk.getPathString() + \" in \"\n \t\t\t\t\t\t\t+ obj.getId().name() + \".\");\n \t\t\t\t}\n@@ -722,14 +726,14 @@ private void markTreeComplete(final RevTree tree) throws IOException {\n \t\t\tfinal int sType = mode.getObjectType();\n \n \t\t\tswitch (sType) {\n-\t\t\tcase Constants.OBJ_BLOB: {\n-\t\t\t\tfinal ObjectId sid = treeWalk.getObjectId(0);\n-\t\t\t\trevWalk.lookupAny(sid, sType).add(COMPLETE);\n+\t\t\tcase Constants.OBJ_BLOB:\n+\t\t\t\ttreeWalk.getObjectId(idBuffer, 0);\n+\t\t\t\trevWalk.lookupAny(idBuffer, sType).add(COMPLETE);\n \t\t\t\tcontinue;\n-\t\t\t}\n+\n \t\t\tcase Constants.OBJ_TREE: {\n-\t\t\t\tfinal ObjectId sid = treeWalk.getObjectId(0);\n-\t\t\t\tfinal RevObject o = revWalk.lookupAny(sid, sType);\n+\t\t\t\ttreeWalk.getObjectId(idBuffer, 0);\n+\t\t\t\tfinal RevObject o = revWalk.lookupAny(idBuffer, sType);\n \t\t\t\tif (!o.has(COMPLETE)) {\n \t\t\t\t\to.add(COMPLETE);\n \t\t\t\t\ttreeWalk.enterSubtree();\n@@ -739,8 +743,9 @@ private void markTreeComplete(final RevTree tree) throws IOException {\n \t\t\tdefault:\n \t\t\t\tif (FileMode.GITLINK.equals(mode))\n \t\t\t\t\tcontinue;\n+\t\t\t\ttreeWalk.getObjectId(idBuffer, 0);\n \t\t\t\tthrow new CorruptObjectException(\"Invalid mode \" + mode\n-\t\t\t\t\t\t+ \" for \" + treeWalk.getObjectId(0).name() + \" \"\n+\t\t\t\t\t\t+ \" for \" + idBuffer.name() + \" \"\n \t\t\t\t\t\t+ treeWalk.getPathString() + \" in \" + tree.name() + \".\");\n \t\t\t}\n \t\t}\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98658","messageId":"1230171079-17156-7-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-6-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 06/23] Reduce garbage allocation when using TreeWalk","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:02Z","receivedAt":"2008-12-25T02:11:02Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"We now support more efficiently resetting a TreeWalk when the\nwalker is using a single tree traversal from the repository.\nThis is very common during an ObjectWalk for a PackWriter, so\noptimizing the code path is worth while. By using a special\nform of reset we can avoid unnecessary temporary arrays and\nalso skip some loop conditional instructions.\n\nWhen diving into a subtree iterator (which is also quite a\ncommon operation in ObjectWalk) we want to reuse an idBuffer\nand a WindowCursor as much as possible, ensuring that these\naren't created temporarily on the stack. This should help\nto reduce the stress on the Inflater cache by allowing it\nto reuse the same Inflater on each tree construction. We\nalso can avoid creating a temporary ObjectId by filling out\nthe mutable idBuffer during the repository lookup.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../jgit/pgm/opt/AbstractTreeIteratorHandler.java | 6 ++-\n .../src/org/spearce/jgit/revwalk/ObjectWalk.java | 5 +-\n .../jgit/transport/WalkFetchConnection.java | 4 +-\n .../jgit/treewalk/AbstractTreeIterator.java | 28 ++++++++++\n .../spearce/jgit/treewalk/CanonicalTreeParser.java | 46 ++++++++++++----\n .../src/org/spearce/jgit/treewalk/TreeWalk.java | 58 ++++++++++++++++++--\n 6 files changed, 124 insertions(+), 23 deletions(-)\n\ndiff --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\nindex 9432d5f..12d4191 100644\n--- a/org.spearce.jgit.pgm/src/org/spearce/jgit/pgm/opt/AbstractTreeIteratorHandler.java\n+++ b/org.spearce.jgit.pgm/src/org/spearce/jgit/pgm/opt/AbstractTreeIteratorHandler.java\n@@ -51,6 +51,7 @@\n import org.spearce.jgit.errors.IncorrectObjectTypeException;\n import org.spearce.jgit.errors.MissingObjectException;\n import org.spearce.jgit.lib.ObjectId;\n+import org.spearce.jgit.lib.WindowCursor;\n import org.spearce.jgit.treewalk.AbstractTreeIterator;\n import org.spearce.jgit.treewalk.CanonicalTreeParser;\n import org.spearce.jgit.treewalk.FileTreeIterator;\n@@ -110,8 +111,9 @@ public int parseArguments(final Parameters params) throws CmdLineException {\n \t\t\tthrow new CmdLineException(name + \" is not a tree\");\n \n \t\tfinal CanonicalTreeParser p = new CanonicalTreeParser();\n+\t\tfinal WindowCursor curs = new WindowCursor();\n \t\ttry {\n-\t\t\tp.reset(clp.getRepository(), clp.getRevWalk().parseTree(id));\n+\t\t\tp.reset(clp.getRepository(), clp.getRevWalk().parseTree(id), curs);\n \t\t} catch (MissingObjectException e) {\n \t\t\tthrow new CmdLineException(name + \" is not a tree\");\n \t\t} catch (IncorrectObjectTypeException e) {\n@@ -119,6 +121,8 @@ public int parseArguments(final Parameters params) throws CmdLineException {\n \t\t} catch (IOException e) {\n \t\t\tthrow new CmdLineException(\"cannot read \" + name + \": \"\n \t\t\t\t\t+ e.getMessage());\n+\t\t} finally {\n+\t\t\tcurs.release();\n \t\t}\n \n \t\tsetter.addValue(p);\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\nindex 454cb4a..cfdbe18 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\n@@ -45,7 +45,6 @@\n import org.spearce.jgit.lib.AnyObjectId;\n import org.spearce.jgit.lib.Constants;\n import org.spearce.jgit.lib.FileMode;\n-import org.spearce.jgit.lib.ObjectId;\n import org.spearce.jgit.lib.Repository;\n import org.spearce.jgit.treewalk.TreeWalk;\n \n@@ -296,7 +295,7 @@ public RevObject nextObject() throws MissingObjectException,\n \t\t\t\tcontinue;\n \t\t\tif (o instanceof RevTree) {\n \t\t\t\tcurrentTree = (RevTree) o;\n-\t\t\t\ttreeWalk.reset(new ObjectId[] { currentTree });\n+\t\t\t\ttreeWalk.reset(currentTree);\n \t\t\t}\n \t\t\treturn o;\n \t\t}\n@@ -386,7 +385,7 @@ private void markTreeUninteresting(final RevTree tree)\n \t\t\treturn;\n \t\ttree.flags |= UNINTERESTING;\n \n-\t\ttreeWalk.reset(new ObjectId[] { tree });\n+\t\ttreeWalk.reset(tree);\n \t\twhile (treeWalk.next()) {\n \t\t\tfinal FileMode mode = treeWalk.getFileMode(0);\n \t\t\tfinal int sType = mode.getObjectType();\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java b/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java\nindex 6300f10..5d0c6bc 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java\n@@ -296,7 +296,7 @@ private void processBlob(final RevObject obj) throws TransportException {\n \n \tprivate void processTree(final RevObject obj) throws TransportException {\n \t\ttry {\n-\t\t\ttreeWalk.reset(new ObjectId[] { obj });\n+\t\t\ttreeWalk.reset(obj);\n \t\t\twhile (treeWalk.next()) {\n \t\t\t\tfinal FileMode mode = treeWalk.getFileMode(0);\n \t\t\t\tfinal int sType = mode.getObjectType();\n@@ -720,7 +720,7 @@ private void markTreeComplete(final RevTree tree) throws IOException {\n \t\tif (tree.has(COMPLETE))\n \t\t\treturn;\n \t\ttree.add(COMPLETE);\n-\t\ttreeWalk.reset(new ObjectId[] { tree });\n+\t\ttreeWalk.reset(tree);\n \t\twhile (treeWalk.next()) {\n \t\t\tfinal FileMode mode = treeWalk.getFileMode(0);\n \t\t\tfinal int sType = mode.getObjectType();\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\nindex 5226ab6..c404cdc 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n@@ -46,8 +46,10 @@\n import org.spearce.jgit.errors.IncorrectObjectTypeException;\n import org.spearce.jgit.lib.Constants;\n import org.spearce.jgit.lib.FileMode;\n+import org.spearce.jgit.lib.MutableObjectId;\n import org.spearce.jgit.lib.ObjectId;\n import org.spearce.jgit.lib.Repository;\n+import org.spearce.jgit.lib.WindowCursor;\n import org.spearce.jgit.treewalk.filter.TreeFilter;\n \n /**\n@@ -347,6 +349,32 @@ public abstract AbstractTreeIterator createSubtreeIterator(Repository repo)\n \t\t\tthrows IncorrectObjectTypeException, IOException;\n \n \t/**\n+\t * Create a new iterator for the current entry's subtree.\n+\t *

\n+\t * The parent reference of the iterator must be this, otherwise\n+\t * the caller would not be able to exit out of the subtree iterator\n+\t * correctly and return to continue walking this.\n+\t * \n+\t * @param repo\n+\t * repository to load the tree data from.\n+\t * @param idBuffer\n+\t * temporary ObjectId buffer for use by this method.\n+\t * @param curs\n+\t * window cursor to use during repository access.\n+\t * @return a new parser that walks over the current subtree.\n+\t * @throws IncorrectObjectTypeException\n+\t * the current entry is not actually a tree and cannot be parsed\n+\t * as though it were a tree.\n+\t * @throws IOException\n+\t * a loose object or pack file could not be read.\n+\t */\n+\tpublic AbstractTreeIterator createSubtreeIterator(final Repository repo,\n+\t\t\tfinal MutableObjectId idBuffer, final WindowCursor curs)\n+\t\t\tthrows IncorrectObjectTypeException, IOException {\n+\t\treturn createSubtreeIterator(repo);\n+\t}\n+\n+\t/**\n \t * Is this tree iterator positioned on its first entry?\n \t *

\n \t * An iterator is positioned on the first entry if back(1)\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java\nindex dcc53cd..df3384d 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java\n@@ -41,11 +41,14 @@\n \n import org.spearce.jgit.errors.IncorrectObjectTypeException;\n import org.spearce.jgit.errors.MissingObjectException;\n+import org.spearce.jgit.lib.AnyObjectId;\n import org.spearce.jgit.lib.Constants;\n import org.spearce.jgit.lib.FileMode;\n+import org.spearce.jgit.lib.MutableObjectId;\n import org.spearce.jgit.lib.ObjectId;\n import org.spearce.jgit.lib.ObjectLoader;\n import org.spearce.jgit.lib.Repository;\n+import org.spearce.jgit.lib.WindowCursor;\n \n /** Parses raw Git trees from the canonical semi-text/semi-binary format. */\n public class CanonicalTreeParser extends AbstractTreeIterator {\n@@ -87,6 +90,8 @@ public void reset(final byte[] treeData) {\n \t * @param id\n \t * identity of the tree being parsed; used only in exception\n \t * messages if data corruption is found.\n+\t * @param curs\n+\t * window cursor to use during repository access.\n \t * @throws MissingObjectException\n \t * the object supplied is not available from the repository.\n \t * @throws IncorrectObjectTypeException\n@@ -95,27 +100,46 @@ public void reset(final byte[] treeData) {\n \t * @throws IOException\n \t * a loose object or pack file could not be read.\n \t */\n-\tpublic void reset(final Repository repo, final ObjectId id)\n+\tpublic void reset(final Repository repo, final AnyObjectId id,\n+\t\t\tfinal WindowCursor curs)\n \t\t\tthrows IncorrectObjectTypeException, IOException {\n-\t\tfinal ObjectLoader ldr = repo.openObject(id);\n-\t\tif (ldr == null)\n-\t\t\tthrow new MissingObjectException(id, Constants.TYPE_TREE);\n+\t\tfinal ObjectLoader ldr = repo.openObject(curs, id);\n+\t\tif (ldr == null) {\n+\t\t\tfinal ObjectId me = id.toObjectId();\n+\t\t\tthrow new MissingObjectException(me, Constants.TYPE_TREE);\n+\t\t}\n \t\tfinal byte[] subtreeData = ldr.getCachedBytes();\n-\t\tif (ldr.getType() != Constants.OBJ_TREE)\n-\t\t\tthrow new IncorrectObjectTypeException(id, Constants.TYPE_TREE);\n+\t\tif (ldr.getType() != Constants.OBJ_TREE) {\n+\t\t\tfinal ObjectId me = id.toObjectId();\n+\t\t\tthrow new IncorrectObjectTypeException(me, Constants.TYPE_TREE);\n+\t\t}\n \t\treset(subtreeData);\n \t}\n \n-\tpublic CanonicalTreeParser createSubtreeIterator(final Repository repo)\n+\t@Override\n+\tpublic CanonicalTreeParser createSubtreeIterator(final Repository repo,\n+\t\t\tfinal MutableObjectId idBuffer, final WindowCursor curs)\n \t\t\tthrows IncorrectObjectTypeException, IOException {\n-\t\tfinal ObjectId id = getEntryObjectId();\n-\t\tif (!FileMode.TREE.equals(mode))\n-\t\t\tthrow new IncorrectObjectTypeException(id, Constants.TYPE_TREE);\n+\t\tidBuffer.fromRaw(idBuffer(), idOffset());\n+\t\tif (!FileMode.TREE.equals(mode)) {\n+\t\t\tfinal ObjectId me = idBuffer.toObjectId();\n+\t\t\tthrow new IncorrectObjectTypeException(me, Constants.TYPE_TREE);\n+\t\t}\n \t\tfinal CanonicalTreeParser p = new CanonicalTreeParser(this);\n-\t\tp.reset(repo, id);\n+\t\tp.reset(repo, idBuffer, curs);\n \t\treturn p;\n \t}\n \n+\tpublic CanonicalTreeParser createSubtreeIterator(final Repository repo)\n+\t\t\tthrows IncorrectObjectTypeException, IOException {\n+\t\tfinal WindowCursor curs = new WindowCursor();\n+\t\ttry {\n+\t\t\treturn createSubtreeIterator(repo, new MutableObjectId(), curs);\n+\t\t} finally {\n+\t\t\tcurs.release();\n+\t\t}\n+\t}\n+\n \t@Override\n \tpublic byte[] idBuffer() {\n \t\treturn raw;\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\nindex 38a726b..cf66bf4 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\n@@ -44,11 +44,13 @@\n import org.spearce.jgit.errors.IncorrectObjectTypeException;\n import org.spearce.jgit.errors.MissingObjectException;\n import org.spearce.jgit.errors.StopWalkException;\n+import org.spearce.jgit.lib.AnyObjectId;\n import org.spearce.jgit.lib.Constants;\n import org.spearce.jgit.lib.FileMode;\n import org.spearce.jgit.lib.MutableObjectId;\n import org.spearce.jgit.lib.ObjectId;\n import org.spearce.jgit.lib.Repository;\n+import org.spearce.jgit.lib.WindowCursor;\n import org.spearce.jgit.revwalk.RevTree;\n import org.spearce.jgit.treewalk.filter.PathFilterGroup;\n import org.spearce.jgit.treewalk.filter.TreeFilter;\n@@ -99,7 +101,7 @@\n \t * a tree object was not found.\n \t */\n \tpublic static TreeWalk forPath(final Repository db, final String path,\n-\t\t\tfinal ObjectId[] trees) throws MissingObjectException,\n+\t\t\tfinal AnyObjectId[] trees) throws MissingObjectException,\n \t\t\tIncorrectObjectTypeException, CorruptObjectException, IOException {\n \t\tfinal TreeWalk r = new TreeWalk(db);\n \t\tr.setFilter(PathFilterGroup.createFromStrings(Collections\n@@ -142,6 +144,10 @@ public static TreeWalk forPath(final Repository db, final String path,\n \n \tprivate final Repository db;\n \n+\tprivate final MutableObjectId idBuffer = new MutableObjectId();\n+\n+\tprivate final WindowCursor curs = new WindowCursor();\n+\n \tprivate TreeFilter filter;\n \n \tAbstractTreeIterator[] trees;\n@@ -278,6 +284,46 @@ public void reset() {\n \t}\n \n \t/**\n+\t * Reset this walker to run over a single existing tree.\n+\t * \n+\t * @param id\n+\t * the tree we need to parse. The walker will execute over this\n+\t * single tree if the reset is successful.\n+\t * @throws MissingObjectException\n+\t * the given tree object does not exist in this repository.\n+\t * @throws IncorrectObjectTypeException\n+\t * the given object id does not denote a tree, but instead names\n+\t * some other non-tree type of object. Note that commits are not\n+\t * trees, even if they are sometimes called a \"tree-ish\".\n+\t * @throws CorruptObjectException\n+\t * the object claimed to be a tree, but its contents did not\n+\t * appear to be a tree. The repository may have data corruption.\n+\t * @throws IOException\n+\t * a loose object or pack file could not be read.\n+\t */\n+\tpublic void reset(final AnyObjectId id) throws MissingObjectException,\n+\t\t\tIncorrectObjectTypeException, CorruptObjectException, IOException {\n+\t\tif (trees.length == 1) {\n+\t\t\tAbstractTreeIterator o = trees[0];\n+\t\t\twhile (o.parent != null)\n+\t\t\t\to = o.parent;\n+\t\t\tif (o instanceof CanonicalTreeParser) {\n+\t\t\t\to.matches = null;\n+\t\t\t\to.matchShift = 0;\n+\t\t\t\t((CanonicalTreeParser) o).reset(db, id, curs);\n+\t\t\t\ttrees[0] = o;\n+\t\t\t} else {\n+\t\t\t\ttrees[0] = parserFor(id);\n+\t\t\t}\n+\t\t} else {\n+\t\t\ttrees = new AbstractTreeIterator[] { parserFor(id) };\n+\t\t}\n+\n+\t\tadvance = false;\n+\t\tdepth = 0;\n+\t}\n+\n+\t/**\n \t * Reset this walker to run over a set of existing trees.\n \t * \n \t * @param ids\n@@ -295,7 +341,7 @@ public void reset() {\n \t * @throws IOException\n \t * a loose object or pack file could not be read.\n \t */\n-\tpublic void reset(final ObjectId[] ids) throws MissingObjectException,\n+\tpublic void reset(final AnyObjectId[] ids) throws MissingObjectException,\n \t\t\tIncorrectObjectTypeException, CorruptObjectException, IOException {\n \t\tfinal int oldLen = trees.length;\n \t\tfinal int newLen = ids.length;\n@@ -311,7 +357,7 @@ public void reset(final ObjectId[] ids) throws MissingObjectException,\n \t\t\t\tif (o instanceof CanonicalTreeParser) {\n \t\t\t\t\to.matches = null;\n \t\t\t\t\to.matchShift = 0;\n-\t\t\t\t\t((CanonicalTreeParser) o).reset(db, ids[i]);\n+\t\t\t\t\t((CanonicalTreeParser) o).reset(db, ids[i], curs);\n \t\t\t\t\tr[i] = o;\n \t\t\t\t\tcontinue;\n \t\t\t\t}\n@@ -709,7 +755,7 @@ public void enterSubtree() throws MissingObjectException,\n \t\t\tfinal AbstractTreeIterator t = trees[i];\n \t\t\tfinal AbstractTreeIterator n;\n \t\t\tif (t.matches == ch && !t.eof() && FileMode.TREE.equals(t.mode))\n-\t\t\t\tn = t.createSubtreeIterator(db);\n+\t\t\t\tn = t.createSubtreeIterator(db, idBuffer, curs);\n \t\t\telse\n \t\t\t\tn = new EmptyTreeIterator(t);\n \t\t\ttmp[i] = n;\n@@ -781,10 +827,10 @@ private void exitSubtree() {\n \t\tcurrentHead = minRef;\n \t}\n \n-\tprivate CanonicalTreeParser parserFor(final ObjectId id)\n+\tprivate CanonicalTreeParser parserFor(final AnyObjectId id)\n \t\t\tthrows IncorrectObjectTypeException, IOException {\n \t\tfinal CanonicalTreeParser p = new CanonicalTreeParser();\n-\t\tp.reset(db, id);\n+\t\tp.reset(db, id, curs);\n \t\treturn p;\n \t}\n \n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98659","messageId":"1230171079-17156-8-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-7-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 07/23] Switch ObjectWalk to use a naked CanonicalTreeParser because its faster","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:03Z","receivedAt":"2008-12-25T02:11:03Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Removing the indirection of the TreeWalk during an ObjectWalk's loop\nover the trees saves us 20 seconds on one of my linux-2.6 clones. On\naverage we went from 1m37s for \"jgit rev-list --objects\" down to 1m17s.\n\nC git still does the same operation in 0m20s, so we're a long way from\nmatching C git's performance, but this is a worthwhile improvement, even\nthough the code has become slightly more complex.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../src/org/spearce/jgit/revwalk/ObjectWalk.java | 42 ++++++++++---------\n .../jgit/treewalk/AbstractTreeIterator.java | 20 +++++++++\n .../spearce/jgit/treewalk/CanonicalTreeParser.java | 39 ++++++++++++++++++-\n .../src/org/spearce/jgit/treewalk/TreeWalk.java | 4 +-\n 4 files changed, 82 insertions(+), 23 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\nindex cfdbe18..0d67a38 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\n@@ -46,7 +46,7 @@\n import org.spearce.jgit.lib.Constants;\n import org.spearce.jgit.lib.FileMode;\n import org.spearce.jgit.lib.Repository;\n-import org.spearce.jgit.treewalk.TreeWalk;\n+import org.spearce.jgit.treewalk.CanonicalTreeParser;\n \n /**\n * Specialized subclass of RevWalk to include trees, blobs and tags.\n@@ -74,7 +74,7 @@\n \t */\n \tprivate static final int IN_PENDING = RevWalk.REWRITE;\n \n-\tprivate final TreeWalk treeWalk;\n+\tprivate CanonicalTreeParser treeWalk;\n \n \tprivate BlockObjQueue pendingObjects;\n \n@@ -92,8 +92,8 @@\n \t */\n \tpublic ObjectWalk(final Repository repo) {\n \t\tsuper(repo);\n-\t\ttreeWalk = new TreeWalk(repo);\n \t\tpendingObjects = new BlockObjQueue();\n+\t\ttreeWalk = new CanonicalTreeParser();\n \t}\n \n \t/**\n@@ -240,17 +240,17 @@ public RevObject nextObject() throws MissingObjectException,\n \t\tfromTreeWalk = false;\n \n \t\tif (enterSubtree) {\n-\t\t\ttreeWalk.enterSubtree();\n+\t\t\ttreeWalk = treeWalk.createSubtreeIterator(db, idBuffer, curs);\n \t\t\tenterSubtree = false;\n \t\t}\n \n-\t\twhile (treeWalk.next()) {\n-\t\t\tfinal FileMode mode = treeWalk.getFileMode(0);\n+\t\tfor (; !treeWalk.eof(); treeWalk = treeWalk.next()) {\n+\t\t\tfinal FileMode mode = treeWalk.getEntryFileMode();\n \t\t\tfinal int sType = mode.getObjectType();\n \n \t\t\tswitch (sType) {\n \t\t\tcase Constants.OBJ_BLOB: {\n-\t\t\t\ttreeWalk.getObjectId(idBuffer, 0);\n+\t\t\t\ttreeWalk.getEntryObjectId(idBuffer);\n \t\t\t\tfinal RevObject o = lookupAny(idBuffer, sType);\n \t\t\t\tif ((o.flags & SEEN) != 0)\n \t\t\t\t\tcontinue;\n@@ -262,7 +262,7 @@ public RevObject nextObject() throws MissingObjectException,\n \t\t\t\treturn o;\n \t\t\t}\n \t\t\tcase Constants.OBJ_TREE: {\n-\t\t\t\ttreeWalk.getObjectId(idBuffer, 0);\n+\t\t\t\ttreeWalk.getEntryObjectId(idBuffer);\n \t\t\t\tfinal RevObject o = lookupAny(idBuffer, sType);\n \t\t\t\tif ((o.flags & SEEN) != 0)\n \t\t\t\t\tcontinue;\n@@ -277,10 +277,11 @@ public RevObject nextObject() throws MissingObjectException,\n \t\t\tdefault:\n \t\t\t\tif (FileMode.GITLINK.equals(mode))\n \t\t\t\t\tcontinue;\n-\t\t\t\ttreeWalk.getObjectId(idBuffer, 0);\n+\t\t\t\ttreeWalk.getEntryObjectId(idBuffer);\n \t\t\t\tthrow new CorruptObjectException(\"Invalid mode \" + mode\n \t\t\t\t\t\t+ \" for \" + idBuffer.name() + \" \"\n-\t\t\t\t\t\t+ treeWalk.getPathString() + \" in \" + currentTree + \".\");\n+\t\t\t\t\t\t+ treeWalk.getEntryPathString() + \" in \" + currentTree\n+\t\t\t\t\t\t+ \".\");\n \t\t\t}\n \t\t}\n \n@@ -295,7 +296,7 @@ public RevObject nextObject() throws MissingObjectException,\n \t\t\t\tcontinue;\n \t\t\tif (o instanceof RevTree) {\n \t\t\t\tcurrentTree = (RevTree) o;\n-\t\t\t\ttreeWalk.reset(currentTree);\n+\t\t\t\ttreeWalk = treeWalk.resetRoot(db, currentTree, curs);\n \t\t\t}\n \t\t\treturn o;\n \t\t}\n@@ -353,7 +354,7 @@ public void checkConnectivity() throws MissingObjectException,\n \t * has no path, such as for annotated tags or root level trees.\n \t */\n \tpublic String getPathString() {\n-\t\treturn fromTreeWalk ? treeWalk.getPathString() : null;\n+\t\treturn fromTreeWalk ? treeWalk.getEntryPathString() : null;\n \t}\n \n \t@Override\n@@ -385,33 +386,34 @@ private void markTreeUninteresting(final RevTree tree)\n \t\t\treturn;\n \t\ttree.flags |= UNINTERESTING;\n \n-\t\ttreeWalk.reset(tree);\n-\t\twhile (treeWalk.next()) {\n-\t\t\tfinal FileMode mode = treeWalk.getFileMode(0);\n+\t\ttreeWalk = treeWalk.resetRoot(db, tree, curs);\n+\t\tfor (;!treeWalk.eof(); treeWalk = treeWalk.next()) {\n+\t\t\tfinal FileMode mode = treeWalk.getEntryFileMode();\n \t\t\tfinal int sType = mode.getObjectType();\n \n \t\t\tswitch (sType) {\n \t\t\tcase Constants.OBJ_BLOB: {\n-\t\t\t\ttreeWalk.getObjectId(idBuffer, 0);\n+\t\t\t\ttreeWalk.getEntryObjectId(idBuffer);\n \t\t\t\tlookupAny(idBuffer, sType).flags |= UNINTERESTING;\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tcase Constants.OBJ_TREE: {\n-\t\t\t\ttreeWalk.getObjectId(idBuffer, 0);\n+\t\t\t\ttreeWalk.getEntryObjectId(idBuffer);\n \t\t\t\tfinal RevObject subtree = lookupAny(idBuffer, sType);\n \t\t\t\tif ((subtree.flags & UNINTERESTING) == 0) {\n \t\t\t\t\tsubtree.flags |= UNINTERESTING;\n-\t\t\t\t\ttreeWalk.enterSubtree();\n+\t\t\t\t\ttreeWalk = treeWalk.createSubtreeIterator(db, idBuffer,\n+\t\t\t\t\t\t\tcurs);\n \t\t\t\t}\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tdefault:\n \t\t\t\tif (FileMode.GITLINK.equals(mode))\n \t\t\t\t\tcontinue;\n-\t\t\t\ttreeWalk.getObjectId(idBuffer, 0);\n+\t\t\t\ttreeWalk.getEntryObjectId(idBuffer);\n \t\t\t\tthrow new CorruptObjectException(\"Invalid mode \" + mode\n \t\t\t\t\t\t+ \" for \" + idBuffer.name() + \" \"\n-\t\t\t\t\t\t+ treeWalk.getPathString() + \" in \" + tree + \".\");\n+\t\t\t\t\t\t+ treeWalk.getEntryPathString() + \" in \" + tree + \".\");\n \t\t\t}\n \t\t}\n \t}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\nindex c404cdc..0229582 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n@@ -308,6 +308,26 @@ public ObjectId getEntryObjectId() {\n \t}\n \n \t/**\n+\t * Obtain the ObjectId for the current entry.\n+\t * \n+\t * @param out\n+\t * buffer to copy the object id into.\n+\t */\n+\tpublic void getEntryObjectId(final MutableObjectId out) {\n+\t\tout.fromRaw(idBuffer(), idOffset());\n+\t}\n+\n+\t/** @return the file mode of the current entry. */\n+\tpublic FileMode getEntryFileMode() {\n+\t\treturn FileMode.fromBits(mode);\n+\t}\n+\n+\t/** @return path of the current entry, as a string. */\n+\tpublic String getEntryPathString() {\n+\t\treturn TreeWalk.pathOf(this);\n+\t}\n+\n+\t/**\n \t * Get the byte array buffer object IDs must be copied out of.\n \t *

\n \t * The id buffer contains the bytes necessary to construct an ObjectId for\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java\nindex df3384d..6a5bada 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java\n@@ -52,6 +52,8 @@\n \n /** Parses raw Git trees from the canonical semi-text/semi-binary format. */\n public class CanonicalTreeParser extends AbstractTreeIterator {\n+\tprivate static final byte[] EMPTY = {};\n+\n \tprivate byte[] raw;\n \n \t/** First offset within {@link #raw} of the current entry's data. */\n@@ -62,7 +64,7 @@\n \n \t/** Create a new parser. */\n \tpublic CanonicalTreeParser() {\n-\t\t// Nothing necessary.\n+\t\traw = EMPTY;\n \t}\n \n \tprivate CanonicalTreeParser(final CanonicalTreeParser p) {\n@@ -92,6 +94,41 @@ public void reset(final byte[] treeData) {\n \t * messages if data corruption is found.\n \t * @param curs\n \t * window cursor to use during repository access.\n+\t * @return the root level parser.\n+\t * @throws MissingObjectException\n+\t * the object supplied is not available from the repository.\n+\t * @throws IncorrectObjectTypeException\n+\t * the object supplied as an argument is not actually a tree and\n+\t * cannot be parsed as though it were a tree.\n+\t * @throws IOException\n+\t * a loose object or pack file could not be read.\n+\t */\n+\tpublic CanonicalTreeParser resetRoot(final Repository repo,\n+\t\t\tfinal AnyObjectId id, final WindowCursor curs)\n+\t\t\tthrows IncorrectObjectTypeException, IOException {\n+\t\tCanonicalTreeParser p = this;\n+\t\twhile (p.parent != null)\n+\t\t\tp = (CanonicalTreeParser) p.parent;\n+\t\tp.reset(repo, id, curs);\n+\t\treturn p;\n+\t}\n+\n+\t/** @return this iterator, or its parent, if the tree is at eof. */\n+\tpublic CanonicalTreeParser next() {\n+\t\tnext(1);\n+\t\treturn eof() && parent != null ? (CanonicalTreeParser) parent : this;\n+\t}\n+\n+\t/**\n+\t * Reset this parser to walk through the given tree.\n+\t * \n+\t * @param repo\n+\t * repository to load the tree data from.\n+\t * @param id\n+\t * identity of the tree being parsed; used only in exception\n+\t * messages if data corruption is found.\n+\t * @param curs\n+\t * window cursor to use during repository access.\n \t * @throws MissingObjectException\n \t * the object supplied is not available from the repository.\n \t * @throws IncorrectObjectTypeException\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\nindex cf66bf4..d1841b3 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\n@@ -596,7 +596,7 @@ public ObjectId getObjectId(final int nth) {\n \tpublic void getObjectId(final MutableObjectId out, final int nth) {\n \t\tfinal AbstractTreeIterator t = trees[nth];\n \t\tif (t.matches == currentHead)\n-\t\t\tout.fromRaw(t.idBuffer(), t.idOffset());\n+\t\t\tt.getEntryObjectId(out);\n \t\telse\n \t\t\tout.clear();\n \t}\n@@ -834,7 +834,7 @@ private CanonicalTreeParser parserFor(final AnyObjectId id)\n \t\treturn p;\n \t}\n \n-\tprivate static String pathOf(final AbstractTreeIterator t) {\n+\tstatic String pathOf(final AbstractTreeIterator t) {\n \t\treturn RawParseUtils.decode(Constants.CHARSET, t.path, 0, t.pathLen);\n \t}\n }\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98657","messageId":"1230171079-17156-9-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-8-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 08/23] Remove the unused PackFile.get(ObjectId) form","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:04Z","receivedAt":"2008-12-25T02:11:04Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Everyone passes in a WindowCursor, except this one test case.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../tst/org/spearce/jgit/lib/T0004_PackReader.java | 2 +-\n .../src/org/spearce/jgit/lib/PackFile.java | 19 -------------------\n 2 files changed, 1 insertions(+), 20 deletions(-)\n\ndiff --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\nindex 8288e56..f6fff52 100644\n--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/T0004_PackReader.java\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/T0004_PackReader.java\n@@ -55,7 +55,7 @@ public void test003_lookupCompressedObject() throws IOException {\n \n \t\tid = ObjectId.fromString(\"902d5476fa249b7abc9d84c611577a81381f0327\");\n \t\tpr = new PackFile(db, TEST_IDX, TEST_PACK);\n-\t\tor = pr.get(id);\n+\t\tor = pr.get(new WindowCursor(), id);\n \t\tassertNotNull(or);\n \t\tassertEquals(id, or.getId());\n \t\tassertEquals(Constants.OBJ_TREE, or.getType());\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\nindex fc1b6ea..cd17bd4 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\n@@ -117,25 +117,6 @@ public boolean hasObject(final AnyObjectId id) {\n \t/**\n \t * Get an object from this pack.\n \t * \n-\t * @param id\n-\t * the object to obtain from the pack. Must not be null.\n-\t * @return the object loader for the requested object if it is contained in\n-\t * this pack; null if the object was not found.\n-\t * @throws IOException\n-\t * the pack file or the index could not be read.\n-\t */\n-\tpublic PackedObjectLoader get(final AnyObjectId id) throws IOException {\n-\t\tfinal WindowCursor wc = new WindowCursor();\n-\t\ttry {\n-\t\t\treturn get(wc, id);\n-\t\t} finally {\n-\t\t\twc.release();\n-\t\t}\n-\t}\n-\n-\t/**\n-\t * Get an object from this pack.\n-\t * \n \t * @param curs\n \t * temporary working space associated with the calling thread.\n \t * @param id\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98663","messageId":"1230171079-17156-10-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-9-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 09/23] Remove getId from ObjectLoader API as its unnecessary overhead","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:05Z","receivedAt":"2008-12-25T02:11:05Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Apparently nobody actually requires the getId() method on an ObjectLoader.\nIn every single location where the getId() is being used the caller has\nan AnyObjectId wich the proper value already in-scope, typically the value\nthey passed into Repository.openObject(). Avoiding having the id in the\nloader API means PackFile doesn't have to copy a MutableObjectId into an\nimmutable ObjectId, saving an object allocation per object lookup.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../tst/org/spearce/jgit/lib/T0004_PackReader.java | 2 -\n .../jgit/errors/CorruptObjectException.java | 12 ++++++\n .../src/org/spearce/jgit/lib/Constants.java | 2 +-\n .../spearce/jgit/lib/DeltaPackedObjectLoader.java | 3 +-\n .../src/org/spearce/jgit/lib/ObjectLoader.java | 38 --------------------\n .../src/org/spearce/jgit/lib/PackFile.java | 12 +-----\n .../src/org/spearce/jgit/lib/Repository.java | 2 +-\n .../org/spearce/jgit/lib/UnpackedObjectLoader.java | 12 +++----\n .../spearce/jgit/lib/WholePackedObjectLoader.java | 3 +-\n .../src/org/spearce/jgit/revwalk/RevWalk.java | 8 ++--\n .../jgit/transport/WalkFetchConnection.java | 15 +++++++-\n 11 files changed, 42 insertions(+), 67 deletions(-)\n\ndiff --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\nindex f6fff52..6ffb904 100644\n--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/T0004_PackReader.java\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/T0004_PackReader.java\n@@ -57,7 +57,6 @@ public void test003_lookupCompressedObject() throws IOException {\n \t\tpr = new PackFile(db, TEST_IDX, TEST_PACK);\n \t\tor = pr.get(new WindowCursor(), id);\n \t\tassertNotNull(or);\n-\t\tassertEquals(id, or.getId());\n \t\tassertEquals(Constants.OBJ_TREE, or.getType());\n \t\tassertEquals(35, or.getSize());\n \t\tassertEquals(7738, or.getDataOffset());\n@@ -72,7 +71,6 @@ public void test004_lookupDeltifiedObject() throws IOException {\n \t\tor = db.openObject(id);\n \t\tassertNotNull(or);\n \t\tassertTrue(or instanceof PackedObjectLoader);\n-\t\tassertEquals(id, or.getId());\n \t\tassertEquals(Constants.OBJ_BLOB, or.getType());\n \t\tassertEquals(18009, or.getSize());\n \t\tassertEquals(537, ((PackedObjectLoader) or).getDataOffset());\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/errors/CorruptObjectException.java b/org.spearce.jgit/src/org/spearce/jgit/errors/CorruptObjectException.java\nindex 4eb7aa6..2b0e287 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/errors/CorruptObjectException.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/errors/CorruptObjectException.java\n@@ -40,6 +40,7 @@\n \n import java.io.IOException;\n \n+import org.spearce.jgit.lib.AnyObjectId;\n import org.spearce.jgit.lib.ObjectId;\n \n /**\n@@ -55,6 +56,17 @@\n \t * @param id\n \t * @param why\n \t */\n+\tpublic CorruptObjectException(final AnyObjectId id, final String why) {\n+\t\tthis(id.toObjectId(), why);\n+\t}\n+\n+\t/**\n+\t * Construct a CorruptObjectException for reporting a problem specified\n+\t * object id\n+\t *\n+\t * @param id\n+\t * @param why\n+\t */\n \tpublic CorruptObjectException(final ObjectId id, final String why) {\n \t\tsuper(\"Object \" + id.name() + \" is corrupt: \" + why);\n \t}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/Constants.java b/org.spearce.jgit/src/org/spearce/jgit/lib/Constants.java\nindex 9613d07..8f093d6 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/Constants.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/Constants.java\n@@ -311,7 +311,7 @@ public static String typeString(final int typeCode) {\n \t * @throws CorruptObjectException\n \t * there is no valid type identified by typeString.\n \t */\n-\tpublic static int decodeTypeString(final ObjectId id,\n+\tpublic static int decodeTypeString(final AnyObjectId id,\n \t\t\tfinal byte[] typeString, final byte endMark,\n \t\t\tfinal MutableInteger offset) throws CorruptObjectException {\n \t\ttry {\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaPackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaPackedObjectLoader.java\nindex e73f8e5..85f2bda 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaPackedObjectLoader.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaPackedObjectLoader.java\n@@ -92,7 +92,8 @@ public long getSize() throws IOException {\n \t\t\treturn data;\n \t\t} catch (DataFormatException dfe) {\n \t\t\tfinal CorruptObjectException coe;\n-\t\t\tcoe = new CorruptObjectException(getId(), \"bad stream\");\n+\t\t\tcoe = new CorruptObjectException(\"Object at \" + dataOffset + \" in \"\n+\t\t\t\t\t+ pack.getPackFile() + \" has bad zlib stream\");\n \t\t\tcoe.initCause(dfe);\n \t\t\tthrow coe;\n \t\t}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectLoader.java\nindex 8d745dd..5485d8d 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectLoader.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectLoader.java\n@@ -39,50 +39,12 @@\n package org.spearce.jgit.lib;\n \n import java.io.IOException;\n-import java.security.MessageDigest;\n \n /**\n * Base class for a set of loaders for different representations of Git objects.\n * New loaders are constructed for every object.\n */\n public abstract class ObjectLoader {\n-\tprivate ObjectId objectId;\n-\n-\t/**\n-\t * @return the id of this object, possibly computed on demand\n-\t * @throws IOException\n-\t */\n-\tpublic ObjectId getId() throws IOException {\n-\t\tif (objectId == null) {\n-\t\t\tfinal MessageDigest md = Constants.newMessageDigest();\n-\t\t\tmd.update(Constants.encodedTypeString(getType()));\n-\t\t\tmd.update((byte) ' ');\n-\t\t\tmd.update(Constants.encodeASCII(getSize()));\n-\t\t\tmd.update((byte) 0);\n-\t\t\tmd.update(getCachedBytes());\n-\t\t\tobjectId = ObjectId.fromRaw(md.digest());\n-\t\t}\n-\t\treturn objectId;\n-\t}\n-\n-\t/**\n-\t * @return true if id of loaded object is already known, false otherwise.\n-\t */\n-\tprotected boolean hasComputedId() {\n-\t\treturn objectId != null;\n-\t}\n-\n-\t/**\n-\t * Set the SHA-1 id of the object handled by this loader\n-\t * \n-\t * @param id\n-\t */\n-\tprotected void setId(final ObjectId id) {\n-\t\tif (objectId != null)\n-\t\t\tthrow new IllegalStateException(\"Id already set.\");\n-\t\tobjectId = id;\n-\t}\n-\n \t/**\n \t * @return Git in pack object type, see {@link Constants}.\n \t * @throws IOException\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\nindex cd17bd4..3cdca8f 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\n@@ -129,11 +129,7 @@ public boolean hasObject(final AnyObjectId id) {\n \tpublic PackedObjectLoader get(final WindowCursor curs, final AnyObjectId id)\n \t\t\tthrows IOException {\n \t\tfinal long offset = idx.findOffset(id);\n-\t\tif (offset == -1)\n-\t\t\treturn null;\n-\t\tfinal PackedObjectLoader objReader = reader(curs, offset);\n-\t\tobjReader.setId(id.toObjectId());\n-\t\treturn objReader;\n+\t\treturn 0 < offset ? reader(curs, offset) : null;\n \t}\n \n \t/**\n@@ -219,11 +215,7 @@ final void copyRawData(final PackedObjectLoader loader,\n \t\t\tpack.copyToStream(dataOffset, buf, cnt, crcOut, curs);\n \t\t\tfinal long computed = crc.getValue();\n \n-\t\t\tObjectId id;\n-\t\t\tif (loader.hasComputedId())\n-\t\t\t\tid = loader.getId();\n-\t\t\telse\n-\t\t\t\tid = findObjectForOffset(objectOffset);\n+\t\t\tfinal ObjectId id = findObjectForOffset(objectOffset);\n \t\t\tfinal long expected = idx.findCRC32(id);\n \t\t\tif (computed != expected)\n \t\t\t\tthrow new CorruptObjectException(id,\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java b/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java\nindex 8f6e96e..02f8103 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java\n@@ -317,7 +317,7 @@ public ObjectLoader openObject(final WindowCursor curs, final AnyObjectId id)\n \t\t\t} while (k > 0);\n \t\t}\n \t\ttry {\n-\t\t\treturn new UnpackedObjectLoader(this, id.toObjectId());\n+\t\t\treturn new UnpackedObjectLoader(this, id);\n \t\t} catch (FileNotFoundException fnfe) {\n \t\t\treturn null;\n \t\t}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectLoader.java\nindex 3ad273f..0560c3a 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectLoader.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectLoader.java\n@@ -67,13 +67,13 @@\n \t * SHA-1\n \t * @throws IOException\n \t */\n-\tpublic UnpackedObjectLoader(final Repository db, final ObjectId id)\n+\tpublic UnpackedObjectLoader(final Repository db, final AnyObjectId id)\n \t\t\tthrows IOException {\n \t\tthis(readCompressed(db, id), id);\n \t}\n \n-\tprivate static byte[] readCompressed(final Repository db, final ObjectId id)\n-\t\t\tthrows FileNotFoundException, IOException {\n+\tprivate static byte[] readCompressed(final Repository db,\n+\t\t\tfinal AnyObjectId id) throws FileNotFoundException, IOException {\n \t\tfinal FileInputStream objStream = new FileInputStream(db.toFile(id));\n \t\tfinal byte[] compressed;\n \t\ttry {\n@@ -101,10 +101,8 @@ public UnpackedObjectLoader(final byte[] compressed)\n \t\tthis(compressed, null);\n \t}\n \n-\tprivate UnpackedObjectLoader(final byte[] compressed, final ObjectId id)\n+\tprivate UnpackedObjectLoader(final byte[] compressed, final AnyObjectId id)\n \t\t\tthrows CorruptObjectException {\n-\t\tsetId(id);\n-\n \t\t// Try to determine if this is a legacy format loose object or\n \t\t// a new style loose object. The legacy format was completely\n \t\t// compressed with zlib so the first byte must be 0x78 (15-bit\n@@ -177,7 +175,7 @@ private UnpackedObjectLoader(final byte[] compressed, final ObjectId id)\n \t\t}\n \t}\n \n-\tprivate void decompress(final ObjectId id, final Inflater inf, int p)\n+\tprivate void decompress(final AnyObjectId id, final Inflater inf, int p)\n \t\t\tthrows CorruptObjectException {\n \t\ttry {\n \t\t\twhile (!inf.finished())\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WholePackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WholePackedObjectLoader.java\nindex 7185df5..3b4f90d 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WholePackedObjectLoader.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WholePackedObjectLoader.java\n@@ -72,7 +72,8 @@ WholePackedObjectLoader(final WindowCursor curs, final PackFile pr,\n \t\t\treturn data;\n \t\t} catch (DataFormatException dfe) {\n \t\t\tfinal CorruptObjectException coe;\n-\t\t\tcoe = new CorruptObjectException(getId(), \"bad stream\");\n+\t\t\tcoe = new CorruptObjectException(\"Object at \" + dataOffset + \" in \"\n+\t\t\t\t\t+ pack.getPackFile() + \" has bad zlib stream\");\n \t\t\tcoe.initCause(dfe);\n \t\t\tthrow coe;\n \t\t}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java\nindex b1571ab..dfb34d9 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java\n@@ -687,23 +687,23 @@ public RevObject parseAny(final AnyObjectId id)\n \t\t\tfinal int type = ldr.getType();\n \t\t\tswitch (type) {\n \t\t\tcase Constants.OBJ_COMMIT: {\n-\t\t\t\tfinal RevCommit c = createCommit(ldr.getId());\n+\t\t\t\tfinal RevCommit c = createCommit(id);\n \t\t\t\tc.parseCanonical(this, data);\n \t\t\t\tr = c;\n \t\t\t\tbreak;\n \t\t\t}\n \t\t\tcase Constants.OBJ_TREE: {\n-\t\t\t\tr = new RevTree(ldr.getId());\n+\t\t\t\tr = new RevTree(id);\n \t\t\t\tr.flags |= PARSED;\n \t\t\t\tbreak;\n \t\t\t}\n \t\t\tcase Constants.OBJ_BLOB: {\n-\t\t\t\tr = new RevBlob(ldr.getId());\n+\t\t\t\tr = new RevBlob(id);\n \t\t\t\tr.flags |= PARSED;\n \t\t\t\tbreak;\n \t\t\t}\n \t\t\tcase Constants.OBJ_TAG: {\n-\t\t\t\tfinal RevTag t = new RevTag(ldr.getId());\n+\t\t\t\tfinal RevTag t = new RevTag(id);\n \t\t\t\tt.parseCanonical(this, data);\n \t\t\t\tr = t;\n \t\t\t\tbreak;\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java b/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java\nindex 5d0c6bc..93b5bd2 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/WalkFetchConnection.java\n@@ -42,6 +42,7 @@\n import java.io.FileNotFoundException;\n import java.io.FileOutputStream;\n import java.io.IOException;\n+import java.security.MessageDigest;\n import java.util.ArrayList;\n import java.util.Collection;\n import java.util.HashMap;\n@@ -155,6 +156,8 @@\n \n \tprivate final MutableObjectId idBuffer = new MutableObjectId();\n \n+\tprivate final MessageDigest objectDigest = Constants.newMessageDigest();\n+\n \t/**\n \t * Errors received while trying to obtain an object.\n \t *

\n@@ -573,9 +576,17 @@ private void verifyLooseObject(final AnyObjectId id, final byte[] compressed)\n \t\t\tthrow e;\n \t\t}\n \n-\t\tif (!AnyObjectId.equals(id, uol.getId())) {\n+\t\tobjectDigest.reset();\n+\t\tobjectDigest.update(Constants.encodedTypeString(uol.getType()));\n+\t\tobjectDigest.update((byte) ' ');\n+\t\tobjectDigest.update(Constants.encodeASCII(uol.getSize()));\n+\t\tobjectDigest.update((byte) 0);\n+\t\tobjectDigest.update(uol.getCachedBytes());\n+\t\tidBuffer.fromRaw(objectDigest.digest(), 0);\n+\n+\t\tif (!AnyObjectId.equals(id, idBuffer)) {\n \t\t\tthrow new TransportException(\"Incorrect hash for \" + id.name()\n-\t\t\t\t\t+ \"; computed \" + uol.getId().name() + \" as a \"\n+\t\t\t\t\t+ \"; computed \" + idBuffer.name() + \" as a \"\n \t\t\t\t\t+ Constants.encodedTypeString(uol.getType()) + \" from \"\n \t\t\t\t\t+ compressed.length + \" bytes.\");\n \t\t}\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98667","messageId":"1230171079-17156-11-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-10-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 10/23] Make mmap mode more reliable by forcing GC at the correct spot","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:06Z","receivedAt":"2008-12-25T02:11:06Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"ObjectLoaders can defer the bulk of their data access to the\ngetCachedBytes() method invocation, rather than at the time\nof their construction. That means there's code paths into\nthe mmap allocator which aren't protected by the \"try GC and\ntry again\" within openObject, resulting in some random crashes\ndue to mmap failures.\n\nThe right place to check for mmap failure and retry is within\nWindowedFile.loadWindow, where we actually invoke the mmap call.\nIf the call fails, we need can immediately retry it, and if it\nfails again, we can temporarily degrade to the byte[] variant\nuntil the JVM is able to evict and GC enough space.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../src/org/spearce/jgit/lib/Repository.java | 27 +-----------\n .../src/org/spearce/jgit/lib/WindowedFile.java | 43 ++++++++++++++-----\n 2 files changed, 34 insertions(+), 36 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java b/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java\nindex 02f8103..e1c4049 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java\n@@ -290,30 +290,9 @@ public ObjectLoader openObject(final WindowCursor curs, final AnyObjectId id)\n \t\tint k = packs.length;\n \t\tif (k > 0) {\n \t\t\tdo {\n-\t\t\t\ttry {\n-\t\t\t\t\tfinal ObjectLoader ol = packs[--k].get(curs, id);\n-\t\t\t\t\tif (ol != null)\n-\t\t\t\t\t\treturn ol;\n-\t\t\t\t} catch (IOException ioe) {\n-\t\t\t\t\t// This shouldn't happen unless the pack was corrupted\n-\t\t\t\t\t// after we opened it or the VM runs out of memory. This is\n-\t\t\t\t\t// a know problem with memory mapped I/O in java and have\n-\t\t\t\t\t// been noticed with JDK < 1.6. Tell the gc that now is a good\n-\t\t\t\t\t// time to collect and try once more.\n-\t\t\t\t\ttry {\n-\t\t\t\t\t\tcurs.release();\n-\t\t\t\t\t\tSystem.gc();\n-\t\t\t\t\t\tfinal ObjectLoader ol = packs[k].get(curs, id);\n-\t\t\t\t\t\tif (ol != null)\n-\t\t\t\t\t\t\treturn ol;\n-\t\t\t\t\t} catch (IOException ioe2) {\n-\t\t\t\t\t\tioe2.printStackTrace();\n-\t\t\t\t\t\tioe.printStackTrace();\n-\t\t\t\t\t\t// Still fails.. that's BAD, maybe the pack has\n-\t\t\t\t\t\t// been corrupted after all, or the gc didn't manage\n-\t\t\t\t\t\t// to release enough previously mmaped areas.\n-\t\t\t\t\t}\n-\t\t\t\t}\n+\t\t\t\tfinal ObjectLoader ol = packs[--k].get(curs, id);\n+\t\t\t\tif (ol != null)\n+\t\t\t\t\treturn ol;\n \t\t\t} while (k > 0);\n \t\t}\n \t\ttry {\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\nindex f640c42..dd94f24 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\n@@ -299,22 +299,41 @@ void cacheClose() {\n \t}\n \n \tvoid loadWindow(final WindowCursor curs, final int windowId,\n-\t\t\tfinal long pos, final int windowSize) throws IOException {\n+\t\t\tfinal long pos, final int size) throws IOException {\n \t\tif (WindowCache.mmap) {\n-\t\t\tfinal MappedByteBuffer map = fd.getChannel().map(MapMode.READ_ONLY,\n-\t\t\t\t\tpos, windowSize);\n-\t\t\tif (map.hasArray()) {\n-\t\t\t\tfinal byte[] b = map.array();\n-\t\t\t\tcurs.window = new ByteArrayWindow(this, pos, windowId, b);\n-\t\t\t\tcurs.handle = b;\n-\t\t\t} else {\n-\t\t\t\tcurs.window = new ByteBufferWindow(this, pos, windowId, map);\n-\t\t\t\tcurs.handle = map;\n+\t\t\tMappedByteBuffer map;\n+\t\t\ttry {\n+\t\t\t\tmap = fd.getChannel().map(MapMode.READ_ONLY, pos, size);\n+\t\t\t} catch (IOException e) {\n+\t\t\t\t// The most likely reason this failed is the JVM has run out\n+\t\t\t\t// of virtual memory. We need to discard quickly, and try to\n+\t\t\t\t// force the GC to finalize and release any existing mappings.\n+\t\t\t\ttry {\n+\t\t\t\t\tcurs.release();\n+\t\t\t\t\tSystem.gc();\n+\t\t\t\t\tSystem.runFinalization();\n+\t\t\t\t\tmap = fd.getChannel().map(MapMode.READ_ONLY, pos, size);\n+\t\t\t\t} catch (IOException ioe2) {\n+\t\t\t\t\t// Temporarily disable mmap and do buffered disk IO.\n+\t\t\t\t\t//\n+\t\t\t\t\tmap = null;\n+\t\t\t\t\tSystem.err.println(\"warning: mmap failure: \"+ioe2);\n+\t\t\t\t}\n+\t\t\t}\n+\t\t\tif (map != null) {\n+\t\t\t\tif (map.hasArray()) {\n+\t\t\t\t\tfinal byte[] b = map.array();\n+\t\t\t\t\tcurs.window = new ByteArrayWindow(this, pos, windowId, b);\n+\t\t\t\t\tcurs.handle = b;\n+\t\t\t\t} else {\n+\t\t\t\t\tcurs.window = new ByteBufferWindow(this, pos, windowId, map);\n+\t\t\t\t\tcurs.handle = map;\n+\t\t\t\t}\n+\t\t\t\treturn;\n \t\t\t}\n-\t\t\treturn;\n \t\t}\n \n-\t\tfinal byte[] b = new byte[windowSize];\n+\t\tfinal byte[] b = new byte[size];\n \t\tsynchronized (fd) {\n \t\t\tfd.seek(pos);\n \t\t\tfd.readFully(b);\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98668","messageId":"1230171079-17156-12-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-11-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 11/23] Rewrite WindowCache to use a hash table","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:07Z","receivedAt":"2008-12-25T02:11:07Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"This shaved 10s off my linux-2.6 \"jgit rev-list --objects\" test.\nWe're also getting slightly better cache hit ratios, approaching\n95% during commit access and 80% during tree access on the same\nrepository. Its a significant win.\n\nThe cache is also a bit better about memory usage. We now make\nsure the byte[] or ByteBuffer handle is cleared out of the soft\nreference when we push the reference into the queue manually. A\nsmall change, but it makes a marked difference with the overall\nJVM memory usage.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../src/org/spearce/jgit/lib/ByteWindow.java | 10 +-\n .../src/org/spearce/jgit/lib/WindowCache.java | 323 ++++++++++++--------\n .../src/org/spearce/jgit/lib/WindowedFile.java | 2 +-\n 3 files changed, 199 insertions(+), 136 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java\nindex 1f6beb8..8d37de7 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java\n@@ -56,14 +56,20 @@\n * type of object reference used to manage the window data.\n */\n abstract class ByteWindow extends SoftReference {\n+\tboolean sizeActive = true;\n+\n+\tByteWindow chainNext;\n+\n+\tByteWindow lruPrev;\n+\n+\tByteWindow lruNext;\n+\n \tfinal WindowedFile provider;\n \n \tfinal int id;\n \n \tfinal int size;\n \n-\tint lastAccessed;\n-\n \tfinal long start;\n \n \tfinal long end;\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\nindex f617845..f478f04 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\n@@ -1,5 +1,5 @@\n /*\n- * Copyright (C) 2007, Robin Rosenberg \n+ * Copyright (C) 2008, Google Inc.\n * Copyright (C) 2008, Shawn O. Pearce \n *\n * All rights reserved.\n@@ -41,11 +41,7 @@\n import java.io.IOException;\n import java.lang.ref.ReferenceQueue;\n \n-/**\n- * The WindowCache manages reusable Windows and inflaters used by\n- * the other windowed file access classes.\n- */\n-public class WindowCache {\n+class WindowCache {\n \tprivate static final int KB = 1024;\n \n \tprivate static final int MB = 1024 * KB;\n@@ -68,23 +64,51 @@ private static final int bits(int newSize) {\n \n \tstatic final ReferenceQueue clearedWindowQueue;\n \n-\tprivate static ByteWindow[] windows;\n+\tprivate static ByteWindow[] cache;\n+\n+\tprivate static ByteWindow lruHead;\n \n-\tprivate static int openWindowCount;\n+\tprivate static ByteWindow lruTail;\n \n \tprivate static int openByteCount;\n \n-\tprivate static int accessClock;\n+\tprivate static int hits;\n+\n+\tprivate static int reqs;\n+\n+\tprivate static int opens;\n+\n+\tprivate static int closes;\n \n \tstatic {\n \t\tmaxByteCount = 10 * MB;\n \t\twindowSizeShift = bits(8 * KB);\n \t\twindowSize = 1 << windowSizeShift;\n \t\tmmap = false;\n-\t\twindows = new ByteWindow[maxByteCount / windowSize];\n+\t\tcache = new ByteWindow[cacheTableSize()];\n \t\tclearedWindowQueue = new ReferenceQueue();\n \t}\n \n+\tstatic synchronized String statString() {\n+\t\tint maxChain = 0, tot = 0;\n+\t\tfor (ByteWindow e : cache) {\n+\t\t\tint n = 0;\n+\t\t\tfor (; e != null; e = e.chainNext) {\n+\t\t\t\tn++;\n+\t\t\t\ttot++;\n+\t\t\t}\n+\t\t\tmaxChain = Math.max(maxChain, n);\n+\t\t}\n+\t\treturn \"WindowCache[ hits: \" + (hits * 100 / reqs) + \"%\"\n+\t\t\t\t+ \"; windows: \" + tot + \" maxChain: \" + maxChain + \"; kb:\"\n+\t\t\t\t+ (openByteCount / KB) + \"; cache: \" + cache.length + \" fds: \"\n+\t\t\t\t+ (opens - closes) + \",\" + opens + \",\" + closes + \" ]\";\n+\t}\n+\n+\tprivate static int cacheTableSize() {\n+\t\treturn 5 * (maxByteCount / windowSize) / 2;\n+\t}\n+\n \t/**\n \t * Modify the configuration of the window cache.\n \t *

\n@@ -135,27 +159,36 @@ private static synchronized void reconfigureImpl(final int packedGitLimit,\n \t\t\t// We have to throw away every window we have. None\n \t\t\t// of them are suitable for the new configuration.\n \t\t\t//\n-\t\t\tfor (int i = 0; i < openWindowCount; i++) {\n-\t\t\t\tfinal ByteWindow win = windows[i];\n-\t\t\t\tif (--win.provider.openCount == 0)\n-\t\t\t\t\twin.provider.cacheClose();\n-\t\t\t\twindows[i] = null;\n+\t\t\tfor (ByteWindow e : cache) {\n+\t\t\t\tfor (; e != null; e = e.chainNext)\n+\t\t\t\t\tclear(e);\n+\t\t\t}\n+\t\t\trunClearedWindowQueue();\n+\t\t\tcache = new ByteWindow[cacheTableSize()];\n+\n+\t\t} else {\n+\t\t\tif (prune) {\n+\t\t\t\t// We should decrease our memory usage.\n+\t\t\t\t//\n+\t\t\t\treleaseMemory();\n+\t\t\t\trunClearedWindowQueue();\n \t\t\t}\n-\t\t\twindows = new ByteWindow[maxByteCount / windowSize];\n-\t\t\topenWindowCount = 0;\n-\t\t\topenByteCount = 0;\n-\t\t} else if (prune) {\n-\t\t\t// Our memory limit was decreased so we should try\n-\t\t\t// to drop windows to ensure we meet the new lower\n-\t\t\t// limit we were just given.\n-\t\t\t//\n-\t\t\tfinal int wincnt = maxByteCount / windowSize;\n-\t\t\treleaseMemory(wincnt, null, 0, 0);\n \n-\t\t\tif (wincnt != windows.length) {\n-\t\t\t\tfinal ByteWindow[] n = new ByteWindow[wincnt];\n-\t\t\t\tSystem.arraycopy(windows, 0, n, 0, openWindowCount);\n-\t\t\t\twindows = n;\n+\t\t\tif (cache.length != cacheTableSize()) {\n+\t\t\t\t// The cache table should be resized.\n+\t\t\t\t// Rehash every entry.\n+\t\t\t\t//\n+\t\t\t\tfinal ByteWindow[] priorTable = cache;\n+\n+\t\t\t\tcache = new ByteWindow[cacheTableSize()];\n+\t\t\t\tfor (ByteWindow e : priorTable) {\n+\t\t\t\t\tfor (ByteWindow n; e != null; e = n) {\n+\t\t\t\t\t\tn = e.chainNext;\n+\t\t\t\t\t\tfinal int idx = hash(e.provider, e.id);\n+\t\t\t\t\t\te.chainNext = cache[idx];\n+\t\t\t\t\t\tcache[idx] = e;\n+\t\t\t\t\t}\n+\t\t\t\t}\n \t\t\t}\n \t\t}\n \t}\n@@ -178,19 +211,27 @@ private static synchronized void reconfigureImpl(final int packedGitLimit,\n \t */\n \tpublic static synchronized final void get(final WindowCursor curs,\n \t\t\tfinal WindowedFile wp, final long position) throws IOException {\n+\t\treqs++;\n \t\tfinal int id = (int) (position >> windowSizeShift);\n-\t\tint idx = binarySearch(wp, id);\n-\t\tif (0 <= idx) {\n-\t\t\tfinal ByteWindow w = windows[idx];\n-\t\t\tif ((curs.handle = w.get()) != null) {\n-\t\t\t\tw.lastAccessed = ++accessClock;\n-\t\t\t\tcurs.window = w;\n-\t\t\t\treturn;\n+\t\tfinal int idx = hash(wp, id);\n+\t\tfor (ByteWindow e = cache[idx]; e != null; e = e.chainNext) {\n+\t\t\tif (e.provider == wp && e.id == id) {\n+\t\t\t\tif ((curs.handle = e.get()) != null) {\n+\t\t\t\t\tcurs.window = e;\n+\t\t\t\t\tmakeMostRecent(e);\n+\t\t\t\t\thits++;\n+\t\t\t\t\treturn;\n+\t\t\t\t}\n+\n+\t\t\t\tclear(e);\n+\t\t\t\tbreak;\n \t\t\t}\n \t\t}\n \n-\t\tif (++wp.openCount == 1) {\n+\t\tif (wp.openCount == 0) {\n \t\t\ttry {\n+\t\t\t\topens++;\n+\t\t\t\twp.openCount = 1;\n \t\t\t\twp.cacheOpen();\n \t\t\t} catch (IOException ioe) {\n \t\t\t\twp.openCount = 0;\n@@ -201,106 +242,55 @@ public static synchronized final void get(final WindowCursor curs,\n \t\t\t} catch (Error ioe) {\n \t\t\t\twp.openCount = 0;\n \t\t\t\tthrow ioe;\n+\t\t\t} finally {\n+\t\t\t\twp.openCount--;\n \t\t\t}\n \n \t\t\t// The cacheOpen may have mapped the window we are trying to\n \t\t\t// map ourselves. Retrying the search ensures that does not\n \t\t\t// happen to us.\n \t\t\t//\n-\t\t\tidx = binarySearch(wp, id);\n-\t\t\tif (0 <= idx) {\n-\t\t\t\tfinal ByteWindow w = windows[idx];\n-\t\t\t\tif ((curs.handle = w.get()) != null) {\n-\t\t\t\t\tw.lastAccessed = ++accessClock;\n-\t\t\t\t\tcurs.window = w;\n-\t\t\t\t\treturn;\n+\t\t\tfor (ByteWindow e = cache[idx]; e != null; e = e.chainNext) {\n+\t\t\t\tif (e.provider == wp && e.id == id) {\n+\t\t\t\t\tif ((curs.handle = e.get()) != null) {\n+\t\t\t\t\t\tcurs.window = e;\n+\t\t\t\t\t\tmakeMostRecent(e);\n+\t\t\t\t\t\treturn;\n+\t\t\t\t\t}\n+\n+\t\t\t\t\tclear(e);\n+\t\t\t\t\tbreak;\n \t\t\t\t}\n \t\t\t}\n \t\t}\n \n-\t\tidx = -(idx + 1);\n-\t\tfinal int wSz = windowSize(wp, id);\n-\t\tidx = releaseMemory(windows.length, wp, idx, wSz);\n-\n-\t\tif (idx < 0)\n-\t\t\tidx = 0;\n-\t\tfinal int toMove = openWindowCount - idx;\n-\t\tif (toMove > 0)\n-\t\t\tSystem.arraycopy(windows, idx, windows, idx + 1, toMove);\n-\t\twp.loadWindow(curs, id, id << windowSizeShift, wSz);\n-\t\twindows[idx] = curs.window;\n-\t\topenWindowCount++;\n-\t\topenByteCount += curs.window.size;\n+\t\tfinal int wsz = windowSize(wp, id);\n+\t\twp.openCount++;\n+\t\topenByteCount += wsz;\n+\t\treleaseMemory();\n+\t\trunClearedWindowQueue();\n+\n+\t\twp.loadWindow(curs, id, id << windowSizeShift, wsz);\n+\t\tfinal ByteWindow e = curs.window;\n+\t\te.chainNext = cache[idx];\n+\t\tcache[idx] = e;\n+\t\tinsertLRU(e);\n \t}\n \n-\tprivate static int releaseMemory(final int maxWindowCount,\n-\t\t\tfinal WindowedFile willRead, int insertionIndex, final int willAdd) {\n-\t\tfor (;;) {\n-\t\t\tfinal ByteWindow w = (ByteWindow) clearedWindowQueue.poll();\n-\t\t\tif (w == null)\n-\t\t\t\tbreak;\n-\t\t\tfinal int oldest = binarySearch(w.provider, w.id);\n-\t\t\tif (oldest < 0 || windows[oldest] != w)\n-\t\t\t\tcontinue; // Must have been evicted by our other controls.\n-\n-\t\t\tfinal WindowedFile p = w.provider;\n-\t\t\tif (--p.openCount == 0 && p != willRead)\n-\t\t\t\tp.cacheClose();\n-\n-\t\t\topenByteCount -= w.size;\n-\t\t\tfinal int toMove = openWindowCount - oldest - 1;\n-\t\t\tif (toMove > 0)\n-\t\t\t\tSystem.arraycopy(windows, oldest + 1, windows, oldest, toMove);\n-\t\t\twindows[--openWindowCount] = null;\n-\t\t\tif (oldest < insertionIndex)\n-\t\t\t\tinsertionIndex--;\n-\t\t}\n-\n-\t\twhile (openWindowCount >= maxWindowCount\n-\t\t\t\t|| (openWindowCount > 0 && openByteCount + willAdd > maxByteCount)) {\n-\t\t\tint oldest = 0;\n-\t\t\tfor (int k = openWindowCount - 1; k > 0; k--) {\n-\t\t\t\tif (windows[k].lastAccessed < windows[oldest].lastAccessed)\n-\t\t\t\t\toldest = k;\n-\t\t\t}\n-\n-\t\t\tfinal ByteWindow w = windows[oldest];\n-\t\t\tfinal WindowedFile p = w.provider;\n-\t\t\tif (--p.openCount == 0 && p != willRead)\n-\t\t\t\tp.cacheClose();\n-\n-\t\t\topenByteCount -= w.size;\n-\t\t\tfinal int toMove = openWindowCount - oldest - 1;\n-\t\t\tif (toMove > 0)\n-\t\t\t\tSystem.arraycopy(windows, oldest + 1, windows, oldest, toMove);\n-\t\t\twindows[--openWindowCount] = null;\n-\t\t\tw.enqueue();\n-\t\t\tif (oldest < insertionIndex)\n-\t\t\t\tinsertionIndex--;\n+\tprivate static void makeMostRecent(ByteWindow e) {\n+\t\tif (lruHead != e) {\n+\t\t\tunlinkLRU(e);\n+\t\t\tinsertLRU(e);\n \t\t}\n-\n-\t\treturn insertionIndex;\n \t}\n \n-\tprivate static final int binarySearch(final WindowedFile sprov,\n-\t\t\tfinal int sid) {\n-\t\tif (openWindowCount == 0)\n-\t\t\treturn -1;\n-\t\tfinal int shc = sprov.hash;\n-\t\tint high = openWindowCount;\n-\t\tint low = 0;\n-\t\tdo {\n-\t\t\tfinal int mid = (low + high) / 2;\n-\t\t\tfinal ByteWindow mw = windows[mid];\n-\t\t\tif (mw.provider == sprov && mw.id == sid)\n-\t\t\t\treturn mid;\n-\t\t\tfinal int mhc = mw.provider.hash;\n-\t\t\tif (mhc < shc || (shc == mhc && mw.id < sid))\n-\t\t\t\tlow = mid + 1;\n-\t\t\telse\n-\t\t\t\thigh = mid;\n-\t\t} while (low < high);\n-\t\treturn -(low + 1);\n+\tprivate static void releaseMemory() {\n+\t\tByteWindow e = lruTail;\n+\t\twhile (openByteCount > maxByteCount && e != null) {\n+\t\t\tfinal ByteWindow p = e.lruPrev;\n+\t\t\tclear(e);\n+\t\t\te = p;\n+\t\t}\n \t}\n \n \t/**\n@@ -316,22 +306,89 @@ private static final int binarySearch(final WindowedFile sprov,\n \t * cache.\n \t */\n \tpublic static synchronized final void purge(final WindowedFile wp) {\n-\t\tint d = 0;\n-\t\tfor (int s = 0; s < openWindowCount; s++) {\n-\t\t\tfinal ByteWindow win = windows[s];\n-\t\t\tif (win.provider != wp)\n-\t\t\t\twindows[d++] = win;\n-\t\t\telse\n-\t\t\t\topenByteCount -= win.size;\n+\t\tfor (ByteWindow e : cache) {\n+\t\t\tfor (; e != null; e = e.chainNext) {\n+\t\t\t\tif (e.provider == wp)\n+\t\t\t\t\tclear(e);\n+\t\t\t}\n+\t\t}\n+\t\trunClearedWindowQueue();\n+\t}\n+\n+\tprivate static void runClearedWindowQueue() {\n+\t\tByteWindow e;\n+\t\twhile ((e = (ByteWindow) clearedWindowQueue.poll()) != null) {\n+\t\t\tunlinkSize(e);\n+\t\t\tunlinkLRU(e);\n+\t\t\tunlinkCache(e);\n+\t\t\te.chainNext = null;\n+\t\t\te.lruNext = null;\n+\t\t\te.lruPrev = null;\n \t\t}\n-\t\topenWindowCount = d;\n+\t}\n+\n+\tprivate static void clear(final ByteWindow e) {\n+\t\tunlinkSize(e);\n+\t\te.clear();\n+\t\te.enqueue();\n+\t}\n \n-\t\tif (wp.openCount > 0) {\n-\t\t\twp.openCount = 0;\n-\t\t\twp.cacheClose();\n+\tprivate static void unlinkSize(final ByteWindow e) {\n+\t\tif (e.sizeActive) {\n+\t\t\tif (--e.provider.openCount == 0) {\n+\t\t\t\tcloses++;\n+\t\t\t\te.provider.cacheClose();\n+\t\t\t}\n+\t\t\topenByteCount -= e.size;\n+\t\t\te.sizeActive = false;\n \t\t}\n \t}\n \n+\tprivate static void unlinkCache(final ByteWindow dead) {\n+\t\tfinal int idx = hash(dead.provider, dead.id);\n+\t\tByteWindow e = cache[idx], p = null, n;\n+\t\tfor (; e != null; p = e, e = n) {\n+\t\t\tn = e.chainNext;\n+\t\t\tif (e == dead) {\n+\t\t\t\tif (p == null)\n+\t\t\t\t\tcache[idx] = n;\n+\t\t\t\telse\n+\t\t\t\t\tp.chainNext = n;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tprivate static void unlinkLRU(final ByteWindow e) {\n+\t\tfinal ByteWindow prev = e.lruPrev;\n+\t\tfinal ByteWindow next = e.lruNext;\n+\n+\t\tif (prev != null)\n+\t\t\tprev.lruNext = next;\n+\t\telse\n+\t\t\tlruHead = next;\n+\n+\t\tif (next != null)\n+\t\t\tnext.lruPrev = prev;\n+\t\telse\n+\t\t\tlruTail = prev;\n+\t}\n+\n+\tprivate static void insertLRU(final ByteWindow e) {\n+\t\tfinal ByteWindow h = lruHead;\n+\t\te.lruPrev = null;\n+\t\te.lruNext = h;\n+\t\tif (h != null)\n+\t\t\th.lruPrev = e;\n+\t\telse\n+\t\t\tlruTail = e;\n+\t\tlruHead = e;\n+\t}\n+\n+\tprivate static int hash(final WindowedFile wp, final int id) {\n+\t\treturn ((wp.hash + id) >>> 1) % cache.length;\n+\t}\n+\n \tprivate static int windowSize(final WindowedFile file, final int id) {\n \t\tfinal long len = file.length();\n \t\tfinal long pos = id << windowSizeShift;\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\nindex dd94f24..9c5cf1e 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\n@@ -88,7 +88,7 @@\n \t */\n \tpublic WindowedFile(final File file) {\n \t\tfPath = file;\n-\t\thash = System.identityHashCode(this);\n+\t\thash = System.identityHashCode(this) * 31;\n \t\tlength = Long.MAX_VALUE;\n \t}\n \n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98664","messageId":"1230171079-17156-13-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-12-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 12/23] Change ByteArrayWindow to read content outside of WindowCache's lock","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:08Z","receivedAt":"2008-12-25T02:11:08Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"This improves the concurrency limit of WindowCache by allowing the\nindividual windows to be paged in outside of the cache lock. By\nmoving it out multiple threads can read in different windows of\nthe same (or different) pack files concurrently, but we still do\nonly one read per window.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../src/org/spearce/jgit/lib/ByteArrayWindow.java | 17 +++++++++++++++++\n .../src/org/spearce/jgit/lib/WindowCache.java | 2 +-\n .../src/org/spearce/jgit/lib/WindowedFile.java | 15 +++++++--------\n 3 files changed, 25 insertions(+), 9 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java\nindex cea71be..b32d4f8 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java\n@@ -38,6 +38,8 @@\n \n package org.spearce.jgit.lib;\n \n+import java.io.IOException;\n+import java.nio.ByteBuffer;\n import java.util.zip.DataFormatException;\n import java.util.zip.Inflater;\n \n@@ -45,6 +47,8 @@\n * A {@link ByteWindow} with an underlying byte array for storage.\n */\n final class ByteArrayWindow extends ByteWindow {\n+\tboolean loaded;\n+\n \t/**\n \t * Constructor for ByteWindow.\n \t * \n@@ -64,6 +68,7 @@ ByteArrayWindow(final WindowedFile o, final long p, final int d,\n \t}\n \n \tint copy(final byte[] array, final int p, final byte[] b, final int o, int n) {\n+\t\tensureLoaded(array);\n \t\tn = Math.min(array.length - p, n);\n \t\tSystem.arraycopy(array, p, b, o, n);\n \t\treturn n;\n@@ -71,6 +76,7 @@ int copy(final byte[] array, final int p, final byte[] b, final int o, int n) {\n \n \tint inflate(final byte[] array, final int pos, final byte[] b, int o,\n \t\t\tfinal Inflater inf) throws DataFormatException {\n+\t\tensureLoaded(array);\n \t\twhile (!inf.finished()) {\n \t\t\tif (inf.needsInput()) {\n \t\t\t\tinf.setInput(array, pos, array.length - pos);\n@@ -82,4 +88,15 @@ int inflate(final byte[] array, final int pos, final byte[] b, int o,\n \t\t\to += inf.inflate(b, o, b.length - o);\n \t\treturn o;\n \t}\n+\n+\tprivate synchronized void ensureLoaded(final byte[] array) {\n+\t\tif (!loaded) {\n+\t\t\ttry {\n+\t\t\t\tprovider.fd.getChannel().read(ByteBuffer.wrap(array), start);\n+\t\t\t} catch (IOException e) {\n+\t\t\t\tthrow new RuntimeException(\"Cannot fault in window\", e);\n+\t\t\t}\n+\t\t\tloaded = true;\n+\t\t}\n+\t}\n }\n\\ No newline at end of file\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\nindex f478f04..649567b 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\n@@ -270,7 +270,7 @@ public static synchronized final void get(final WindowCursor curs,\n \t\treleaseMemory();\n \t\trunClearedWindowQueue();\n \n-\t\twp.loadWindow(curs, id, id << windowSizeShift, wsz);\n+\t\twp.allocWindow(curs, id, id << windowSizeShift, wsz);\n \t\tfinal ByteWindow e = curs.window;\n \t\te.chainNext = cache[idx];\n \t\tcache[idx] = e;\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\nindex 9c5cf1e..7626693 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\n@@ -73,7 +73,7 @@\n \n \tfinal int hash;\n \n-\tprivate RandomAccessFile fd;\n+\tRandomAccessFile fd;\n \n \tprivate long length;\n \n@@ -298,8 +298,8 @@ void cacheClose() {\n \t\tfd = null;\n \t}\n \n-\tvoid loadWindow(final WindowCursor curs, final int windowId,\n-\t\t\tfinal long pos, final int size) throws IOException {\n+\tvoid allocWindow(final WindowCursor curs, final int windowId,\n+\t\t\tfinal long pos, final int size) {\n \t\tif (WindowCache.mmap) {\n \t\t\tMappedByteBuffer map;\n \t\t\ttry {\n@@ -323,7 +323,10 @@ void loadWindow(final WindowCursor curs, final int windowId,\n \t\t\tif (map != null) {\n \t\t\t\tif (map.hasArray()) {\n \t\t\t\t\tfinal byte[] b = map.array();\n-\t\t\t\t\tcurs.window = new ByteArrayWindow(this, pos, windowId, b);\n+\t\t\t\t\tfinal ByteArrayWindow w;\n+\t\t\t\t\tw = new ByteArrayWindow(this, pos, windowId, b);\n+\t\t\t\t\tw.loaded = true;\n+\t\t\t\t\tcurs.window = w;\n \t\t\t\t\tcurs.handle = b;\n \t\t\t\t} else {\n \t\t\t\t\tcurs.window = new ByteBufferWindow(this, pos, windowId, map);\n@@ -334,10 +337,6 @@ void loadWindow(final WindowCursor curs, final int windowId,\n \t\t}\n \n \t\tfinal byte[] b = new byte[size];\n-\t\tsynchronized (fd) {\n-\t\t\tfd.seek(pos);\n-\t\t\tfd.readFully(b);\n-\t\t}\n \t\tcurs.window = new ByteArrayWindow(this, pos, windowId, b);\n \t\tcurs.handle = b;\n \t}\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98675","messageId":"1230171079-17156-14-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-13-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 13/23] Dispose of RevCommit buffers when they aren't used in PackWriter","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:09Z","receivedAt":"2008-12-25T02:11:09Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"We don't need the commit buffer, so we might as well throw it\naway immediately to reduce the total memory usage within the\nwriter process.\n\nThe same goes for the buffers within UploadPack when its doing\na check to see if it has a complete base.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../src/org/spearce/jgit/lib/PackWriter.java | 2 ++\n .../src/org/spearce/jgit/transport/UploadPack.java | 1 +\n 2 files changed, 3 insertions(+), 0 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\nindex 89460f2..88b2b1f 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n@@ -802,10 +802,12 @@ private void findObjectsToPack(final ObjectWalk walker)\n \n \t\twhile ((o = walker.next()) != null) {\n \t\t\taddObject(o);\n+\t\t\to.dispose();\n \t\t\tinitMonitor.update(1);\n \t\t}\n \t\twhile ((o = walker.nextObject()) != null) {\n \t\t\taddObject(o);\n+\t\t\to.dispose();\n \t\t\tinitMonitor.update(1);\n \t\t}\n \t\tinitMonitor.endTask();\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/UploadPack.java b/org.spearce.jgit/src/org/spearce/jgit/transport/UploadPack.java\nindex 4401951..d57df03 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/transport/UploadPack.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/UploadPack.java\n@@ -434,6 +434,7 @@ private boolean wantSatisfied(final RevCommit want) throws IOException {\n \t\t\t\t}\n \t\t\t\treturn true;\n \t\t\t}\n+\t\t\tc.dispose();\n \t\t}\n \t\treturn false;\n \t}\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98672","messageId":"1230171079-17156-15-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-14-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 14/23] Don't unpack delta chains while writing a pack from a pack v1 index","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:10Z","receivedAt":"2008-12-25T02:11:10Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"We only need to inflate the delta to verify the content is sane;\ngoing all the way through the delta chain by getCachedBytes is\na massive expensive that we just cannot afford to pay. This\nsimple change improves clone time for the Linux kernel from\n14m50s to 3m20s, due to the improved throughput in our write\nobjects phase.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../src/org/spearce/jgit/lib/ByteArrayWindow.java | 14 ++++++++++++++\n .../src/org/spearce/jgit/lib/ByteBufferWindow.java | 17 +++++++++++++++++\n .../src/org/spearce/jgit/lib/ByteWindow.java | 10 ++++++++++\n .../src/org/spearce/jgit/lib/PackFile.java | 18 +++++++++++-------\n .../src/org/spearce/jgit/lib/WindowCursor.java | 16 ++++++++++++++++\n .../src/org/spearce/jgit/lib/WindowedFile.java | 5 +++++\n 6 files changed, 73 insertions(+), 7 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java\nindex b32d4f8..7b7c7a4 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteArrayWindow.java\n@@ -89,6 +89,20 @@ int inflate(final byte[] array, final int pos, final byte[] b, int o,\n \t\treturn o;\n \t}\n \n+\tvoid inflateVerify(final byte[] array, final int pos, final Inflater inf)\n+\t\t\tthrows DataFormatException {\n+\t\tensureLoaded(array);\n+\t\twhile (!inf.finished()) {\n+\t\t\tif (inf.needsInput()) {\n+\t\t\t\tinf.setInput(array, pos, array.length - pos);\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tinf.inflate(verifyGarbageBuffer, 0, verifyGarbageBuffer.length);\n+\t\t}\n+\t\twhile (!inf.finished() && !inf.needsInput())\n+\t\t\tinf.inflate(verifyGarbageBuffer, 0, verifyGarbageBuffer.length);\n+\t}\n+\n \tprivate synchronized void ensureLoaded(final byte[] array) {\n \t\tif (!loaded) {\n \t\t\ttry {\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteBufferWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteBufferWindow.java\nindex 03bafb1..a6757e8 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteBufferWindow.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteBufferWindow.java\n@@ -90,4 +90,21 @@ int inflate(final ByteBuffer buffer, final int pos, final byte[] b, int o,\n \t\t\to += inf.inflate(b, o, b.length - o);\n \t\treturn o;\n \t}\n+\n+\tvoid inflateVerify(final ByteBuffer buffer, final int pos,\n+\t\t\tfinal Inflater inf) throws DataFormatException {\n+\t\tfinal byte[] tmp = new byte[512];\n+\t\tfinal ByteBuffer s = buffer.slice();\n+\t\ts.position(pos);\n+\t\twhile (s.remaining() > 0 && !inf.finished()) {\n+\t\t\tif (inf.needsInput()) {\n+\t\t\t\tfinal int n = Math.min(s.remaining(), tmp.length);\n+\t\t\t\ts.get(tmp, 0, n);\n+\t\t\t\tinf.setInput(tmp, 0, n);\n+\t\t\t}\n+\t\t\tinf.inflate(verifyGarbageBuffer, 0, verifyGarbageBuffer.length);\n+\t\t}\n+\t\twhile (!inf.finished() && !inf.needsInput())\n+\t\t\tinf.inflate(verifyGarbageBuffer, 0, verifyGarbageBuffer.length);\n+\t}\n }\n\\ No newline at end of file\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java\nindex 8d37de7..732664b 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java\n@@ -207,4 +207,14 @@ final int inflate(T ref, long pos, byte[] dstbuf, int dstoff, Inflater inf)\n \t */\n \tabstract int inflate(T ref, int pos, byte[] dstbuf, int dstoff, Inflater inf)\n \t\t\tthrows DataFormatException;\n+\n+\tprotected static final byte[] verifyGarbageBuffer = new byte[2048];\n+\n+\tfinal void inflateVerify(T ref, long pos, Inflater inf)\n+\t\t\tthrows DataFormatException {\n+\t\tinflateVerify(ref, (int) (pos - start), inf);\n+\t}\n+\n+\tabstract void inflateVerify(T ref, int pos, Inflater inf)\n+\t\t\tthrows DataFormatException;\n }\n\\ No newline at end of file\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\nindex 3cdca8f..0de4c55 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\n@@ -218,15 +218,19 @@ final void copyRawData(final PackedObjectLoader loader,\n \t\t\tfinal ObjectId id = findObjectForOffset(objectOffset);\n \t\t\tfinal long expected = idx.findCRC32(id);\n \t\t\tif (computed != expected)\n-\t\t\t\tthrow new CorruptObjectException(id,\n-\t\t\t\t\t\t\"Possible data corruption - CRC32 of raw pack data (object offset \"\n-\t\t\t\t\t\t\t\t+ objectOffset\n-\t\t\t\t\t\t\t\t+ \") mismatch CRC32 from pack index\");\n+\t\t\t\tthrow new CorruptObjectException(\"Object at \" + dataOffset\n+\t\t\t\t\t\t+ \" in \" + getPackFile() + \" has bad zlib stream\");\n \t\t} else {\n+\t\t\ttry {\n+\t\t\t\tpack.verifyCompressed(dataOffset, curs);\n+\t\t\t} catch (DataFormatException dfe) {\n+\t\t\t\tfinal CorruptObjectException coe;\n+\t\t\t\tcoe = new CorruptObjectException(\"Object at \" + dataOffset\n+\t\t\t\t\t\t+ \" in \" + getPackFile() + \" has bad zlib stream\");\n+\t\t\t\tcoe.initCause(dfe);\n+\t\t\t\tthrow coe;\n+\t\t\t}\n \t\t\tpack.copyToStream(dataOffset, buf, cnt, out, curs);\n-\n-\t\t\t// read to verify against Adler32 zlib checksum\n-\t\t\tloader.getCachedBytes();\n \t\t}\n \t}\n \ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCursor.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCursor.java\nindex 7aad081..5c8bec5 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCursor.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCursor.java\n@@ -125,6 +125,22 @@ int inflate(final WindowedFile provider, long position,\n \t\t}\n \t}\n \n+\tvoid inflateVerify(final WindowedFile provider, long position)\n+\t\t\tthrows IOException, DataFormatException {\n+\t\tif (inf == null)\n+\t\t\tinf = InflaterCache.get();\n+\t\telse\n+\t\t\tinf.reset();\n+\t\tfor (;;) {\n+\t\t\tpin(provider, position);\n+\t\t\twindow.inflateVerify(handle, position, inf);\n+\t\t\tif (inf.finished())\n+\t\t\t\treturn;\n+\t\t\tposition = window.end;\n+\t\t}\n+\t}\n+\n+\t\n \tprivate void pin(final WindowedFile provider, final long position)\n \t\t\tthrows IOException {\n \t\tfinal ByteWindow w = window;\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\nindex 7626693..5eb8465 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\n@@ -248,6 +248,11 @@ void readCompressed(final long position, final byte[] dstbuf,\n \t\t\tthrow new EOFException(\"Short compressed stream at \" + position);\n \t}\n \n+\tvoid verifyCompressed(final long position, final WindowCursor curs)\n+\t\t\tthrows IOException, DataFormatException {\n+\t\tcurs.inflateVerify(this, position);\n+\t}\n+\n \t/**\n \t * Overridable hook called after the file is opened.\n \t *

\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98674","messageId":"1230171079-17156-16-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-15-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 15/23] Don't unpack delta chains while converting delta to whole object","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:11Z","receivedAt":"2008-12-25T02:11:11Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"If an object is currently a delta but we need to convert it into\na whole object we shouldn't be chasing the delta chain to get its\nreal type code. We had the type code at the time we made the list\nof objects to pack; so we save it in the ObjectToPack structure.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../src/org/spearce/jgit/lib/PackWriter.java | 28 ++++++++++++++-----\n 1 files changed, 20 insertions(+), 8 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\nindex 88b2b1f..a0823c7 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n@@ -705,14 +705,14 @@ private void writeObject(final ObjectToPack otp) throws IOException {\n \tprivate void writeWholeObject(final ObjectToPack otp) throws IOException {\n \t\tif (otp.hasReuseLoader()) {\n \t\t\tfinal PackedObjectLoader loader = otp.getReuseLoader();\n-\t\t\twriteObjectHeader(loader.getType(), loader.getSize());\n+\t\t\twriteObjectHeader(otp.getType(), loader.getSize());\n \t\t\tloader.copyRawData(out, buf);\n \t\t\totp.disposeLoader();\n \t\t} else {\n \t\t\tfinal ObjectLoader loader = db.openObject(windowCursor, otp);\n \t\t\tfinal DeflaterOutputStream deflaterOut = new DeflaterOutputStream(\n \t\t\t\t\tout, deflater);\n-\t\t\twriteObjectHeader(loader.getType(), loader.getSize());\n+\t\t\twriteObjectHeader(otp.getType(), loader.getSize());\n \t\t\tdeflaterOut.write(loader.getCachedBytes());\n \t\t\tdeflaterOut.finish();\n \t\t\tdeflater.reset();\n@@ -833,7 +833,7 @@ public void addObject(final RevObject object)\n \t\t\treturn;\n \t\t}\n \n-\t\tfinal ObjectToPack otp = new ObjectToPack(object);\n+\t\tfinal ObjectToPack otp = new ObjectToPack(object, object.getType());\n \t\ttry {\n \t\t\tobjectsLists[object.getType()].add(otp);\n \t\t} catch (ArrayIndexOutOfBoundsException x) {\n@@ -858,7 +858,8 @@ public void addObject(final RevObject object)\n \n \t\tprivate PackedObjectLoader reuseLoader;\n \n-\t\tprivate int deltaDepth;\n+\t\t/** Low bits contain the objectType; higher bits the deltaDepth */\n+\t\tprivate int flags;\n \n \t\tprivate boolean wantWrite;\n \n@@ -868,9 +869,12 @@ public void addObject(final RevObject object)\n \t\t *\n \t\t * @param src\n \t\t * object id of object for packing\n+\t\t * @param type\n+\t\t * real type code of the object, not its in-pack type.\n \t\t */\n-\t\tObjectToPack(AnyObjectId src) {\n+\t\tObjectToPack(AnyObjectId src, final int type) {\n \t\t\tsuper(src);\n+\t\t\tflags |= type;\n \t\t}\n \n \t\t/**\n@@ -946,15 +950,23 @@ void disposeLoader() {\n \t\t\tthis.reuseLoader = null;\n \t\t}\n \n+\t\tint getType() {\n+\t\t\treturn flags & 0x7;\n+\t\t}\n+\n \t\tint getDeltaDepth() {\n-\t\t\treturn deltaDepth;\n+\t\t\treturn flags >>> 3;\n \t\t}\n \n \t\tvoid updateDeltaDepth() {\n+\t\t\tfinal int d;\n \t\t\tif (deltaBase instanceof ObjectToPack)\n-\t\t\t\tdeltaDepth = ((ObjectToPack) deltaBase).deltaDepth + 1;\n+\t\t\t\td = ((ObjectToPack) deltaBase).getDeltaDepth() + 1;\n \t\t\telse if (deltaBase != null)\n-\t\t\t\tdeltaDepth = 1;\n+\t\t\t\td = 1;\n+\t\t\telse\n+\t\t\t\td = 0;\n+\t\t\tflags = (d << 3) | getType();\n \t\t}\n \n \t\tboolean wantWrite() {\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98677","messageId":"1230171079-17156-17-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-16-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 16/23] Defer parsing of the ObjectId while walking a PackIndex Iterator","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:12Z","receivedAt":"2008-12-25T02:11:12Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"This is a slight performance improvement for the PackReverseIndex\nconstruction. The only code that really cares about the ObjectId\nfrom a PackIndex entry is test cases. By avoiding construction\nwe can save some CPU time during the several passes we do to make\nthe reverse index data structure within PackWriter.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../tst/org/spearce/jgit/lib/PackIndexTest.java | 4 +-\n .../tst/org/spearce/jgit/lib/PackWriterTest.java | 2 +-\n .../src/org/spearce/jgit/lib/PackIndex.java | 48 +++++++++++--------\n .../src/org/spearce/jgit/lib/PackIndexV1.java | 20 +++++---\n .../src/org/spearce/jgit/lib/PackIndexV2.java | 27 +++++++----\n 5 files changed, 61 insertions(+), 40 deletions(-)\n\ndiff --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\nindex 8ab380e..7163718 100644\n--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexTest.java\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexTest.java\n@@ -134,10 +134,10 @@ assertEquals(\"c59759f143fb1fe21c197981df75a7ee00290799\", iter.next()\n \t */\n \tpublic void testCompareEntriesOffsetsWithFindOffsets() {\n \t\tfor (MutableEntry me : smallIdx) {\n-\t\t\tassertEquals(smallIdx.findOffset(me), me.getOffset());\n+\t\t\tassertEquals(smallIdx.findOffset(me.toObjectId()), me.getOffset());\n \t\t}\n \t\tfor (MutableEntry me : denseIdx) {\n-\t\t\tassertEquals(denseIdx.findOffset(me), me.getOffset());\n+\t\t\tassertEquals(denseIdx.findOffset(me.toObjectId()), me.getOffset());\n \t\t}\n \t}\n \ndiff --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\nindex 3c02955..ec138a0 100644\n--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackWriterTest.java\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackWriterTest.java\n@@ -487,7 +487,7 @@ public int compare(MutableEntry o1, MutableEntry o2) {\n \n \t\tint i = 0;\n \t\tfor (MutableEntry me : entries) {\n-\t\t\tassertEquals(objectsOrder[i++], me.copy());\n+\t\t\tassertEquals(objectsOrder[i++].toObjectId(), me.toObjectId());\n \t\t}\n \t}\n }\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java\nindex 5fb41b1..5b7a62d 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java\n@@ -239,15 +239,10 @@ abstract long findCRC32(AnyObjectId objId) throws MissingObjectException,\n \t * in pack (both mutable).\n \t * \n \t */\n-\tpublic static class MutableEntry extends MutableObjectId {\n-\t\tprivate long offset;\n+\tpublic static class MutableEntry {\n+\t\tprotected final MutableObjectId idBuffer = new MutableObjectId();\n \n-\t\t/**\n-\t\t * Empty constructor. Object fields should be filled in later.\n-\t\t */\n-\t\tpublic MutableEntry() {\n-\t\t\tsuper();\n-\t\t}\n+\t\tlong offset;\n \n \t\t/**\n \t\t * Returns offset for this index object entry\n@@ -258,30 +253,43 @@ public long getOffset() {\n \t\t\treturn offset;\n \t\t}\n \n-\t\tvoid setOffset(long offset) {\n-\t\t\tthis.offset = offset;\n+\t\t/** @return hex string describing the object id of this entry. */\n+\t\tpublic String name() {\n+\t\t\tensureId();\n+\t\t\treturn idBuffer.name();\n \t\t}\n \n-\t\tprivate MutableEntry(MutableEntry src) {\n-\t\t\tsuper(src);\n-\t\t\tthis.offset = src.offset;\n+\t\t/** @return a copy of the object id. */\n+\t\tpublic ObjectId toObjectId() {\n+\t\t\tensureId();\n+\t\t\treturn idBuffer.toObjectId();\n \t\t}\n \n-\t\t/**\n-\t\t * Returns mutable copy of this mutable entry.\n-\t\t * \n-\t\t * @return copy of this mutable entry\n-\t\t */\n+\t\t/** @return a complete copy of this entry, that won't modify */\n \t\tpublic MutableEntry cloneEntry() {\n-\t\t\treturn new MutableEntry(this);\n+\t\t\tfinal MutableEntry r = new MutableEntry();\n+\t\t\tensureId();\n+\t\t\tr.idBuffer.w1 = idBuffer.w1;\n+\t\t\tr.idBuffer.w2 = idBuffer.w2;\n+\t\t\tr.idBuffer.w3 = idBuffer.w3;\n+\t\t\tr.idBuffer.w4 = idBuffer.w4;\n+\t\t\tr.idBuffer.w5 = idBuffer.w5;\n+\t\t\tr.offset = offset;\n+\t\t\treturn r;\n+\t\t}\n+\t\t\n+\t\tprotected void ensureId() {\n+\t\t\t// Override in implementations.\n \t\t}\n \t}\n \n \tprotected abstract class EntriesIterator implements Iterator {\n-\t\tprotected MutableEntry objectId = new MutableEntry();\n+\t\tprotected final MutableEntry entry = initEntry();\n \n \t\tprotected long returnedNumber = 0;\n \n+\t\tprotected abstract MutableEntry initEntry();\n+\n \t\tpublic boolean hasNext() {\n \t\t\treturn returnedNumber < getObjectCount();\n \t\t}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java\nindex 02465f6..90b5f6f 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java\n@@ -162,21 +162,27 @@ boolean hasCRC32Support() {\n \n \t\tprivate int levelTwo;\n \n+\t\t@Override\n+\t\tprotected MutableEntry initEntry() {\n+\t\t\treturn new MutableEntry() {\n+\t\t\t\tprotected void ensureId() {\n+\t\t\t\t\tidBuffer.fromRaw(idxdata[levelOne], levelTwo\n+\t\t\t\t\t\t\t- Constants.OBJECT_ID_LENGTH);\n+\t\t\t\t}\n+\t\t\t};\n+\t\t}\n+\n \t\tpublic MutableEntry next() {\n \t\t\tfor (; levelOne < idxdata.length; levelOne++) {\n \t\t\t\tif (idxdata[levelOne] == null)\n \t\t\t\t\tcontinue;\n-\n \t\t\t\tif (levelTwo < idxdata[levelOne].length) {\n-\t\t\t\t\tlong offset = NB.decodeUInt32(idxdata[levelOne], levelTwo);\n-\t\t\t\t\tobjectId.setOffset(offset);\n-\t\t\t\t\tobjectId.fromRaw(idxdata[levelOne], levelTwo + 4);\n+\t\t\t\t\tentry.offset = NB.decodeUInt32(idxdata[levelOne], levelTwo);\n \t\t\t\t\tlevelTwo += Constants.OBJECT_ID_LENGTH + 4;\n \t\t\t\t\treturnedNumber++;\n-\t\t\t\t\treturn objectId;\n-\t\t\t\t} else {\n-\t\t\t\t\tlevelTwo = 0;\n+\t\t\t\t\treturn entry;\n \t\t\t\t}\n+\t\t\t\tlevelTwo = 0;\n \t\t\t}\n \t\t\tthrow new NoSuchElementException();\n \t\t}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\nindex cc3ad65..48a5206 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\n@@ -234,25 +234,32 @@ else if (cmp == 0) {\n \n \t\tprivate int levelTwo;\n \n+\t\t@Override\n+\t\tprotected MutableEntry initEntry() {\n+\t\t\treturn new MutableEntry() {\n+\t\t\t\tprotected void ensureId() {\n+\t\t\t\t\tidBuffer.fromRaw(names[levelOne], levelTwo\n+\t\t\t\t\t\t\t- Constants.OBJECT_ID_LENGTH / 4);\n+\t\t\t\t}\n+\t\t\t};\n+\t\t}\n+\n \t\tpublic MutableEntry next() {\n \t\t\tfor (; levelOne < names.length; levelOne++) {\n \t\t\t\tif (levelTwo < names[levelOne].length) {\n-\t\t\t\t\tobjectId.fromRaw(names[levelOne], levelTwo);\n-\t\t\t\t\tint arrayIdx = levelTwo / (Constants.OBJECT_ID_LENGTH / 4)\n-\t\t\t\t\t\t\t* 4;\n-\t\t\t\t\tlong offset = NB.decodeUInt32(offset32[levelOne], arrayIdx);\n+\t\t\t\t\tint idx = levelTwo / (Constants.OBJECT_ID_LENGTH / 4) * 4;\n+\t\t\t\t\tlong offset = NB.decodeUInt32(offset32[levelOne], idx);\n \t\t\t\t\tif ((offset & IS_O64) != 0) {\n-\t\t\t\t\t\tarrayIdx = (8 * (int) (offset & ~IS_O64));\n-\t\t\t\t\t\toffset = NB.decodeUInt64(offset64, arrayIdx);\n+\t\t\t\t\t\tidx = (8 * (int) (offset & ~IS_O64));\n+\t\t\t\t\t\toffset = NB.decodeUInt64(offset64, idx);\n \t\t\t\t\t}\n-\t\t\t\t\tobjectId.setOffset(offset);\n+\t\t\t\t\tentry.offset = offset;\n \n \t\t\t\t\tlevelTwo += Constants.OBJECT_ID_LENGTH / 4;\n \t\t\t\t\treturnedNumber++;\n-\t\t\t\t\treturn objectId;\n-\t\t\t\t} else {\n-\t\t\t\t\tlevelTwo = 0;\n+\t\t\t\t\treturn entry;\n \t\t\t\t}\n+\t\t\t\tlevelTwo = 0;\n \t\t\t}\n \t\t\tthrow new NoSuchElementException();\n \t\t}\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98669","messageId":"1230171079-17156-18-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-17-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 17/23] Only do one getCachedBytes per whole object written","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:13Z","receivedAt":"2008-12-25T02:11:13Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Getting the size of an object may cause getCachedBytes to be invoked,\nand then have its result discarded. To save time we should make the\ncall to getCachedBytes first, hold onto the byte[], then obtain the\nsize off the byte[], and finally write from the byte[].\n\nSigned-off-by: Shawn O. Pearce \n---\n .../src/org/spearce/jgit/lib/PackWriter.java | 5 +++--\n 1 files changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\nindex a0823c7..bb889e8 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n@@ -710,10 +710,11 @@ private void writeWholeObject(final ObjectToPack otp) throws IOException {\n \t\t\totp.disposeLoader();\n \t\t} else {\n \t\t\tfinal ObjectLoader loader = db.openObject(windowCursor, otp);\n+\t\t\tfinal byte[] data = loader.getCachedBytes();\n \t\t\tfinal DeflaterOutputStream deflaterOut = new DeflaterOutputStream(\n \t\t\t\t\tout, deflater);\n-\t\t\twriteObjectHeader(otp.getType(), loader.getSize());\n-\t\t\tdeflaterOut.write(loader.getCachedBytes());\n+\t\t\twriteObjectHeader(otp.getType(), data.length);\n+\t\t\tdeflaterOut.write(data);\n \t\t\tdeflaterOut.finish();\n \t\t\tdeflater.reset();\n \t\t}\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98673","messageId":"1230171079-17156-19-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-18-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 18/23] Correctly use a long for the offsets within a generated pack","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:14Z","receivedAt":"2008-12-25T02:11:14Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Pack files can be larger than 2 GiB, especially if the PackIndexV2\nformat is being used.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../tst/org/spearce/jgit/lib/PackWriterTest.java | 12 ++++++------\n .../spearce/jgit/util/CountingOutputStream.java | 5 ++---\n 2 files changed, 8 insertions(+), 9 deletions(-)\n\ndiff --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\nindex ec138a0..98e0d3a 100644\n--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackWriterTest.java\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackWriterTest.java\n@@ -308,11 +308,11 @@ public void testWritePack4ThinPack() throws IOException {\n \t */\n \tpublic void testWritePack2SizeDeltasVsNoDeltas() throws Exception {\n \t\ttestWritePack2();\n-\t\tfinal int sizePack2NoDeltas = cos.getCount();\n+\t\tfinal long sizePack2NoDeltas = cos.getCount();\n \t\ttearDown();\n \t\tsetUp();\n \t\ttestWritePack2DeltasReuseRefs();\n-\t\tfinal int sizePack2DeltasRefs = cos.getCount();\n+\t\tfinal long sizePack2DeltasRefs = cos.getCount();\n \n \t\tassertTrue(sizePack2NoDeltas > sizePack2DeltasRefs);\n \t}\n@@ -327,11 +327,11 @@ public void testWritePack2SizeDeltasVsNoDeltas() throws Exception {\n \t */\n \tpublic void testWritePack2SizeOffsetsVsRefs() throws Exception {\n \t\ttestWritePack2DeltasReuseRefs();\n-\t\tfinal int sizePack2DeltasRefs = cos.getCount();\n+\t\tfinal long sizePack2DeltasRefs = cos.getCount();\n \t\ttearDown();\n \t\tsetUp();\n \t\ttestWritePack2DeltasReuseOffsets();\n-\t\tfinal int sizePack2DeltasOffsets = cos.getCount();\n+\t\tfinal long sizePack2DeltasOffsets = cos.getCount();\n \n \t\tassertTrue(sizePack2DeltasRefs > sizePack2DeltasOffsets);\n \t}\n@@ -345,11 +345,11 @@ public void testWritePack2SizeOffsetsVsRefs() throws Exception {\n \t */\n \tpublic void testWritePack4SizeThinVsNoThin() throws Exception {\n \t\ttestWritePack4();\n-\t\tfinal int sizePack4 = cos.getCount();\n+\t\tfinal long sizePack4 = cos.getCount();\n \t\ttearDown();\n \t\tsetUp();\n \t\ttestWritePack4ThinPack();\n-\t\tfinal int sizePack4Thin = cos.getCount();\n+\t\tfinal long sizePack4Thin = cos.getCount();\n \n \t\tassertTrue(sizePack4 > sizePack4Thin);\n \t}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/util/CountingOutputStream.java b/org.spearce.jgit/src/org/spearce/jgit/util/CountingOutputStream.java\nindex 53935dc..b0b5f7d 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/util/CountingOutputStream.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/util/CountingOutputStream.java\n@@ -45,8 +45,7 @@\n * Counting output stream decoration. Counts bytes written to stream.\n */\n public class CountingOutputStream extends FilterOutputStream {\n-\n-\tprivate int count;\n+\tprivate long count;\n \n \t/**\n \t * Create counting stream being decorated to provided real output stream.\n@@ -76,7 +75,7 @@ public void write(byte[] b, int off, int len) throws IOException {\n \t * @return number of written bytes since last reset (object is reset upon\n \t * creation)\n \t */\n-\tpublic int getCount() {\n+\tpublic long getCount() {\n \t\treturn count;\n \t}\n \n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98676","messageId":"1230171079-17156-20-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-19-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 19/23] Allow more direct access to determine isWritten","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:15Z","receivedAt":"2008-12-25T02:11:15Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"This gives the JVM a better chance to inline the isWritten method\nwhen writing a pack file out.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../src/org/spearce/jgit/lib/PackWriter.java | 2 +-\n .../spearce/jgit/transport/PackedObjectInfo.java | 2 +-\n 2 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\nindex bb889e8..50d06c2 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n@@ -932,7 +932,7 @@ boolean isDeltaRepresentation() {\n \t\t * @return true if object is already written; false otherwise.\n \t\t */\n \t\tboolean isWritten() {\n-\t\t\treturn getOffset() != 0;\n+\t\t\treturn offset != 0;\n \t\t}\n \n \t\tPackedObjectLoader getReuseLoader() {\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/PackedObjectInfo.java b/org.spearce.jgit/src/org/spearce/jgit/transport/PackedObjectInfo.java\nindex f37f421..045b795 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/transport/PackedObjectInfo.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/transport/PackedObjectInfo.java\n@@ -49,7 +49,7 @@\n * objects from the pack. This extension of ObjectId includes the offset.\n */\n public class PackedObjectInfo extends ObjectId {\n-\tprivate long offset;\n+\tprotected long offset;\n \n \tprivate int crc;\n \n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98671","messageId":"1230171079-17156-21-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-20-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 20/23] Move \"wantWrite\" field of ObjectToPack into the flags field","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:16Z","receivedAt":"2008-12-25T02:11:16Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"This reduces the ObjectToPack structure by 4 bytes, saving us 4 MB\non the linux kernel repository. Its only a single bit value, so\nkeeping it in a full boolean is rather wasteful given how many of\nthese objects we need in to pack a large project.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../src/org/spearce/jgit/lib/PackWriter.java | 23 ++++++++++++-------\n 1 files changed, 14 insertions(+), 9 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\nindex 50d06c2..3ef9154 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n@@ -859,11 +859,16 @@ public void addObject(final RevObject object)\n \n \t\tprivate PackedObjectLoader reuseLoader;\n \n-\t\t/** Low bits contain the objectType; higher bits the deltaDepth */\n+\t\t/**\n+\t\t * Bit field, from bit 0 to bit 31:\n+\t\t *

    \n+\t\t *
  • 1 bit: wantWrite
    • \n+\t\t *
  • 3 bits: type
    • \n+\t\t *
  • 28 bits: deltaDepth
    • \n+\t\t *
\n+\t\t */\n \t\tprivate int flags;\n \n-\t\tprivate boolean wantWrite;\n-\n \t\t/**\n \t\t * Construct object for specified object id.
By default object is\n \t\t * marked as not written and non-delta packed (as a whole object).\n@@ -875,7 +880,7 @@ public void addObject(final RevObject object)\n \t\t */\n \t\tObjectToPack(AnyObjectId src, final int type) {\n \t\t\tsuper(src);\n-\t\t\tflags |= type;\n+\t\t\tflags |= type << 1;\n \t\t}\n \n \t\t/**\n@@ -952,11 +957,11 @@ void disposeLoader() {\n \t\t}\n \n \t\tint getType() {\n-\t\t\treturn flags & 0x7;\n+\t\t\treturn (flags>>1) & 0x7;\n \t\t}\n \n \t\tint getDeltaDepth() {\n-\t\t\treturn flags >>> 3;\n+\t\t\treturn flags >>> 4;\n \t\t}\n \n \t\tvoid updateDeltaDepth() {\n@@ -967,15 +972,15 @@ else if (deltaBase != null)\n \t\t\t\td = 1;\n \t\t\telse\n \t\t\t\td = 0;\n-\t\t\tflags = (d << 3) | getType();\n+\t\t\tflags = (d << 4) | flags & 0x15;\n \t\t}\n \n \t\tboolean wantWrite() {\n-\t\t\treturn wantWrite;\n+\t\t\treturn (flags & 1) == 1;\n \t\t}\n \n \t\tvoid markWantWrite() {\n-\t\t\tthis.wantWrite = true;\n+\t\t\tflags |= 1;\n \t\t}\n \t}\n }\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98678","messageId":"1230171079-17156-22-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-21-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 21/23] Use an ArrayList for the reuseLoader collection in PackWriter","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:17Z","receivedAt":"2008-12-25T02:11:17Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Nulling out the elements of the array is quicker than deallocating\nLinkedList nodes and allocating new ones for the next use.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../src/org/spearce/jgit/lib/PackWriter.java | 4 +---\n 1 files changed, 1 insertions(+), 3 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\nindex 3ef9154..69b4294 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n@@ -46,7 +46,6 @@\n import java.util.Collection;\n import java.util.Collections;\n import java.util.Iterator;\n-import java.util.LinkedList;\n import java.util.List;\n import java.util.zip.Deflater;\n import java.util.zip.DeflaterOutputStream;\n@@ -577,8 +576,7 @@ public void writePack(OutputStream packStream) throws IOException {\n \n \tprivate void searchForReuse() throws IOException {\n \t\tinitMonitor.beginTask(SEARCHING_REUSE_PROGRESS, getObjectsNumber());\n-\t\tfinal Collection reuseLoaders = new LinkedList();\n-\n+\t\tfinal Collection reuseLoaders = new ArrayList();\n \t\tfor (List list : objectsLists) {\n \t\t\tfor (ObjectToPack otp : list) {\n \t\t\t\tif (initMonitor.isCancelled())\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98670","messageId":"1230171079-17156-23-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-22-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 22/23] Don't cut off existing delta chains if we are reusing deltas","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:18Z","receivedAt":"2008-12-25T02:11:18Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"The existing pack file may have chains longer than our current max\ndepth, such as if it is a historical pack and was generated with a\nmaximum chain depth >100. Cutting off the chains would create a\nbigger pack file that we need to transmit, and it costs a lot more\nCPU time to expand the delta object in order to recompress it whole,\nbecause we couldn't copy it directly from the pack file.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../src/org/spearce/jgit/lib/PackWriter.java | 6 ------\n 1 files changed, 0 insertions(+), 6 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\nindex 69b4294..4c01b6e 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n@@ -681,12 +681,6 @@ private void writeObject(final ObjectToPack otp) throws IOException {\n \t\t\t\t\twriteObject(deltaBase);\n \t\t\t\t}\n \t\t\t}\n-\n-\t\t\totp.updateDeltaDepth();\n-\t\t\tif (otp.getDeltaDepth() > maxDeltaDepth) {\n-\t\t\t\totp.clearDeltaBase();\n-\t\t\t\totp.disposeLoader();\n-\t\t\t}\n \t\t}\n \n \t\tassert !otp.isWritten();\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98666","messageId":"1230171079-17156-24-git-send-email-spearce@spearce.org","threadId":"16859","inReplyTo":"1230171079-17156-23-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 23/23] Correctly honor the thin parameter to PackWriter.writePack","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-25T02:11:19Z","receivedAt":"2008-12-25T02:11:19Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Signed-off-by: Shawn O. Pearce \n---\n .../src/org/spearce/jgit/lib/PackWriter.java | 5 +++--\n 1 files changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\nindex 4c01b6e..b2d0227 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n@@ -465,8 +465,9 @@ public void preparePack(\n \t\t\tfinal Collection uninterestingObjects,\n \t\t\tfinal boolean thin, final boolean ignoreMissingUninteresting)\n \t\t\tthrows IOException {\n+\t\tthis.thin = thin;\n \t\tObjectWalk walker = setUpWalker(interestingObjects,\n-\t\t\t\tuninterestingObjects, thin, ignoreMissingUninteresting);\n+\t\t\t\tuninterestingObjects, ignoreMissingUninteresting);\n \t\tfindObjectsToPack(walker);\n \t}\n \n@@ -759,7 +760,7 @@ private void writeChecksum() throws IOException {\n \tprivate ObjectWalk setUpWalker(\n \t\t\tfinal Collection interestingObjects,\n \t\t\tfinal Collection uninterestingObjects,\n-\t\t\tfinal boolean thin, final boolean ignoreMissingUninteresting)\n+\t\t\tfinal boolean ignoreMissingUninteresting)\n \t\t\tthrows MissingObjectException, IOException,\n \t\t\tIncorrectObjectTypeException {\n \t\tfinal ObjectWalk walker = new ObjectWalk(db);\n-- \n1.6.1.rc4.301.g5497a\n"},{"id":"98793","messageId":"200812271430.06052.robin.rosenberg.lists@dewire.com","threadId":"16859","inReplyTo":"1230171079-17156-12-git-send-email-spearce@spearce.org","subject":"Re: [JGIT PATCH 11/23] Rewrite WindowCache to use a hash table","fromName":"Robin Rosenberg","fromEmail":"robin.rosenberg.lists@dewire.com","sentAt":"2008-12-27T13:30:05Z","receivedAt":"2008-12-27T13:30:05Z","isPatch":true,"sender":{"key":"robin.rosenberg@dewire.com","avatar":"https://avatars.githubusercontent.com/u/46357?v=4"},"body":"torsdag 25 december 2008 03:11:07 skrev Shawn O. Pearce:\n> diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\n> index f617845..f478f04 100644\n> --- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\n> +++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\n> @@ -41,11 +41,7 @@\n> import java.io.IOException;\n> import java.lang.ref.ReferenceQueue;\n> \n> -/**\n> - * The WindowCache manages reusable Windows and inflaters used by\n> - * the other windowed file access classes.\n> - */\n> -public class WindowCache {\n> +class WindowCache {\n\nThis breaks the Eclipse plugin which want to call WindowCache.reconfigure. Package level\nclass can also have javadocs. Even though we do not require it, I still thinks it's a good idea. Not\nsure how useful that one was.\n\n-- robin\n"},{"id":"98797","messageId":"20081227173251.GB22075@spearce.org","threadId":"16859","inReplyTo":"200812271430.06052.robin.rosenberg.lists@dewire.com","subject":"[JGIT PATCH 11/23 v2] Rewrite WindowCache to use a hash table","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-12-27T17:32:51Z","receivedAt":"2008-12-27T17:32:51Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"This shaved 10s off my linux-2.6 \"jgit rev-list --objects\" test.\nWe're also getting slightly better cache hit ratios, approaching\n95% during commit access and 80% during tree access on the same\nrepository. Its a significant win.\n\nThe cache is also a bit better about memory usage. We now make\nsure the byte[] or ByteBuffer handle is cleared out of the soft\nreference when we push the reference into the queue manually. A\nsmall change, but it makes a marked difference with the overall\nJVM memory usage.\n\nSigned-off-by: Shawn O. Pearce \n---\n Robin Rosenberg wrote:\n > > -/**\n > > - * The WindowCache manages reusable Windows and inflaters used by\n > > - * the other windowed file access classes.\n > > - */\n > > -public class WindowCache {\n > > +class WindowCache {\n > \n > This breaks the Eclipse plugin which want to call WindowCache.reconfigure. Package level\n > class can also have javadocs. Even though we do not require it, I still thinks it's a good idea. Not\n > sure how useful that one was.\n\n Dammit, good catch. I was working on this in the context of only\n having the JGit code in my workspace, so I missed the impact on\n the Eclipse plugin, and possibly on the NetBeans one as well.\n\n Corrected patch follows.\n\n \n .../src/org/spearce/jgit/lib/ByteWindow.java | 10 +-\n .../src/org/spearce/jgit/lib/WindowCache.java | 317 ++++++++++++--------\n .../src/org/spearce/jgit/lib/WindowedFile.java | 2 +-\n 3 files changed, 198 insertions(+), 131 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java\nindex 1f6beb8..8d37de7 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ByteWindow.java\n@@ -56,14 +56,20 @@\n * type of object reference used to manage the window data.\n */\n abstract class ByteWindow extends SoftReference {\n+\tboolean sizeActive = true;\n+\n+\tByteWindow chainNext;\n+\n+\tByteWindow lruPrev;\n+\n+\tByteWindow lruNext;\n+\n \tfinal WindowedFile provider;\n \n \tfinal int id;\n \n \tfinal int size;\n \n-\tint lastAccessed;\n-\n \tfinal long start;\n \n \tfinal long end;\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\nindex f617845..e71ca73 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowCache.java\n@@ -1,5 +1,5 @@\n /*\n- * Copyright (C) 2007, Robin Rosenberg \n+ * Copyright (C) 2008, Google Inc.\n * Copyright (C) 2008, Shawn O. Pearce \n *\n * All rights reserved.\n@@ -68,23 +68,51 @@ private static final int bits(int newSize) {\n \n \tstatic final ReferenceQueue clearedWindowQueue;\n \n-\tprivate static ByteWindow[] windows;\n+\tprivate static ByteWindow[] cache;\n \n-\tprivate static int openWindowCount;\n+\tprivate static ByteWindow lruHead;\n+\n+\tprivate static ByteWindow lruTail;\n \n \tprivate static int openByteCount;\n \n-\tprivate static int accessClock;\n+\tprivate static int hits;\n+\n+\tprivate static int reqs;\n+\n+\tprivate static int opens;\n+\n+\tprivate static int closes;\n \n \tstatic {\n \t\tmaxByteCount = 10 * MB;\n \t\twindowSizeShift = bits(8 * KB);\n \t\twindowSize = 1 << windowSizeShift;\n \t\tmmap = false;\n-\t\twindows = new ByteWindow[maxByteCount / windowSize];\n+\t\tcache = new ByteWindow[cacheTableSize()];\n \t\tclearedWindowQueue = new ReferenceQueue();\n \t}\n \n+\tstatic synchronized String statString() {\n+\t\tint maxChain = 0, tot = 0;\n+\t\tfor (ByteWindow e : cache) {\n+\t\t\tint n = 0;\n+\t\t\tfor (; e != null; e = e.chainNext) {\n+\t\t\t\tn++;\n+\t\t\t\ttot++;\n+\t\t\t}\n+\t\t\tmaxChain = Math.max(maxChain, n);\n+\t\t}\n+\t\treturn \"WindowCache[ hits: \" + (hits * 100 / reqs) + \"%\"\n+\t\t\t\t+ \"; windows: \" + tot + \" maxChain: \" + maxChain + \"; kb:\"\n+\t\t\t\t+ (openByteCount / KB) + \"; cache: \" + cache.length + \" fds: \"\n+\t\t\t\t+ (opens - closes) + \",\" + opens + \",\" + closes + \" ]\";\n+\t}\n+\n+\tprivate static int cacheTableSize() {\n+\t\treturn 5 * (maxByteCount / windowSize) / 2;\n+\t}\n+\n \t/**\n \t * Modify the configuration of the window cache.\n \t *

\n@@ -135,27 +163,36 @@ private static synchronized void reconfigureImpl(final int packedGitLimit,\n \t\t\t// We have to throw away every window we have. None\n \t\t\t// of them are suitable for the new configuration.\n \t\t\t//\n-\t\t\tfor (int i = 0; i < openWindowCount; i++) {\n-\t\t\t\tfinal ByteWindow win = windows[i];\n-\t\t\t\tif (--win.provider.openCount == 0)\n-\t\t\t\t\twin.provider.cacheClose();\n-\t\t\t\twindows[i] = null;\n+\t\t\tfor (ByteWindow e : cache) {\n+\t\t\t\tfor (; e != null; e = e.chainNext)\n+\t\t\t\t\tclear(e);\n+\t\t\t}\n+\t\t\trunClearedWindowQueue();\n+\t\t\tcache = new ByteWindow[cacheTableSize()];\n+\n+\t\t} else {\n+\t\t\tif (prune) {\n+\t\t\t\t// We should decrease our memory usage.\n+\t\t\t\t//\n+\t\t\t\treleaseMemory();\n+\t\t\t\trunClearedWindowQueue();\n \t\t\t}\n-\t\t\twindows = new ByteWindow[maxByteCount / windowSize];\n-\t\t\topenWindowCount = 0;\n-\t\t\topenByteCount = 0;\n-\t\t} else if (prune) {\n-\t\t\t// Our memory limit was decreased so we should try\n-\t\t\t// to drop windows to ensure we meet the new lower\n-\t\t\t// limit we were just given.\n-\t\t\t//\n-\t\t\tfinal int wincnt = maxByteCount / windowSize;\n-\t\t\treleaseMemory(wincnt, null, 0, 0);\n \n-\t\t\tif (wincnt != windows.length) {\n-\t\t\t\tfinal ByteWindow[] n = new ByteWindow[wincnt];\n-\t\t\t\tSystem.arraycopy(windows, 0, n, 0, openWindowCount);\n-\t\t\t\twindows = n;\n+\t\t\tif (cache.length != cacheTableSize()) {\n+\t\t\t\t// The cache table should be resized.\n+\t\t\t\t// Rehash every entry.\n+\t\t\t\t//\n+\t\t\t\tfinal ByteWindow[] priorTable = cache;\n+\n+\t\t\t\tcache = new ByteWindow[cacheTableSize()];\n+\t\t\t\tfor (ByteWindow e : priorTable) {\n+\t\t\t\t\tfor (ByteWindow n; e != null; e = n) {\n+\t\t\t\t\t\tn = e.chainNext;\n+\t\t\t\t\t\tfinal int idx = hash(e.provider, e.id);\n+\t\t\t\t\t\te.chainNext = cache[idx];\n+\t\t\t\t\t\tcache[idx] = e;\n+\t\t\t\t\t}\n+\t\t\t\t}\n \t\t\t}\n \t\t}\n \t}\n@@ -178,19 +215,27 @@ private static synchronized void reconfigureImpl(final int packedGitLimit,\n \t */\n \tpublic static synchronized final void get(final WindowCursor curs,\n \t\t\tfinal WindowedFile wp, final long position) throws IOException {\n+\t\treqs++;\n \t\tfinal int id = (int) (position >> windowSizeShift);\n-\t\tint idx = binarySearch(wp, id);\n-\t\tif (0 <= idx) {\n-\t\t\tfinal ByteWindow w = windows[idx];\n-\t\t\tif ((curs.handle = w.get()) != null) {\n-\t\t\t\tw.lastAccessed = ++accessClock;\n-\t\t\t\tcurs.window = w;\n-\t\t\t\treturn;\n+\t\tfinal int idx = hash(wp, id);\n+\t\tfor (ByteWindow e = cache[idx]; e != null; e = e.chainNext) {\n+\t\t\tif (e.provider == wp && e.id == id) {\n+\t\t\t\tif ((curs.handle = e.get()) != null) {\n+\t\t\t\t\tcurs.window = e;\n+\t\t\t\t\tmakeMostRecent(e);\n+\t\t\t\t\thits++;\n+\t\t\t\t\treturn;\n+\t\t\t\t}\n+\n+\t\t\t\tclear(e);\n+\t\t\t\tbreak;\n \t\t\t}\n \t\t}\n \n-\t\tif (++wp.openCount == 1) {\n+\t\tif (wp.openCount == 0) {\n \t\t\ttry {\n+\t\t\t\topens++;\n+\t\t\t\twp.openCount = 1;\n \t\t\t\twp.cacheOpen();\n \t\t\t} catch (IOException ioe) {\n \t\t\t\twp.openCount = 0;\n@@ -201,106 +246,55 @@ public static synchronized final void get(final WindowCursor curs,\n \t\t\t} catch (Error ioe) {\n \t\t\t\twp.openCount = 0;\n \t\t\t\tthrow ioe;\n+\t\t\t} finally {\n+\t\t\t\twp.openCount--;\n \t\t\t}\n \n \t\t\t// The cacheOpen may have mapped the window we are trying to\n \t\t\t// map ourselves. Retrying the search ensures that does not\n \t\t\t// happen to us.\n \t\t\t//\n-\t\t\tidx = binarySearch(wp, id);\n-\t\t\tif (0 <= idx) {\n-\t\t\t\tfinal ByteWindow w = windows[idx];\n-\t\t\t\tif ((curs.handle = w.get()) != null) {\n-\t\t\t\t\tw.lastAccessed = ++accessClock;\n-\t\t\t\t\tcurs.window = w;\n-\t\t\t\t\treturn;\n+\t\t\tfor (ByteWindow e = cache[idx]; e != null; e = e.chainNext) {\n+\t\t\t\tif (e.provider == wp && e.id == id) {\n+\t\t\t\t\tif ((curs.handle = e.get()) != null) {\n+\t\t\t\t\t\tcurs.window = e;\n+\t\t\t\t\t\tmakeMostRecent(e);\n+\t\t\t\t\t\treturn;\n+\t\t\t\t\t}\n+\n+\t\t\t\t\tclear(e);\n+\t\t\t\t\tbreak;\n \t\t\t\t}\n \t\t\t}\n \t\t}\n \n-\t\tidx = -(idx + 1);\n-\t\tfinal int wSz = windowSize(wp, id);\n-\t\tidx = releaseMemory(windows.length, wp, idx, wSz);\n-\n-\t\tif (idx < 0)\n-\t\t\tidx = 0;\n-\t\tfinal int toMove = openWindowCount - idx;\n-\t\tif (toMove > 0)\n-\t\t\tSystem.arraycopy(windows, idx, windows, idx + 1, toMove);\n-\t\twp.loadWindow(curs, id, id << windowSizeShift, wSz);\n-\t\twindows[idx] = curs.window;\n-\t\topenWindowCount++;\n-\t\topenByteCount += curs.window.size;\n+\t\tfinal int wsz = windowSize(wp, id);\n+\t\twp.openCount++;\n+\t\topenByteCount += wsz;\n+\t\treleaseMemory();\n+\t\trunClearedWindowQueue();\n+\n+\t\twp.loadWindow(curs, id, id << windowSizeShift, wsz);\n+\t\tfinal ByteWindow e = curs.window;\n+\t\te.chainNext = cache[idx];\n+\t\tcache[idx] = e;\n+\t\tinsertLRU(e);\n \t}\n \n-\tprivate static int releaseMemory(final int maxWindowCount,\n-\t\t\tfinal WindowedFile willRead, int insertionIndex, final int willAdd) {\n-\t\tfor (;;) {\n-\t\t\tfinal ByteWindow w = (ByteWindow) clearedWindowQueue.poll();\n-\t\t\tif (w == null)\n-\t\t\t\tbreak;\n-\t\t\tfinal int oldest = binarySearch(w.provider, w.id);\n-\t\t\tif (oldest < 0 || windows[oldest] != w)\n-\t\t\t\tcontinue; // Must have been evicted by our other controls.\n-\n-\t\t\tfinal WindowedFile p = w.provider;\n-\t\t\tif (--p.openCount == 0 && p != willRead)\n-\t\t\t\tp.cacheClose();\n-\n-\t\t\topenByteCount -= w.size;\n-\t\t\tfinal int toMove = openWindowCount - oldest - 1;\n-\t\t\tif (toMove > 0)\n-\t\t\t\tSystem.arraycopy(windows, oldest + 1, windows, oldest, toMove);\n-\t\t\twindows[--openWindowCount] = null;\n-\t\t\tif (oldest < insertionIndex)\n-\t\t\t\tinsertionIndex--;\n-\t\t}\n-\n-\t\twhile (openWindowCount >= maxWindowCount\n-\t\t\t\t|| (openWindowCount > 0 && openByteCount + willAdd > maxByteCount)) {\n-\t\t\tint oldest = 0;\n-\t\t\tfor (int k = openWindowCount - 1; k > 0; k--) {\n-\t\t\t\tif (windows[k].lastAccessed < windows[oldest].lastAccessed)\n-\t\t\t\t\toldest = k;\n-\t\t\t}\n-\n-\t\t\tfinal ByteWindow w = windows[oldest];\n-\t\t\tfinal WindowedFile p = w.provider;\n-\t\t\tif (--p.openCount == 0 && p != willRead)\n-\t\t\t\tp.cacheClose();\n-\n-\t\t\topenByteCount -= w.size;\n-\t\t\tfinal int toMove = openWindowCount - oldest - 1;\n-\t\t\tif (toMove > 0)\n-\t\t\t\tSystem.arraycopy(windows, oldest + 1, windows, oldest, toMove);\n-\t\t\twindows[--openWindowCount] = null;\n-\t\t\tw.enqueue();\n-\t\t\tif (oldest < insertionIndex)\n-\t\t\t\tinsertionIndex--;\n+\tprivate static void makeMostRecent(ByteWindow e) {\n+\t\tif (lruHead != e) {\n+\t\t\tunlinkLRU(e);\n+\t\t\tinsertLRU(e);\n \t\t}\n-\n-\t\treturn insertionIndex;\n \t}\n \n-\tprivate static final int binarySearch(final WindowedFile sprov,\n-\t\t\tfinal int sid) {\n-\t\tif (openWindowCount == 0)\n-\t\t\treturn -1;\n-\t\tfinal int shc = sprov.hash;\n-\t\tint high = openWindowCount;\n-\t\tint low = 0;\n-\t\tdo {\n-\t\t\tfinal int mid = (low + high) / 2;\n-\t\t\tfinal ByteWindow mw = windows[mid];\n-\t\t\tif (mw.provider == sprov && mw.id == sid)\n-\t\t\t\treturn mid;\n-\t\t\tfinal int mhc = mw.provider.hash;\n-\t\t\tif (mhc < shc || (shc == mhc && mw.id < sid))\n-\t\t\t\tlow = mid + 1;\n-\t\t\telse\n-\t\t\t\thigh = mid;\n-\t\t} while (low < high);\n-\t\treturn -(low + 1);\n+\tprivate static void releaseMemory() {\n+\t\tByteWindow e = lruTail;\n+\t\twhile (openByteCount > maxByteCount && e != null) {\n+\t\t\tfinal ByteWindow p = e.lruPrev;\n+\t\t\tclear(e);\n+\t\t\te = p;\n+\t\t}\n \t}\n \n \t/**\n@@ -316,22 +310,89 @@ private static final int binarySearch(final WindowedFile sprov,\n \t * cache.\n \t */\n \tpublic static synchronized final void purge(final WindowedFile wp) {\n-\t\tint d = 0;\n-\t\tfor (int s = 0; s < openWindowCount; s++) {\n-\t\t\tfinal ByteWindow win = windows[s];\n-\t\t\tif (win.provider != wp)\n-\t\t\t\twindows[d++] = win;\n-\t\t\telse\n-\t\t\t\topenByteCount -= win.size;\n+\t\tfor (ByteWindow e : cache) {\n+\t\t\tfor (; e != null; e = e.chainNext) {\n+\t\t\t\tif (e.provider == wp)\n+\t\t\t\t\tclear(e);\n+\t\t\t}\n+\t\t}\n+\t\trunClearedWindowQueue();\n+\t}\n+\n+\tprivate static void runClearedWindowQueue() {\n+\t\tByteWindow e;\n+\t\twhile ((e = (ByteWindow) clearedWindowQueue.poll()) != null) {\n+\t\t\tunlinkSize(e);\n+\t\t\tunlinkLRU(e);\n+\t\t\tunlinkCache(e);\n+\t\t\te.chainNext = null;\n+\t\t\te.lruNext = null;\n+\t\t\te.lruPrev = null;\n \t\t}\n-\t\topenWindowCount = d;\n+\t}\n+\n+\tprivate static void clear(final ByteWindow e) {\n+\t\tunlinkSize(e);\n+\t\te.clear();\n+\t\te.enqueue();\n+\t}\n \n-\t\tif (wp.openCount > 0) {\n-\t\t\twp.openCount = 0;\n-\t\t\twp.cacheClose();\n+\tprivate static void unlinkSize(final ByteWindow e) {\n+\t\tif (e.sizeActive) {\n+\t\t\tif (--e.provider.openCount == 0) {\n+\t\t\t\tcloses++;\n+\t\t\t\te.provider.cacheClose();\n+\t\t\t}\n+\t\t\topenByteCount -= e.size;\n+\t\t\te.sizeActive = false;\n \t\t}\n \t}\n \n+\tprivate static void unlinkCache(final ByteWindow dead) {\n+\t\tfinal int idx = hash(dead.provider, dead.id);\n+\t\tByteWindow e = cache[idx], p = null, n;\n+\t\tfor (; e != null; p = e, e = n) {\n+\t\t\tn = e.chainNext;\n+\t\t\tif (e == dead) {\n+\t\t\t\tif (p == null)\n+\t\t\t\t\tcache[idx] = n;\n+\t\t\t\telse\n+\t\t\t\t\tp.chainNext = n;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tprivate static void unlinkLRU(final ByteWindow e) {\n+\t\tfinal ByteWindow prev = e.lruPrev;\n+\t\tfinal ByteWindow next = e.lruNext;\n+\n+\t\tif (prev != null)\n+\t\t\tprev.lruNext = next;\n+\t\telse\n+\t\t\tlruHead = next;\n+\n+\t\tif (next != null)\n+\t\t\tnext.lruPrev = prev;\n+\t\telse\n+\t\t\tlruTail = prev;\n+\t}\n+\n+\tprivate static void insertLRU(final ByteWindow e) {\n+\t\tfinal ByteWindow h = lruHead;\n+\t\te.lruPrev = null;\n+\t\te.lruNext = h;\n+\t\tif (h != null)\n+\t\t\th.lruPrev = e;\n+\t\telse\n+\t\t\tlruTail = e;\n+\t\tlruHead = e;\n+\t}\n+\n+\tprivate static int hash(final WindowedFile wp, final int id) {\n+\t\treturn ((wp.hash + id) >>> 1) % cache.length;\n+\t}\n+\n \tprivate static int windowSize(final WindowedFile file, final int id) {\n \t\tfinal long len = file.length();\n \t\tfinal long pos = id << windowSizeShift;\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\nindex dd94f24..9c5cf1e 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\n@@ -88,7 +88,7 @@\n \t */\n \tpublic WindowedFile(final File file) {\n \t\tfPath = file;\n-\t\thash = System.identityHashCode(this);\n+\t\thash = System.identityHashCode(this) * 31;\n \t\tlength = Long.MAX_VALUE;\n \t}\n \n-- \n1.6.1.302.gccd4d\n"}]}