Changeset 3476 in josm

Timestamp:

Aug 29, 2010 12:58:38 PM (3 years ago)

Author:

jttt

Message:

QuadBuckets optimization - keep children as fields instead of 4-item array

Location:

trunk

Files:

• src/org/openstreetmap/josm/data/osm/QuadBuckets.java (modified) (15 diffs)
• test/unit/org/openstreetmap/josm/data/osm/QuadBucketsTest.java (modified) (2 diffs)

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

@@ -20 +20 @@
     private static boolean debug = false;
     private static final boolean consistency_testing = false;
+    private static final int NW_INDEX = 1;
+    private static final int NE_INDEX = 3;
+    private static final int SE_INDEX = 2;
+    private static final int SW_INDEX = 0;
     /*
      * Functions prefixed with __ need locking before
@@ -62 +66 @@
         final long quad;
         final QBLevel parent;
+        private boolean isLeaf = true;
 
         public List<T> content;
-        public QBLevel children[];
+        public QBLevel nw, ne, sw, se;
+
+        private QBLevel getChild(int index) {
+            switch (index) {
+            case NE_INDEX:
+                if (ne == null) {
+                    ne = new QBLevel(this, index);
+                }
+                return ne;
+            case NW_INDEX:
+                if (nw == null) {
+                    nw = new QBLevel(this, index);
+                }
+                return nw;
+            case SE_INDEX:
+                if (se == null) {
+                    se = new QBLevel(this, index);
+                }
+                return se;
+            case SW_INDEX:
+                if (sw == null) {
+                    sw = new QBLevel(this, index);
+                }
+                return sw;
+            default:
+                return null;
+            }
+        }
+
+        private QBLevel[] getChildren() {
+            // This is ugly and hackish.  But, it seems to work,
+            // and using an ArrayList here seems to cost us
+            // a significant performance penalty -- 50% in my
+            // testing.  Child access is one of the single
+            // hottest code paths in this entire class.
+            QBLevel[] result = (QBLevel[]) Array.newInstance(this.getClass(), QuadTiling.TILES_PER_LEVEL);
+            result[NW_INDEX] = nw;
+            result[NE_INDEX] = ne;
+            result[SW_INDEX] = sw;
+            result[SE_INDEX] = se;
+            return result;
+        }
+
         @Override
-        public String toString()
-        {
+        public String toString()  {
             return super.toString()+ "["+level+"]: " + bbox();
         }
@@ -117 +163 @@
                 if (index == -1)
                     return this;
-                if (children[index] == null) {
-                    children[index] = new QBLevel(this, index);
-                }
-                return children[index].findBucket(bbox);
+                return getChild(index).findBucket(bbox);
             }
         }
@@ -144 +187 @@
             }
         }
-        QBLevel[] newChildren()
-        {
-            // This is ugly and hackish.  But, it seems to work,
-            // and using an ArrayList here seems to cost us
-            // a significant performance penalty -- 50% in my
-            // testing.  Child access is one of the single
-            // hottest code paths in this entire class.
-            return (QBLevel[])Array.newInstance(this.getClass(), QuadTiling.TILES_PER_LEVEL);
-        }
         // Get the correct index for the given primitive
         // at the given level.  If the primitive can not
@@ -190 +224 @@
                         + this.bbox().width()+", "+this.bbox().height()+")");
             }
-            // deferring allocation of children until use
-            // seems a bit faster
-            //for (int i = 0; i < TILES_PER_LEVEL; i++)
-            //    children[i] = new QBLevel(this, i);
             List<T> tmpcontent = content;
             content = null;
-            children = newChildren();
+
             for (T o: tmpcontent) {
-                add(o);
-            }
-            if (!hasChildren()) {
-                // All items stay at this level (get_index == -1). Create at least first child to keep the contract
-                // that at least one child always exists
-                children[0] = new QBLevel(this, 0);
-            }
+                int index = get_index(o.getBBox(), level);
+                if (index == -1) {
+                    __add_content(o);
+                } else {
+                    getChild(index).doAdd(o);
+                }
+            }
+            isLeaf = false; // It's not enough to check children because all items could end up in this level (index == -1)
         }
 
@@ -254 +285 @@
          * is fast.  Runtime type determination must be slow.
          */
-        boolean isLeaf()
-        {
-            if (children == null)
-                return true;
-            return false;
-        }
+        boolean isLeaf() {
+            return isLeaf;
+        }
+        boolean hasChildren() {
+            return nw != null || ne != null || sw != null || se != null;
+        }
+
         QBLevel next_sibling()
         {
@@ -265 +297 @@
             if (parent == null)
                 return null;
-            if (parent.children == null)
-                return null;
             int __nr = 0;
-            for (QBLevel sibling : parent.children) {
+            for (QBLevel sibling : parent.getChildren()) {
                 __nr++;
                 int nr = __nr-1;
@@ -325 +355 @@
         {
             QBLevel ret = null;
-            for (QBLevel child : this.children) {
+            for (QBLevel child : getChildren()) {
                 if (child == null) {
                     continue;
@@ -358 +388 @@
                     get_index(o.getBBox(), level-1);
                     int nr = 0;
-                    for (QBLevel sibling : parent.children) {
+                    for (QBLevel sibling : parent.getChildren()) {
                         out("sibling["+ (nr++) +"]: " + sibling.bbox() + " this: " + (this==sibling));
                     }
@@ -389 +419 @@
                 }
                 return;
-            }
+            } else if (bbox().bounds(search_bbox)) {
+                search_cache = this;
+            }
+
             if (this.hasContent()) {
                 search_contents(search_bbox, result);
@@ -403 +436 @@
                 out("[" + level + "] not leaf, moving down");
             }
-            for (int i = 0; i < children.length; i++) {
-                QBLevel q = children[i];
-                if (debug) {
-                    out("child["+i+"]: " + q);
-                }
-                if (q == null) {
-                    continue;
-                }
-                if (debug) {
-                    System.out.print(i+": ");
-                }
-                q.search(search_bbox, result);
-                if (q.bbox().bounds(search_bbox)) {
-                    search_cache = q;
-                    // optimization: do not continue searching
-                    // other tiles if this one wholly contained
-                    // what we were looking for.
-                    if (debug) {
-                        out("break early");
-                    }
-                    break;
-                }
+
+            //TODO Coincidence vector should be calculated here and only buckets that match search_bbox should be checked
+
+            if (nw != null) {
+                nw.search(search_bbox, result);
+            }
+            if (ne != null) {
+                ne.search(search_bbox, result);
+            }
+            if (se != null) {
+                se.search(search_bbox, result);
+            }
+            if (sw != null) {
+                sw.search(search_bbox, result);
             }
         }
@@ -436 +461 @@
                 return -1;
 
+            QBLevel[] children = getChildren();
             for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) {
                 if (children[i] == find_this)
@@ -461 +487 @@
             return QuadTiling.tile2LatLon(this.quad);
         }
-        boolean hasChildren()
-        {
-            if (children == null)
-                return false;
-
-            for (QBLevel child : children) {
-                if (child != null)
-                    return true;
-            }
-            return false;
-        }
         void remove_from_parent()
         {
@@ -477 +492 @@
                 return;
 
-            int nr_siblings = 0;
-            for (int i = 0; i < parent.children.length; i++) {
-                QBLevel sibling = parent.children[i];
-                if (sibling != null) {
-                    nr_siblings++;
-                }
-                if (sibling != this) {
-                    continue;
-                }
-                if (!canRemove()) {
-                    abort("attempt to remove non-empty child: " + this.content + " " + Arrays.toString(this.children));
-                }
-                parent.children[i] = null;
-                nr_siblings--;
-            }
-            if (nr_siblings == 0) {
-                parent.children = null;
-            }
+            if (!canRemove()) {
+                abort("attempt to remove non-empty child: " + this.content + " " + Arrays.toString(this.getChildren()));
+            }
+
+            if (parent.nw == this) {
+                parent.nw = null;
+            } else if (parent.ne == this) {
+                parent.ne = null;
+            } else if (parent.sw == this) {
+                parent.sw = null;
+            } else if (parent.se == this) {
+                parent.se = null;
+            }
+
             if (parent.canRemove()) {
                 parent.remove_from_parent();
@@ -791 +802 @@
             }
         }
-        if (level.children != null) {
-            for (QBLevel child:level.children) {
-                printTreeRecursive(child, indent + 2);
-            }
+        for (QBLevel child:level.getChildren()) {
+            printTreeRecursive(child, indent + 2);
         }
     }

trunk/test/unit/org/openstreetmap/josm/data/osm/QuadBucketsTest.java

@@ -4 +4 @@
 import java.io.FileInputStream;
 import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Iterator;
 import java.util.List;
 
+import org.fest.reflect.core.Reflection;
+import org.fest.reflect.reference.TypeRef;
 import org.junit.Assert;
 import org.junit.Test;
@@ -20 +24 @@
         List<Way> allWays = new ArrayList<Way>(ds.getWays());
         List<Relation> allRelations = new ArrayList<Relation>(ds.getRelations());
+
+        QuadBuckets<Node> nodes = Reflection.field("nodes").ofType(new TypeRef<QuadBuckets<Node>>() {}).in(ds).get();
+        QuadBuckets<Way> ways = Reflection.field("ways").ofType(new TypeRef<QuadBuckets<Way>>() {}).in(ds).get();
+        Collection<Relation> relations = Reflection.field("relations").ofType(new TypeRef<Collection<Relation>>() {}).in(ds).get();
+
+        int expectedCount = allNodes.size();
         for (OsmPrimitive o: allNodes) {
             ds.removePrimitive(o);
+            checkIterator(nodes, --expectedCount);
         }
+        expectedCount = allWays.size();
         for (OsmPrimitive o: allWays) {
             ds.removePrimitive(o);
+            checkIterator(ways, --expectedCount);
         }
         for (OsmPrimitive o: allRelations) {
             ds.removePrimitive(o);
         }
+        Assert.assertTrue(nodes.isEmpty());
+        Assert.assertTrue(ways.isEmpty());
+        Assert.assertTrue(relations.isEmpty());
+    }
 
-        Assert.assertTrue(ds.getNodes().isEmpty());
-        Assert.assertTrue(ds.getWays().isEmpty());
-        Assert.assertTrue(ds.getRelations().isEmpty());
+    private void checkIterator(Collection<? extends OsmPrimitive> col, int expectedCount) {
+        int count = 0;
+        Iterator<? extends OsmPrimitive> it = col.iterator();
+        while (it.hasNext()) {
+            count++;
+            it.next();
+        }
+        Assert.assertEquals(expectedCount, count);
     }