GNOME Bugzilla – Bug 324724
o(n^2) slowdown in e_cal_backend_cache_get_components
Last modified: 2013-09-14 16:49:59 UTC
Subscribe to this webcal: webcal://ical.mac.com/ical/DVDs.ics (this is the torture test I use for the ical code) CPU load goes up to 100% and Evolution UI stops refreshing. On repeatedly breaking into the e-d-s process, there seems to be a slow loop here:
+ Trace 64743
It's building a long g_list by repeatedly appending to the end; this is O(n^2) behaviour: (gdb) print list->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next->next $24 = (GList *) 0x94b9ce8 (yes, it's a long list). Looks like the function needs an end-of-list temporary to optimize the construction of the "list" local
To add to the above reasons, the main reason for 100% cpu is that, the ical object is parsed from the ical string every time. All the ical objects are hashed based on the uid as a key and ical string as a value. So a search expression which queries for appointments between a <start date> to a <end date> will have to get all the ical strings, parse them to check if it matches the search expression. If there are very large number of appointments as in this case, the cpu raises to 100%. This should be optimized.
Dave, Thanks for pointing that out. A prize catch :-). Now that I am looking at this I might as well take a closer look at the cache search logic and see if we can tame the beast better.
hmm... harish, are there any news on this?
removing old target milestone
Duh..The patch addressing the above g_list_append evil as well as the usage of xx_get_components in the backends has been rotting on my patch queue for ages now..thanks for the wake-up call :-) Testing this and committing this for the 1.7.4 release.
well - i am not done testing on revamping the cache usage - but realize albeit late that the O(n^2) could have been addressed with a 2 line change..committed the same.
harish: thanks for looking into this! :-) http://cvs.gnome.org/viewcvs/evolution-data-server/calendar/libedata-cal/e-cal-backend-cache.c?r1=1.28&r2=1.29 (adding diff link here just for tracking, because changelog entry did not include the bug id.)