You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@ant.apache.org by an...@apache.org on 2014/04/27 22:02:51 UTC
svn commit: r1590481 - in /ant/ivy/core/trunk: CHANGES.txt
src/java/org/apache/ivy/core/module/id/MatcherLookup.java
src/java/org/apache/ivy/core/module/id/ModuleRules.java
Author: antoine
Date: Sun Apr 27 20:02:51 2014
New Revision: 1590481
URL: http://svn.apache.org/r1590481
Log:
MPROVEMENT: ModuleRules.getRule is O(n) leading to resolution slowness (IVY-1465) (Thanks to Zhong Wang aka Kewpie)
Added:
ant/ivy/core/trunk/src/java/org/apache/ivy/core/module/id/MatcherLookup.java (with props)
Modified:
ant/ivy/core/trunk/CHANGES.txt
ant/ivy/core/trunk/src/java/org/apache/ivy/core/module/id/ModuleRules.java
Modified: ant/ivy/core/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/ant/ivy/core/trunk/CHANGES.txt?rev=1590481&r1=1590480&r2=1590481&view=diff
==============================================================================
--- ant/ivy/core/trunk/CHANGES.txt (original)
+++ ant/ivy/core/trunk/CHANGES.txt Sun Apr 27 20:02:51 2014
@@ -138,10 +138,12 @@ for detailed view of each issue, please
Jaroslaw Wypychowski
Sven Zethelius
Aleksey Zhukov
+ Zhong Wang
trunk
=====================================
- IMPROVEMENT: Add support for packed jar within an OSGi bundle
+- IMPROVEMENT: ModuleRules.getRule is O(n) leading to resolution slowness (IVY-1465) (Thanks to Zhong Wang aka Kewpie)
- FIX: impossible to get artifacts when data has not been loaded. (IVY-1399) (Thanks to David Turner)
Added: ant/ivy/core/trunk/src/java/org/apache/ivy/core/module/id/MatcherLookup.java
URL: http://svn.apache.org/viewvc/ant/ivy/core/trunk/src/java/org/apache/ivy/core/module/id/MatcherLookup.java?rev=1590481&view=auto
==============================================================================
--- ant/ivy/core/trunk/src/java/org/apache/ivy/core/module/id/MatcherLookup.java (added)
+++ ant/ivy/core/trunk/src/java/org/apache/ivy/core/module/id/MatcherLookup.java Sun Apr 27 20:02:51 2014
@@ -0,0 +1,153 @@
+/*
+ * 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.ivy.core.module.id;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.ivy.core.IvyPatternHelper;
+import org.apache.ivy.plugins.matcher.ExactPatternMatcher;
+import org.apache.ivy.plugins.matcher.MapMatcher;
+import org.apache.ivy.plugins.matcher.PatternMatcher;
+
+/**
+ * This class targets to speed up lookup for exact pattern matcher by keys, which are created with
+ * (organization, module) information. When exact pattern matcher is added, the key is created from
+ * matcher's attributes. When matcher is looked up against specific module, the key is recreated
+ * from module's attributes.
+ * <p>
+ * </p>
+ * The lookup doesn't target to speed up lookup for non exact pattern matcher. All non exact
+ * matchers are placed in non-keyed collection.
+ * <p>
+ * </p>
+ * At lookup for matchers against specific module, all non exact pattern matchers are iterated to
+ * match with module attributes, and exact pattern matchers binding to the same key will also
+ * iterated to match with module attributes.
+ * <p>
+ * </p>
+ * If there are much more exact pattern matchers than non exact pattern matchers, the matcher lookup
+ * speed can benefit from this class significantly. A quick example could be user declares lots of
+ * dependencyOverrides which are typically exact pattern matchers.
+ * <p>
+ * </p>
+ * If there are balanced exact and non exact pattern matchers, the matcher lookup speed doesn't hurt
+ * by this class.
+ * <p>
+ * </p>
+ */
+public class MatcherLookup {
+
+ //private static final String FORMAT = "{org:%s, module:%s}";
+
+ private static final String DEFAULT = "{org:" + "default" + ", module:" + "default" + "}";
+
+ private Map/* <String, List<MapMatcher>> */lookup = new HashMap();
+
+ private List/* <MapMatcher> */non_exact_matchers = new ArrayList();
+
+ /**
+ * Add matcher.
+ *
+ * If matcher is exact pattern matcher, it will be associated with a key and placed in keyed
+ * collection.
+ *
+ * If matcher is not exact pattern matcher, it will be placed into non-keyed collection
+ *
+ * @param matcher
+ */
+ public void add(MapMatcher matcher) {
+ if (!(matcher.getPatternMatcher() instanceof ExactPatternMatcher)) {
+ non_exact_matchers.add(matcher);
+ return;
+ }
+ Object key = key(matcher.getAttributes());
+ List exact_matchers = (List) lookup.get(key);
+ if (exact_matchers == null) {
+ exact_matchers = new ArrayList();
+ lookup.put(key, exact_matchers);
+ }
+ exact_matchers.add(matcher);
+ }
+
+ /**
+ * Get a list of matchers which can apply to module with specified attributes
+ *
+ * @param attrs
+ * A map of attributes that matcher should match.
+ *
+ * @return list A list of candidate matchers that matches specified attributes
+ */
+ public List get(Map attrs) {
+ List matchers = new ArrayList();
+ // Step 1: find matchers from non_exact_matchers list
+ if (!non_exact_matchers.isEmpty()) {
+ for (Iterator iter = non_exact_matchers.iterator(); iter.hasNext();) {
+ MapMatcher matcher = (MapMatcher) iter.next();
+ if (matcher.matches(attrs)) {
+ matchers.add(matcher);
+ }
+ }
+ }
+ // Step 2: find matchers from exact_matchers list of key
+ Object key = key(attrs);
+ List exact_matchers = (List) lookup.get(key);
+ if (exact_matchers != null) {
+ for (Iterator iter = exact_matchers.iterator(); iter.hasNext();) {
+ MapMatcher matcher = (MapMatcher) iter.next();
+ if (matcher.matches(attrs)) {
+ matchers.add(matcher);
+ }
+ }
+ }
+ // Step 3: (iff key != DEFAULT) find matchers from exact_matchers of DEFAULT
+ if (key != DEFAULT) {
+ List default_exact_matchers = (List) lookup.get(DEFAULT);
+ if (default_exact_matchers != null) {
+ for (Iterator iter = default_exact_matchers.iterator(); iter.hasNext();) {
+ MapMatcher matcher = (MapMatcher) iter.next();
+ if (matcher.matches(attrs)) {
+ matchers.add(matcher);
+ }
+ }
+ }
+ }
+ return matchers;
+ }
+
+ /**
+ * Create a key from specified attributes
+ *
+ * @param attrs
+ * A map of attributes
+ * @return key object
+ */
+ private Object key(Map attrs) {
+ Object org = attrs.get(IvyPatternHelper.ORGANISATION_KEY);
+ Object module = attrs.get(IvyPatternHelper.MODULE_KEY);
+ if (org == null || PatternMatcher.ANY_EXPRESSION.equals(org) || module == null
+ || PatternMatcher.ANY_EXPRESSION.equals(module)) {
+ return DEFAULT;
+ }
+ return "{org:" + org + ", module:" + module + "}";
+ }
+
+}
Propchange: ant/ivy/core/trunk/src/java/org/apache/ivy/core/module/id/MatcherLookup.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified: ant/ivy/core/trunk/src/java/org/apache/ivy/core/module/id/ModuleRules.java
URL: http://svn.apache.org/viewvc/ant/ivy/core/trunk/src/java/org/apache/ivy/core/module/id/ModuleRules.java?rev=1590481&r1=1590480&r2=1590481&view=diff
==============================================================================
--- ant/ivy/core/trunk/src/java/org/apache/ivy/core/module/id/ModuleRules.java (original)
+++ ant/ivy/core/trunk/src/java/org/apache/ivy/core/module/id/ModuleRules.java Sun Apr 27 20:02:51 2014
@@ -23,7 +23,6 @@ import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
-import java.util.Map.Entry;
import org.apache.ivy.plugins.matcher.MapMatcher;
import org.apache.ivy.util.Checks;
@@ -53,6 +52,8 @@ import org.apache.ivy.util.filter.NoFilt
public class ModuleRules {
private Map/* <MapMatcher,Object> */rules = new LinkedHashMap();
+ private MatcherLookup matcher_lookup = new MatcherLookup();
+
/**
* Constructs an empty ModuleRules.
*/
@@ -61,6 +62,9 @@ public class ModuleRules {
private ModuleRules(Map/* <MapMatcher,Object> */rules) {
this.rules = new LinkedHashMap(rules);
+ for (Iterator iter = rules.keySet().iterator(); iter.hasNext();) {
+ matcher_lookup.add((MapMatcher) iter.next());
+ }
}
/**
@@ -76,6 +80,7 @@ public class ModuleRules {
Checks.checkNotNull(rule, "rule");
rules.put(condition, rule);
+ matcher_lookup.add(condition);
}
/**
@@ -123,7 +128,7 @@ public class ModuleRules {
* Returns the rule object matching the given {@link ModuleId} and accepted by the given
* {@link Filter}, or <code>null</code> if no rule applies.
*
- * @param mrid
+ * @param mid
* the {@link ModuleRevisionId} to search the rule for. Must not be <code>null</code>
* .
* @param filter
@@ -164,14 +169,12 @@ public class ModuleRules {
}
private Object getRule(Map moduleAttributes, Filter filter) {
- for (Iterator iter = rules.entrySet().iterator(); iter.hasNext();) {
- Map.Entry ruleEntry = (Entry) iter.next();
- MapMatcher midm = (MapMatcher) ruleEntry.getKey();
- if (midm.matches(moduleAttributes)) {
- Object rule = ruleEntry.getValue();
- if (filter.accept(rule)) {
- return rule;
- }
+ List matchers = matcher_lookup.get(moduleAttributes);
+ for (Iterator iter = matchers.iterator(); iter.hasNext();) {
+ MapMatcher midm = (MapMatcher) iter.next();
+ Object rule = rules.get(midm);
+ if (filter.accept(rule)) {
+ return rule;
}
}
return null;
@@ -198,15 +201,13 @@ public class ModuleRules {
}
private Object[] getRules(Map moduleAttributes, Filter filter) {
+ List matchers = matcher_lookup.get(moduleAttributes);
List matchingRules = new ArrayList();
- for (Iterator iter = rules.entrySet().iterator(); iter.hasNext();) {
- Map.Entry ruleEntry = (Entry) iter.next();
- MapMatcher midm = (MapMatcher) ruleEntry.getKey();
- if (midm.matches(moduleAttributes)) {
- Object rule = ruleEntry.getValue();
- if (filter.accept(rule)) {
- matchingRules.add(rule);
- }
+ for (Iterator iter = matchers.iterator(); iter.hasNext();) {
+ MapMatcher midm = (MapMatcher) iter.next();
+ Object rule = rules.get(midm);
+ if (filter.accept(rule)) {
+ matchingRules.add(rule);
}
}
return matchingRules.toArray();