Avoid TemporaryBuffer.Heap on very small deltas

TemporaryBuffer is great when the output size is not known, but must
be bound by a relatively large upper limit that fits in memory, e.g.
64 KiB or 20 MiB.  The buffer gracefully supports growing storage by
allocating 8 KiB blocks and storing them in an ArrayList.

In a Git repository many deltas are less than 8 KiB.  Typical tree
objects are well below this threshold, and their deltas must be
encoded even smaller.

For these much smaller cases avoid the 8 KiB minimum allocation used
by TemporaryBuffer.  Instead allocate a very small OutputStream
writing to an array that is sized at the limit.

Change-Id: Ie25c6d3a8cf4604e0f8cd9a3b5b701a592d6ffca

1 files changed, 60 insertions, 25 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/DeltaWindow.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/DeltaWindow.java
index 144b9bdb45..66871bb145 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/DeltaWindow.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/pack/DeltaWindow.java
@@ -83,11 +83,10 @@ final class DeltaWindow {
 	/** Window entry of the object we are currently considering. */
 	private DeltaWindowEntry res;
 
-	/** If we have a delta for {@link #res}, this is the shortest found yet. */
-	private TemporaryBuffer.Heap bestDelta;
-
-	/** If we have {@link #bestDelta}, the window entry it was created from. */
+	/** If we have chosen a base, the window entry it was created from. */
 	private DeltaWindowEntry bestBase;
+	private int deltaLen;
+	private Object deltaBuf;
 
 	/** Used to compress cached deltas. */
 	private Deflater deflater;
@@ -207,7 +206,7 @@ final class DeltaWindow {
 			if (delta(src) /* == NEXT_SRC */)
 				continue;
 			bestBase = null;
-			bestDelta = null;
+			deltaBuf = null;
 			return;
 		}
 
@@ -249,7 +248,7 @@ final class DeltaWindow {
 		}
 
 		bestBase = null;
-		bestDelta = null;
+		deltaBuf = null;
 	}
 
 	private boolean delta(final DeltaWindowEntry src)
@@ -293,17 +292,31 @@ final class DeltaWindow {
 		}
 
 		try {
-			TemporaryBuffer.Heap delta = new TemporaryBuffer.Heap(msz);
-			if (srcIndex.encode(delta, resBuf, msz)) {
-				bestBase = src;
-				bestDelta = delta;
-			}
+			OutputStream delta = msz <= (8 << 10)
+				? new ArrayStream(msz)
+				: new TemporaryBuffer.Heap(msz);
+			if (srcIndex.encode(delta, resBuf, msz))
+				selectDeltaBase(src, delta);
 		} catch (IOException deltaTooBig) {
 			// Unlikely, encoder should see limit and return false.
 		}
 		return NEXT_SRC;
 	}
 
+	private void selectDeltaBase(DeltaWindowEntry src, OutputStream delta) {
+		bestBase = src;
+
+		if (delta instanceof ArrayStream) {
+			ArrayStream a = (ArrayStream) delta;
+			deltaBuf = a.buf;
+			deltaLen = a.cnt;
+		} else {
+			TemporaryBuffer.Heap b = (TemporaryBuffer.Heap) delta;
+			deltaBuf = b;
+			deltaLen = (int) b.length();
+		}
+	}
+
 	private int deltaSizeLimit(DeltaWindowEntry src) {
 		if (bestBase == null) {
 			// Any delta should be no more than 50% of the original size
@@ -319,7 +332,7 @@ final class DeltaWindow {
 		// With a delta base chosen any new delta must be "better".
 		// Retain the distribution described above.
 		int d = bestBase.depth();
-		int n = (int) bestDelta.length();
+		int n = deltaLen;
 
 		// If src is whole (depth=0) and base is near limit (depth=9/10)
 		// any delta using src can be 10x larger and still be better.
@@ -330,25 +343,23 @@ final class DeltaWindow {
 	}
 
 	private void cacheDelta(ObjectToPack srcObj, ObjectToPack resObj) {
-		if (Integer.MAX_VALUE < bestDelta.length())
-			return;
-
-		int rawsz = (int) bestDelta.length();
-		if (deltaCache.canCache(rawsz, srcObj, resObj)) {
+		if (deltaCache.canCache(deltaLen, srcObj, resObj)) {
 			try {
-				byte[] zbuf = new byte[deflateBound(rawsz)];
-
+				byte[] zbuf = new byte[deflateBound(deltaLen)];
 				ZipStream zs = new ZipStream(deflater(), zbuf);
-				bestDelta.writeTo(zs, null);
-				bestDelta = null;
+				if (deltaBuf instanceof byte[])
+					zs.write((byte[]) deltaBuf, 0, deltaLen);
+				else
+					((TemporaryBuffer.Heap) deltaBuf).writeTo(zs, null);
+				deltaBuf = null;
 				int len = zs.finish();
 
-				resObj.setCachedDelta(deltaCache.cache(zbuf, len, rawsz));
-				resObj.setCachedSize(rawsz);
+				resObj.setCachedDelta(deltaCache.cache(zbuf, len, deltaLen));
+				resObj.setCachedSize(deltaLen);
 			} catch (IOException err) {
-				deltaCache.credit(rawsz);
+				deltaCache.credit(deltaLen);
 			} catch (OutOfMemoryError err) {
-				deltaCache.credit(rawsz);
+				deltaCache.credit(deltaLen);
 			}
 		}
 	}
@@ -468,4 +479,28 @@ final class DeltaWindow {
 			throw new UnsupportedOperationException();
 		}
 	}
+
+	static final class ArrayStream extends OutputStream {
+		final byte[] buf;
+		int cnt;
+
+		ArrayStream(int max) {
+			buf = new byte[max];
+		}
+
+		@Override
+		public void write(int b) throws IOException {
+			if (cnt == buf.length)
+				throw new IOException();
+			buf[cnt++] = (byte) b;
+		}
+
+		@Override
+		public void write(byte[] b, int off, int len) throws IOException {
+			if (len > buf.length - cnt)
+				throw new IOException();
+			System.arraycopy(b, off, buf, cnt, len);
+			cnt += len;
+		}
+	}
 }