... while a hash is purported to be O(1).

Don't blame the hash lookup performance here.

The thing that slows the dispatch table is simply that subroutines in Perl are slow relative to inline blocks.

If you make it so that the ifelse chain also has to do hash lookups, and the dispatch table doesn't call the subroutines, it (unsurprisingly) makes the dispatch table fastest even for very low numbers of choices:

C:\test>587072 -N=10 -KEYS=a,b
dispatch =>
# line 1 "dispatch.pl"
        my $x += ( $dispatch{ $_ } ||= $dispatch{ default } )  for @da
+ta;

ifelse =>
# line 1 "ifelse.pl"
        for( @data ) {
            if( $_ eq "a" ) { my $x = $dispatch{ a } }
            elsif( $_ eq "b" ) { my $x = $dispatch{ b } }
            else{ my $x = $dispatch{ default } }
        }

            Rate   ifelse dispatch
ifelse   39306/s       --     -29%
dispatch 55351/s      41%       --
[download]

Equally, if we have both call the subroutines, the dispatch table wins:

C:\test>587072 -N=10 -KEYS=a,b
dispatch =>
# line 1 "dispatch.pl"
        my $x += ( $dispatch{ $_ } ||= $dispatch{ default } )->()  for
+ @data;

ifelse =>
# line 1 "ifelse.pl"
        for( @data ) {
            if( $_ eq "a" ) { my $x = $dispatch{ a }->() }
            elsif( $_ eq "b" ) { my $x = $dispatch{ b }->() }
            else{ my $x = $dispatch{ default }->() }
        }

            Rate   ifelse dispatch
ifelse   21966/s       --     -15%
dispatch 25880/s      18%       --

C:\test>587072 -N=10 -KEYS=a,b,c
dispatch =>
# line 1 "dispatch.pl"
        my $x += ( $dispatch{ $_ } ||= $dispatch{ default } )->()  for
+ @data;

ifelse =>
# line 1 "ifelse.pl"
        for( @data ) {
            if( $_ eq "a" ) { my $x = $dispatch{ a }->() }
            elsif( $_ eq "b" ) { my $x = $dispatch{ b }->() }
            elsif( $_ eq "c" ) { my $x = $dispatch{ c }->() }
            else{ my $x = $dispatch{ default }->() }
        }

            Rate   ifelse dispatch
ifelse   16250/s       --     -22%
dispatch 20798/s      28%       --
[download]

But if you leave the lookups in both, but only have the dispatch table call the subs, the ifelse chain wins upto similar numbers to those you report:

C:\test>587072 -N=10 -KEYS=a,b,c,d,e,f,g
dispatch =>
# line 1 "dispatch.pl"
        my $x += ( $dispatch{ $_ } ||= $dispatch{ default } )->()  for
+ @data;

ifelse =>
# line 1 "ifelse.pl"
        for( @data ) {
            if( $_ eq "a" ) { my $x = $dispatch{ a } }
            elsif( $_ eq "b" ) { my $x = $dispatch{ b } }
            elsif( $_ eq "c" ) { my $x = $dispatch{ c } }
            elsif( $_ eq "d" ) { my $x = $dispatch{ d } }
            elsif( $_ eq "e" ) { my $x = $dispatch{ e } }
            elsif( $_ eq "f" ) { my $x = $dispatch{ f } }
            elsif( $_ eq "g" ) { my $x = $dispatch{ g } }
            else{ my $x = $dispatch{ default } }
        }

            Rate dispatch   ifelse
dispatch 10511/s       --      -8%
ifelse   11428/s       9%       --

C:\test>587072 -N=10 -KEYS=a,b,c,d,e,f,g,h
dispatch =>
# line 1 "dispatch.pl"
        my $x += ( $dispatch{ $_ } ||= $dispatch{ default } )->()  for
+ @data;

ifelse =>
# line 1 "ifelse.pl"
        for( @data ) {
            if( $_ eq "a" ) { my $x = $dispatch{ a } }
            elsif( $_ eq "b" ) { my $x = $dispatch{ b } }
            elsif( $_ eq "c" ) { my $x = $dispatch{ c } }
            elsif( $_ eq "d" ) { my $x = $dispatch{ d } }
            elsif( $_ eq "e" ) { my $x = $dispatch{ e } }
            elsif( $_ eq "f" ) { my $x = $dispatch{ f } }
            elsif( $_ eq "g" ) { my $x = $dispatch{ g } }
            elsif( $_ eq "h" ) { my $x = $dispatch{ h } }
            else{ my $x = $dispatch{ default } }
        }

           Rate dispatch   ifelse
dispatch 9558/s       --      -1%
ifelse   9635/s       1%       --

C:\test>587072 -N=10 -KEYS=a,b,c,d,e,f,g,h,i
dispatch =>
# line 1 "dispatch.pl"
        my $x += ( $dispatch{ $_ } ||= $dispatch{ default } )->()  for
+ @data;

ifelse =>
# line 1 "ifelse.pl"
        for( @data ) {
            if( $_ eq "a" ) { my $x = $dispatch{ a } }
            elsif( $_ eq "b" ) { my $x = $dispatch{ b } }
            elsif( $_ eq "c" ) { my $x = $dispatch{ c } }
            elsif( $_ eq "d" ) { my $x = $dispatch{ d } }
            elsif( $_ eq "e" ) { my $x = $dispatch{ e } }
            elsif( $_ eq "f" ) { my $x = $dispatch{ f } }
            elsif( $_ eq "g" ) { my $x = $dispatch{ g } }
            elsif( $_ eq "h" ) { my $x = $dispatch{ h } }
            elsif( $_ eq "i" ) { my $x = $dispatch{ i } }
            else{ my $x = $dispatch{ default } }
        }

           Rate   ifelse dispatch
ifelse   8092/s       --      -6%
dispatch 8566/s       6%       --
[download]

I thought I read somewhere that subroutine call performance had been improved in bleedperl, but I cannot find the reference?

BrowserUk,
Don't blame the hash lookup performance here.

I didn't. To quote myself from the very next sentence: The hash does have the overhead of looking up the key, dereferencing the value, and executing the code ref. I knew that subroutine overhead is expensive - I even wrote a node inquiring into optimizing them a few years ago: (Inline subs?).

I am glad you replied and allocated the majority of the performance hit to the correct culprit. Unfortunately, typical dispatch tables use code refs. I hear lots of good things about bleed perl so hopefully 5.10 will be released soon.

Cheers - L~R

I was trying to point out that "the overhead of looking up the key, dereferencing the value," is marginal relative to the overhead of "executing the code ref".

Even that last phrase slightly conflates

• the process of invoking the sub;
• executing the code it contains.

I realise that you know the difference, but your wording--combined with your use of "purported"--tended to imply that "looking up the key" was a significant factor. Which it isn't. I sought to demonstrate this.

Unfortunately, typical dispatch tables use code refs.

It wouldn't be a dispatch table if it didn't :). I agree, you cannot avoid the overhead of calling the subroutine.

I had a couple of cracks at coding a 'macro processor'--really just a sub inliner a couple of years ago.one of them may even be posted here somewhere?--using source filters, but it was never very satisfactory.

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

I think performance optimization should not be the principle determining factor in deciding which technique to use. Unless your application is running unacceptably slowly and you've identified the multi-branch if/else section as a bottleneck, it's ridiculous to change that to something else just for a performance gain.

Maintainability, and design — as in consistency of — those are of primary importance.

I like dispatch tables. They're clever. But at the same time, they raise a red flag for me — the same one I see whenever hashes are used to store a static set of entities in an application: It completely undermines the safety of strict. (There are steps you can take to regain some of this safety, such as using Tie::StrictHash.)

The solution is to make the subs named class methods. I recently did this on a project at work.

I had two dispatch tables, one for the "real" functions and one for a set of stubs, to be used when debugging.

Old way:

my %real_functions = (
  wipe_system => sub { system "rm -rf /" },
);
my %debug_stubs = (
  wipe_system => sub { warn "wiping system (no, not really)\n" },
);

my $funcs = 
    $debug
    ? \%debug_stubs
    : \%real_functions;

$funcs->{'wipe_system'}->();
[download]

New way:

{
    package SystemFunctions::Real;
    sub wipe_system {
        shift; # will be the class name
        system "rm -rf";
    }
}
{
    package SystemFunctions::Debug;
    sub wipe_system {
        shift; # will be the class name
        warn "wiping system (no, not really)\n";
    }
}

my $funcs = 
    $debug
    ? 'SystemFunctions::Real'
    : 'SystemFunctions::Debug';

$funcs->wipe_system();
[download]

Now, it sometimes won't be convenient to do this, due to the complication of packages. In my case, it was; in fact, it was a significant improvement, since it gave me a convenient place to encapsulate all my "system functions", which hitherto had lived in the main namespace.

In the very simplest cases, you don't need to worry about packages at all:

my %dispatch = (
  incr => sub { $x++ },
  decr => sub { $x-- },
);
$dispatch{$op}->();
[download]

sub incr { shift; $x++ }
sub decr { shift; $x-- }

main->$op();
[download]

Note: I only left the shift in as a reminder that it will always be necessary unless the sub takes no arguments (or, as I sometimes do, you pop the args rather than shifting them).

Finally, what about default cases? One possibility is to use AUTOLOAD.

While the code reduction and maintainability is still an advantage, the performance boost may not be all it is cracked up to be.

I summon chromatic's second rule of performance optimization: You're doing IO! That's almost always the slow part!

chromatic,
In private /msg with madbombX I made this very point. When benchmarking it is important to eliminate as many factors unrelated to what you are testing as possible. In my benchmark generating code however, no IO comes into play (that I can see anyway). This is strictly determining the difference between a series of equality tests (linear search) and a hash lookup, reference dereference, and nearly empty sub execution.

Cheers - L~R

In mumble years of programming, I can't think of a single example where the overhead of a dispatch table versus cascading conditionals made a whit of difference compared to the cost of performing IO. Therefore, unless I ever write a FFT or a petabyte-Ethernet driver, I don't see much point to worrying about a handful of milliseconds of difference between two constructs where one is so much more maintainable than the other.

Then again, almost every program I've ever written performs some sort of IO somewhere.

As it's the holidays, can I wish that Benchmark refused to give meaningful results for syntax questions and only helped profile various algorithms?

chromatic already has the IO part handled but your comparison is also getting dwarfed by making those function calls. Remove those too, they're one of the more expensive things you can do in perl (except for IO and just deliberately sleeping).

⠤⠤ ⠙⠊⠕⠞⠁⠇⠑⠧⠊

The values in @find are integers, but in the if_else comparison tree, you test for string equality.

Testing the hash for existance of a key first, seems wasteful. It might be faster if you did an eval and only acted on failure in that case. Of course, I haven't benched that, yet.

My theory: maybe, just maybe, perl does the thing C used to (and maybe still does) and and builds if-else chains into a hash table for evaluation. Dunno.

--traveler

Avoiding exists:

($dispatch{$item} || $dispatch{default})->()
[download]

runrig,
The issue that traveler pointed out was that I tested if a key existed when I didn't need to. Only when the user defines the -u option is it necessary to test for the hash key's existance. Without the -u, there is no default condition and the exists can be avoided. I corrected the template accordingly.

You have mentioned an alternative way of determining which sub to dispatch. Unfortunately it may actually be less efficient than exists. You are fetching the value and testing it for truth where exists need only check to see if the key is present in the hash.

Cheers - L~R

runrig++, very clever. I had to stare at it for a second to realize what was going on.

traveler,
The values are integers only because it made enumerating easier. The string equality is intentional. The 1 .. n could have as easily been 'a' .. 'z'.

The testing for the hash key existance is necessary sometimes (default condition). The template didn't discriminate and always added it. Thanks to your keen eye, it has been fixed. It did not change the results that much with or without default conditions.

Cheers - L~R

The values are integers only because it made enumerating easier. The string equality is intentional. The 1 .. n could have as easily been 'a' .. 'z'.

OK. But doesn't that make the ifelse code slower because it has to stringify and/or do string comparison, while the hash can do an integer comparison?

I did try another test. Since the values were integers I replaced the dispatch table hash with an array and performance improved, but not enough to catch the ifelse. I am still quite confused.

I must admit that my eyes popped somewhat at "I have re-written your code to be much more efficient." in that node. However I was too busy to bother benchmarking it and the dispatch table is much cleaner than the original code in any case so I let it go.

I'm glad to see that you've followed up with some actual testing and the result doesn't much surprise me. Another thing to consider is that if at the time of coding you know the likely hit rate for each of the tests, the chained if/elsif can be much more efficient by testing the most likely hits first. That is still nasty code to write, test and maintain compared with the dispatch table, but stooping to "assembly language" techniques has to be a win sometimes. :)

GrandFather,
I am not sure if you looked at the options of this benchmark generating code but I included the ability for testing likely hit rates.

Cheers - L~R

I admit to my shame that I didn't do more than glance at your code and missed that (let's blame pressure of work). However I really intended to suggest that an implementor of such code ought consider the effect of such an optimisation, rather than that you would be remiss in not accounting for it in your benchmark. Kudos for allowing for hit rate optimisation though!

---

DWIM is Perl's answer to Gödel

Luckely for me, most of the time, the milliseconds are not important, and I can use both Perl, and whatever technique I find more readable/maintainable.