sortGraph=false => too slow, sortGraph=true => java.lang.OutOfMemoryError

Hi,

we’re trying to get Graphhopper running with road data (nodes: 1 687 333, edges: 1 037 892, according to graphhopper). We use the postgres adapter (https://github.com/mbasa/graphhopper/tree/postgis-4.0/reader-postgis/src) and a simple (default) config:

graphhopper:

profiles:
- name: car
vehicle: car
weighting: fastest

profiles_ch:
- profile: car

profiles_lm: []
prepare.min_network_size: 200
routing.non_ch.max_waypoint_distance: 1000000
graph.dataaccess: RAM_STORE

The problem seems to be memory/performance related.

  • When sortGraph=false and increasing the following parameters:
    private int preciseIndexResolution = 300*100; // 300
    private int maxRegionSearch = 4*40; // 4
    // for prepare
    private int minNetworkSize = 200; // original: 200

We reach to a point where LocationIndexTree#prepareInMemConstructionIndex is executed.
The problem however is that this is painfully slow: it takes about 1second for 10 random edge iterations. It seems inMem.addToAllTilesOnLine in this loop (https://github.com/graphhopper/graphhopper/blob/27b9ad3edf8c2e8c07c946f6293b1c265b3aa6b4/core/src/main/java/com/graphhopper/storage/index/LocationIndexTree.java#L202) is slow:

loop for 44points took=1614ms
loop for 9points took=487ms
loop for 28points took=1263ms
loop for 1points took=0ms
loop for 21points took=952ms

Since we have 1mil+ edges this is not a feasible approach. We also needed to increase these parameters because otherwise we get an error of the class SpatialKeyAlgo: allBits is too big for this implementation: 52.

  • When sortGraph=true, we get an java.lang.OutOfMemoryError when IndexStructureInfo.create is executed. We assumed that sorting the graph might speedup, but are unable to get it working wit 8GB ram.

We are not sure how this sorting impacts Graphhopper, but our main problem is that we cannot get past the index creation for our dataset because it is very slow.

Below is a partial log output. Anyone knows how to optimise or what can be done to get it working?

/Users/…/Library/Java/JavaVirtualMachines/openjdk-15.0.1/Contents/Home/bin/java -ea -Xmx15096m -Xmx8096m -Xms8096m -Duser.language=en -Didea.test.cyclic.buffer.size=4194304 -Dfile.encoding=UTF-8 -classpath /Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar: …

2022-01-03 14:22:47 INFO GraphHopperPostgis:625 - version 4.0|2022-01-03T12:44:56Z (7,20,5,4,5,7)
2022-01-03 14:22:47 INFO GraphHopperPostgis:627 - graph car|RAM_STORE|2D|no_turn_cost|, details:edges:0(0MB), nodes:0(0MB), name:(0MB), geo:0(0MB), bounds:1.7976931348623157E308,-1.7976931348623157E308,1

2022-01-03 14:23:05 INFO OSMPostgisReader:146 - 8 900 000 (junctions), junctionMap:8 894 341 totalMB:8096, usedMB:1319
2022-01-03 14:23:05 INFO OSMPostgisReader:164 - Number of junction points : 1687332
processed junctions
2022-01-03 14:23:05 INFO PostgisReader:134 - Opening DB connection to postgis localhost:5432 to database locatieservices2 schema public
2022-01-03 14:23:05 INFO PostgisReader:103 - Getting the feature iterator for graphhopper
2022-01-03 14:23:23 INFO OSMPostgisReader:227 - 1 000 000 (edges) totalMB:8096, usedMB:2692
processed roads
2022-01-03 14:23:23 INFO PostgisReader:134 - Opening DB connection to postgis localhost:5432 to database locatieservices2 schema public
2022-01-03 14:23:23 INFO PostgisReader:103 - Getting the feature iterator for graphhopper
processed restrictions
2022-01-03 14:23:33 INFO OSMPostgisReader:351 - Finished reading. Zero Counter 0 totalMB:8096, usedMB:3311
finished reading
imported osm
2022-01-03 14:23:33 INFO PrepareRoutingSubnetworks:90 - Start marking subnetworks, prepare.min_network_size: 200, nodes: 1 687 333, edges: 1 037 892, jobs: [my_car_subnetwork|fastest|car], totalMB:8096, usedMB:3311
2022-01-03 14:23:34 INFO PrepareRoutingSubnetworks:108 - my_car - Found 649686 subnetworks (0 single edges and 649686 components with more than one edge, total nodes: 2075784), took: 0.56943756s
2022-01-03 14:23:34 INFO PrepareRoutingSubnetworks:150 - my_car - Marked 649685 subnetworks (biggest: 210 edges) → 1 components(s) remain (smallest: 240, biggest: 240 edges), total marked edges: 1037772, took: 0.27964166s
2022-01-03 14:23:34 INFO PrepareRoutingSubnetworks:95 - Finished finding and marking subnetworks for 1 jobs, took: 0.8502388s, totalMB:8096, usedMB:2895
2022-01-03 14:23:34 INFO GraphHopperPostgis:1176 - nodes: 1 687 333, edges: 1 037 892
cleanup
sortGraph=false
interpolateBridgesTunnelsAndFerries
initLocationIndex
LocationIndexTree
setResolution
setMaxRegionSearch
loadExisting
ensureWriteAccess
prepareIndex
2022-01-03 14:26:34 INFO LocationIndexTree:187 - creating IndexStructureInfo.create(bounds=3.0E-6,261489.846,5.03E-4,260803.533, minResolutionInMeter=30000)
2022-01-03 14:26:34 INFO LocationIndexTree:189 - creating InMemConstructionIndex=IndexStructureInfo{entries=10, shiftssize=10, shifts=[4, 4, 4, 4, 4, 4, 4, 4, 4, 2], pixelGridTraversal=com.graphhopper.storage.index.PixelGridTraversal@40238dd0, keyAlgo=com.graphhopper.geohash.SpatialKeyAlgo@7776ab, bounds=3.0E-6,261489.846,5.03E-4,260803.533, parts=524288})

You are using a fork and should probably ask the maintainer there. Also it is a quite old version of GH and additionally you changed many core parameters. I wouldn’t change so many things at once. Start without changes and see when it stops working.

And especially the index parameters shouldn’t be changed by such a large factor (why not use the defaults?):

private int preciseIndexResolution = 300*100; // 300
private int maxRegionSearch = 4*40; // 4

Also this setting does not make sense:

-Xmx15096m -Xmx8096m

Hi @karussell,

thanks for the reply,
however i’m not sure why you say it is and old version as it is based on the latest release GraphHopper 4.0? What is the latest version instead?

Also, if I don’t change the parameters we get the following error:
SpatialKeyAlgo : allBits is too big for this implementation: 52 .

I actually figured out that the runs become very fast (like 2mins for all edges) once I increase the precision:
private int preciseIndexResolution = 300*100000;
and keep the original
private int maxRegionSearch = 4;

now I am able to do mapmatching, but the matching fails

runs=1037880
runs=1037890
2022-01-04 10:32:29 INFO LocationIndexTree:174 - location index created in 102.95165s, size:402 773 844, leafs:512, precision:30000000, depth:5, checksum:1468769, entries:[16, 16, 16, 16, 4], entriesPerLeaf:786667.7
returning index
importPublicTransit
lmPreparationHandler createPreparations
chPreparationHandler createPreparations
postProcessing
2022-01-04 10:32:29 INFO GraphHopperPostgis:1190 - flushing graph car|RAM_STORE|2D|no_turn_cost|7,20,5,4,5, details:edges:1 037 892(32MB), nodes:1 687 333(20MB), name:(12MB), geo:15 498 756(60MB), bounds:3.0E-6,261489.846,5.03E-4,260803.533, totalMB:8096, usedMB:6707)
2022-01-04 10:32:30 INFO GraphHopperPostgis:1193 - flushed graph totalMB:8096, usedMB:6374)
edges:1037892
Importing the database took: 151.69008
2022-01-04 10:32:30 INFO MapMatching:149 - MAX_VISITED_NODES2147483647
2022-01-04 10:32:30 DEBUG MapMatching:213 - Kept observation: 1
2022-01-04 10:32:30 DEBUG MapMatching:217 - Filter out observation: 2

some are kept, some are filtered

2022-01-04 10:32:30 DEBUG MapMatching:217 - Filter out observation: 519
2022-01-04 10:32:30 DEBUG MapMatching:217 - Filter out observation: 520
2022-01-04 10:32:30 DEBUG MapMatching:217 - Filter out observation: 521
2022-01-04 10:32:30 DEBUG MapMatching:213 - Kept observation: 522
java.lang.IllegalArgumentException: Sequence is broken for submitted track at time step 0. observation:Observation{point=51.0471666,4.0277075,0.0}, 0 candidates: []. If a match is expected consider increasing max_visited_nodes.

Any pointers on how to debug this? I guess it doesn’t find an edge for that point?

Then something fundamentally is wrong and you should fix this instead of the tweaks. Probably some too big boundaries are used or a different coordinate system. You do not get this error in the original code github.com/graphhopper/graphhopper

@karussell Thanks, i’ll try to figure out what’s wrong. Maybe the data is not loaded correctly. Otherwise I guess it’s better to abandon this way as it’s not officially supported and try the low-level api of graphhopper directly.

You can also reach out to the maintainers. Seems to be still actively maintained.

You can even ping them here I guess @mbasa :slight_smile:

We figured it out. Some pointers in case anyone reaches this post:

make sure that:

  • the geometry is in WGS84
  • the geometry is simplified enough + doesn’t have too many decimal places
Powered by Discourse