Bug 127186

Summary: ksysguardd uses bubble sort that calls a linear search function
Product: [Unmaintained] ksysguard Reporter: Greg Martyn <greg.martyn>
Component: generalAssignee: KSysGuard Developers <ksysguard-bugs>
Status: RESOLVED FIXED    
Severity: wishlist    
Priority: NOR    
Version First Reported In: unspecified   
Target Milestone: ---   
Platform: Compiled Sources   
OS: Linux   
Latest Commit: Version Fixed/Implemented In:
Sentry Crash Report:
Attachments: Use mergesort instead of bubblesort

Description Greg Martyn 2006-05-12 08:34:38 UTC 
Version:            (using KDE Devel)
Installed from:    Compiled sources

Valgrind profiling of ksysguardd reveals a function, get_ctnr in CContLib/ccont.c, that does a linear search through a linked list for an item at a given index. In my sample run it was called 3,000,000 times. Most of these calls were from a bubblesort function, bsort_ctnr. The bubble sort is already going through the items linearly, so there is no need to call an external function to retrieve an item by its index in the list.
Comment 1 Greg Martyn 2006-05-15 20:00:01 UTC 
Created attachment 16107 [details]
Use mergesort instead of bubblesort

time ksysguardd < commands.txt

where commands.txt contained:
monitors
ps
quit

went from:
--------
real	0m1.160s
user	0m1.060s
sys	0m0.084s
--------

to:
--------
real	0m0.186s
user	0m0.068s
sys	0m0.092s
--------

this should make ksysguard startup time much snappier

both benchmarks were run a couple times and the final value used (everything
was fresh in cache)
tests run on AMD 2800+ with 2gb ram
Comment 2 Dirk Mueller 2006-05-15 21:07:08 UTC 
wow, nice catch.
Comment 3 Greg Martyn 2006-05-20 10:51:16 UTC 
Fixed in revision 542608