Changeset 7423 in josm

Timestamp:

2014-08-16T20:14:24+02:00 (10 years ago)

Author:

Don-vip

Message:

see #9680, see #4626 - multithreaded multipolygon creation

Location:

trunk/src/org/openstreetmap/josm

Files:

• actions/CreateMultipolygonAction.java (modified) (11 diffs)
• data/osm/MultipolygonBuilder.java (modified) (4 diffs)
• data/osm/visitor/paint/StyledMapRenderer.java (modified) (5 diffs)
• tools/Utils.java (modified) (2 diffs)

trunk/src/org/openstreetmap/josm/actions/CreateMultipolygonAction.java

@@ -43 +43 @@
  * Create multipolygon from selected ways automatically.
  *
- * New relation with type=multipolygon is created
+ * New relation with type=multipolygon is created.
  *
  * If one or more of ways is already in relation with type=multipolygon or the
- * way is not closed, then error is reported and no relation is created
+ * way is not closed, then error is reported and no relation is created.
  *
  * The "inner" and "outer" roles are guessed automatically. First, bbox is
@@ -93 +93 @@
             final Relation relation = commandAndRelation.b;
 
-
             // to avoid EDT violations
             SwingUtilities.invokeLater(new Runnable() {
@@ -103 +102 @@
                     // knows about the new relation before we try to select it.
                     // (Yes, we are already in event dispatch thread. But DatasetEventManager
-                    // uses 'SwingUtilities.invokeLater' to fire events so we have to do
-                    // the same.)
+                    // uses 'SwingUtilities.invokeLater' to fire events so we have to do the same.)
                     SwingUtilities.invokeLater(new Runnable() {
                         @Override
@@ -123 +121 @@
     }
 
-    /**
-     * The action button has been clicked
-     *
-     * @param e Action Event
-     */
     @Override
     public void actionPerformed(ActionEvent e) {
@@ -239 +232 @@
 
     /** Enable this action only if something is selected */
-    @Override protected void updateEnabledState() {
+    @Override
+    protected void updateEnabledState() {
         if (getCurrentDataSet() == null) {
             setEnabled(false);
@@ -252 +246 @@
       * @param selection the current selection, gets tested for emptyness
       */
-    @Override protected void updateEnabledState(Collection < ? extends OsmPrimitive > selection) {
+    @Override
+    protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
         if (update) {
             setEnabled(getSelectedMultipolygonRelation() != null);
@@ -265 +260 @@
      * @return <code>null</code>, if there was a problem with the ways.
      */
-    private static MultipolygonBuilder analyzeWays(Collection < Way > selectedWays, boolean showNotif) {
+    private static MultipolygonBuilder analyzeWays(Collection<Way> selectedWays, boolean showNotif) {
 
         MultipolygonBuilder pol = new MultipolygonBuilder();
@@ -324 +319 @@
      * @return a list of commands to execute
      */
-    public static List<Command> removeTagsFromWaysIfNeeded( Relation relation ) {
+    public static List<Command> removeTagsFromWaysIfNeeded(Relation relation) {
         Map<String, String> values = new HashMap<>(relation.getKeys());
 
@@ -342 +337 @@
                 outerWays.add(way);
 
-                for( String key : way.keySet() ) {
-                    if( !values.containsKey(key) ) { //relation values take precedence
+                for (String key : way.keySet()) {
+                    if (!values.containsKey(key)) { //relation values take precedence
                         values.put(key, way.get(key));
-                    } else if( !relation.hasKey(key) && !values.get(key).equals(way.get(key)) ) {
+                    } else if (!relation.hasKey(key) && !values.get(key).equals(way.get(key))) {
                         conflictingKeys.add(key);
                     }
@@ -353 +348 @@
 
         // filter out empty key conflicts - we need second iteration
-        if( !Main.pref.getBoolean("multipoly.alltags", false) )
-            for( RelationMember m : relation.getMembers() )
-                if( m.hasRole() && "outer".equals(m.getRole()) && m.isWay() )
-                    for( String key : values.keySet() )
-                        if( !m.getWay().hasKey(key) && !relation.hasKey(key) )
+        if (!Main.pref.getBoolean("multipoly.alltags", false))
+            for (RelationMember m : relation.getMembers())
+                if (m.hasRole() && "outer".equals(m.getRole()) && m.isWay())
+                    for (String key : values.keySet())
+                        if (!m.getWay().hasKey(key) && !relation.hasKey(key))
                             conflictingKeys.add(key);
 
-        for( String key : conflictingKeys )
+        for (String key : conflictingKeys)
             values.remove(key);
 
-        for( String linearTag : Main.pref.getCollection("multipoly.lineartagstokeep", DEFAULT_LINEAR_TAGS) )
+        for (String linearTag : Main.pref.getCollection("multipoly.lineartagstokeep", DEFAULT_LINEAR_TAGS))
             values.remove(linearTag);
 
@@ -402 +397 @@
         if (moveTags) {
             // add those tag values to the relation
-
             boolean fixed = false;
             Relation r2 = new Relation(relation);

trunk/src/org/openstreetmap/josm/data/osm/MultipolygonBuilder.java

@@ -12 +12 @@
 import java.util.List;
 import java.util.Set;
+import java.util.concurrent.Callable;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Future;
 
 import org.openstreetmap.josm.tools.Geometry;
 import org.openstreetmap.josm.tools.Geometry.PolygonIntersection;
 import org.openstreetmap.josm.tools.MultiMap;
+import org.openstreetmap.josm.tools.Pair;
+import org.openstreetmap.josm.tools.Utils;
 
 /**
@@ -24 +30 @@
  */
 public class MultipolygonBuilder {
+
+    private static final Pair<Integer, ExecutorService> THREAD_POOL =
+            Utils.newThreadPool("multipolygon_creation.numberOfThreads");
 
     /**
@@ -237 +246 @@
      */
     private String makeFromPolygons(List<JoinedPolygon> polygons) {
-        List<PolygonLevel> list = findOuterWaysRecursive(0, polygons);
+        List<PolygonLevel> list = findOuterWaysMultiThread(polygons);
 
         if (list == null) {
@@ -258 +267 @@
     }
 
+    private static Pair<Boolean, List<JoinedPolygon>> findInnerWaysCandidates(JoinedPolygon outerWay, Collection<JoinedPolygon> boundaryWays) {
+        boolean outerGood = true;
+        List<JoinedPolygon> innerCandidates = new ArrayList<>();
+
+        for (JoinedPolygon innerWay : boundaryWays) {
+            if (innerWay == outerWay) {
+                continue;
+            }
+
+            // Preliminary computation on bounds. If bounds do not intersect, no need to do a costly area intersection
+            if (outerWay.bounds.intersects(innerWay.bounds)) {
+                // Bounds intersection, let's see in detail
+                PolygonIntersection intersection = Geometry.polygonIntersection(outerWay.area, innerWay.area);
+
+                if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) {
+                    outerGood = false;  // outer is inside another polygon
+                    break;
+                } else if (intersection == PolygonIntersection.SECOND_INSIDE_FIRST) {
+                    innerCandidates.add(innerWay);
+                } else if (intersection == PolygonIntersection.CROSSING) {
+                    // ways intersect
+                    return null;
+                }
+            }
+        }
+
+        return new Pair<>(outerGood, innerCandidates);
+    }
+
     /**
      * Collects outer way and corresponding inner ways from all boundaries.
-     * @param boundaryWays
      * @return the outermostWay, or {@code null} if intersection found.
      */
-    private List<PolygonLevel> findOuterWaysRecursive(int level, Collection<JoinedPolygon> boundaryWays) {
-
-        //TODO: bad performance for deep nesting...
-        List<PolygonLevel> result = new ArrayList<>();
-
-        for (JoinedPolygon outerWay : boundaryWays) {
-
-            boolean outerGood = true;
-            List<JoinedPolygon> innerCandidates = new ArrayList<>();
-
-            for (JoinedPolygon innerWay : boundaryWays) {
-                if (innerWay == outerWay) {
-                    continue;
-                }
-
-                // Preliminary computation on bounds. If bounds do not intersect, no need to do a costly area intersection
-                if (outerWay.bounds.intersects(innerWay.bounds)) {
-                    // Bounds intersection, let's see in detail
-                    PolygonIntersection intersection = Geometry.polygonIntersection(outerWay.area, innerWay.area);
-
-                    if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND) {
-                        outerGood = false;  // outer is inside another polygon
-                        break;
-                    } else if (intersection == PolygonIntersection.SECOND_INSIDE_FIRST) {
-                        innerCandidates.add(innerWay);
-                    } else if (intersection == PolygonIntersection.CROSSING) {
-                        //ways intersect
+    private static List<PolygonLevel> findOuterWaysMultiThread(List<JoinedPolygon> boundaryWays) {
+        final List<PolygonLevel> result = new ArrayList<>();
+        final List<Worker> tasks = new ArrayList<>();
+        final int bucketsize = Math.max(32, boundaryWays.size()/THREAD_POOL.a/3);
+        final int noBuckets = (boundaryWays.size() + bucketsize - 1) / bucketsize;
+        final boolean singleThread = THREAD_POOL.a == 1 || noBuckets == 1;
+        for (int i=0; i<noBuckets; i++) {
+            int from = i*bucketsize;
+            int to = Math.min((i+1)*bucketsize, boundaryWays.size());
+            List<PolygonLevel> target = singleThread ? result : new ArrayList<PolygonLevel>(to - from);
+            tasks.add(new Worker(boundaryWays, from, to, target));
+        }
+        if (singleThread) {
+            try {
+                for (Worker task : tasks) {
+                    if (task.call() == null) {
                         return null;
                     }
                 }
-            }
-
-            if (!outerGood) {
-                continue;
-            }
-
-            //add new outer polygon
-            PolygonLevel pol = new PolygonLevel(outerWay, level);
-
-            //process inner ways
-            if (!innerCandidates.isEmpty()) {
-                List<PolygonLevel> innerList = this.findOuterWaysRecursive(level + 1, innerCandidates);
-                if (innerList == null) {
-                    return null; //intersection found
-                }
-
-                result.addAll(innerList);
-
-                for (PolygonLevel pl : innerList) {
-                    if (pl.level == level + 1) {
-                        pol.innerWays.add(pl.outerWay);
-                    }
-                }
-            }
-
-            result.add(pol);
-        }
-
+            } catch (Exception ex) {
+                throw new RuntimeException(ex);
+            }
+        } else if (!tasks.isEmpty()) {
+            try {
+                for (Future<List<PolygonLevel>> future : THREAD_POOL.b.invokeAll(tasks)) {
+                    List<PolygonLevel> res = future.get();
+                    if (res == null) {
+                        return null;
+                    }
+                    result.addAll(res);
+                }
+            } catch (InterruptedException | ExecutionException ex) {
+                throw new RuntimeException(ex);
+            }
+        }
         return result;
     }
+
+    private static class Worker implements Callable<List<PolygonLevel>> {
+
+        private final List<JoinedPolygon> input;
+        private final int from;
+        private final int to;
+        private final List<PolygonLevel> output;
+
+        public Worker(List<JoinedPolygon> input, int from, int to, List<PolygonLevel> output) {
+            this.input = input;
+            this.from = from;
+            this.to = to;
+            this.output = output;
+        }
+
+        /**
+         * Collects outer way and corresponding inner ways from all boundaries.
+         * @return the outermostWay, or {@code null} if intersection found.
+         */
+        private static List<PolygonLevel> findOuterWaysRecursive(int level, List<JoinedPolygon> boundaryWays) {
+
+            final List<PolygonLevel> result = new ArrayList<>();
+
+            for (JoinedPolygon outerWay : boundaryWays) {
+                if (processOuterWay(level, boundaryWays, result, outerWay) == null) {
+                    return null;
+                }
+            }
+
+            return result;
+        }
+
+        private static List<PolygonLevel> processOuterWay(int level, List<JoinedPolygon> boundaryWays, final List<PolygonLevel> result, JoinedPolygon outerWay) {
+            Pair<Boolean, List<JoinedPolygon>> p = findInnerWaysCandidates(outerWay, boundaryWays);
+            if (p == null) {
+                // ways intersect
+                return null;
+            }
+
+            if (p.a) {
+                //add new outer polygon
+                PolygonLevel pol = new PolygonLevel(outerWay, level);
+
+                //process inner ways
+                if (!p.b.isEmpty()) {
+                    List<PolygonLevel> innerList = findOuterWaysRecursive(level + 1, p.b);
+                    if (innerList == null) {
+                        return null; //intersection found
+                    }
+
+                    result.addAll(innerList);
+
+                    for (PolygonLevel pl : innerList) {
+                        if (pl.level == level + 1) {
+                            pol.innerWays.add(pl.outerWay);
+                        }
+                    }
+                }
+
+                result.add(pol);
+            }
+            return result;
+        }
+
+        @Override
+        public List<PolygonLevel> call() throws Exception {
+            for (int i = from; i<to; i++) {
+                if (processOuterWay(0, input, output, input.get(i)) == null) {
+                    return null;
+                }
+            }
+            return output;
+        }
+    }
 }

trunk/src/org/openstreetmap/josm/data/osm/visitor/paint/StyledMapRenderer.java

@@ -33 +33 @@
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
-import java.util.concurrent.Executors;
 import java.util.concurrent.Future;
 
@@ -73 +72 @@
 import org.openstreetmap.josm.tools.CompositeList;
 import org.openstreetmap.josm.tools.ImageProvider;
+import org.openstreetmap.josm.tools.Pair;
 import org.openstreetmap.josm.tools.Utils;
 
 /**
- * <p>A map renderer which renders a map according to style rules in a set of style sheets.</p>
- *
+ * A map renderer which renders a map according to style rules in a set of style sheets.
+ * @since 486
  */
 public class StyledMapRenderer extends AbstractMapRenderer {
 
-    final public static int noThreads;
-    final public static ExecutorService styleCreatorPool;
-
-    static {
-        noThreads = Main.pref.getInteger(
-                "mappaint.StyledMapRenderer.style_creation.numberOfThreads",
-                Runtime.getRuntime().availableProcessors());
-        styleCreatorPool = noThreads <= 1 ? null : Executors.newFixedThreadPool(noThreads);
-    }
+    private static final Pair<Integer, ExecutorService> THREAD_POOL =
+            Utils.newThreadPool("mappaint.StyledMapRenderer.style_creation.numberOfThreads");
 
     /**
@@ -1245 +1238 @@
                 Main.pref.getBoolean("mappaint.use-antialiasing", true) ?
                         RenderingHints.VALUE_ANTIALIAS_ON : RenderingHints.VALUE_ANTIALIAS_OFF);
-            
+
         highlightLineWidth = Main.pref.getInteger("mappaint.highlight.width", 4);
         highlightPointRadius = Main.pref.getInteger("mappaint.highlight.radius", 7);
@@ -1441 +1434 @@
         void process(List<? extends OsmPrimitive> prims) {
             final List<ComputeStyleListWorker> tasks = new ArrayList<>();
-            final int bucketsize = Math.max(100, prims.size()/noThreads/3);
+            final int bucketsize = Math.max(100, prims.size()/THREAD_POOL.a/3);
             final int noBuckets = (prims.size() + bucketsize - 1) / bucketsize;
-            final boolean singleThread = noThreads == 1 || noBuckets == 1;
+            final boolean singleThread = THREAD_POOL.a == 1 || noBuckets == 1;
             for (int i=0; i<noBuckets; i++) {
                 int from = i*bucketsize;
@@ -1458 +1451 @@
                     throw new RuntimeException(ex);
                 }
-            } else if (tasks.size() > 1) {
+            } else if (!tasks.isEmpty()) {
                 try {
-                    for (Future<List<StyleRecord>> future : styleCreatorPool.invokeAll(tasks)) {
-                            allStyleElems.addAll(future.get());
+                    for (Future<List<StyleRecord>> future : THREAD_POOL.b.invokeAll(tasks)) {
+                        allStyleElems.addAll(future.get());
                     }
                 } catch (InterruptedException | ExecutionException ex) {

trunk/src/org/openstreetmap/josm/tools/Utils.java

@@ -42 +42 @@
 import java.util.Iterator;
 import java.util.List;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
 import java.util.regex.Matcher;
 import java.util.regex.Pattern;
@@ -1064 +1066 @@
         return true;
     }
+
+    /**
+     * Returns a pair containing the number of threads (n), and a thread pool (if n > 1) to perform
+     * multi-thread computation in the context of the given preference key.
+     * @param pref The preference key
+     * @return a pair containing the number of threads (n), and a thread pool (if n > 1, null otherwise)
+     * @since 7423
+     */
+    public static Pair<Integer, ExecutorService> newThreadPool(String pref) {
+        int noThreads = Main.pref.getInteger(pref, Runtime.getRuntime().availableProcessors());
+        ExecutorService pool = noThreads <= 1 ? null : Executors.newFixedThreadPool(noThreads);
+        return new Pair<>(noThreads, pool);
+    }
 }