Implement nearest neighbor search for common deserialization path
This significantly drops the overhead of deserializing GWeatherLocation
from GVariant
which hottest path is in gweather_location_common_deserialize()
.
Particularly because it was nearing O(n²). When doing a simple search from gnome-clocks
we clocked in around 500,000 to 1,000,000 GWeatherLocation
instances allocated and freed.
Instead, at startup, a kdtree is built using the lat/lon positions of == GWEATHER_LOCATION_CITY
along with it's index in the World.locations
of the GVariant
database.
Not all of the find_nearest_city()
variants have been implemented because they would require an additional parameter of the allotted distance before additional filtering is applied. The most important hot path, however, is drastically reduced into a fraction of a percent of overhead according to Sysprof.
Simple testing with Sysprof shows this takes things from about 15% search time in gnome-clocks
to about 2%.
We're still easily creating 10s of thousands of GWeatherLocation
though and solving that would be how you get this into the .25%
CPU range.