Wow! Devel::OpProf. My toolbox just got bigger...

So, the follow-up question: is there a better way to code max() than the control structure I used? The theory is that sort() should be less efficient than max(). There must be a more efficient way to code max(), then. max() should be in O(1), where Perl's sort is (usually) in O(N log N). How can we get the best performance for the "greatest value less than another value" algorithm?

Russ

Okay, here is the max() given in Mastering Algorithms with Perl (O'Reilly):

sub max { # Numbers.
    my $max = shift;
    foreach ( @_ ) { $max = $_ if $_ > $max }
    return $max;
}
[download]

So, modifying that to fit into our existing benchmark/profiling code, it looks like:

foreach ( keys %{$url{'monday'}} ) { $now = $_ if $_ > $now }
[download]

And then, the score:

grep constant item 2 numeric le (<=) 1000 shift 1 sort 1 hash dereference 2 hash element 1 pushmark 10 grep 1 grep iterator 1000 scalar variable 2001 next statement 6 list slice 1 scalar assignment 2 keys 1 subroutine exit 1 block 1000 array dereference 1 glob value 5 private variable 3 subroutine entry 4	if/then/else constant item 993 foreach loop entry 1 shift 1 foreach loop iterator 1001 iteration finalizer 1000 hash dereference 2 hash element 1 pushmark 7 scalar variable 4992 next statement 1007 logical and (&&) 2001 scalar assignment 1001 conditional expression 1000 keys 1 subroutine exit 1 loop exit 1 array dereference 1 glob value 6 private variable 3 subroutine entry 4 numeric lt (<) 1992	book max() constant item 1 foreach loop entry 1 shift 1 foreach loop iterator 1001 iteration finalizer 1000 hash dereference 2 numeric gt (>) 1000 hash element 1 pushmark 7 scalar variable 2292 next statement 2006 logical and (&&) 2001 scalar assignment 147 keys 1 subroutine exit 1 loop exit 1 array dereference 1 glob value 6 private variable 3 subroutine entry 4
Benchmark: timing 10000 iterations of bench_grep, bench_if_then, bench_max... bench_grep: 115 wallclock secs (111.04 usr + 0.01 sys = 111.05 CPU) @ 90.05/s (n=10000) bench_if_then: 73 wallclock secs (70.02 usr + 0.01 sys = 70.03 CPU) @ 142.80/s (n=10000) bench_max: 64 wallclock secs (62.72 usr + 0.01 sys = 62.73 CPU) @ 159.41/s (n=10000)

---

Well, we have some surprises here! grep comes in last, even though it has the least operations. As you can see, not all operations are equal... but the book technique is the big winner. Which tells me it was worth the $35US.

The results also show that Devel::OpProf is a useful tool, but only as an accessory to Benchmark. On it's own, it can be misleading.

Paris Sinclair    |    4a75737420416e6f74686572
pariss@efn.org    |    205065726c204861636b6572
I wear my Geek Code on my finger.

Very interesting.

I started with the Mastering Perl Algorithms code (I left it in a subroutine), and abandoned it for the ternary when the ternary was faster. Of course, the subroutine entry was the main speed bottleneck.

This is fascinating. In the if/then/else results, we pay a considerably higher cost for the "constant item," "scalar variable" and "scalar assignment" operations. I wonder why that is so... Even the numeric comparison is more expensive in if/then/else than book max.

Also, your grep benchmarked slower than if/then/else. I saw the opposite. Would you post your complete code, to let me compare?

Thanks, you've made a fantastic post!

Russ