[Xfce-bugs] review granted: [Bug 11817] Slow startup when a folder with many wallpapers is selected : [Attachment 6237] Sorting optimization patch

[bugzilla-daemon at xfce.org]

Igor Kushnir <igorkuo at meta.ua> has granted  review:
Bug 11817: Slow startup when a folder with many wallpapers is selected
https://bugzilla.xfce.org/show_bug.cgi?id=11817

Attachment 6237: Sorting optimization patch
https://bugzilla.xfce.org/attachment.cgi?id=6237&action=edit



--- Comment #2 from Igor Kushnir <igorkuo at meta.ua> ---
Created attachment 6237
  --> https://bugzilla.xfce.org/attachment.cgi?id=6237&action=edit
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