Repository: graphhopper/graphhopper (java)

Issue:
CH preparation for foot is too slow
Unfortunately #2491 introduced a performance regression for the CH preparation of the foot profile. It used to take around 630s and for current master it takes more than 2000s. I recently added a performance measurement for foot here: 1ec3397bfb832f07202136f00dc81182fa5896aa, 92842baaf07f3d81cbf5925b104db51713417aaa. The query time seems unaffected for our test map of Germany but turned out to be also slower when using an OSM file of the entire planet.

The current workaround is to disable neighbor updates and increase the maximum of visited nodes, i.e. in config.yml use the following parameters:

```yaml
  prepare.ch.node.max_visited_nodes_heuristic: 200
  prepare.ch.node.max_visited_nodes_contraction: 500
  prepare.ch.updates.periodic: 20
  prepare.ch.updates.lazy: 100
  prepare.ch.updates.neighbor: 0
```

Unfortunately this slows down the CH preparation for car and increases the number of shortcuts compared to the current default parameters. 

Two things we could do to improve this:

1) limit the maximum number of neighbor updates per node
2) make the number of maximum visited nodes depend on the mean degree of the graph again as we used to do (but without the bugs we fixed in #2491)

Another option might be to allow setting these parameters per profile, but currently I'd prefer a solution that works reasonably well for all profiles.


Pull request description:
Speed up CH for foot
Fixes #2507.

> Two things we could do to improve this:

After lots of experimenting I arrived at a version that works well for car and foot (and country_rules as well) using default parameters (the same for both profiles). I still use neighbor updates as in #2491, because this allows reducing the shortcut numbers, but I went back to adjusting the maximum number of settled nodes based on the mean degree of the graph instead of keeping it constant throughout the entire preparation. The factor that is used to determine the number of maximum number of settled nodes from the mean degree is now a tuning parameter (actually two: one for priority calculation and one for the contraction). There is also another new parameter that allows limiting the number of neighbor updates *per node*.

To benchmark my results I used this commit: 7082297bd380f76b1a48754d1f50df82f42359cd, so just before #2491. I got this:

```
  vehicle      map   t_total  t_period  t_neighbor   t_lazy  t_contr  shortcuts  query  failed       dummy
0     car  germany    176.81     76.84       32.06    18.15    43.96    7380812  1.356      85    69376783
1     car   europe   1526.48    578.80      323.31   196.91   381.55   60378311  1.514      85    69250710
2     car   planet   5518.90   1961.99     1290.32   749.15  1363.71  223885440  1.643      24    69539356
3    foot  germany    866.87    258.30      295.11   147.44   155.00   20771335  4.220      57  1032616176
4    foot   europe   5225.88   1422.77     1797.37   926.19  1003.18  119770559  3.688      58  1030103581
5    foot   planet  13389.75   4269.26     4070.32  2312.93  2532.51  322852419  3.779      19  1031819233
```

`t_total` is the CH preparation time in seconds, `shortcuts` the number of created shortcuts and `query` the average query time using random queries in Bavaria in ms.

For this branch I got for car/planet (I copied the benchmark data from above for better readability)

```
  vehicle      map  neighbor_max   t_total  t_period  t_neighbor   t_lazy  t_contr  shortcuts  query  failed       dummy
0     car  planet             5   4680.12    420.96     2322.51   773.62  1027.22  203305137  1.582      24    69539359
1     car  planet             2   4517.43    413.17     1825.70  1013.56  1115.64  210875372  1.500      24    69539361
--- benchmark
2     car  planet             -   5518.90   1961.99     1290.32   749.15  1363.71  223885440  1.643      24    69539356
```

and for foot/planet:
```
  vehicle      map  neighbor_max   t_total  t_period  t_neighbor   t_lazy  t_contr  shortcuts  query  failed       dummy
0    foot  planet             5  11990.42    579.07     7342.81  1990.92  1835.28  302747715  3.986      19  1031819232
1    foot  planet             2  10260.37    596.18     4598.70  2832.17  2040.38  312983091  3.806      19  1031819231
-- benchmark
2    foot  planet             -  13389.75   4269.26     4070.32  2312.93  2532.51  322852419  3.779      19  1031819233
```

We see that for both the `foot` and `car` profile the preparation time is faster, the shortcuts are less and the query time is either about equal or slightly faster, depending on the new parameter `neighbor_max` that I set to `2` and `5` here.

For Europe the new branch also works better:

```
  vehicle     map  neighbor_max  t_total  t_period  t_neighbor  t_lazy  t_contr  shortcuts  query  failed     dummy
0     car  europe            -1  1131.17    101.71      563.12  164.26   261.93   55406484  1.357      85  69250710
1     car  europe            10  1117.52    101.34      548.40  164.70   262.40   55417098  1.362      85  69250708
2     car  europe             5  1089.58    101.92      508.55  168.11   270.14   55518276  1.391      85  69250708
3     car  europe             2  1044.15    101.27      409.84  209.32   281.53   57037606  1.391      85  69250709
--- benchmark
4     car   europe            -  1526.48    578.80      323.31   196.91   381.55   60378311  1.514      85    69250710
```

```
  vehicle     map neighbor_max  t_total  t_period  t_neighbor   t_lazy  t_contr  shortcuts  query  failed       dummy
0    foot  europe           -1  6885.67    177.27     5343.68   635.52   663.92  113131197  3.327      58  1030103571
1    foot  europe           10  5373.92    175.20     3813.17   648.22   671.08  113172449  3.337      58  1030103574
2    foot  europe            5  4586.25    177.22     2947.22   739.54   656.37  113501003  3.461      58  1030103579
3    foot  europe            2  3715.17    177.17     1719.40  1018.65   732.45  116806227  3.503      58  1030103578
--- benchmark
4    foot  europe            -  5225.88   1422.77     1797.37   926.19  1003.18  119770559  3.688      58  1030103581
```

Using `neighbor_max` we actually can choose between faster preparation, less shortcuts and faster queries. For now I chose `neighbor_max=2` as default.

Including country rules (for Germany), c.f. #2375, I get this:

before:

```
   vehicle     pbf  periodic   lazy  neighbor  edge_diff  orig_edges   t_total  t_period  t_neighbor  t_lazy  t_contr  shortcuts  query  failed     dummy country_rules
0     car  germany      20.0   10.0      20.0       10.0         1.0    231.20    103.13       40.62   21.60    59.70    7255266  1.356      85  96031267          true
1     car  germany      20.0   10.0      20.0       10.0         1.0    177.70     77.16       32.32   18.29    44.19    7382932  1.372      85  69376777         false
```

after:
```
   vehicle      pbf  periodic   lazy  neighbor  neighbor_max  edge_diff  orig_edges  mpf_heur  mpf_contr  t_total  t_period  t_neighbor  t_lazy  t_contr  shortcuts  query  failed     dummy country_rules
0      car  germany       0.0  100.0     100.0           2.0       10.0         1.0       5.0      200.0    188.57     14.73       48.16   22.94    97.25    6754789  1.354      85  96031262          true
1      car  germany       0.0  100.0     100.0           2.0       10.0         1.0       5.0      200.0    124.32     14.89       46.81   22.93    33.74    7051462  1.387      85  69376780         false
```

Also here we get less shortcuts and a faster preparation time than before without slowing down the queries, no matter whether country rules are enabled. The `GermanyCountryRule` still does slow down the preparation by around 50%. This can be improved by decreasing the maximum poll factor for contraction (`mpf_contr`). Note how `t_contr` goes down from around 97s to 61s while the number of shortcuts goes only slightly up (~1%)

```
   vehicle      pbf  periodic   lazy  neighbor  neighbor_max  edge_diff  orig_edges  mpf_heur  mpf_contr  t_total  t_period  t_neighbor  t_lazy  t_contr  shortcuts  query  failed     dummy country_rules
0      car  germany       0.0  100.0     100.0           2.0       10.0         1.0       5.0      150.0    158.43     14.93       44.20   21.45    72.14    6785332  1.374      85  96031263    true
1      car  germany       0.0  100.0     100.0           2.0       10.0         1.0       5.0      100.0    147.03     14.31       45.03   21.57    61.12    6839704  1.314      85  96031261    true
```

Patch:
diff --git a/core/src/main/java/com/graphhopper/routing/ch/CHParameters.java b/core/src/main/java/com/graphhopper/routing/ch/CHParameters.java
index 5f7b7e718..f3baa7976 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/CHParameters.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/CHParameters.java
@@ -7,13 +7,14 @@ public final class CHParameters {
     public static final String PERIODIC_UPDATES = Parameters.CH.PREPARE + "updates.periodic";
     public static final String LAST_LAZY_NODES_UPDATES = Parameters.CH.PREPARE + "updates.lazy";
     public static final String NEIGHBOR_UPDATES = Parameters.CH.PREPARE + "updates.neighbor";
+    public static final String NEIGHBOR_UPDATES_MAX = Parameters.CH.PREPARE + "updates.neighbor_max";
     public static final String CONTRACTED_NODES = Parameters.CH.PREPARE + "contracted_nodes";
     public static final String LOG_MESSAGES = Parameters.CH.PREPARE + "log_messages";
     // node contraction, node-based
     public static final String EDGE_DIFFERENCE_WEIGHT = Parameters.CH.PREPARE + "node.edge_difference_weight";
     public static final String ORIGINAL_EDGE_COUNT_WEIGHT = Parameters.CH.PREPARE + "node.original_edge_count_weight";
-    public static final String MAX_VISITED_NODES_HEURISTIC = Parameters.CH.PREPARE + "node.max_visited_nodes_heuristic";
-    public static final String MAX_VISITED_NODES_CONTRACTION = Parameters.CH.PREPARE + "node.max_visited_nodes_contraction";
+    public static final String MAX_POLL_FACTOR_HEURISTIC_NODE = Parameters.CH.PREPARE + "node.max_poll_factor_heuristic";
+    public static final String MAX_POLL_FACTOR_CONTRACTION_NODE = Parameters.CH.PREPARE + "node.max_poll_factor_contraction";
     // node contraction, edge-based
     public static final String EDGE_QUOTIENT_WEIGHT = Parameters.CH.PREPARE + "edge.edge_quotient_weight";
     public static final String ORIGINAL_EDGE_QUOTIENT_WEIGHT = Parameters.CH.PREPARE + "edge.original_edge_quotient_weight";
diff --git a/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java b/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java
index 3cfdb7b9b..f4f5712b7 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/NodeBasedNodeContractor.java
@@ -58,8 +58,8 @@ class NodeBasedNodeContractor implements NodeContractor {
     private void extractParams(PMap pMap) {
         params.edgeDifferenceWeight = pMap.getFloat(EDGE_DIFFERENCE_WEIGHT, params.edgeDifferenceWeight);
         params.originalEdgesCountWeight = pMap.getFloat(ORIGINAL_EDGE_COUNT_WEIGHT, params.originalEdgesCountWeight);
-        params.maxVisitedNodesHeuristic = pMap.getInt(MAX_VISITED_NODES_HEURISTIC, params.maxVisitedNodesHeuristic);
-        params.maxVisitedNodesContraction = pMap.getInt(MAX_VISITED_NODES_CONTRACTION, params.maxVisitedNodesContraction);
+        params.maxPollFactorHeuristic = pMap.getDouble(MAX_POLL_FACTOR_HEURISTIC_NODE, params.maxPollFactorHeuristic);
+        params.maxPollFactorContraction = pMap.getDouble(MAX_POLL_FACTOR_CONTRACTION_NODE, params.maxPollFactorContraction);
     }
 
     @Override
@@ -97,7 +97,7 @@ class NodeBasedNodeContractor implements NodeContractor {
         // originalEdgesCount = σ(v) := sum_{ (u,w) ∈ shortcuts(v) } of r(u, w)
         shortcutsCount = 0;
         originalEdgesCount = 0;
-        findAndHandleShortcuts(node, this::countShortcuts, params.maxVisitedNodesHeuristic);
+        findAndHandleShortcuts(node, this::countShortcuts, (int) (meanDegree * params.maxPollFactorHeuristic));
 
         // from shortcuts we can compute the edgeDifference
         // # low influence: with it the shortcut creation is slightly faster
@@ -116,7 +116,7 @@ class NodeBasedNodeContractor implements NodeContractor {
 
     @Override
     public IntContainer contractNode(int node) {
-        long degree = findAndHandleShortcuts(node, this::addOrUpdateShortcut, params.maxVisitedNodesContraction);
+        long degree = findAndHandleShortcuts(node, this::addOrUpdateShortcut, (int) (meanDegree * params.maxPollFactorContraction));
         insertShortcuts(node);
         // put weight factor on meanDegree instead of taking the average => meanDegree is more stable
         meanDegree = (meanDegree * 2 + degree) / 3;
@@ -310,11 +310,10 @@ class NodeBasedNodeContractor implements NodeContractor {
         private float edgeDifferenceWeight = 10;
         private float originalEdgesCountWeight = 1;
         // these values seemed to work best for planet (fast prep without compromising too much for the query time)
-        // higher values can further decrease the number of shortcuts and improve the query time, but only by a few
-        // percent and at the cost of a longer preparation. for smaller maps smaller values can work even better, i.e.
-        // try 20/100 or similar.
-        private int maxVisitedNodesHeuristic = 30;
-        private int maxVisitedNodesContraction = 200;
+        // higher values can further decrease the number of shortcuts and improve the query time, but normally at the
+        // cost of a longer preparation (see #2514)
+        private double maxPollFactorHeuristic = 5;
+        private double maxPollFactorContraction = 200;
     }
 
     private static class Shortcut {
diff --git a/core/src/main/java/com/graphhopper/routing/ch/PrepareContractionHierarchies.java b/core/src/main/java/com/graphhopper/routing/ch/PrepareContractionHierarchies.java
index 27949217d..bf7beaf3f 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/PrepareContractionHierarchies.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/PrepareContractionHierarchies.java
@@ -97,6 +97,7 @@ public class PrepareContractionHierarchies {
         params.setPeriodicUpdatesPercentage(pMap.getInt(PERIODIC_UPDATES, params.getPeriodicUpdatesPercentage()));
         params.setLastNodesLazyUpdatePercentage(pMap.getInt(LAST_LAZY_NODES_UPDATES, params.getLastNodesLazyUpdatePercentage()));
         params.setNeighborUpdatePercentage(pMap.getInt(NEIGHBOR_UPDATES, params.getNeighborUpdatePercentage()));
+        params.setMaxNeighborUpdates(pMap.getInt(NEIGHBOR_UPDATES_MAX, params.getMaxNeighborUpdates()));
         params.setNodesContractedPercentage(pMap.getInt(CONTRACTED_NODES, params.getNodesContractedPercentage()));
         params.setLogMessagesPercentage(pMap.getInt(LOG_MESSAGES, params.getLogMessagesPercentage()));
         return this;
@@ -289,13 +290,14 @@ public class PrepareContractionHierarchies {
                 // skipped nodes are already set to maxLevel
                 break;
 
+            int neighborCount = 0;
             // there might be multiple edges going to the same neighbor nodes -> only calculate priority once per node
             for (IntCursor neighbor : neighbors) {
-                int nn = neighbor.value;
-                if (neighborUpdate && rand.nextInt(100) < params.getNeighborUpdatePercentage()) {
+                if (neighborUpdate && (params.getMaxNeighborUpdates() < 0 || neighborCount < params.getMaxNeighborUpdates()) && rand.nextInt(100) < params.getNeighborUpdatePercentage()) {
+                    neighborCount++;
                     neighborUpdateSW.start();
-                    float priority = calculatePriority(nn);
-                    sortedNodes.update(nn, priority);
+                    float priority = calculatePriority(neighbor.value);
+                    sortedNodes.update(neighbor.value, priority);
                     neighborUpdateSW.stop();
                 }
             }
@@ -508,6 +510,11 @@ public class PrepareContractionHierarchies {
          * times, but the node priorities will be more up-to-date.
          */
         private int neighborUpdatePercentage;
+        /**
+         * Specifies the maximum number of neighbor updates per contracted node. For example for the foot profile we
+         * see a large number of neighbor updates that can be limited with this setting. -1 means unlimited.
+         */
+        private int maxNeighborUpdates;
         /**
          * Defines how many nodes (percentage) should be contracted. A value of 20 means only the first 20% of all nodes
          * will be contracted. Higher values here mean longer preparation times, but faster queries (because the
@@ -524,17 +531,18 @@ public class PrepareContractionHierarchies {
         static Params forTraversalMode(TraversalMode traversalMode) {
             if (traversalMode.isEdgeBased()) {
                 // todo: optimize
-                return new Params(0, 100, 0, 100, 5);
+                return new Params(0, 100, 0, -1, 100, 5);
             } else {
-                return new Params(0, 0, 100, 100, 20);
+                return new Params(0, 100, 100, 2, 100, 20);
             }
         }
 
-        private Params(int periodicUpdatesPercentage, int lastNodesLazyUpdatePercentage, int neighborUpdatePercentage,
+        private Params(int periodicUpdatesPercentage, int lastNodesLazyUpdatePercentage, int neighborUpdatePercentage, int maxNeighborUpdates,
                        int nodesContractedPercentage, int logMessagesPercentage) {
             setPeriodicUpdatesPercentage(periodicUpdatesPercentage);
             setLastNodesLazyUpdatePercentage(lastNodesLazyUpdatePercentage);
             setNeighborUpdatePercentage(neighborUpdatePercentage);
+            setMaxNeighborUpdates(maxNeighborUpdates);
             setNodesContractedPercentage(nodesContractedPercentage);
             setLogMessagesPercentage(logMessagesPercentage);
         }
@@ -566,6 +574,14 @@ public class PrepareContractionHierarchies {
             this.neighborUpdatePercentage = neighborUpdatePercentage;
         }
 
+        int getMaxNeighborUpdates() {
+            return maxNeighborUpdates;
+        }
+
+        void setMaxNeighborUpdates(int maxNeighborUpdates) {
+            this.maxNeighborUpdates = maxNeighborUpdates;
+        }
+
         int getNodesContractedPercentage() {
             return nodesContractedPercentage;
         }


Test patch:
diff --git a/core/src/test/java/com/graphhopper/GraphHopperTest.java b/core/src/test/java/com/graphhopper/GraphHopperTest.java
index 9f9db11e8..6298b5143 100644
--- a/core/src/test/java/com/graphhopper/GraphHopperTest.java
+++ b/core/src/test/java/com/graphhopper/GraphHopperTest.java
@@ -95,8 +95,8 @@ public class GraphHopperTest {
             ASTAR + ",false,444",
             DIJKSTRA_BI + ",false,228",
             ASTAR_BI + ",false,184",
-            ASTAR_BI + ",true,67",
-            DIJKSTRA_BI + ",true,65"
+            ASTAR_BI + ",true,61",
+            DIJKSTRA_BI + ",true,61"
     })
     public void testMonacoDifferentAlgorithms(String algo, boolean withCH, int expectedVisitedNodes) {
         final String vehicle = "car";
diff --git a/tools/src/main/java/com/graphhopper/tools/CHImportTest.java b/tools/src/main/java/com/graphhopper/tools/CHImportTest.java
new file mode 100644
index 000000000..cca9839a2
--- /dev/null
+++ b/tools/src/main/java/com/graphhopper/tools/CHImportTest.java
@@ -0,0 +1,102 @@
+/*
+ *  Licensed to GraphHopper GmbH under one or more contributor
+ *  license agreements. See the NOTICE file distributed with this work for
+ *  additional information regarding copyright ownership.
+ *
+ *  GraphHopper GmbH 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 com.graphhopper.tools;
+
+import com.graphhopper.GHRequest;
+import com.graphhopper.GHResponse;
+import com.graphhopper.GraphHopper;
+import com.graphhopper.GraphHopperConfig;
+import com.graphhopper.config.CHProfile;
+import com.graphhopper.config.Profile;
+import com.graphhopper.routing.ch.CHParameters;
+import com.graphhopper.routing.util.countryrules.CountryRuleFactory;
+import com.graphhopper.util.MiniPerfTest;
+import com.graphhopper.util.PMap;
+import com.graphhopper.util.exceptions.ConnectionNotFoundException;
+import com.graphhopper.util.exceptions.PointNotFoundException;
+import com.graphhopper.util.shapes.BBox;
+import com.graphhopper.util.shapes.GHPoint;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Random;
+import java.util.concurrent.atomic.AtomicInteger;
+
+public class CHImportTest {
+    public static void main(String[] args) {
+        System.out.println("running for args: " + Arrays.toString(args));
+        PMap map = PMap.read(args);
+        String vehicle = map.getString("vehicle", "car");
+        GraphHopperConfig config = new GraphHopperConfig(map);
+        config.putObject("datareader.file", map.getString("pbf", "map-matching/files/leipzig_germany.osm.pbf"));
+        config.putObject("graph.location", map.getString("gh", "ch-import-test-gh"));
+        config.setProfiles(Arrays.asList(
+                new Profile(vehicle).setVehicle(vehicle).setWeighting("fastest")
+        ));
+        config.setCHProfiles(Collections.singletonList(new CHProfile(vehicle)));
+        config.putObject(CHParameters.PERIODIC_UPDATES, map.getInt("periodic", 0));
+        config.putObject(CHParameters.LAST_LAZY_NODES_UPDATES, map.getInt("lazy", 100));
+        config.putObject(CHParameters.NEIGHBOR_UPDATES, map.getInt("neighbor", 100));
+        config.putObject(CHParameters.NEIGHBOR_UPDATES_MAX, map.getInt("neighbor_max", 2));
+        config.putObject(CHParameters.CONTRACTED_NODES, map.getInt("contracted", 100));
+        config.putObject(CHParameters.LOG_MESSAGES, map.getInt("logs", 20));
+        config.putObject(CHParameters.EDGE_DIFFERENCE_WEIGHT, map.getDouble("edge_diff", 10));
+        config.putObject(CHParameters.ORIGINAL_EDGE_COUNT_WEIGHT, map.getDouble("orig_edge", 1));
+        config.putObject(CHParameters.MAX_POLL_FACTOR_HEURISTIC_NODE, map.getDouble("mpf_heur", 5));
+        config.putObject(CHParameters.MAX_POLL_FACTOR_CONTRACTION_NODE, map.getDouble("mpf_contr", 200));
+        GraphHopper hopper = new GraphHopper();
+        hopper.init(config);
+        if (map.getBool("use_country_rules", false))
+            // note that using this requires a new import of the base graph!
+            hopper.setCountryRuleFactory(new CountryRuleFactory());
+        hopper.importOrLoad();
+        runQueries(hopper, vehicle);
+    }
+
+    private static void runQueries(GraphHopper hopper, String profile) {
+        // Bavaria, but trying to avoid regions that are not covered
+        BBox bounds = new BBox(10.508422, 12.326602, 47.713457, 49.940615);
+        int numQueries = 10_000;
+        long seed = 123;
+        Random rnd = new Random(seed);
+        AtomicInteger notFoundCount = new AtomicInteger();
+        MiniPerfTest test = new MiniPerfTest().setIterations(numQueries).start((warmup, run) -> {
+            GHPoint from = getRandomPoint(rnd, bounds);
+            GHPoint to = getRandomPoint(rnd, bounds);
+            GHRequest req = new GHRequest(from, to).setProfile(profile);
+            GHResponse rsp = hopper.route(req);
+            if (rsp.hasErrors()) {
+                if (rsp.getErrors().stream().anyMatch(t -> !(t instanceof PointNotFoundException || t instanceof ConnectionNotFoundException)))
+                    throw new IllegalStateException("Unexpected error: " + rsp.getErrors().toString());
+                notFoundCount.incrementAndGet();
+                return 0;
+            } else {
+                return (int) rsp.getBest().getRouteWeight();
+            }
+        });
+        System.out.println("Total queries: " + numQueries + ", Failed queries: " + notFoundCount.get());
+        System.out.println(test.getReport());
+    }
+
+    private static GHPoint getRandomPoint(Random rnd, BBox bounds) {
+        double lat = bounds.minLat + rnd.nextDouble() * (bounds.maxLat - bounds.minLat);
+        double lon = bounds.minLon + rnd.nextDouble() * (bounds.maxLon - bounds.minLon);
+        return new GHPoint(lat, lon);
+    }
+}
\ No newline at end of file