I have an app that heavily uses graphhopper - all things that needs to be done takes about 3 minutes (distances between couple hundreds of points). Therefor I need to find a way to make it run faster. I’m using one of the best android devices on the market (Huawei p8 and xperia z4 tab) and those have large RAM memory, so I was thinking about loading GraphHopper directy into RAM - using GraphHopper.forDesktop(). Sadly, I cannot get it working, even when I add “large heap” to the manifest.
Do you have any suggestion how to make GH runs faster on Android? I’m using GH pretty much just like it’s used in Android demo. I’m using map for Poland, which is about 800 MBs (Nexus 5X has 2 GB of RAM, P8 and Z4 have 3 GB. If my math is correct, even if everything else would take 2 GB of RAM , I should still have some left…).
Thanks for any help, and thank you very much for working on this great project.
There’s difference between the device’s RAM and the heap limit that the system provides for each app.
Accessing all RAM usually requires native access (e.g. with NDK).
That is a really interesting task and as @devemux86 says: you’ll need to utilize NDK. Maybe you try using the Unsafe approach which already exists for the Desktop - see UnsafeDataAccess. But I’m not aware of an equivalent of ‘unsafe’ for Android/Dalvik. But it should be possible to implement something native with the NDK.
The funny/strange thing is that under iOS we do not have this limitation and all can be loaded into RAM and it can be nicely fast …
Another approach would be to use the data from disc and load it in a kind of a cache.
Thanks for reply!
Sadly I’m not advanced Android developer (actually this is my second project, and the first one was rather simple on android side) to understand all the details about working with NDK, but if maybe you can clear up some things for me:
- About UnsafeDataAccess - it’s marked as “experimental” in sources. This app will have to be as stable as possible (so limited to poor Android stability) as it is made to help people at work. Will loading GH into memory harm stability?
- Will it be possible to use standard GraphHopper java class in NDK to handle initialization etc? Or is there GraphHopper written in C/C++ that can be used in NDK app?
- If main app is written in Android SDK (and definitly cannot be ported to C/C++, as my client has to deal with huge amount of business logic and I don’t think that they can port their app to C/C++) won’t I be bind to this whole “heap limit”?
- Dummy question. Is there a quick way to do this? Is the solution available or will it require changing GH code?
Thanks for replies
Maybe you can advice me something else, which will speed up querying GH? I need to make about 40k querries on init
Improving in this area is likely to be time consuming or requires expert knowledge. Loading GH into memory via RAMDataAccess is stable and the default - but only on the server side. Doing this on Android will fail as the OS artificially limits heap memory, so you have to go off-heap via the NDK to ‘workaround’ the limit.
The other questions I cannot really comment on as I have no epxerience with NDK on Android. But regarding 3: doing just a tiny part on NDK is possible - no need for a rewrite.
Another way to improve speed could be to increase heuristics and therefore improve speed. See https://github.com/graphhopper/graphhopper/issues/506
Thanks a lot, that might be what I am looking for. I had some troubles to find an example of how to use this feature, could you guide me a bit here?
That’s the code I’m using now to get response from GH:
GHRequest req = new GHRequest(fromLat, fromLon, toLat, toLon). setAlgorithm(AlgorithmOptions.DIJKSTRA_BI); req.getHints().put("instructions", "false"); GHResponse resp = hopper.route(req);
I have no idea how to form proper request for hopper. According to your link I should be really into A* with"astarbi.approximation=BeelineSimplification" and epsilon between value of 1 and 1.8, but I have no idea how to use it.
Thanks a lot
You can put those infos into the hints like the instructions:
or in the URL as normal parameters
Now my request to GraphHopper looks like:
`final String algo = AlgorithmOptions.ASTAR_BI;
GHRequest req = new GHRequest(fromLat, fromLon, toLat, toLon).setAlgorithm(algo);
req.getHints().put(algo + “.approximation”, “BeelineSimplification”);
req.getHints().put(algo + “.epsilon”, 1.8);
GHResponse resp = hopper.route(req);`
Sadly it doesn’t provide any performance improvement over DIJKSTRA_BI algorithm without beeline simplification and epsilon. (2 mins with DIJKSTRA vs 2 mins 20 secs with ASTAR). What am I doing wrong?
Are you using CH or non-CH? And can you fetch and compare the visited nodes? rsp.getHints().getInt(“visited_nodes.sum”)
It’s worth mentioning that first route calculations are significantly slower than the next ones - more noticeable on mobile devices (see #194).
I have “isCHenabled = true”, I guess that I should change that. The way I’m loading graphhopper:
hopper = new GraphHopper().forMobile(); hopper.setCHEnable(false); **_//this is new, I didn't have this line before._** String f = new File(maps_loc, current_area).getAbsolutePath(); //System.out.println("Loading graph"); hopper.load(f); //System.out.println("Completed"); hopper_initialized = true;
Returns an error:
Caused by: java.lang.IllegalStateException: Configured graph.chWeightings:  is not equal to loaded [fastest|car]
I wrote line:
hopper.setCHWeightings("fastest|car"); after setting CHenabled to false, but it didn’t help either.
That won’t be the case - GraphHopper is used only when new points arrives from server, so it will calculate each path only once.
If you already had CH enabled then you already had maximum performance. Or to express this differently: then tuning with the described epsilon changes etc won’t have significant improvements.
Are you calculating special many-to-many tables or why are 40K queries necessary?
Yes, I’m calculating many-to-many tables for my TSP-like algorithm. Actually for 200 points I will have 20K querries, because I approximate, that distance from point A to B is equal to distance from B to A (in most cases there are no significant difference).
So when I have CH enabled with DIJKSTRA_BI algorithm thats the max performance I’ll get? I had noticed that my CPU usage is about ~14% and multithreading don’t improve this situation, so I’m guessing that internal storage bandwidth (or rather time to access) limits performance for me.
So I have no other option than accept waiting about 2-3 minutes for initialization?
Thanks a lot for help and great job on GH.
You could try also here with heuristics and increase epsilon a lot more, but you won’t get substantial improvements I think. Why not calculate this on the server side? Another possibility is to wait for our performance improvements in the next months, they should applicable to CH as well but could make setup more complex. Also there are special algorithms for the many-to-many case but they aren’t open source for GH and I’m not 100% sure they would improve speed here as you were correctly stating that this is more disc than CPU bound.
Long init time isn’t deal-breaker at all - client’s app will have many users, and their server app is rather heavy, because it has to process a huge amount of business data etc. and traffic has burst characteristic, so in the end we probably won’t save time. Moreover, initializing about 200 points will probably happen rarely, as they will update couple points each day/week or sth. Also - we wanted to make HA system which requires working offline, because there are no internet connection (over umts/lte) in some off-city location. Moreover, this app will probably be used in other countries too, and heavy calculations off-server will improve scalability. Though, improving user experience by speeding up heavy tasks would be nice.
Thanks a lot for your help, I’ll track GH changes and if something useful appear we will update our app. You are doing great work on GraphHopper, keep doing that!