Implement nearest neighbor search for common deserialization path

Merged Christian Hergert requested to merge wip/chergert/kdtree into main

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.

Edited by Christian Hergert

Merge request reports