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