Bug 127186 - ksysguardd uses bubble sort that calls a linear search function
Summary: ksysguardd uses bubble sort that calls a linear search function
Status: RESOLVED FIXED
Alias: None
Product: ksysguard
Classification: Applications
Component: general (show other bugs)
Version: unspecified
Platform: Compiled Sources Linux
: NOR wishlist
Target Milestone: ---
Assignee: KSysGuard Developers
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2006-05-12 08:34 UTC by Greg Martyn
Modified: 2006-05-20 10:51 UTC (History)
0 users

See Also:
Latest Commit:
Version Fixed In:


Attachments
Use mergesort instead of bubblesort (3.04 KB, patch)
2006-05-15 20:00 UTC, Greg Martyn
Details

Note You need to log in before you can comment on or make changes to this bug.
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