Skip to content

Draft: performance improvements Tiling and NoneEmptyIterator for GPS mapsearch

This PR fixes a some performance issues observed with the map search.

  1. One could end up in an infinite repaint/prepareTiles loop. This occurred if after resizing one would zoom out from a smaller map.
  2. With the marble backend the level used for tiling is quite high and with enough images (eg a few 1000) performance got really bad (multiple seconds to compute the clusters). The main bottlneck was the NonEmptyIterator and the structure of the tiles. Even if a tile only had one child we would iterate through all 100 possible children.

The fix to 1. is simple and is in the first commit of this PR.

For 2. I changed the Tiles to have a Map from index to children instead of having an array of size Tiling*Tiling with potentially nullptrs. Then in the NoneEmptyIterator we can keep an iterator of that map such that we really only try non-empty tiles. For this I require the invariant that all Tiles ever created are non-empty. I pulled common functionality back into AbstractMarkerTiler. The benchmark in test_itemmarkertiler previously took a few seconds on a debug build while now it takes 200ms.

The modification of the Tile structure during iteration would now lead to a crash while previously only to weird behaviour (This did happen with the google maps backend and qwebengine). But there are only two uses of the NonEmptyIterator and I checked both of them and added asserts as well.

On the change to AbstractMarker::Tile and TileIndex:

  1. I made Tile have virtual methods. This adds a vtable pointer to each tile, but previously we had a 10x10 grid of pointers, which was much larger, so the claimed saving in size wasn't big. Also one of the derived classes already added a virtual dtor.
  2. By adding virtual functions a lot of logic could be simplified and moved into the tile instead of having it in the *MarkerTiler subclasses.
  3. I added some tests and (hopefully) better handling for rounding in conversion to and from coordinates.
Edited by justus schwartz

Merge request reports