Route calculation in Osmand 1.7.3 very slow

[primavera1969]

Hi! I update via google play to 1.7.3 version and i noticed the route calculation is very slow, even for short distances (10 km). I've just tried to delete data, uninstall the app, delete the osmand folder and reinstall again the app. I download new map files (world and region). I experienced the same problem with the nightly versions of 1.7. But with 1.6.5 version the route calculation for the same distance was immediated (few seconds). 
I use Cyanogenmod 7, Galaxy Mini. Is my phone too old for the new routing engine?
Emanuele

[Peter B]

YES !
https://groups.google.com/forum/#!topic/osmand/xtZGd5q-UnU
Peter

[primavera1969]

Nobody else has experienced this issue? Any ideas or suggestions? Sadly, at the moment i must give up. The problem is specially in the time of re-calculation. If there is a bad suggestion of the app, due to an error of the map, the time to get a new route is too long. Travelling in a city, ths happen quite frequently, and it's annoying indeed.
Emanuele

[Harry van der Wolf]

It does happen when your maps, including the world map, is too old: before February 2014.

Another issue is double maps: If you have for example both toscane and the entire Italian map, it will calculate the route using both maps as both maps contain routing data.

Harry

--
You received this message because you are subscribed to the Google Groups "Osmand" group.
To unsubscribe from this group and stop receiving emails from it, send an email to osmand+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Peter B]

My test-scenario:
I removed ALL obf-files, the downloaded world_basemap and Germany_Baden-wuerttemberg_europe.
Then reboot, and again calculating the same route (linear distance of about 6 km), which is in Baden-wuerttemberg.
Time was 45 seconds.
Peter
---

[Harry van der Wolf]

Check your settings: Is safe mode "greyed out" (disabled)?

If so, OsmAnd is not using the native library. Thee were some messages mentioning this for the last build.

[Red MM]

Hi,
I have the same issue, very slow route calculation since the update to 1.7.3. I have updated all maps, world basemap does not have an update since October of last year, though. Calculating a route from Frankfurt, Germany to Munich, Germany (about 400km) takes 4 minutes. The time needed to calculate is roughly the same with Safe Mode enabled or disabled. Previous versions also took a while to calculate such a long route, but it did not take as long as it does now. So to me it seems the new algorithm is either only suitable for more modern, powerful phones or it still needs quite some performance improvements. Alternatively, an option to go back to the old algorithm would be helpful, especially for people using older devices.

I'm running it on a Samsung Galaxy Nexus (i9250), which is not the newest device, but still comparatively powerful, I'd say.

Regards,
Red MM

[Nelson A. de Oliveira]

On Thu, Apr 3, 2014 at 8:43 AM, Red MM <red...@gmail.com> wrote:
> performance improvements. Alternatively, an option to go back to the old
> algorithm would be helpful, especially for people using older devices.

If you enable the "OsmAnd development" plugin then there is an option
under "OsmAnd development" where you can disable the new routing
algorithm (as "Disable complex routing")

[Red MM]

Thanks Nelson, just gave it a try. Unfortunately, it seems to make it even worse, routing takes longer than before. :(
I might run some more "controlled" tests in the next few days to see which difference the various settings make, but right now, offline routing is close to unusable for me.

[Peter B]

Checkbox Safe mode is OFF.
Meanwhile I tried:
Uninstall the app, delete local settings, reboot, reinstall, test again -> again slow, 40-50 seconds (linear distance 6km).
details see issue
   http://code.google.com/p/osmand/issues/detail?id=2294
Harry, what time your device needs for such short distances ?
Peter
---

[Harry van der Wolf]

On my phone which is a duo-core Wolfgang AT-AS40D2 with 512MB on Android 4.2.2 (cheap phone) it takes less then 10 seconds for a distance of 5.58 km.

I'm still on nightly build 5766D which I downloaded yesterday or so.

Harry

[Mihail Konovalov]

I have HTC wildfire S and Osmand+ installed. Yesterday I upgrade osmand to 1.7.3. Route calculation became slow. I tried to use  recommendation found here. It make calculation some faster but not much. I need about 1 min for 4km.  I installed net.osmand-1.6.5 beta-167.apk and now it takes about 5 sec to find route. What I have to do yet to increase rate of finding or how install Osmand+  v1.6.5?

[Mihail Konovalov]

P.S. I delete World basemap. I use only Russia saint-petersburg asia.

[Harry van der Wolf]

Frankfurt-Munchen crashes on my phone after 6 minutes.

The two-step approach is good for short distances, but on longer distances it seems to take exponential time and memory.

2014-04-03 17:57 GMT+02:00 Mihail Konovalov <vbi...@gmail.com>:

P.S. I delete World basemap. I use only Russia saint-petersburg asia.

--

[Sabra Sharaya]

If the date of the maps affects the route calculation speed, does this apply to the world base map?

[primavera1969]

I use the latest obf file uploaded (world and Veneto). I've just tried to delete the world map, but time calculation for a 40 km route is 80 sec, so there is no improvemente. But really...it seems the app does a double calculation. The yellow progession line on the screen shown during route calculation, once arrived at the end for the first time, restarts again. When the line arrive at the end the second time, the route is displayed. Strange behaviour....indeed.

[Harry van der Wolf]

2014-04-03 18:47 GMT+02:00 primavera1969 <stocc...@gmail.com>:

I use the latest obf file uploaded (world and Veneto). I've just tried to delete the world map, but time calculation for a 40 km route is 80 sec, so there is no improvemente. But really...it seems the app does a double calculation.

 

The app does a double route calculation!

The first step is a quick calculation step (see the very thin fast blue progress bar).

When finished the progress bar disappears.

Then the second step does the exact calculation and this second step can be very slow (again a very thin slow blue progress bar)

Harry

[Red MM]

So, I ran a few tests now with different options:

1 - Safe Mode off & Disable complex routing off
2 - Safe Mode on & Disable complex routing off
3 - Safe Mode off & Disable complex routing on
4 - Safe Mode on & Disable complex routing on
5 - using YOURS (on-line routing service)

I had a route of 22km length within Germany, containing Autobahn down to residential area roads.

Options 1 - 4 all used between 55 and 70 seconds, so there is actually not much difference between the options. Though it seems the longer the route, the time needed grows exponentially, especially with "Disable complex routing" enabled (which was supposed to be faster??).

Using YOURS (option 5) took 3 seconds to calculate. Ergo, as long as I am within the country (no roaming) I can live with using YOURS. While roaming, I just have to wait, I guess. In any case, I would like to see some performance improvements. After all, 100% off-line navigation was the reason I bought the app...

Red MM

[Mihail Konovalov]

I absolutely agree with Red MM. And how return to previous version?

четверг, 3 апреля 2014 г., 23:17:44 UTC+4 пользователь Red MM написал:

[Max]

Two-step approach should limit search space -> limits memory usage and calculation time.

Test routing on Note 3:

From:
https://www.openstreetmap.org/?mlat=48.90681&mlon=10.78394#map=6/48.90681/10.78394
To:
https://www.openstreetmap.org/?mlat=53.07879&mlon=11.84522#map=6/53.07879/11.84522

First pass: 3 min 50 sec
Second pass: 15 sec
Total: 4 min 05 sec

Calculated route:
632 km
6h 48min

From/to remote areas takes longer to calculate (example above).

For example Munich to Berlin it takes only 2 min 15 sec (2 min for first pass, 15 sec for second pass).

Regards,
Max

[Max]

Since 1.7.5 my routing test is much faster now (4:05 -> 2:16):

First pass: 2 min 10 sec
Second pass: 6 sec
Total: 2 min 16 sec

Regards,
Max

[Harry van der Wolf]

1.7.5?

Test user or regular user?

Harry

[Max]

Don't know. :)

Here it is:
net.osmand-1.7.5-175.apk

I think this is the speed-up:
https://github.com/osmandapp/OsmAnd-resources/commit/63cecb604b16d8cf0489eb078191c1b297390020

Regards,
Max

[grin]

On Thursday, April 3, 2014 11:36:01 AM UTC+2, Harry van der Wolf wrote:

It does happen when your maps, including the world map, is too old: before February 2014.

World basemap is 2013/10/30 in the download screen.

 

g

[Peter B]

Until now it seems to be obvious, that most of users don't have problems, but for some users it is very slow.
I testet again:
More details in http://code.google.com/p/osmand/issues/detail?id=2294
All files in srtm-dir are removed, all obf-files except the local one (Germany_Baden-wuerttemberg_europe.obf  2014-04-05) are removed, the device was rebooted.

Test-1 (linear distance of 6 km)
The calculation for a distance of 6 km needs 30-35 seconds. After < 3 seconds the progress bar is blue (it jumped from 0 to 100%) and it stays until end.

Test-2 with a longer distance (linear dist. 67km) shows: pass-1 (100%) with 5 sec., then pass-2 with 22 seconds. The blue progress bar stays on 100% for more than 26 seconds, totally ~53 seconds.

So I suppose that in Test-1 pass-1 (or pass-2) was so fast, that I did not realize it, and it stayed after pass-2 for the most time as in Test-2.
Maybe there is something wrong at the end of (or after) pass-2 ?
Does anybody have an idea how to test more ?

Current version is #5778D
Test with #1532D needs < 4 seconds.
Regards Peter
-----

[Harry van der Wolf]

I had the 1.7.4 from play store.
I downloaded the new nightly but it is just as slow.

Then I downloaded "your" version from the releases page on osmand.net.

That one is also just as slow. I don't see any speed improvement.

What's more: I even have the feeling that it is slower then approx. 1 month ago: also with the new routing.

I'm no expert at all in the performance of the A* algorithm (or Dijkstra or, by now, improved Dijkstra, A* algorithms) and whether uni-directional is faster then bi-directional. About half a year ago I "think" I remember that bi-directinal A* is faster on multi-core/multi-threading (when programmed that way), but I'm not sure.

Harry

[Red MandM]

Hi,

Since there seems to be no official response from any of the developers, I have now sent a mail directly to the support address given in google play. I hope they will answer. If they do, I'll post here. This is the mail I've sent:

Hello,

there has been quite some discussion going on about the latest version (1.7.x) of OSMAnd+ where users have very poor performance when it comes to route calculation. Since the update to 1.7.x and the new routing engine, the calculation takes exponentially longer than compared to previous versions of the App. A discussion thread about this is open in the forums: https://groups.google.com/forum/#!topic/osmand/NKeblpLkm4g

I am writing to you directly now since it seems this thread has not yet been noticed by the developers. I'm hoping that you could give some insights on the problems that the people seem to have with the new version.

As a comparison, I have installed on an HTC Desire X both OSMAnd+ (1.7.4, latest maps) and MapFactor Navigator (latest version, latest maps). Both use the same map source (OSM) so the data used for routing should be rather similar. I tried calculating a route of about 900km from a small town near Munich to a street in Flensburg, Germany. MapFactor Navigator needed 20 seconds to calculate the route, OSMAnd+ crashed and restarted itself after 10 minutes.

I would truly appreciate a response and hopefully also a solution to these problems. As of now, OSMAnd is rendered useless due to these performance issues.

Best regards,


Red MM

[Harry van der Wolf]

2014-04-09 11:24 GMT+02:00 Red MandM <red...@gmail.com>:

Hi,

Since there seems to be no official response from any of the developers,

Most of the time the developers are extremely busy trying to improve the program, especially after a release when many (minor) bugs that slipped through the test mazes need to be investigated and solved. As it is an open source project run by only a few number of volunteers, there is no help desk or support team, or a group of programmers in a commercial, paid environment.

So, it could very well be that the developer(s) did miss this as there are so many "free time" hours in a day next to the regular job:  "free time" he spends almost entirely on programming: for us, where us consists of thousands of users where most of them don't even pay for the application (and maybe you do pay like also a lot of others, I don't know).

On the other hand: I do think he is aware of it and looking frantically into it, but again: should he spend time in answering many mails (where there are several likewise threads here on performance: why don't people stick to one), or should he work on fixing things and once fixed, report that back?

I fully agree that communication is a key to connect to your users and to "manage expectations" of your users, but if your time is that limited you need to prioritize. I think that solving issues is then the right priority. Please follow the developments (https://github.com/osmandapp/) and you can see how much work is done.

Nevertheless, the route calculation performance issue and memory (ab)use is really terrible. I fully agree on that. Hopefully that can be optimized in the near future.

Harry

[Red MandM]

Hi Harry,

I do agree to what you are saying and I know that the few developers that are working on it spend most, if not all, there free time on this. I'm also not expecting him/them to answer right away, I am aware that it could be days, if ever, I get an answer. But looking at the comments especially on the Play Store about the app, there is not much mentioning of the issues we are facing here. Most complaints there are about not being able to store maps on the external SD card. And there have been responses to that on the Play Store, while no response yet here in the forums to the performance issue. So that is why I chose to send an email directly, just in case he would not be aware of it. Looking through bunches of forum threads and figuring out the most burning issues is yet more time consuming than checking mails, I believe. And as you say " the route calculation performance issue and memory (ab)use is really terrible" and this is the core functionality of this app, so it should be treated as a rather major or critical defect, I would say.

In any case, let's see what may happen in the next few days.

Cheers,
Red MM

P.S. I did pay for the app.... :)

[Sabra Sharaya]

Because the date of the maps seems to be important, I think the world base map should be regenerated so there will be no question about whether it is new enough.

Also, in computer science, people often have to choose between speed and memory usage. It might be too much to expect the app to get faster and use less memory at the same time.

[Torsten Bronger]

Hallöchen!

Am Mittwoch, 9. April 2014 13:36:01 UTC+2 schrieb Harry van der Wolf:

2014-04-09 11:24 GMT+02:00 Red MandM <red...@gmail.com>:

Hi,

Since there seems to be no official response from any of the developers,

Most of the time the developers are extremely busy trying to improve the program, especially after a release when many (minor) bugs that slipped through the test mazes need to be investigated and solved. As it is an open source project run by only a few number of volunteers, there is no help desk or support team, or a group of programmers in a commercial, paid environment.

Come on.  I've been using Open Source for two decades now, and I can't remember any major project the developers of which were less responsive.  FWIW, I read the Darktable mailing list, too, as well as its IRC chat, and you get answers from the core devs within seconds, every time.  And both projects have equal size, commit-wise as well as developers-wise.

Tschö,

Torsten.

[Leopoldo Saggin]

Il giorno giovedì 3 aprile 2014 21:17:44 UTC+2, Red MandM ha scritto:

So, I ran a few tests now with different options:

1 - Safe Mode off & Disable complex routing off
2 - Safe Mode on & Disable complex routing off
3 - Safe Mode off & Disable complex routing on
4 - Safe Mode on & Disable complex routing on

[skip]

I can't find any "Complex routing" in OsmAnd 1.7.4+
I found "safe Mode (checked/unchecked) and Fastest vs Shortes route, but I can't find Complex routing. Am I blind?
Cheers,
Leopoldo aka Topoldo

[Red MandM]

In settings, go to "Additional Moduls" and enable "OsmAnd Debugging". It'll give you an additional entry in the settings list and in there you can enable/disable complex routing...

Cheers

[Peter Gervai]

On Wed, Apr 9, 2014 at 2:33 PM, Torsten Bronger
<torsten...@gmail.com> wrote:

> Come on. I've been using Open Source for two decades now, and I can't
> remember any major project the developers of which were less responsive.

You haven't seen most of the wide world yet! :-)

OsmAnd is not really bad regarding responsiveness. It is quite a good
project to handle the issues too. There are problems and disagreements
and annoyed and blockheaded people, but overall this goes nicely.

> FWIW, I read the Darktable mailing list, too, as well as its IRC chat, and
> you get answers from the core devs within seconds, every time. And both
> projects have equal size, commit-wise as well as developers-wise.

And I know projects with unresolved serious bugs kept around for 2+
years. And developers only responding the polite equivalent to fsck
off. Complaining doesn't get you anywhere. You can help, you can pay
up, or you can, you know.

grin

[sympa]

My first paid Android app was a navigation app that was unstable and often didn't work.

The developer even abandoned it while leaving it for sale in the play store, but not offering map updates any more.

While here I see real developments and progress. And the talking is in the software, not in empty promises or 'we will fix that maybe ever' messages.

[Torsten Bronger]

Hallöchen!

Am Mittwoch, 9. April 2014 18:32:08 UTC+2 schrieb grin:

On Wed, Apr 9, 2014 at 2:33 PM, Torsten Bronger
<torsten...@gmail.com> wrote:

> Come on.  I've been using Open Source for two decades now, and I can't
> remember any major project the developers of which were less responsive.

[...]

OsmAnd is not really bad regarding responsiveness.

Well, then we have different definitions of this word.

Tschö,

Torsten.

[Leopoldo Saggin]

Il giorno mercoledì 9 aprile 2014 17:56:34 UTC+2, Red MandM ha scritto:

In settings, go to "Additional Moduls" and enable "OsmAnd Debugging". It'll give you an additional entry in the settings list and in there you can enable/disable complex routing...

Tnx
Leopoldo aka Topoldo

[V S]

Hi All and thank you Harry for support, 

I even could speak for myself and other who worked on the new version of routing.

Slow routing is very broad term.  For some people it is 5 minutes, for some 30 seconds.

Again, for 1.7 release the average route should be calculated under 1 minute. 

It doesn't matter that 1.6 took 10 seconds or 20 seconds to calculate 20 km route and 1.7 takes 45 seconds. This is expected. 

Why? Because 1.6 used couple of heuristics which calculated 2-3 times faster for routes 20-60km, but (!) these heuristics where wrong in 5% of routes. In order to reduce complains about the routes heuristics are deleted in 1.7.

For long routes (longer > 40 km) please don't disable complex routing (2 phase routing) ! This is the only way to get them calculated.

Important 1.7.4 -> 1.7.5 (latest night builds)

There was very critical bug for countries with miles per hour, which is fixed in 1.7.5 and this week will be released. Now we are waiting for other bugs possibly to include in 1.7.5.

P.S. For people who are interested how complexity is growing, the answer is. It is not exponentially, but quadratically. We use 2D world to navigate.

Regards,

Victor

[V S]

>>> For the car-distance of 9.4km 58 seconds are needed. I think this is very slow.
Positions 
Dest. http://download.osmand.net/go?lat=48.04772&lon=7.7987695&z=12
Start http://download.osmand.net/go?lat=48.04264&lon=7.877665&z=15

-----------------------------------

On my reference slow phone (Nexus S) that route took 25 seconds (without restart and fresh system), which is acceptable but not really fast.

The speed of this type of  routing will be addressed in future releases.

Victor

[Red MandM]

Hi Victor,

appreciate your response! Let's hope that it will be possible to still increase performance with future releases, though I understand that it might take a while. I guess you'll have to find the best compromise between precise routing and speed of calculation.
For those that were happy with the route calculation as it was up to version 1.6., would it be possible to integrate that as a fall back option? Knowing that the route might not be as precise as it could be? I don't know about other folks, but for me that would be ok and I could live with 5% error rate. So far, OsmAnd has brought me where I wanted to go...

Cheers.

[Peter Gervai]

On Thu, Apr 10, 2014 at 1:18 AM, V S <victor....@gmail.com> wrote:

> Why? Because 1.6 used couple of heuristics which calculated 2-3 times faster
> for routes 20-60km, but (!) these heuristics where wrong in 5% of routes. In
> order to reduce complains about the routes heuristics are deleted in 1.7.

Right now it's impossible on my phone used for navigation to calculate
a route from budapest to villach without crashing the program due to
out of memory (somewhere about 73MB allocation told by devel menu).
Probably going into developer options and temporarily activating
"imprecise routing" is better than having no route at all. :-)

Fiddling with waypoints may help but it's not easy to plan a 800Km
route by manually waypointing it every 100Km. I mean, I usually use
the computer to plan for me and not vice versa. :-)

(I have tried now with 3 waypoints but probably some of them is still
too distant and crash the code.)

> For long routes (longer > 40 km) please don't disable complex routing (2
> phase routing) ! This is the only way to get them calculated.

If I disable it I am able to calculate medium length (200-400km)
without crash. Magic?

g

[Max]

I had the 1.7.4 from play store.
I downloaded the new nightly but it is just as slow.

Then I downloaded "your" version from the releases page on osmand.net.

That one is also just as slow. I don't see any speed improvement.

I did not compare 1.7.4 to 1.7.5.
Actually I compared a nightly build to 1.7.5, which had this big speed improvement.
But I guess this nightly build had a bug, so that it was slower than usual.
So maybe 1.7.5 is not faster, only my tested nightly build was slower?

I'm no expert at all in the performance of the A* algorithm (or Dijkstra or, by now, improved Dijkstra, A* algorithms) and whether uni-directional is faster then bi-directional. About half a year ago I "think" I remember that bi-directinal A* is faster on multi-core/multi-threading (when programmed that way), but I'm not sure.

Bi-directional search reduces complexity, so it should also be faster, if it does not run in parallel.

I looked at it, and the uni-directional algorithm was only active for a few hours.
Bi-directional algorithm was always active in 1.7.x releases (but it was not for a few hours in nightly builds).

Regards,
Max

[Harry van der Wolf]

Hi Victor,

2014-04-10 1:18 GMT+02:00 V S <victor....@gmail.com>:

Again, for 1.7 release the average route should be calculated under 1 minute. 

It doesn't matter that 1.6 took 10 seconds or 20 seconds to calculate 20 km route and 1.7 takes 45 seconds. This is expected. 

Why? Because 1.6 used couple of heuristics which calculated 2-3 times faster for routes 20-60km, but (!) these heuristics where wrong in 5% of routes. In order to reduce complains about the routes heuristics are deleted in 1.7.

From my knowledge about the "pathfinder" or "shortest path" algorithms:
- Dijkstra always finds the shortest path and should be chosen when "memory time and CPU usage" are not important and (absolute) accuracy is important.

-A* uses heuristics and is much faster but does not always finds the shortest path.

When you say that you removed heuristics, do you mean that we are back on the Dijkstra algorithm? And that it's therefore slower and uses more memory, but will always find the shortest route (mathematically that is)?

Or am I now miles off?

Harry

[Nelson A. de Oliveira]

It could use a memory bounded algorithm on lower spec devices, like
http://en.wikipedia.org/wiki/SMA*

[Peter Gervai]

On Thu, Apr 10, 2014 at 3:28 PM, Nelson A. de Oliveira <nao...@gmail.com> wrote:
> It could use a memory bounded algorithm on lower spec devices, like
> http://en.wikipedia.org/wiki/SMA*

1) nice find

2) uh, "lower spec" is clearly anything except the top10 most
expensive and memory-packed models. I don't consider desireHD or Moto
Atrix "lower spec", regardless how old they are. But here's a galaxy
tab2 which chokes on it either and that's not exactly "low spec". [no
offense taken, just mentioning that the world generally seems to be
low-spec regarding this.]

g

[Arndt]

Am Donnerstag, 10. April 2014 15:24:25 UTC+2 schrieb Harry van der Wolf:

From my knowledge about the "pathfinder" or "shortest path" algorithms:
- Dijkstra always finds the shortest path and should be chosen when "memory time and CPU usage" are not important and (absolute) accuracy is important.

-A* uses heuristics and is much faster but does not always finds the shortest path.

When you say that you removed heuristics, do you mean that we are back on the Dijkstra algorithm? And that it's therefore slower and uses more memory, but will always find the shortest route (mathematically that is)?

Or am I now miles off?

not miles, but off anyhow. Please read my writeup on BRouter's way to handle this: http://www.brensche.de/brouter/algorithm.html

[V S]

Hi All,

Somewhere I published routing implementation details, but people still asking so I belive I need to write a wiki page sometimes.

Short answers :

1. It is impossible to use 1.6 routing engine with 1.7 because 1.6 doesn't support routing parameters, so it couldn't use such UI. 

You still could use 1.6, the map updates will be provided.

2. OsmAnd Routing implements part of technique from SMA, and unloads/loads using own memory management but it still fails and this is not bad thing otherwise you will wait hours to route calculate. We don't keep the graph and links in memory, we keep only queue and visited segments map (queue could be stored on the disk before it is processed, but visited segments could not be).

Will investigate SMA* thoroughly anyway.

3. We already use bidirectional A*

4. A* with current heuristic always find optimal way. By definition it is optimal search (but depends on heuristic)

четверг, 10 апреля 2014 г., 18:53:54 UTC+2 пользователь Arndt написал:

[Osmandtrier]

 please don't disable complex routing (2 phase routing)

In the german translation I am not sure, do I have to see  check mark or not?