Improve responsiveness in address search

[aerostitch]

Issue migrated from trac ticket # 1305

component: gui/internal | priority: major

2015-06-17 03:52:11: @mvglasow created the issue

---

Address search is currently slow since navit starts searching as soon as a character is entered. I currently see two was to improve this:

The easy solution: Introduce a delay for starting search. Instead of (re-)starting search immediately after each character, do so only if no new characters have been entered for ~2 seconds. (This is quite a standard procedure which I have seen in other applications as well.) That way search won't start running while the user is still typing (unless the user is a really slow typist).

The perfect solution: Multithreading. Have search run in a different thread. When a new character is entered, stop the current search thread and start a new one. That way the UI will remain responsive while search is in progress.

Both approaches can eventually be combined, thus implementing the first does not rule out implementing the other at some later point.

[aerostitch]

2015-10-14 07:24:27: @mvglasow commented

---

Another option might be to run the actual search in an idle loop, similar to routing. I just developed something similar for maneuver generation, see #1324.

[aerostitch]

2015-10-14 07:34:52: @mvglasow commented

---

I see the internal GUI already has a function gui_internal_search_idle() and thus apparently implements the idle loop solution. So we have to find out where the delay occurs: either outside the loop (which means the respective operations would need to be split up and moved into another idle loop) or inside the loop (which means we'd need to shorten the time spent inside each call to the loop function, possibly at the cost of increasing the number of calls).

Note that the delay is heavily device-dependent (the effect is more serious on a mobile device than on my laptop).

[aerostitch]

2015-10-15 07:55:28: @mvglasow commented

---

Just profiled the calls and it turns out that the first instance of gui_internal_search_idle() takes about 50 times as long as the subsequent ones. The extra time, it seems, is spent inside search_list_get_result(). The latter gets called once per instance of gui_internal_search_idle(), but only the first call of each search operation takes that long.

Analysis revealed the following call stack:

binmap_search_street_by_place()
binmap_search_new() // via m->meth.map_search_new()
map_search_new()
mapset_search_get_item()
search_list_get_result()
gui_internal_search_idle()
...

This happens only on the first call (when initializing the result list). binmap_search_street_by_place() indeed has a while loop which goes through streets one by one.

This is probably a bit big to process atomically – searching Munich for all streets containing the letter "S" takes about 0.2s on a laptop, but much longer on "weaker" devices.

I'm just not sure how to split that up, as the whole call sequence is already happening inside an idle loop...

[aerostitch]

2015-10-18 12:54:49: tryagain commented

---

Actually, binmap_search_street_by_place() iterates over all items which belong to all tiles covering a single point. That's at most 18 tiles, and we attempt to keep them as small as possible. Though, unfortunately, sometimes we meet tiles of above 1MB size.

For other delays, related to actually checking all items in all tiles covering given town, i think the following optimization could help.

We have a special item reference, &busy_item, defined in item.c

It is used in graphics.c and binfile.c to properly cooperate during map file download. (Sorry, map download seems to be broken now, at least i was unable to fire it up.)

But the idea behind busy_item is following: we can return it at line 2302 of binfile.c. Then idle function should decide if it's time to let other operations run. I guess we could return busy_item each, say, 1000 iterations without any performance problems. Decision to interrupt or to continue idle function, at best, should be time-dependent.

This would require some search.c changes as well as other search results consumers (android native search, other GUIs, dbus binding) should become aware of this new feature. I think these changes would be trivial.

[aerostitch]

2015-10-18 12:54:49: tryagain