xfdesktop 4.12.1 in Manjaro GNU/Linux hangs at startup for more than 2 minutes taking up a CPU core when a folder with many wallpapers (I have 6193 items, totalling 2.2 GB) is selected with a Random Order checkbox on. While xfdesktop process is hanging, the desktop has a light gray solid color, even though I have a black-green Vertical gradient color selected alongside the background images. 2 minutes later everything works fine: xfdesktop uses very little CPU and the background images are changed properly. There is no such issue with xfdesktop 4.12.0. I checked by downgrading package. I used the xfdesktop -Q && xfdesktop command to restart the process. My test results indicate that some algorithm with quadratic complexity with respect to the number of images in the directory is used at xfdesktop startup since version 4.12.1: number of images | xfdesktop startup in the directory | time (in seconds) 400 1 1200 5 2400 20 4800 77 6200 140
Created attachment 6236 Load image list in the background (Bug #11817) This patch makes xfdesktop load those image directories in an async callback and an idle loop so it doesn't block xfdesktop from doing other things. Same as how the settings dialog works for loading its wallpapers.
Created attachment 6237 Sorting optimization patch Hi Eric! First of all, thank you for your work on xfdesktop! It is *usually* stable and low on resources. I tried your patch. Even though loading images is asynchronous, it still isn't an optimal implementation. xfdesktop still consumes the same CPU resources at start-up. I suggest improving the algorithm complexity. Currently each file is inserted in the sorted linked list. This operation has an O(N^2) complexity and it is the reason for the start-up slowdown and consuming the CPU time. In the attached patch I sort an array instead, which has an O(N*log(N)) complexity. The modified version consumes much less CPU time with a big number of images. I also tried a simpler implementation with g_list_sort and no temporary array, but it proved to be significantly slower for many images and even slightly slower for 10 images, so I prefer the array-ed custom implementation regardless of the list size. The following table shows the average CPU consumption of xfdesktop at start-up in seconds for the 2 reimplementations: number of images | g_list_sort | sort_image_list 6192 1.54 0.61 3143 0.94 0.49 1626 0.63 0.43 604 0.47 0.40 314 0.39 0.35 179 0.36 0.35 150 0.35 0.34 100 0.35 0.34 10 0.34 0.33 The above table demonstrates that g_list_sort function is not very efficient because it uses stable sort, which is usually much slower than quick sort. Of course it is still much faster than the original implementation (g_list_insert_sorted in a loop). I also tried to optimize the settings dialog thumbnail preview code, because it consumes a lot of CPU time with many images in the directory. Even more than the original implementation of xfdesktop: 3 minutes and 30 seconds of CPU time for 6192 images. But that code looked more complicated to me. Besides I'm not very good in C and have no experience with GTK at all. It would be good if that code's author optimized it in his spare time. By the way, in this patch I also optimized xfdesktop-icon-view.c even though it probably isn't a bottleneck - just to eliminate this poor choice of sorting algorithm from the xfdesktop code. Regards, Igor
That is much better, thanks! Do you want to make it a full git patch so you can get credit for your work? I'll look into the doing the same for the settings dialog.
Created attachment 6239 Slightly improved git patch Improved my patch (added a comment; small optimization for 0 or 1 image list size) and formatted it with git. I profiled xfdesktop with callgrind/KCachegrind and found that compare_by_collate_key is very slow. When I replaced it with strcmp, both g_list_sort and sort_image_list implementations started in 0.5s with 6192 images. When I completely disabled sorting, the starting time was also 0.5s, so it is only sorting with compare_by_collate_key that is slow. xfdesktop can be further optimized for the Random Order case, when sorting is not useful. For random wallpaper order you could store images in an unsorted array instead of a sorted list. This way not only the sorting overhead would be eliminated, but also O(1) random access would be possible (currently the O(N) random list access is used when choosing the next random image). If you don't want to complicate the code with the array, you could at least sort the list only when Random Order option is/gets disabled. I also profiled xfdesktop-settings, but didn't find anything useful. Maybe it's because of the asynchronous loading of images. http://s10.postimg.org/m6ucayj61/xfdesktop_settings_KCachegrind_screenshot.png
Thanks again for your work! Yeah, I wasn't a fan of comparing by collate keys but quite a few people wanted/expected it to use the same order as thunar. Indeed, we can look into making xfdesktop do less when random or no cycling is selected. Pushed your patch to master in: commit 5650454c6e16389994b4628834c2aeba68551125 Author: Igor Kushnir <igorkuo@meta.ua> Date: Mon May 11 11:25:26 2015 +0300 Optimized loading wallpapers at start-up; optimized sorting icons in icon view. Signed-off-by: Eric Koegel <eric.koegel@gmail.com> http://git.xfce.org/xfce/xfdesktop/commit/?id=5650454c6e16389994b4628834c2aeba68551125 I'll cherry-pick it over to 4.12 once it gets a little more testing.
Created attachment 6240 Don't load an image list unless we're cycling So here's one change, this patch has xfdesktop only load the image list when the user has decided to cycle on that backdrop.
Comment on attachment 6236 Load image list in the background (Bug #11817) Marking this patch as obsolete.
> So here's one change, this patch has xfdesktop only load the image list when > the user has decided to cycle on that backdrop. The idea is especially useful for the user who selects one image from a directory with scores of files. I checked the patch and it reduced the start-up CPU time from 0.61 to 0.36 seconds when cycling is disabled. I'm not doing any code review, because I'm a C++ guy and know neither GTK and XFCE libraries, nor the xfdesktop code base. Besides I don't use that option (static background).
Hi Eric! I tried your last commit and it works great: xfdesktop spends only 0.47 seconds on start-up on average with Random Order and 6192 images. So this issue is effectively resolved. Maybe another one could be created for xfdesktop-settings, but I don't care very much about it as I rarely change those settings. I looked at your code and noticed that you created 2 similar comparison functions. I looked up the documentation (http://developer.gimp.org/api/2.0/glib/glib-Doubly-Linked-Lists.html#GCompareFunc), and it seems that both g_list and qsort require the same function pointer type: gint (*GCompareFunc)(gconstpointer a, gconstpointer b); is the same as int (*comp)(const void *, const void *); I'd leave just one function and remove all the casting, e.g.: backdrop->priv->image_files = g_list_insert_sorted(backdrop->priv->image_files, changed_file, (GCompareFunc)glist_compare_by_collate_key); -> backdrop->priv->image_files = g_list_insert_sorted(backdrop->priv->image_files, changed_file, compare_by_collate_key); Or am I missing something?
I also noticed that you use g_list_length() in several places, among them the xfce_backdrop_choose_random() function which can be called quite often. g_list_length has to traverse the entire list to find its size. Doesn't it make sense to cache the list size? There is a special class for this GQueue: http://developer.gimp.org/api/2.0/glib/glib-Double-ended-Queues.html#glib-Double-ended-Queues.description If GList gets replaced by GQueue, the file_count variable in list_image_files_in_dir() and the list_size parameter in sort_image_list() will no longer be needed.
Even better data structure for storing images is GPtrArray (https://developer.gnome.org/glib/stable/glib-Pointer-Arrays.html#GPtrArray), because images rarely get inserted to or erased from the middle of the list. And even if they do, the complexity is O(N) in the current implementation and it will remain O(N) with an array, so there will be no big insertion/deletion performance regression. Combined with stdlib functions qsort and bsearch, the array data structure will provide the best performance because each of the functions (choose_next, choose_random and choose_chronological) will work with either O(1) or O(log(N)) complexity. As a small bonus: this array data structure will occupy 1.5-3 times less memory. On the other hand, switching to a different data structure is a major change, it is not going to significantly improve performance, so maybe not warranted.
OK, I see what's the difference between the 2 comparison functions. There is an extra indirection in the qsort_ version. Looks like the gdk developers made the comparison function semantics subtly different from the standard one.
I just found that the speed advantage of qsort was bogus and only caused by the wrong implementation (the list was already sorted by that address comparison criterion). So, it's back to 1.54 seconds for 6192 images with Random Order off :( The qsort_compare_by_collate_key() and sort_image_list() functions can be safely removed and their usage replaced by g_list_sort().
I think I know of a way to gain a major sorting speed-up, so please don't remove qsort just yet. I'll implement the optimization soon and attach a patch.
Created attachment 6245 Much faster sorting + test code
Created attachment 6246 Much faster sorting (without test code) In this patch I cache collation keys and this dramatically improves performance: from 1.54 to 0.51 seconds for 6192 images with Random Order off. This time I verified that the sorting function works correctly (it passes my tests). Pick one of the 2 attached patches depending on whether the test code in one of them makes sense.
Awesome, thanks again for the patches and help testing! I pushed the patch with the test code to master. commit 753b67d0e868818cc8d9978154e2fea2fee9206a Author: Igor Kushnir <igorkuo@gmail.com> Date: Wed May 13 20:58:04 2015 +0300 Optimized sorting wallpapers; added sorting test code. Signed-off-by: Eric Koegel <eric.koegel@gmail.com> http://git.xfce.org/xfce/xfdesktop/commit/?id=753b67d0e868818cc8d9978154e2fea2fee9206a
Cherry-picked the patches over to the 4.12 branch and did a release. Marking this bug closed. Thanks again for the help!