Return-Path: 
 <commits-return-1309-apmail-velocity-commits-archive=velocity.apache.org@velocity.apache.org>
Delivered-To: apmail-velocity-commits-archive@locus.apache.org
Received: (qmail 28814 invoked from network); 25 Jul 2008 22:58:34 -0000
Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.2)
  by minotaur.apache.org with SMTP; 25 Jul 2008 22:58:34 -0000
Received: (qmail 13769 invoked by uid 500); 25 Jul 2008 22:58:34 -0000
Delivered-To: apmail-velocity-commits-archive@velocity.apache.org
Received: (qmail 13730 invoked by uid 500); 25 Jul 2008 22:58:34 -0000
Mailing-List: contact commits-help@velocity.apache.org; run by ezmlm
Precedence: bulk
List-Help: <mailto:commits-help@velocity.apache.org>
List-Unsubscribe: <mailto:commits-unsubscribe@velocity.apache.org>
List-Post: <mailto:commits@velocity.apache.org>
List-Id: <commits.velocity.apache.org>
Reply-To: dev@velocity.apache.org
Delivered-To: mailing list commits@velocity.apache.org
Received: (qmail 13720 invoked by uid 99); 25 Jul 2008 22:58:34 -0000
Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136)
    by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 25 Jul 2008 15:58:34 -0700
X-ASF-Spam-Status: No, hits=-2000.0 required=10.0
	tests=ALL_TRUSTED
X-Spam-Check-By: apache.org
Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4)
    by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 25 Jul 2008 22:57:47 +0000
Received: by eris.apache.org (Postfix, from userid 65534)
	id 92F4923889FF; Fri, 25 Jul 2008 15:58:13 -0700 (PDT)
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r679922 - in
 /velocity/engine/trunk/src/java/org/apache/velocity/util/introspection:
 ClassMap.java MethodMap.java
Date: Fri, 25 Jul 2008 22:58:13 -0000
To: commits@velocity.apache.org
From: nbubna@apache.org
X-Mailer: svnmailer-1.0.8
Message-Id: <20080725225813.92F4923889FF@eris.apache.org>
X-Virus-Checked: Checked by ClamAV on apache.org

Author: nbubna
Date: Fri Jul 25 15:58:13 2008
New Revision: 679922

URL: http://svn.apache.org/viewvc?rev=679922&view=rev
Log:
VELOCITY-606 marginal performance improvements for ClassMap and MethodMap

Modified:
    velocity/engine/trunk/src/java/org/apache/velocity/util/introspection/ClassMap.java
    velocity/engine/trunk/src/java/org/apache/velocity/util/introspection/MethodMap.java

Modified: velocity/engine/trunk/src/java/org/apache/velocity/util/introspection/ClassMap.java
URL: http://svn.apache.org/viewvc/velocity/engine/trunk/src/java/org/apache/velocity/util/introspection/ClassMap.java?rev=679922&r1=679921&r2=679922&view=diff
==============================================================================
--- velocity/engine/trunk/src/java/org/apache/velocity/util/introspection/ClassMap.java (original)
+++ velocity/engine/trunk/src/java/org/apache/velocity/util/introspection/ClassMap.java Fri Jul 25 15:58:13 2008
@@ -26,7 +26,7 @@
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
-
+import org.apache.commons.lang.text.StrBuilder;
 import org.apache.velocity.runtime.log.Log;
 
 /**
@@ -39,6 +39,7 @@
  * @author <a href="mailto:szegedia@freemail.hu">Attila Szegedi</a>
  * @author <a href="mailto:geirm@optonline.net">Geir Magnusson Jr.</a>
  * @author <a href="mailto:henning@apache.org">Henning P. Schmiedehausen</a>
+ * @author Nathan Bubna
  * @version $Id$
  */
 public class ClassMap
@@ -72,9 +73,7 @@
             log.debug("== Class: " + clazz);
         }
         
-        methodCache = new MethodCache(log);
-        
-        populateMethodCache();
+        methodCache = createMethodCache();
 
         if (debugReflection && log.isDebugEnabled())
         {
@@ -111,10 +110,11 @@
      * are taken from all the public methods
      * that our class, its parents and their implemented interfaces provide.
      */
-    private void populateMethodCache()
+    private MethodCache createMethodCache()
     {
+        MethodCache methodCache = new MethodCache(log);
 	//
-	// Build a list of all elements in the class hierarchy. This one is bottom-first (i.e. we start
+	// Looks through all elements in the class hierarchy. This one is bottom-first (i.e. we start
 	// with the actual declaring class and its interfaces and then move up (superclass etc.) until we
 	// hit java.lang.Object. That is important because it will give us the methods of the declaring class
 	// which might in turn be abstract further up the tree.
@@ -126,70 +126,60 @@
 	// until Velocity 1.4. As we always reflect all elements of the tree (that's what we have a cache for), we will
 	// hit the public elements sooner or later because we reflect all the public elements anyway.
 	//
-        List classesToReflect = new ArrayList();
-        
         // Ah, the miracles of Java for(;;) ... 
         for (Class classToReflect = getCachedClass(); classToReflect != null ; classToReflect = classToReflect.getSuperclass())
         {
             if (Modifier.isPublic(classToReflect.getModifiers()))
             {
-                classesToReflect.add(classToReflect);
-                if (debugReflection && log.isDebugEnabled())
-                {
-                    log.debug("Adding " + classToReflect + " for reflection");
-                }
+                populateMethodCacheWith(methodCache, classToReflect);
             }
             Class [] interfaces = classToReflect.getInterfaces();
             for (int i = 0; i < interfaces.length; i++)
             {
                 if (Modifier.isPublic(interfaces[i].getModifiers()))
                 {
-                    classesToReflect.add(interfaces[i]);
-                    if (debugReflection && log.isDebugEnabled())
-                    {
-                        log.debug("Adding " + interfaces[i] + " for reflection");
-                    }
+                    populateMethodCacheWith(methodCache, interfaces[i]);
                 }
             }
         }
+        // return the already initialized cache
+        return methodCache;
+    }
 
-        for (Iterator it = classesToReflect.iterator(); it.hasNext(); )
+    private void populateMethodCacheWith(MethodCache methodCache, Class classToReflect)
+    {
+        if (debugReflection && log.isDebugEnabled())
         {
-            Class classToReflect = (Class) it.next();
-            if (debugReflection && log.isDebugEnabled())
-            {
-                log.debug("Reflecting " + classToReflect);
-            }
-            
+            log.debug("Reflecting " + classToReflect);
+        }
 
-            try
-            {
-                Method[] methods = classToReflect.getMethods();
+        try
+        {
+            Method[] methods = classToReflect.getDeclaredMethods();
 
-                for (int i = 0; i < methods.length; i++)
+            for (int i = 0; i < methods.length; i++)
+            {
+                // Strictly spoken that check shouldn't be necessary
+                // because getMethods only returns public methods.
+                int modifiers = methods[i].getModifiers();
+                if (Modifier.isPublic(modifiers)) //  && !)
                 {
-                    // Strictly spoken that check shouldn't be necessary
-                    // because getMethods only returns public methods.
-                    int modifiers = methods[i].getModifiers();
-                    if (Modifier.isPublic(modifiers)) //  && !)
-            	    {
-                        // Some of the interfaces contain abstract methods. That is fine, because the actual object must 
-                        // implement them anyway (else it wouldn't be implementing the interface). If we find an abstract
-                        // method in a non-interface, we skip it, because we do want to make sure that no abstract methods end up in
-                        // the cache.                       
-                        if (classToReflect.isInterface() || !Modifier.isAbstract(modifiers))
-                        {
-                            methodCache.put(methods[i]);
-                        }
+                    // Some of the interfaces contain abstract methods. That is fine, because the actual object must 
+                    // implement them anyway (else it wouldn't be implementing the interface). If we find an abstract
+                    // method in a non-interface, we skip it, because we do want to make sure that no abstract methods end up in
+                    // the cache.                       
+                    if (classToReflect.isInterface() || !Modifier.isAbstract(modifiers))
+                    {
+                        methodCache.put(methods[i]);
                     }
                 }
             }
-            catch (SecurityException se) // Everybody feels better with...
+        }
+        catch (SecurityException se) // Everybody feels better with...
+        {
+            if (log.isDebugEnabled())
             {
-                if (log.isDebugEnabled())
-                {
-                    log.debug("While accessing methods of " + classToReflect + ": ", se);
-                }
+                log.debug("While accessing methods of " + classToReflect + ": ", se);
             }
         }
     }
@@ -202,11 +192,9 @@
      */
     private static final class MethodCache
     {
-        private static final class CacheMiss { }
-        
-        private static final CacheMiss CACHE_MISS = new CacheMiss();
+        private static final Object CACHE_MISS = new Object();
 
-        private static final Object OBJECT = new Object();
+        private static final String NULL_ARG = new Object().getClass().getName();
 
         private static final Map convertPrimitives = new HashMap();
 
@@ -230,6 +218,7 @@
          * name and actual arguments used to find it.
          */
         private final Map cache = new HashMap();
+        private final Map locks = new HashMap();
 
         /** Map of methods that are searchable according to method parameters to find a match */
         private final MethodMap methodMap = new MethodMap();
@@ -255,52 +244,55 @@
          * @return A Method object representing the method to invoke or null.
          * @throws MethodMap.AmbiguousException When more than one method is a match for the parameters.
          */
-        public synchronized Method get(final String name, final Object [] params)
+        public Method get(final String name, final Object [] params)
                 throws MethodMap.AmbiguousException
         {
-            String methodKey = makeMethodKey(name, params);
+            String methodKey = getLock(makeMethodKey(name, params));
 
-            Object cacheEntry = cache.get(methodKey);
-
-            // We looked this up before and failed. 
-            if (cacheEntry == CACHE_MISS)
+            synchronized (methodKey)
             {
-                return null;
-            }
+                Object cacheEntry = cache.get(methodKey);
 
-            if (cacheEntry == null)
-            {
-                try
+                // We looked this up before and failed. 
+                if (cacheEntry == CACHE_MISS)
                 {
-                    // That one is expensive...
-                    cacheEntry = methodMap.find(name, params);
+                    return null;
                 }
-                catch(MethodMap.AmbiguousException ae)
+
+                if (cacheEntry == null)
                 {
-                    /*
-                     *  that's a miss :-)
-                     */
-                    cache.put(methodKey, CACHE_MISS);
-                    throw ae;
-                }
+                    try
+                    {
+                        // That one is expensive...
+                        cacheEntry = methodMap.find(name, params);
+                    }
+                    catch(MethodMap.AmbiguousException ae)
+                    {
+                        /*
+                         *  that's a miss :-)
+                         */
+                        cache.put(methodKey, CACHE_MISS);
+                        throw ae;
+                    }
 
-                cache.put(methodKey, 
-                        (cacheEntry != null) ? cacheEntry : CACHE_MISS);
-            }
+                    cache.put(methodKey, 
+                            (cacheEntry != null) ? cacheEntry : CACHE_MISS);
+                }
 
-            // Yes, this might just be null.
+                // Yes, this might just be null.
 
-            return (Method) cacheEntry;
+                return (Method) cacheEntry;
+            }
         }
 
-        public synchronized void put(Method method)
+        private void put(Method method)
         {
             String methodKey = makeMethodKey(method);
-            
-            // We don't overwrite methods. Especially not if we fill the
-            // cache from defined class towards java.lang.Object because 
-            // abstract methods in superclasses would else overwrite concrete
-            // classes further down the hierarchy.
+
+            // We don't overwrite methods because we fill the
+            // cache from defined class towards java.lang.Object
+            // and that would cause overridden methods to appear
+            // as if they were not overridden.
             if (cache.get(methodKey) == null)
             {
                 cache.put(methodKey, method);
@@ -312,6 +304,18 @@
             }
         }
 
+        private final String getLock(String key) {
+            synchronized (locks)
+            {
+                String lock = (String)locks.get(key);
+                if (lock == null)
+                {
+                    return key;
+                }
+                return lock;
+            }
+        }
+
         /**
          * Make a methodKey for the given method using
          * the concatenation of the name and the
@@ -323,10 +327,15 @@
         private String makeMethodKey(final Method method)
         {
             Class[] parameterTypes = method.getParameterTypes();
+            int args = parameterTypes.length;
+            if (args == 0)
+            {
+                return method.getName();
+            }
 
-            StringBuffer methodKey = new StringBuffer(method.getName());
+            StrBuilder methodKey = new StrBuilder((args+1)*16).append(method.getName());
 
-            for (int j = 0; j < parameterTypes.length; j++)
+            for (int j = 0; j < args; j++)
             {
                 /*
                  * If the argument type is primitive then we want
@@ -353,18 +362,25 @@
 
         private String makeMethodKey(String method, Object[] params)
         {
-            StringBuffer methodKey = new StringBuffer().append(method);
+            int args = params.length;
+            if (args == 0)
+            {
+                return method;
+            }
 
-            for (int j = 0; j < params.length; j++)
+            StrBuilder methodKey = new StrBuilder((args+1)*16).append(method);
+
+            for (int j = 0; j < args; j++)
             {
                 Object arg = params[j];
-
                 if (arg == null)
                 {
-                    arg = OBJECT;
+                    methodKey.append(NULL_ARG);
+                }
+                else
+                {
+                    methodKey.append(arg.getClass().getName());
                 }
-
-                methodKey.append(arg.getClass().getName());
             }
 
             return methodKey.toString();

Modified: velocity/engine/trunk/src/java/org/apache/velocity/util/introspection/MethodMap.java
URL: http://svn.apache.org/viewvc/velocity/engine/trunk/src/java/org/apache/velocity/util/introspection/MethodMap.java?rev=679922&r1=679921&r2=679922&view=diff
==============================================================================
--- velocity/engine/trunk/src/java/org/apache/velocity/util/introspection/MethodMap.java (original)
+++ velocity/engine/trunk/src/java/org/apache/velocity/util/introspection/MethodMap.java Fri Jul 25 15:58:13 2008
@@ -21,7 +21,7 @@
 
 import java.lang.reflect.Method;
 import java.util.ArrayList;
-import java.util.Hashtable;
+import java.util.HashMap;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
@@ -45,7 +45,7 @@
     /**
      * Keep track of all methods with the same name.
      */
-    Map methodByNameMap = new Hashtable();
+    Map methodByNameMap = new HashMap();
 
     /**
      * Add a method to a list of methods by name.
@@ -132,99 +132,99 @@
                     arg == null ? null : arg.getClass();
         }
 
-        return getMostSpecific(methodList, classes);
+        return getBestMatch(methodList, classes);
     }
 
-    /**
-     *  Simple distinguishable exception, used when
-     *  we run across ambiguous overloading.  Caught
-     *  by the introspector.
-     */
-    public static class AmbiguousException extends RuntimeException
-    {
-        /**
-         * Version Id for serializable
-         */
-        private static final long serialVersionUID = -2314636505414551663L;
-    }
-
-
-    private static Method getMostSpecific(List methods, Class[] classes)
-        throws AmbiguousException
+    private static Method getBestMatch(List methods, Class[] args)
     {
-        LinkedList applicables = getApplicables(methods, classes);
-
-        if(applicables.isEmpty())
+        List equivalentMatches = null;
+        Method bestMatch = null;
+        Class[] bestMatchTypes = null;
+        for (Iterator i = methods.iterator(); i.hasNext(); )
         {
-            return null;
-        }
-
-        if(applicables.size() == 1)
-        {
-            return (Method)applicables.getFirst();
-        }
-
-        /*
-         * This list will contain the maximally specific methods. Hopefully at
-         * the end of the below loop, the list will contain exactly one method,
-         * (the most specific method) otherwise we have ambiguity.
-         */
-
-        LinkedList maximals = new LinkedList();
-
-        for (Iterator applicable = applicables.iterator();
-             applicable.hasNext();)
-        {
-            Method app = (Method) applicable.next();
-            Class[] appArgs = app.getParameterTypes();
-            boolean lessSpecific = false;
-
-            for (Iterator maximal = maximals.iterator();
-                 !lessSpecific && maximal.hasNext();)
+            Method method = (Method)i.next();
+            if (isApplicable(method, args))
             {
-                Method max = (Method) maximal.next();
-
-                switch(moreSpecific(appArgs, max.getParameterTypes()))
+                if (bestMatch == null)
                 {
-                    case MORE_SPECIFIC:
-                    {
-                        /*
-                         * This method is more specific than the previously
-                         * known maximally specific, so remove the old maximum.
-                         */
-
-                        maximal.remove();
-                        break;
-                    }
-
-                    case LESS_SPECIFIC:
+                    bestMatch = method;
+                    bestMatchTypes = method.getParameterTypes();
+                }
+                else
+                {
+                    Class[] methodTypes = method.getParameterTypes();
+                    switch (compare(methodTypes, bestMatchTypes))
                     {
-                        /*
-                         * This method is less specific than some of the
-                         * currently known maximally specific methods, so we
-                         * won't add it into the set of maximally specific
-                         * methods
-                         */
-
-                        lessSpecific = true;
-                        break;
+                        case MORE_SPECIFIC:
+                            if (equivalentMatches == null)
+                            {
+                                bestMatch = method;
+                                bestMatchTypes = methodTypes;
+                            }
+                            else
+                            {
+                                // have to beat all other ambiguous ones...
+                                int ambiguities = equivalentMatches.size();
+                                for (int a=0; a < ambiguities; a++)
+                                {
+                                    Method other = (Method)equivalentMatches.get(a);
+                                    switch (compare(methodTypes, other.getParameterTypes()))
+                                    {
+                                        case MORE_SPECIFIC:
+                                            // ...and thus replace them all...
+                                            bestMatch = method;
+                                            bestMatchTypes = methodTypes;
+                                            equivalentMatches = null;
+                                            ambiguities = 0;
+                                            break;
+
+                                        case INCOMPARABLE:
+                                            // ...join them...
+                                            equivalentMatches.add(method);
+                                            break;
+
+                                        case LESS_SPECIFIC:
+                                            // ...or just go away.
+                                            break;
+                                    }
+                                }
+                            }
+                            break;
+
+                        case INCOMPARABLE:
+                            if (equivalentMatches == null)
+                            {
+                                equivalentMatches = new ArrayList(bestMatchTypes.length);
+                            }
+                            equivalentMatches.add(method);
+                            break;
+
+                        case LESS_SPECIFIC:
+                            // do nothing
+                            break;
                     }
                 }
             }
-
-            if(!lessSpecific)
-            {
-                maximals.addLast(app);
-            }
         }
-
-        if(maximals.size() > 1)
+                
+        if (equivalentMatches != null)
         {
-            // We have more than one maximally specific method
             throw new AmbiguousException();
         }
+        return bestMatch;
+    }
 
-        return (Method)maximals.getFirst();
+    /**
+     *  Simple distinguishable exception, used when
+     *  we run across ambiguous overloading.  Caught
+     *  by the introspector.
+     */
+    public static class AmbiguousException extends RuntimeException
+    {
+        /**
+         * Version Id for serializable
+         */
+        private static final long serialVersionUID = -2314636505414551663L;
     }
 
     /**
@@ -235,7 +235,7 @@
      * @return MORE_SPECIFIC if c1 is more specific than c2, LESS_SPECIFIC if
      * c1 is less specific than c2, INCOMPARABLE if they are incomparable.
      */
-    private static int moreSpecific(Class[] c1, Class[] c2)
+    private static int compare(Class[] c1, Class[] c2)
     {
         boolean c1MoreSpecific = false;
         boolean c2MoreSpecific = false;
@@ -310,31 +310,6 @@
     }
 
     /**
-     * Returns all methods that are applicable to actual argument types.
-     * @param methods list of all candidate methods
-     * @param classes the actual types of the arguments
-     * @return a list that contains only applicable methods (number of
-     * formal and actual arguments matches, and argument types are assignable
-     * to formal types through a method invocation conversion).
-     */
-    private static LinkedList getApplicables(List methods, Class[] classes)
-    {
-        LinkedList list = new LinkedList();
-
-        for (Iterator imethod = methods.iterator(); imethod.hasNext();)
-        {
-            Method method = (Method) imethod.next();
-
-            if(isApplicable(method, classes))
-            {
-                list.add(method);
-            }
-
-        }
-        return list;
-    }
-
-    /**
      * Returns true if the supplied method is applicable to actual
      * argument types.
      *