Skip to content

add non-empty child list to Tile to speed up non empty tile iteration

sorry, but this is again a bit larger. but it would also be the final PR in the series to speed up the NonEmptyChild iteration.

below some details on the change:

as we maintain the invariant that all Tile have at least one item we can speed up iteration by adding a list of non-empty children.

the QVEctor<int> nonEmptyIndices is kept sorted at all times. so we can implement a function Tile::nextNonEmptyIndex(int linearIndex) using binary search.

Previously the NonEmptyIterator would iterate over all children which are in bounds and then check if they are empty. As most positions usually are empty this is wasteful. This change iterates over all nonEmpty children and skips the ones that are not in bounds.

This change speeds up the benchmark test (in a debug build) by roughly a factor of six (from 4.5seconds to 0.7seconds). On a large collection of geolocated photos this makes the map search widget a good bit more responsive.

This is mostly a problem with the marble backend as the zoom levels are a bit too large (i think).

Merge request reports