From b16aa00a9ef8c3f6bfcdc514a85e99ba096efd77 Mon Sep 17 00:00:00 2001 From: "Shawn O. Pearce" Date: Wed, 29 Apr 2009 11:54:41 -0700 Subject: [PATCH] Replace inefficient new Long(long) constructor to silence FindBugs FindBugs keeps warning us that new Long(long) is inefficient because it doesn't permit using cached values in the -128..127 range. We now use a custom Map implementation which supports primitive long as the hash key, rather than requiring boxing for java.util.HashMap. This removes the issue FindBugs was identifying. This version performs slightly better than before. index-pack on linux-2.6: parent commit: 2m58.611s this commit : 2m57.068s Signed-off-by: Shawn O. Pearce CC: Yann Simon CC: Matthias Sohn Signed-off-by: Robin Rosenberg --- .../org/spearce/jgit/transport/LongMapTest.java | 132 ++++++++++++++++++ .../src/org/spearce/jgit/transport/IndexPack.java | 12 +- .../src/org/spearce/jgit/transport/LongMap.java | 152 +++++++++++++++++++++ 3 files changed, 289 insertions(+), 7 deletions(-) create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/transport/LongMapTest.java create mode 100644 org.spearce.jgit/src/org/spearce/jgit/transport/LongMap.java diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/transport/LongMapTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/transport/LongMapTest.java new file mode 100644 index 00000000..c59fd1f4 --- /dev/null +++ b/org.spearce.jgit.test/tst/org/spearce/jgit/transport/LongMapTest.java @@ -0,0 +1,132 @@ +/* + * Copyright (C) 2009, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.transport; + +import junit.framework.TestCase; + +public class LongMapTest extends TestCase { + private LongMap map; + + protected void setUp() throws Exception { + super.setUp(); + map = new LongMap(); + } + + public void testEmptyMap() { + assertFalse(map.containsKey(0)); + assertFalse(map.containsKey(1)); + + assertNull(map.get(0)); + assertNull(map.get(1)); + + assertNull(map.remove(0)); + assertNull(map.remove(1)); + } + + public void testInsertMinValue() { + final Long min = Long.valueOf(Long.MIN_VALUE); + assertNull(map.put(Long.MIN_VALUE, min)); + assertTrue(map.containsKey(Long.MIN_VALUE)); + assertSame(min, map.get(Long.MIN_VALUE)); + assertFalse(map.containsKey(Integer.MIN_VALUE)); + } + + public void testReplaceMaxValue() { + final Long min = Long.valueOf(Long.MAX_VALUE); + final Long one = Long.valueOf(1); + assertNull(map.put(Long.MAX_VALUE, min)); + assertSame(min, map.get(Long.MAX_VALUE)); + assertSame(min, map.put(Long.MAX_VALUE, one)); + assertSame(one, map.get(Long.MAX_VALUE)); + } + + public void testRemoveOne() { + final long start = 1; + assertNull(map.put(start, Long.valueOf(start))); + assertEquals(Long.valueOf(start), map.remove(start)); + assertFalse(map.containsKey(start)); + } + + public void testRemoveCollision1() { + // This test relies upon the fact that we always >>> 1 the value + // to derive an unsigned hash code. Thus, 0 and 1 fall into the + // same hash bucket. Further it relies on the fact that we add + // the 2nd put at the top of the chain, so removing the 1st will + // cause a different code path. + // + assertNull(map.put(0, Long.valueOf(0))); + assertNull(map.put(1, Long.valueOf(1))); + assertEquals(Long.valueOf(0), map.remove(0)); + + assertFalse(map.containsKey(0)); + assertTrue(map.containsKey(1)); + } + + public void testRemoveCollision2() { + // This test relies upon the fact that we always >>> 1 the value + // to derive an unsigned hash code. Thus, 0 and 1 fall into the + // same hash bucket. Further it relies on the fact that we add + // the 2nd put at the top of the chain, so removing the 2nd will + // cause a different code path. + // + assertNull(map.put(0, Long.valueOf(0))); + assertNull(map.put(1, Long.valueOf(1))); + assertEquals(Long.valueOf(1), map.remove(1)); + + assertTrue(map.containsKey(0)); + assertFalse(map.containsKey(1)); + } + + public void testSmallMap() { + final long start = 12; + final long n = 8; + for (long i = start; i < start + n; i++) + assertNull(map.put(i, Long.valueOf(i))); + for (long i = start; i < start + n; i++) + assertEquals(Long.valueOf(i), map.get(i)); + } + + public void testLargeMap() { + final long start = Integer.MAX_VALUE; + final long n = 100000; + for (long i = start; i < start + n; i++) + assertNull(map.put(i, Long.valueOf(i))); + for (long i = start; i < start + n; i++) + assertEquals(Long.valueOf(i), map.get(i)); + } +} diff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java b/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java index e0e48556..59fdeaef 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java +++ b/org.spearce.jgit/src/org/spearce/jgit/transport/IndexPack.java @@ -47,7 +47,6 @@ import java.io.RandomAccessFile; import java.security.MessageDigest; import java.util.ArrayList; import java.util.Arrays; -import java.util.HashMap; import java.util.List; import java.util.zip.CRC32; import java.util.zip.DataFormatException; @@ -163,7 +162,7 @@ public class IndexPack { private ObjectIdMap> baseById; - private HashMap> baseByPos; + private LongMap> baseByPos; private byte[] objectData; @@ -303,7 +302,7 @@ public class IndexPack { entries = new PackedObjectInfo[(int) objectCount]; baseById = new ObjectIdMap>(); - baseByPos = new HashMap>(); + baseByPos = new LongMap>(); progress.beginTask(PROGRESS_DOWNLOAD, (int) objectCount); for (int done = 0; done < objectCount; done++) { @@ -382,8 +381,7 @@ public class IndexPack { private void resolveDeltas(final PackedObjectInfo oe) throws IOException { final int oldCRC = oe.getCRC(); - if (baseById.containsKey(oe) - || baseByPos.containsKey(new Long(oe.getOffset()))) + if (baseById.containsKey(oe) || baseByPos.containsKey(oe.getOffset())) resolveDeltas(oe.getOffset(), oldCRC, Constants.OBJ_BAD, null, oe); } @@ -448,7 +446,7 @@ public class IndexPack { private void resolveChildDeltas(final long pos, int type, byte[] data, PackedObjectInfo oe) throws IOException { final ArrayList a = baseById.remove(oe); - final ArrayList b = baseByPos.remove(new Long(pos)); + final ArrayList b = baseByPos.remove(pos); int ai = 0, bi = 0; if (a != null && b != null) { while (ai < a.size() && bi < b.size()) { @@ -679,7 +677,7 @@ public class IndexPack { ofs <<= 7; ofs += (c & 127); } - final Long base = new Long(pos - ofs); + final long base = pos - ofs; ArrayList r = baseByPos.get(base); if (r == null) { r = new ArrayList(8); diff --git a/org.spearce.jgit/src/org/spearce/jgit/transport/LongMap.java b/org.spearce.jgit/src/org/spearce/jgit/transport/LongMap.java new file mode 100644 index 00000000..ac41f56a --- /dev/null +++ b/org.spearce.jgit/src/org/spearce/jgit/transport/LongMap.java @@ -0,0 +1,152 @@ +/* + * Copyright (C) 2009, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.transport; + +/** + * Simple Map helper for {@link IndexPack}. + * + * @param + * type of the value instance. + */ +final class LongMap { + private static final float LOAD_FACTOR = 0.75f; + + private Node[] table; + + /** Number of entries currently in the map. */ + private int size; + + /** Next {@link #size} to trigger a {@link #grow()}. */ + private int growAt; + + LongMap() { + table = createArray(64); + growAt = (int) (table.length * LOAD_FACTOR); + } + + boolean containsKey(final long key) { + return get(key) != null; + } + + V get(final long key) { + for (Node n = table[index(key)]; n != null; n = n.next) { + if (n.key == key) + return n.value; + } + return null; + } + + V remove(final long key) { + Node n = table[index(key)]; + Node prior = null; + while (n != null) { + if (n.key == key) { + if (prior == null) + table[index(key)] = n.next; + else + prior.next = n.next; + size--; + return n.value; + } + prior = n; + n = n.next; + } + return null; + } + + V put(final long key, final V value) { + for (Node n = table[index(key)]; n != null; n = n.next) { + if (n.key == key) { + final V o = n.value; + n.value = value; + return o; + } + } + + if (++size == growAt) + grow(); + insert(new Node(key, value)); + return null; + } + + private void insert(final Node n) { + final int idx = index(n.key); + n.next = table[idx]; + table[idx] = n; + } + + private void grow() { + final Node[] oldTable = table; + final int oldSize = table.length; + + table = createArray(oldSize << 1); + growAt = (int) (table.length * LOAD_FACTOR); + for (int i = 0; i < oldSize; i++) { + Node e = oldTable[i]; + while (e != null) { + final Node n = e.next; + insert(e); + e = n; + } + } + } + + private final int index(final long key) { + int h = ((int) key) >>> 1; + h ^= (h >>> 20) ^ (h >>> 12); + return h & (table.length - 1); + } + + @SuppressWarnings("unchecked") + private static final Node[] createArray(final int sz) { + return new Node[sz]; + } + + private static class Node { + final long key; + + V value; + + Node next; + + Node(final long k, final V v) { + key = k; + value = v; + } + } +} -- 2.11.4.GIT