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).