in reply to Re: A better way of lookup?
in thread A better way of lookup?

I must admit, like RichardK, I was skeptical about the benefits of using elsifs where the logic short-circuits with returns anyway, and immediately tried switching from your:if( cond ) { return x; } form to the statement modifier form: return x if cond;; and ... it made no difference. elsif still won out.

So then I looked at -MO=Deparse,-x9 to see if if/elsif/else chains were perhaps being converted to some kind of jump table or switch.

But no. They appear to be implemented as (the equivalent of) a chain of nested ternaries, but when I tried coding them that way, they were still slower than the if/elsif/else chain?

I then turned my attention to your rather more interesting innovation; namely (partially) unrolling a binary search. I tried adding another level, and got greater benefit; then another and (reduced, but) still more; so then another; and the benefits ran out :(

My (long and winding) benchmark and results are here:

#! perl -slw use strict; use Benchmark qw[ cmpthese ]; sub lookup1 { my $v = shift; return 2500 if $v < 25000; return 5000 if $v < 50000; return 12500 if $v < 150000; return 25000 if $v < 225000; return 37500 if $v < 300000; return 60000 if $v < 600000; return 120000 if $v < 1200000; return 300000 if $v < 3600000; return 600000 if $v < 5400000; return 900000 if $v < 10800000; return 1800000 if $v < 21600000; return 3600000 if $v < 43200000; return 7200000 if $v < 64800000; return 10800000 if $v < 129600000; return 21600000 if $v < 216000000; return 43200000 if $v < 432000000; return 86400000 if $v < 864000000; return 172800000 if $v < 1728000000; return 345600000 if $v < 3024000000; return 604800000 if $v < 6048000000; return 1209600000 if $v < 12096000000; return 2629800000 if $v < 31557600000; return 5259600000 if $v < 63115200000; return 7889400000 if $v < 78894000000; return 15778800000 if $v < 157788000000; return 31557600000; } sub lookup1a { my $v = shift @_; $v < 25000 and return 2500; $v < 50000 and return 5000; $v < 150000 and return 12500; $v < 225000 and return 25000; $v < 300000 and return 37500; $v < 600000 and return 60000; $v < 1200000 and return 120000; $v < 3600000 and return 300000; $v < 5400000 and return 600000; $v < 10800000 and return 900000; $v < 21600000 and return 1800000; $v < 43200000 and return 3600000; $v < 64800000 and return 7200000; $v < 129600000 and return 10800000; $v < 216000000 and return 21600000; $v < 432000000 and return 43200000; $v < 864000000 and return 86400000; $v < 1728000000 and return 172800000; $v < 3024000000 and return 345600000; $v < 6048000000 and return 604800000; $v < 12096000000 and return 1209600000; $v < 31557600000 and return 2629800000; $v < 63115200000 and return 5259600000; $v < 78894000000 and return 7889400000; $v < 157788000000 and return 15778800000; return 31557600000; } sub lookup2 { my $v = shift; if ( $v < 25000 ) { return 2500; } elsif( $v < 50000 ) { return 5000; } elsif( $v < 150000 ) { return 12500; } elsif( $v < 225000 ) { return 25000; } elsif( $v < 300000 ) { return 37500; } elsif( $v < 600000 ) { return 60000; } elsif( $v < 1200000 ) { return 120000; } elsif( $v < 3600000 ) { return 300000; } elsif( $v < 5400000 ) { return 600000; } elsif( $v < 10800000 ) { return 900000; } elsif( $v < 21600000 ) { return 1800000; } elsif( $v < 43200000 ) { return 3600000; } elsif( $v < 64800000 ) { return 7200000; } elsif( $v < 129600000 ) { return 10800000; } elsif( $v < 216000000 ) { return 21600000; } elsif( $v < 432000000 ) { return 43200000; } elsif( $v < 864000000 ) { return 86400000; } elsif( $v < 1728000000 ) { return 172800000; } elsif( $v < 3024000000 ) { return 345600000; } elsif( $v < 6048000000 ) { return 604800000; } elsif( $v < 12096000000 ) { return 1209600000; } elsif( $v < 31557600000 ) { return 2629800000; } elsif( $v < 63115200000 ) { return 5259600000; } elsif( $v < 78894000000 ) { return 7889400000; } elsif( $v < 157788000000 ) { return 15778800000; } else { return 31557600000; } } sub lookup2a { my $v = shift @_; $v < 25000 ? do { return 2500 } : (do { $v < 50000 } ? do { return 5000 } : (do { $v < 150000 } ? do { return 12500 } : (do { $v < 225000 } ? do { return 25000 } : (do { $v < 300000 } ? do { return 37500 } : (do { $v < 600000 } ? do { return 60000 } : (do { $v < 1200000 } ? do { return 120000 } : (do { $v < 3600000 } ? do { return 300000 } : (do { $v < 5400000 } ? do { return 600000 } : (do { $v < 10800000 } ? do { return 900000 } : (do { $v < 21600000 } ? do { return 1800000 } : (do { $v < 43200000 } ? do { return 3600000 } : (do { $v < 64800000 } ? do { return 7200000 } : (do { $v < 129600000 } ? do { return 10800000 } : (do { $v < 216000000 } ? do { return 21600000 } : (do { $v < 432000000 } ? do { return 43200000 } : (do { $v < 864000000 } ? do { return 86400000 } : (do { $v < 1728000000 } ? do { return 172800000 } : (do { $v < 3024000000 } ? do { return 345600000 } : (do { $v < 6048000000 } ? do { return 604800000 } : (do { $v < 12096000000 } ? do { return 1209600000 } : (do { $v < 31557600000 } ? do { return 2629800000 } : (do { $v < 63115200000 } ? do { return 5259600000 } : (do { $v < 78894000000 } ? do { return 7889400000 } : (do { $v < 157788000000 } ? do { return 15778800000 } : do { return 31557600000 })))))))))))))))))))))))); } sub lookup3 { my $v = shift; if ( $v >= 64800000 ) { if ( $v < 129600000 ) { return 10800000; } elsif( $v < 216000000 ) { return 21600000; } elsif( $v < 432000000 ) { return 43200000; } elsif( $v < 864000000 ) { return 86400000; } elsif( $v < 1728000000 ) { return 172800000; } elsif( $v < 3024000000 ) { return 345600000; } elsif( $v < 6048000000 ) { return 604800000; } elsif( $v < 12096000000 ) { return 1209600000; } elsif( $v < 31557600000 ) { return 2629800000; } elsif( $v < 63115200000 ) { return 5259600000; } elsif( $v < 78894000000 ) { return 7889400000; } elsif( $v < 157788000000 ) { return 15778800000; } else { return 31557600000; } } else { if ( $v < 25000 ) { return 2500; } elsif( $v < 50000 ) { return 5000; } elsif( $v < 150000 ) { return 12500; } elsif( $v < 225000 ) { return 25000; } elsif( $v < 300000 ) { return 37500; } elsif( $v < 600000 ) { return 60000; } elsif( $v < 1200000 ) { return 120000; } elsif( $v < 3600000 ) { return 300000; } elsif( $v < 5400000 ) { return 600000; } elsif( $v < 10800000 ) { return 900000; } elsif( $v < 21600000 ) { return 1800000; } elsif( $v < 43200000 ) { return 3600000; } elsif( $v < 64800000 ) { return 7200000; } } } sub lookup4 { my $v = shift; if ( $v < 600000 ) { if ( $v < 25000 ) { return 2500; } elsif( $v < 50000 ) { return 5000; } elsif( $v < 150000 ) { return 12500; } elsif( $v < 225000 ) { return 25000; } elsif( $v < 300000 ) { return 37500; } else { return 60000; } } elsif( $v < 64800000 ) { if ( $v < 1200000 ) { return 120000; } elsif( $v < 3600000 ) { return 300000; } elsif( $v < 5400000 ) { return 600000; } elsif( $v < 10800000 ) { return 900000; } elsif( $v < 21600000 ) { return 1800000; } elsif( $v < 43200000 ) { return 3600000; } else { return 7200000; } } elsif( $v < 3024000000 ) { if ( $v < 129600000 ) { return 10800000; } elsif( $v < 216000000 ) { return 21600000; } elsif( $v < 432000000 ) { return 43200000; } elsif( $v < 864000000 ) { return 86400000; } elsif( $v < 1728000000 ) { return 172800000; } else { return 345600000; } } else { if ( $v < 6048000000 ) { return 604800000; } elsif( $v < 12096000000 ) { return 1209600000; } elsif( $v < 31557600000 ) { return 2629800000; } elsif( $v < 63115200000 ) { return 5259600000; } elsif( $v < 78894000000 ) { return 7889400000; } elsif( $v < 157788000000 ) { return 15778800000; } else { return 31557600000; } } } sub lookup5 { my $v = shift; if( $v < 600000 ) { if( $v < 150000 ) { if ( $v < 25000 ) { return 2500; } elsif( $v < 50000 ) { return 5000; } else { return 12500; } } else { if ( $v < 225000 ) { return 25000; } elsif( $v < 300000 ) { return 37500; } else { return 60000; } } } elsif( $v < 64800000 ) { if( $v < 5400000 ) { if ( $v < 1200000 ) { return 120000; } elsif( $v < 3600000 ) { return 300000; } else { return 600000; } } else { if( $v < 10800000 ) { return 900000; } elsif( $v < 21600000 ) { return 1800000; } elsif( $v < 43200000 ) { return 3600000; } else { return 7200000; } } } elsif( $v < 3024000000 ) { if( $v < 432000000 ) { if ( $v < 129600000 ) { return 10800000; } elsif( $v < 216000000 ) { return 21600000; } else { return 43200000; } } else { if ( $v < 864000000 ) { return 86400000; } elsif( $v < 1728000000 ) { return 172800000; } else { return 345600000; } } } else { if( $v < 63115200000 ) { if ( $v < 6048000000 ) { return 604800000; } elsif( $v < 12096000000 ) { return 1209600000; } elsif( $v < 31557600000 ) { return 2629800000; } else { return 5259600000; } } else { if ( $v < 78894000000 ) { return 7889400000; } elsif( $v < 157788000000 ) { return 15778800000; } else { return 31557600000; } } } } our $I //= -1; our $N //= 1e3; our @inputs = map int( rand() * 160e9 ), 1 .. $N; cmpthese $I, { if => q[ my $r = lookup1( $_ ) for @inputs; ], andreturn => q[ my $r = lookup1a( $_ ) for @inputs; ], ifelse => q[ my $r = lookup2( $_ ) for @inputs; ], nestedTernary => q[ my $r = lookup2a( $_ ) for @inputs; ], ififelse => q[ my $r = lookup3( $_ ) for @inputs; ], ifelseifelse => q[ my $r = lookup4( $_ ) for @inputs; ], ifelseifelseifelse => q[ my $r = lookup5( $_ ) for @inputs; ], } __END__ E:\Chart>DateInterval.pl -N=1e3 Rate andreturn if nestedTernary ifelse ififelse i +felseifelseifelse ifelseifelse andreturn 406/s -- -1% -12% -15% -37% + -46% -46% if 412/s 1% -- -11% -14% -36% + -45% -46% nestedTernary 464/s 14% 13% -- -3% -28% + -38% -39% ifelse 477/s 18% 16% 3% -- -26% + -36% -37% ififelse 645/s 59% 57% 39% 35% -- + -14% -15% ifelseifelseifelse 746/s 84% 81% 61% 56% 16% + -- -2% ifelseifelse 758/s 87% 84% 63% 59% 17% + 2% -- E:\Chart>DateInterval.pl -N=1e3 Rate if ifelse ififelse ifelseifelseifelse if +elseifelse if 410/s -- -13% -36% -43% + -44% ifelse 471/s 15% -- -27% -34% + -36% ififelse 643/s 57% 37% -- -10% + -12% ifelseifelseifelse 714/s 74% 52% 11% -- + -3% ifelseifelse 735/s 79% 56% 14% 3% + -- E:\Chart>DateInterval.pl -N=1e4 Rate if ifelse ififelse ifelseifelseifelse if +elseifelse if 41.4/s -- -12% -34% -42% + -43% ifelse 47.1/s 14% -- -25% -34% + -35% ififelse 63.0/s 52% 34% -- -12% + -13% ifelseifelseifelse 71.4/s 73% 52% 13% -- + -2% ifelseifelse 72.7/s 76% 54% 15% 2% + -- E:\Chart>DateInterval.pl -N=1e5 Rate if ifelse ififelse ifelseifelse ifelseif +elseifelse if 4.16/s -- -10% -36% -42% + -43% ifelse 4.64/s 12% -- -29% -36% + -37% ififelse 6.49/s 56% 40% -- -10% + -11% ifelseifelse 7.21/s 73% 55% 11% -- + -2% ifelseifelseifelse 7.32/s 76% 58% 13% 2% + -- E:\Chart>DateInterval.pl -N=1e6 -I=-7 s/iter if ifelse ififelse ifelseifelseifelse if +elseifelse if 2.44 -- -15% -35% -42% + -43% ifelse 2.09 17% -- -24% -32% + -34% ififelse 1.59 54% 31% -- -11% + -13% ifelseifelseifelse 1.42 73% 47% 12% -- + -3% ifelseifelse 1.38 77% 51% 15% 3% + --

Many thanks for a) responding; b) teaching me something(if/elsif); c) stimulating my brain in a different direction (hardcoding a binary search).


With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this
In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked