So, just for fun I benchmarked the code. I didn't do it with
profiling turned on to give the optimizer a decent chance at
generating fast code (compiled with -O2). It just so happens I have a
1.33GHz PowerBook with 1GB of RAM, which is pretty close to what this
guy was working with. I used "time" to benchmark the code's execution
time. I didn't try to benchmark memory utilization, which I supposed
I should do. Anyway, here's what I got on the first run (I ran the
benchmarks twice and saw <5% variance, and it seemed to be a random
distribution which I presume is just a function of the random
datasets rather than anything significant):
100,000 elements, qsort1:
real 0m1.812s
user 0m1.515s
sys 0m0.075s
1,000,000 elements, qsort1:
real 0m24.688s
user 0m20.781s
sys 0m0.744s
2,000,000 elements, qsort1:
real 0m54.258s
user 0m46.873s
sys 0m1.496s
100,000 elements, qsort3 (~57.5% the runtime):
real 0m1.041s
user 0m0.864s
sys 0m0.043s
1,000,000 elements, qsort3 (~62.5% the runtime):
real 0m15.434s
user 0m13.295s
sys 0m0.455s
2,000,000 elements, qsort3 (~60.1% the runtime):
real 0m32.599s
user 0m28.070s
sys 0m0.900s
As you can see, while qsort3 seems to be much faster than qsort1,
it's runtime stays near 60% of the runtime of qsort1even when the
element sizes increase 10x or even 20x. Given that qsort3 shows an n
(log(n)) growth pattern, you can infer that so does qsort1.
I also did profiling runs without optimizations cranked up, and you
can see the results attached. It shows that while qsort3 does
allocate substantially less memory allocation than qsort1, they both
show slightly more than a 10 fold increase in memory allocations when
working with a 10x larger data set. This again implies that they are
both using O(n) memory.
--Chris "I told you so" Smith
--
KPLUG-LPSG@kernel-panic.org
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
