navit-project.org

Hi together!

I recently did make good use of navit on WinCE in the Alps, when hiking.
It worked good for day trips of hiking and even car routing in the area between Pfronten and Oberjoch, which actually has some interesting routing problems, but a relatively limited amount of paths or streets.

Back in a well mapped large city it proves near to impossible to route to destinations a few kilometers away: navit crashes, because it runs out of memory (which is not abundant on the 64MB WinCE devices).

I tried minimizing the number and sizes of map layouts and vehicle-profiles loaded within navit.xml (actually in a modularized version allowing to switch them on/off as needed), to reduce the memory footprint of navit. Further I freed as much memory as feasible by stripping the device down (removing applications, etc.).

Essentially to no avail.

Next I reduced routing radius by using

• Code:
  route_depth="4:50%,6:1%,8:40000,12:10000,18:5000"
  for motorized travel modes
• Code:
  route_depth="10:25%,12:1%,18:5000"
  for muscle-based travel modes

Still distances beyond 4-6 km typically run out of memory¹ ...

So now I'm wondering: There is still active WinCE support, so obviously people are using navit sucessfully on these devices ...
Please: What is the trick?!?

[¹] From the "route graph" display it is clear to me that the routing algorithm is spreading undirected over the complete enclosure given by the "route_depth" parameter -- as is of course to be expected from a Dijkstra algorithm.
The obvious, but non-trivial, solution is of course improving time and memory efficiency by switching to a better suited algorithm like SMA* or fringe-based routing, possibly combined with bidirectional routing. (To avoid confusion: the Dijkstra algorithm is optimal in the sense, that it will find all shortest routes for all points on the map to a specific destination because it actually calculates a complete spider graph or weighted reachability graph for this destination. It is neither time nor memory efficient for the problem of interest in navit: finding an optimal route from point A to point B (plus some blur around it in the case of voluntary or involuntary detours).

Well the current dev stage of Navit isn't easy as we lack of devs and try to do our best to keep all platforms supported. Of course this exlude intense testing, but we will try to help and fix the problem

Currently I don't find any existing ticket on WinCE that focuses routing crashs, but I remember that there was already something very similar....

Maybe the Navit cache is set to a too large value. This can be set in the navit.xml config file in the "<config ... >" line, for example, to set it to 32MB:

You can also try even smaller values such as 16MB.

I've been using navit on wince device. But my device had 256 mb of ram.
About a year ago i began encountering hw problems with it. Now i switched to android device with multitouch, wifi, 512 mb of ram, it costed me below 80bucks...

As for 64mb device, i suggest reducing cache size to or below 1 mb.

Yep, but I guess we have still enough possibilities to reduce the footprint of Navit even for low ressource devices
https://wiki.navit-project.org/index.php/Brainstorming

But I guess we are getting offtopic. I have still 2 devices with CE/Mobile here, but lack time for testing.

Actually just a few weeks ago I bought a specialized PNA with TMC for 60 EUR ...
But that is besides the point.

"Low-powered" devices are a magnifying glass for efficiency problems (results of a test series follow soon).

On a tablet or smart-phone with quad-core and 1GB RAM you may not notice them much, but they are still wasting battery power, CPU cycles, RAM and persistent storage. All in all may leading to less usage of navit -- wouldn't this be a waste?

Further, minimum requirements should be given for the supported platforms, to avoid disappointment of potential new users ...
If the results of my tests are a minimum of 256 MB RAM for a WinCE device -- fine!

Thank you Usul and Xenos!
I appreciate your fast responses and all the work the developers and supporters put into navit, bringing us this great application -- I want to send this ahead of the test results below, to avoid any misunderstanding.


I've run a series of tests based on Xenos suggestion and the tickets #1158 and #1044, Usul seemed to refer to. The test setup is a WinCE 4.20 device (Blue Media BM6280), with navit installed on the storage card and a minimal set of tools for performing and analyzing the test (memory gauge, task manager, editor for changing configs, file manager, a GPS tool) plus a few apps considered indispensible for productive use. The test destination lies 3 km south from my position as the raven flies, 3.9 km by street in car navigation mode with route_depth="4:50%,6:1%,8:40000,12:10000,18:5000"


First I tried the trick from #1044: creating a directory navit.log to prevent writing of the log file. It did not reduce memory footprint of navit. Obviously there is not much write cache used and IMHO the trick would only be effective when navit is installed in the RAM of the device (what I would not recommend). If told were, I will gladly document this conclusions ...

Subjectively the GUI becomes a little bit sluggish with this trick, but this is not easy to measure, as GUI reaction seems to depend on GPS signals ...


Second I tested various settings for cache_size. As ticket #1158 suggested successful tests with 256KB and 512KB, I started lower than Xenon's suggestion. Here the results of the test series:

• base line:
  
  • With all tools installed and the memory gauge and task manager active, there are 34.11 MBs of free memory available for navit. (This is not tight, for comparison: Within this freespace a commercial car navigation app was operating for years over long distances (500-1000 km), still leaving 7-8 MB space for other applications.)
  • navit without any cache_size limits has the following reproducible memory footprints some minutes after start up without any routing active and any user interaction (but the setting of a fixed position)
    
    • 11.52 MB after getting a GPS position
    • 11.70 MB when the same position is set as fixed position is set from a bookmark
  • navit without any cache_size limits, after the successful calculation of the route to the identical destination
    
    • start position via GPS: 24.43-24.63 MB total memory usage, or 13.11-13.32 MB pure routing memory footprint for a (trivial) short route (reproducible)
    • identical start position, but as a fixed position set from a bookmark -- memory is eaten up much quicker than with a GPS position, navit reproducibly runs out of memory and crashes
• navit with cache_size=5MB (well actually cache_size=5242880)
  
  • wildly oszillating between 8.69 MB to 11.87 MB while waiting for a GPS fix, GPS fix is not achieved over half an hour
    After a few minutes waiting for GPS fix, navit would not respond anymore to user interaction on the map.
    (This test was repeated several times for 20-30 minutes at 2 different locations, one having practically unlimited sky view (only <30° elevation to the north is obstructed). With the identical device and navit without a cache_size setting as well as another GPS application, GPS positions could be acquired within at most 2-3 minutes, often <1 minute, between the failed tests).
  • 7.13 MB, when quickly setting identical fixed position, no routing active
  • routing from this fixed position: 24.07 total, or 12.55 MB pure routing memory footprint
• navit with cache_size=4MB
  
  • Same behavior as previous test, when waiting for a GPS fix, but GUI starts to feel sluggish ...
  • 6.45 MB, when quickly setting identical fixed position, no routing active
  • routing from this fixed position: 22.15-22.35 total, or 10.45-10.65 (?) MB pure routing memory footprint
• navit with cache_size=3MB
  
  • Same behavior as previous test, when waiting for a GPS fix, but GUI feels more sluggish, time span to set a fixed position before non-responsiveness is shorter ...
  • routing from this fixed position: 17.63 MB total, or 5.93 (?) MB pure routing memory footprint
• navit with cache_size=2MB
  
  • even interaction immediately after application start is not taking effect anymore

A similar, even shorter route leading north into a region with more detailed OSM mapping runs always out of memory.

I think a few conclusions can be drawn from these tests yesterday and today :

• the increasing detail of OSM maps over time continously rises the bar in terms of memory and processing power for navit, IMHO in an unhealthy manner, which will lead at least to resource hogging on "high-powered" devices ... are there possibilities to reduce the amount of POIs, nodes, edges used/loaded for routing?
• the "route graph" option shows that the Dijkstra algorithm evenly spreads in all directions, such touching a lot of map elements not even remotely having any relevance for the route. Besides RAM usage, this leads to a lot of IO and CPU usage. A "high-powered" device may not suffer from this, but routing with navit will nevertheless be much slower than with other navigation applications, potentially reducing the user base. So, some improvements in the routing algorithm might really be necessary!?

On the other hand, I do not have the slightest explanation, why setting cache_size interferes with GPS reception, and why without cache_size the identical route with identical start and end points works with a GPS position but fails when this position is set from a bookmark.

All in all, the results are baffling, partially even queer. To exclude the possibility, that there is some problem in the OSM mapping of the local area -- a kind of "black hole", leading to massive RAM usage, as soon as the area is touched by the routing algorithm -- it would be good, if somebody could reproduce these tests elsewhere.

Any tests I can run to clarify issues?