Igor Kushnir <[email protected]> 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 <[email protected]> --- 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 _______________________________________________ Xfce-bugs mailing list [email protected] https://mail.xfce.org/mailman/listinfo/xfce-bugs
