Reason for such big differences in calculation time between BRouter-web and OSRM and Graphhopper

[Michał Durak]

Hello.
Today I discovered this new BRouter web client and I like it very much, mostly for the nice routes it finds.
But as far as the routes are good, it takes some time to calculate longer routes. I'm wondering what's the reason for this. Is it either the host machine BRouter-web is running on which simply can't compete with the OSRM and Graphhopper ones, or maybe is it because BRouter's code isn't optimized as much yet?
For example, trying to calculate a route from here: https://www.openstreetmap.org/node/2319935672 to there: https://www.openstreetmap.org/way/111977844 using the car-test profile with no alternative index takes about 6 seconds, while on OSRM and Graphhopper it is pretty much instant (about one second).
While 6 seconds for a 480 km route isn't really bad, I would like to know the reason behind this. I'd really love to hear that it's only because of the host machine rather than code optimization :)

[abre...@googlemail.com]

Am Donnerstag, 1. Mai 2014 20:50:26 UTC+2 schrieb Michał Durak:

the car-test profile with no alternative index takes about 6 seconds, while on OSRM and Graphhopper it is pretty much instant (about one second).

Hi Michel,

it's both. OSRM and Graphhopper are using "contraction hirachies" (=precalculated shortcuts for a specific routing mode). BRouter does not do that, and it's not really an issue of "not doing it yet", BRouter is not doing it by design. This is because contraction hirachies are killing flexibility, and this is why  OSRM and Graphhopper do not offer e.g. alternatives or nogo-areas. They just cannot.

On the other side, my server is really low-end (virtual server with 1 cpu and 4 GB RAM), and if I would pre-load the routing graph into a really big RAM, as OSRM and Graphhopper are doing, of course I could have better response times. But this is not the intention.

regards, Arndt


 

[Michał Durak]

Thanks for the reply. I'm planning on buying some Android phone this year, preferably with a Tegra K1 soc. Could you give me some estimation on what kind of BRouter performance can I expect from it? If it was about the same as the web version, it would be really great :) I know OsmAnd isn't really fast and I'd prefer to use BRouter with it. Sorry for bothering you, but I haven't yet got any Android device I could test with :(

[abre...@googlemail.com]

Am Freitag, 2. Mai 2014 13:41:20 UTC+2 schrieb Michał Durak:

I'm planning on buying some Android phone this year, preferably with a Tegra K1 soc. Could you give me some estimation on what kind of BRouter performance can I expect from it? If it was about the same as the web version, it would be really great :)

Hi Michel,

no, expect BRouter to be significantly slower on a phone compared to a Desktop- or Server-System. I cannot really tell the reason, because the clock-rates are not so much different, but there's also file-system buffer cache vs. plain sd-card access, HotSpot VM versus Dalvik etc.

You can check Harry's tests on osmands forum for some house numbers: https://groups.google.com/d/msg/osmand/Scdy74-CixA/c8-G5rQJnooJ

However, please consider that processing time scales quadratic with distance, so what's getting a problem for long-distance application is no problem at all for "normal" distances. Please check also the explanation on "timeout-free recalculations" in that osmand-forum-thread, this is a working solution for handling long-distance trips, so I don't really see so much problems from the performance side.

In short: buy any (cheap) phone, you don't need a high-end device.

[Michał Durak]

Thanks again for replying, Arndt.

I had a look at the thread you linked and I can see it clearly wins compared to OsmAnd's routing algorithm both speed and chosen route wise (for me, as I mostly travel with a moped, so going by city is actually better than by longer motorway).

But there's still one thing that bothers me when interfacing BRouter with OsmAnd: does it support automatic route recalculation? For example when I take different route (by mistake or purposedly), will it create a new route for me automatically?

Regards, Michał.