Re: When should I use a dispatch table?

... 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?

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.

Comment on Re: When should I use a dispatch table? Select or Download Code

Replies are listed 'Best First'.
Re^2: When should I use a dispatch table? by Limbic~Region (Chancellor) on Dec 01, 2006 at 01:14 UTC
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	[reply]
Re^3: When should I use a dispatch table? by BrowserUk (Patriarch) on Dec 01, 2006 at 01:36 UTC
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.	[reply]


Syntactic Confectionery Delight
	PerlMonks