Opened 7 years ago

Closed 7 years ago

#1324 closed defect/bug (fixed)

Generate maneuvers asynchronously

Reported by: mvglasow (2) Owned by: mvglasow (2)
Priority: major Milestone:
Component: core Version: git master
Severity: normal Keywords: highfive, performance, routing, navigation


#456 mentions a tweak to the route_depth settings, which is needed in order to make Navit consider primary roads for long-distance routing. This setting is needed in some parts of Europe where the motorway/trunk network is sparse (notably parts of Czech republic and Poland); without it, Navit will either not find a route at all or suggest huge detours.

The setting I use is route_depth="4:25%,6:1%,8:40000,18:10000".

This tweak has worked well for me for a long time. However, after introducing HighFive?, I've noticed that long routes (example: Munich-Łódź, approx. 1000 km) now take extremely long to calculate, due to the larger route map (more nodes to examine) and the extra processing at each potential maneuver. The same is true for route recalulation (e.g. after a wrong turn), where this behavior is even more annoying.

Currently I see a few potential ways to tackle this issue:

  • Reduce the route graph, as described in #1066. This decreases the number of nodes to examine by dropping nodes which have exactly two connecting ways. These nodes would never generate maneuvers anyway, hence no need for navigation.c to examine them. This would save both memory and processing time.
  • Review the changes made in navigation.c, especially those concerning maneuver_required2(), and try to optimize them by running expensive operations (such as iterations over all ways connecting to a node) on as few nodes as possible.
  • When recalculating a route, do not discard the old route immediately but keep it in memory. When generating maneuvers, find where the new route joins the old one and reuse the old route's maneuvers rather than generating them again from scratch. Note that this will only speed up recalculation (not initial calculation), and can be used only if the recalculation is due to deviation from the route. If at a later time we were to add recalculation due to traffic distortions, we'd need some extra logic for reusing route portions.

Assigning to myself as I was involved in the project that introduced the issue, as well as a heavy user of the route_depth tweak.

Change History (12)

comment:1 Changed 7 years ago by mvglasow (2)

  • Owner changed from KaZeR to mvglasow (2)
  • Status changed from new to assigned

comment:2 Changed 7 years ago by mvglasow (2)

I've looked through the code and added some extra logging to analyze the time Navit spends on the various stages of route/maneuver calculation. On the Munich-Łódź test route, finding the route takes 4 seconds on my machine, whereas maneuver generation adds another 47 seconds.

Also, I see that building the route graph can be done asynchronously, splitting the task into small portions and running them in an idle loop. We might want to do something similar for maneuver generation to increase the responsiveness of Navit during that time. Though this won't solve the main issue, i.e. the total amount of time spent on that task.

Another thing that I noticed is that generating maneuvers is a lot faster on route recalculation, even when the route is very different. When I calculate a route from Munich to Vilnius and then change the destination to Łódź, maneuver generation takes some 6 seconds. When I calculate a route from Vilnius to Łódź and then change the position to Munich, maneuver generation takes about 9 seconds. Clicking "Stop navigation" and then calculating a new route will again result in long processing times.

The crazy thing is that calculating a route (including generating maneuvers) from Munich to Vilnius takes 13 seconds, and changing the destination to Łódź takes 9 seconds – so these two steps in sequence are actually faster than calculating the route from Munich to Łódź right away – even though the route from Munich to Vilnius passes near Łódź. No idea why that is...

comment:3 Changed 7 years ago by mvglasow (2)

Up to now my code was based on r6288. I now upgraded to r6297, which includes some patches by jandegr.

Now Munich–Łódź completes in 10 seconds, Munich–Vilnius takes 11 s and Łódź-Vilnius completed in 2 seconds. Next step is to see how this improves things in a real-world situation, i.e. on a smartphone with position changing constantly.

comment:4 Changed 7 years ago by mvglasow (2)

On my phone Munich–Łódź now takes around 30 seconds before I get the first maneuver, which is already a huge improvement. However, since around half of that time is spent on maneuver generation, Navit seems completely frozen for around 15 seconds. I'll look into a way to do this task in an idle loop, similar to routing.

comment:5 Changed 7 years ago by mvglasow (2)

A closer look at this revealed that the bulk of time in navigation_update() is spent in the while loop processing items from the route map. This is the code which would need to go into the idle loop. The rest of the function, including the call to make_maneuvers(), takes less than a second. Probably no longer a HighFive? regression (since I don't remember any of us making extensive changes to that portion of the code), but should be fixed nonetheless.

comment:6 Changed 7 years ago by mvglasow (2)

I've refactored the code accordingly, which eliminates the UI freeze while Navit is generating maneuvers. However, this implies that maneuver generation is no longer an atomic action, thus some additional changes are needed:

  • Users may now select "Stop navigation" or enter a different destination while maneuver generation is in progress. When that happens, the idle loop needs to be stopped. This is already implemented.
  • User-defined actions which wait for route calculation to complete (e.g. showing the maneuver icon only when there is a maneuver to show): Until now, waiting for route_status to take one of the two values route_status_path_done_new or route_status_path_done_incremental was sufficient because the event would not fire before maneuvers were complete. Asynchronous maneuver generation, however, may well be in progress when the trigger fires. Therefore, we'll probably want to introduce a new status indicator to indicate that maneuver creation has finished.

Apart from this, the current solution is hard-coded to always generate maneuvers asynchronously. We might want to change that maneuvers are generated asynchronously if and only if the route was also calculated asynchronously.

Last edited 7 years ago by mvglasow (2) (previous) (diff)

comment:7 Changed 7 years ago by mvglasow (2)

  • Summary changed from HighFive regression when route_depth tweak is used to Generate maneuvers asynchronously

comment:8 Changed 7 years ago by mvglasow (2)

Logic for synchronous/asynchronous maneuver generation is now in place as well. This leaves status as the last remaining issue.

comment:9 Changed 7 years ago by mvglasow (2)

We essentially have two options for status:

  • Add another flag to route.route_status. This would be fairly easy to implement, but this particular status is really about navigation rather than routing.
  • Introduce a new status attribute in navigation. This comes with more overhead but leaves the information with the object to which it belongs.

After a brief discussion with RobertP on IRC, I am now leaning towards the second option. I would give the navigation object a new attribute which indicates the status of the routing engine in user-friendly terms:

  • No destination: No route because no destination has been set.
  • Waiting for position: A destination has been set but routing cannot start until we have a valid position.
  • Calculation in progress: A destination has been set and a valid position is known, but route calculation is still in progress. This is the status from the moment we have both the current position and a destination until maneuver generation has finished. This status may also indicate rerouting (when deviating from a previously calculated route).
  • Navigating: A route with maneuvers has been calculated and the user is being guided.
  • No route: Navit cannot determine a route from the current position to the selected destination.

This would make the new attribute the single source of information for all status information that the user might be interested in, allowing it to be used e.g. to show/hide turn instruction OSDs depending on whether a route is available, or for a status indicator OSD.

comment:10 Changed 7 years ago by mvglasow (2)

Status is now implemented as navigation.nav_status. States are as described above, with one addition: since the route is recalculated each time the position changes, I have added a separate state for recalculation in progress. In real-life use, the status will continuously flip between "navigating" and "recalculating".

Furthermore I've fixed some bugs revealed by testing in real-world scenarios.

I've successfully tested the code against the following scenarios on the Munich-Łódź route:

  • Calculate a route with disabled vehicle and position entered manually
  • Stop navigation while maneuvers are being generated
  • Change destination while maneuvers are being generated
  • Repeat the above test cases with the demo vehicle, ensuring the vehicle moves along the route
  • Routing on an actual device (with a different route), including deviating from the route
  • OSD with enable_expression based on navigation.nav_status.

comment:12 Changed 7 years ago by mvglasow (2)

  • Resolution set to fixed
  • Status changed from assigned to closed
Note: See TracTickets for help on using tickets.