harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From sjanu...@apache.org
Subject svn commit: r671920 - in /harmony/enhanced/classlib/trunk/modules/pack200/src: main/java/org/apache/harmony/unpack200/ main/java/org/apache/harmony/unpack200/bytecode/ test/java/org/apache/harmony/unpack200/tests/
Date Thu, 26 Jun 2008 15:21:14 GMT
Author: sjanuary
Date: Thu Jun 26 08:21:14 2008
New Revision: 671920

URL: http://svn.apache.org/viewvc?rev=671920&view=rev
Log:
Apply patch for HARMONY-5882 ([classlib][pack200] Performance improvements for pack200)

Added:
    harmony/enhanced/classlib/trunk/modules/pack200/src/main/java/org/apache/harmony/unpack200/SegmentConstantPoolArrayCache.java
  (with props)
    harmony/enhanced/classlib/trunk/modules/pack200/src/test/java/org/apache/harmony/unpack200/tests/SegmentConstantPoolArrayCacheTest.java
  (with props)
Modified:
    harmony/enhanced/classlib/trunk/modules/pack200/src/main/java/org/apache/harmony/unpack200/SegmentConstantPool.java
    harmony/enhanced/classlib/trunk/modules/pack200/src/main/java/org/apache/harmony/unpack200/bytecode/CPUTF8.java

Modified: harmony/enhanced/classlib/trunk/modules/pack200/src/main/java/org/apache/harmony/unpack200/SegmentConstantPool.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/pack200/src/main/java/org/apache/harmony/unpack200/SegmentConstantPool.java?rev=671920&r1=671919&r2=671920&view=diff
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/pack200/src/main/java/org/apache/harmony/unpack200/SegmentConstantPool.java
(original)
+++ harmony/enhanced/classlib/trunk/modules/pack200/src/main/java/org/apache/harmony/unpack200/SegmentConstantPool.java
Thu Jun 26 08:21:14 2008
@@ -20,6 +20,7 @@
 import org.apache.harmony.unpack200.bytecode.ClassConstantPool;
 import org.apache.harmony.unpack200.bytecode.ClassFileEntry;
 import org.apache.harmony.unpack200.bytecode.ConstantPoolEntry;
+import java.util.List;
 
 /**
  * SegmentConstantPool manages the constant pool used for re-creating class
@@ -28,7 +29,7 @@
 public class SegmentConstantPool {
 
     private final CpBands bands;
-
+    private final SegmentConstantPoolArrayCache arrayCache = new SegmentConstantPoolArrayCache();
     /**
      * @param bands
      */
@@ -202,9 +203,9 @@
      * of the number of hits it finds using the following basis of comparison
      * for a hit: - the primaryArray[index] must be .equals() to the
      * primaryCompareString - the secondaryArray[index] .matches() the
-     * secondaryCompareString When the desiredIndex number of hits has been
-     * reached, the index into the original two arrays of the element hit is
-     * returned.
+     * secondaryCompareString. When the desiredIndex number of hits 
+     * has been reached, the index into the original two arrays of 
+     * the element hit is returned. 
      *
      * @param primaryArray
      *            The first array to search
@@ -220,22 +221,27 @@
      *         primaryArray and secondaryArray
      */
     protected int matchSpecificPoolEntryIndex(String[] primaryArray,
-            String[] secondaryArray, String primaryCompareString,
-            String secondaryCompareRegex, int desiredIndex) {
-        int instanceCount = -1;
-        for (int index = 0; index < primaryArray.length; index++) {
-            if ((primaryArray[index].equals(primaryCompareString))
-                    && regexMatches(secondaryCompareRegex,
-                            secondaryArray[index])) {
-                instanceCount++;
-                if (instanceCount == desiredIndex) {
-                    return index;
-                }
-            }
-        }
-        // We didn't return in the for loop, so the desiredMatch
-        // with desiredIndex must not exist in the array.
-        return -1;
+	    String[] secondaryArray, String primaryCompareString,
+	    String secondaryCompareRegex, int desiredIndex) {
+	int instanceCount = -1;
+	List indexList = arrayCache.indexesForArrayKey(primaryArray, primaryCompareString);
+	if(indexList.isEmpty()) {
+	    // Primary key not found, no chance of finding secondary
+	    return -1;
+	}
+
+	for(int index=0; index < indexList.size(); index++) {
+	    int arrayIndex = ((Integer)indexList.get(index)).intValue();
+	    if(regexMatches(secondaryCompareRegex, secondaryArray[arrayIndex])) {
+		instanceCount++;
+		if(instanceCount == desiredIndex) {
+		    return arrayIndex;
+		}
+	    }
+	}
+	// We didn't return in the for loop, so the desiredMatch
+	// with desiredIndex must not exist in the arrays.
+	return -1;
     }
 
     /**

Added: harmony/enhanced/classlib/trunk/modules/pack200/src/main/java/org/apache/harmony/unpack200/SegmentConstantPoolArrayCache.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/pack200/src/main/java/org/apache/harmony/unpack200/SegmentConstantPoolArrayCache.java?rev=671920&view=auto
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/pack200/src/main/java/org/apache/harmony/unpack200/SegmentConstantPoolArrayCache.java
(added)
+++ harmony/enhanced/classlib/trunk/modules/pack200/src/main/java/org/apache/harmony/unpack200/SegmentConstantPoolArrayCache.java
Thu Jun 26 08:21:14 2008
@@ -0,0 +1,182 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one or more
+ *  contributor license agreements.  See the NOTICE file distributed with
+ *  this work for additional information regarding copyright ownership.
+ *  The ASF licenses this file to You under the Apache License, Version 2.0
+ *  (the "License"); you may not use this file except in compliance with
+ *  the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+package org.apache.harmony.unpack200;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.IdentityHashMap;
+import java.util.List;
+
+/**
+ * The SegmentConstantPool spends a lot of time searching
+ * through large arrays of Strings looking for matches.
+ * This can be sped up by caching the arrays in HashMaps
+ * so the String keys are looked up and resolve to positions
+ * in the array rather than iterating through the arrays
+ * each time.
+ *
+ * Because the arrays only grow (never shrink or change)
+ * we can use the last known size as a way to determine if
+ * the array has changed.
+ *
+ * Note that this cache must be synchronized externally
+ * if it is shared.
+ */
+public class SegmentConstantPoolArrayCache {
+
+    protected IdentityHashMap knownArrays = new IdentityHashMap(1000);
+
+    protected List lastIndexes = null;
+    protected String[] lastArray = null;
+    protected String lastKey = null;
+
+    /**
+     * Answer the indices for the given key in the given
+     * array. If no such key exists in the cached array,
+     * answer -1.
+     * @param array String[] array to search for the value
+     * @param key String value for which to search
+     * @return List collection of index positions in the array
+     */
+    public List indexesForArrayKey(String[] array, String key) {
+        if(!arrayIsCached(array)) {
+            cacheArray(array);
+        }
+
+        // If the search is one we've just done, don't even
+        // bother looking and return the last indices. This
+        // is a second cache within the cache. This is
+        // efficient because we usually are looking for
+        // several secondary elements with the same primary
+        // key.
+        if((lastArray == array) && (lastKey == key)) {
+            return lastIndexes;
+        }
+
+        // Remember the last thing we found.
+        lastArray = array;
+        lastKey = key;
+        lastIndexes = ((CachedArray)knownArrays.get(array)).indexesForKey(key);
+
+        return lastIndexes;
+    }
+
+    /**
+     * Given a String array, answer true if the
+     * array is correctly cached. Answer false
+     * if the array is not cached, or if the
+     * array cache is outdated.
+     *
+     * @param array of String
+     * @return boolean true if up-to-date cache,
+     *   otherwise false.
+     */
+    protected boolean arrayIsCached(String[] array) {
+        if(!knownArrays.containsKey(array)) {
+            return false;
+        }
+        CachedArray cachedArray = (CachedArray)knownArrays.get(array);
+        if(cachedArray.lastKnownSize() != array.length) {
+            return false;
+        }
+        return true;
+    }
+
+    /**
+     * Cache the array passed in as the argument
+     * @param array String[] to cache
+     */
+    protected void cacheArray(String[] array) {
+        if(arrayIsCached(array)) {
+            throw new IllegalArgumentException("Trying to cache an array that already exists");
+        }
+        knownArrays.put(array, new CachedArray(array));
+        // Invalidate the cache-within-a-cache
+        lastArray = null;
+    }
+
+    /**
+     * CachedArray keeps track of the last known size of
+     * an array as well as a HashMap that knows the mapping
+     * from element values to the indices of the array
+     * which contain that value.
+     */
+    protected class CachedArray {
+        String[] primaryArray;
+        int lastKnownSize;
+        HashMap primaryTable;
+
+        public CachedArray(String[] array) {
+            super();
+            this.primaryArray = array;
+            this.lastKnownSize = array.length;
+            this.primaryTable = new HashMap(lastKnownSize);
+            cacheIndexes();
+        }
+
+        /**
+         * Answer the last known size of the array cached.
+         * If the last known size is not the same as the
+         * current size, the array must have changed.
+         * @return int last known size of the cached array
+         */
+        public int lastKnownSize() {
+            return lastKnownSize;
+        }
+
+        /**
+         * Given a particular key, answer a List of
+         * index locations in the array which contain that
+         * key.
+         *
+         * If no elements are found, answer an empty list.
+         *
+         * @param key String element of the array
+         * @return List of indexes containing that key
+         *   in the array.
+         */
+        public List indexesForKey(String key) {
+            if(!primaryTable.containsKey(key)) {
+                return Collections.EMPTY_LIST;
+            }
+            return (List)primaryTable.get(key);
+        }
+
+        /**
+         * Given a primaryArray, cache its values in a HashMap
+         * to provide a backwards mapping from element values
+         * to element indexes. For instance, a primaryArray
+         * of:
+         *  {"Zero", "Foo", "Two", "Foo"}
+         *  would yield a HashMap of:
+         *   "Zero" -> 0
+         *   "Foo" -> 1, 3
+         *   "Two" -> 2
+         * which is then cached.
+         */
+        protected void cacheIndexes() {
+            for(int index=0; index < primaryArray.length; index++) {
+                String key = primaryArray[index];
+                if(!primaryTable.containsKey(key)) {
+                    primaryTable.put(key, new ArrayList());
+                }
+                ((ArrayList)primaryTable.get(key)).add(new Integer(index));
+            }
+        }
+    }
+}

Propchange: harmony/enhanced/classlib/trunk/modules/pack200/src/main/java/org/apache/harmony/unpack200/SegmentConstantPoolArrayCache.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: harmony/enhanced/classlib/trunk/modules/pack200/src/main/java/org/apache/harmony/unpack200/SegmentConstantPoolArrayCache.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain

Modified: harmony/enhanced/classlib/trunk/modules/pack200/src/main/java/org/apache/harmony/unpack200/bytecode/CPUTF8.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/pack200/src/main/java/org/apache/harmony/unpack200/bytecode/CPUTF8.java?rev=671920&r1=671919&r2=671920&view=diff
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/pack200/src/main/java/org/apache/harmony/unpack200/bytecode/CPUTF8.java
(original)
+++ harmony/enhanced/classlib/trunk/modules/pack200/src/main/java/org/apache/harmony/unpack200/bytecode/CPUTF8.java
Thu Jun 26 08:21:14 2008
@@ -72,16 +72,7 @@
     }
 
     protected void writeBody(DataOutputStream dos) throws IOException {
-        byte[] bytes;
-        try {
-            // TODO Check that this is the right UTF-8 for bytes
-            bytes = utf8.getBytes("UTF-8");
-        } catch (UnsupportedEncodingException e) {
-            throw new RuntimeException("Couldn't convert string " + utf8
-                    + " to UTF-8");
-        }
-        dos.writeShort(bytes.length);
-        dos.write(bytes);
+        dos.writeUTF(utf8);
     }
 
     public String underlyingString() {

Added: harmony/enhanced/classlib/trunk/modules/pack200/src/test/java/org/apache/harmony/unpack200/tests/SegmentConstantPoolArrayCacheTest.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/pack200/src/test/java/org/apache/harmony/unpack200/tests/SegmentConstantPoolArrayCacheTest.java?rev=671920&view=auto
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/pack200/src/test/java/org/apache/harmony/unpack200/tests/SegmentConstantPoolArrayCacheTest.java
(added)
+++ harmony/enhanced/classlib/trunk/modules/pack200/src/test/java/org/apache/harmony/unpack200/tests/SegmentConstantPoolArrayCacheTest.java
Thu Jun 26 08:21:14 2008
@@ -0,0 +1,78 @@
+/*
+ *  Licensed to the Apache Software Foundation (ASF) under one or more
+ *  contributor license agreements.  See the NOTICE file distributed with
+ *  this work for additional information regarding copyright ownership.
+ *  The ASF licenses this file to You under the Apache License, Version 2.0
+ *  (the "License"); you may not use this file except in compliance with
+ *  the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+package org.apache.harmony.unpack200.tests;
+
+import java.util.List;
+
+import junit.framework.TestCase;
+
+import org.apache.harmony.unpack200.SegmentConstantPoolArrayCache;
+
+public class SegmentConstantPoolArrayCacheTest extends TestCase {
+    
+    public void testSingleSimpleArray() {
+        SegmentConstantPoolArrayCache arrayCache = new SegmentConstantPoolArrayCache();
+        String array[] = {"Zero", "One", "Two", "Three", "Four"};
+        List list = arrayCache.indexesForArrayKey(array, "Three");
+        assertEquals(1, list.size());
+        assertEquals(3, ((Integer)list.get(0)).intValue());
+    }
+    
+    public void testSingleMultipleHitArray() {
+        SegmentConstantPoolArrayCache arrayCache = new SegmentConstantPoolArrayCache();
+        String array[] = {"Zero", "OneThreeFour", "Two", "OneThreeFour", "OneThreeFour"};
+        List list = arrayCache.indexesForArrayKey(array, "OneThreeFour");
+        assertEquals(3, list.size());
+        assertEquals(1, ((Integer)list.get(0)).intValue());
+        assertEquals(3, ((Integer)list.get(1)).intValue());
+        assertEquals(4, ((Integer)list.get(2)).intValue());
+    }
+
+    public void testMultipleArrayMultipleHit() {
+        SegmentConstantPoolArrayCache arrayCache = new SegmentConstantPoolArrayCache();
+        String arrayOne[] = {"Zero", "Shared", "Two", "Shared", "Shared"};
+        String arrayTwo[] = {"Shared", "One", "Shared", "Shared", "Shared"};
+
+        List listOne = arrayCache.indexesForArrayKey(arrayOne, "Shared");
+        List listTwo = arrayCache.indexesForArrayKey(arrayTwo, "Shared");
+        // Make sure we're using the cached values. First trip
+        // through builds the cache.
+        listOne = arrayCache.indexesForArrayKey(arrayOne, "Two");
+        listTwo = arrayCache.indexesForArrayKey(arrayTwo, "Shared");
+        
+        assertEquals(1, listOne.size());
+        assertEquals(2, ((Integer)listOne.get(0)).intValue());
+
+        // Now look for a different element in list one
+        listOne = arrayCache.indexesForArrayKey(arrayOne, "Shared");
+        assertEquals(3, listOne.size());
+        assertEquals(1, ((Integer)listOne.get(0)).intValue());
+        assertEquals(3, ((Integer)listOne.get(1)).intValue());
+        assertEquals(4, ((Integer)listOne.get(2)).intValue());
+        
+        assertEquals(4, listTwo.size());
+        assertEquals(0, ((Integer)listTwo.get(0)).intValue());
+        assertEquals(2, ((Integer)listTwo.get(1)).intValue());
+        assertEquals(3, ((Integer)listTwo.get(2)).intValue());
+        assertEquals(4, ((Integer)listTwo.get(3)).intValue());
+        
+        List listThree = arrayCache.indexesForArrayKey(arrayOne, "Not found");
+        assertEquals(0, listThree.size());
+    }
+    
+}

Propchange: harmony/enhanced/classlib/trunk/modules/pack200/src/test/java/org/apache/harmony/unpack200/tests/SegmentConstantPoolArrayCacheTest.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: harmony/enhanced/classlib/trunk/modules/pack200/src/test/java/org/apache/harmony/unpack200/tests/SegmentConstantPoolArrayCacheTest.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain



Mime
View raw message