in reply to A better way of lookup?

Hello BrowserUk,

As usual, I'm late to the table, but I've found in my *nix environments that using 'elsif' does improve the performance and adding some minimal binary splitting also improved the performance of your subroutine. I benchmarked both your original and my re-work and results are at the bottom. Obviously if the inputs are better known you could improve the break points. Hope this spurs your imagination a little. 

use strict;
use warnings;
use Benchmark qw(:all);

my @input = ( 25000, 50000, 150000, 225000, 300000, 600000, 1200000, 3
+600000,
              5400000, 10800000, 21600000, 43200000, 64800000, 1296000
+00,
              216000000, 432000000, 864000000, 1728000000, 3024000000,
              6048000000, 12096000000, 31557600000, 63115200000, 78894
+000000,
              157788000000, 315576000000,
             );

my @newinput = ();

for ( 0 .. $#input )
{    $newinput[$_] = $input[$_] - 11;     #     print $newinput[$_],"\
+n";    #    Testing
}

#    print $#newinput,"\n";        # size of input array

## Make sure both subroutines return same results!
for my $no ( 0 .. $#newinput )
{   my $r1 = &lookup_org ( $newinput[ $no ] );
    my $r2 = &lookup_new ( $newinput[ $no ] );
    if ( $r1 != $r2 ) { print "$no|$r1|$r2|\n"; exit(1); }
    #    print "$no|$r1|$r2|\n";     # Testing
}

timethese ( -2 ,
        {
           case1 => sub { &lookup1 },
           case2 => sub { &lookup2 },
        },
    );


sub lookup1
{    for ( 0 .. $#newinput )
    {    lookup_org ( $newinput[ $_ ] ); }
}

sub lookup2
{    for ( 0 .. $#newinput )
    {    lookup_new ( $newinput[ $_ ] ); }
}


sub lookup_org {
    my $v = shift;
    if( $v <        25000 ) { return        2500; }
    if( $v <        50000 ) { return        5000; }
    if( $v <       150000 ) { return       12500; }
    if( $v <       225000 ) { return       25000; }
    if( $v <       300000 ) { return       37500; }
    if( $v <       600000 ) { return       60000; }
    if( $v <      1200000 ) { return      120000; }
    if( $v <      3600000 ) { return      300000; }
    if( $v <      5400000 ) { return      600000; }
    if( $v <     10800000 ) { return      900000; }
    if( $v <     21600000 ) { return     1800000; }
    if( $v <     43200000 ) { return     3600000; }
    if( $v <     64800000 ) { return     7200000; }
    if( $v <    129600000 ) { return    10800000; }
    if( $v <    216000000 ) { return    21600000; }
    if( $v <    432000000 ) { return    43200000; }
    if( $v <    864000000 ) { return    86400000; }
    if( $v <   1728000000 ) { return   172800000; }
    if( $v <   3024000000 ) { return   345600000; }
    if( $v <   6048000000 ) { return   604800000; }
    if( $v <  12096000000 ) { return  1209600000; }
    if( $v <  31557600000 ) { return  2629800000; }
    if( $v <  63115200000 ) { return  5259600000; }
    if( $v <  78894000000 ) { return  7889400000; }
    if( $v < 157788000000 ) { return 15778800000; }
    else { return 31557600000; }
}

sub lookup_new {
   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; }
    }
}

__END__

Results: 1st is worst time, 2nd is best time

Benchmark: running case1, case2 for at least 2 CPU seconds...
   case1:  2 wallclock secs ( 2.24 usr +  0.00 sys =  2.24 CPU) @ 4799
+9.55/s (n=107519)
   case2:  3 wallclock secs ( 2.06 usr +  0.00 sys =  2.06 CPU) @ 6088
+8.83/s (n=125431)

Benchmark: running case1, case2 for at least 2 CPU seconds...
    case1:  3 wallclock secs ( 2.32 usr +  0.00 sys =  2.32 CPU) @ 486
+57.33/s (n=112885)
    case2:  2 wallclock secs ( 2.24 usr +  0.00 sys =  2.24 CPU) @ 610
+86.61/s (n=136834)

[download]

Best Regards...Ed

"Well done is better than well said." - Benjamin Franklin

Replies are listed 'Best First'.
Re^2: A better way of lookup?
by RichardK (Parson) on Apr 26, 2015 at 17:03 UTC

    There's another possible micro optimization. You could change the last line of the second group to just return 7200000 as you already know v is less then 64800000. There's no point testing it again.

    # replace
    elsif( $v <     64800000 ) { return     7200000; }
#with
    else { return 7200000; }

    [download]

    BTW that's an interesting result that elsif is quicker, did you test them in isolation? What improvement did the partial binary chop make compared with the elsif?

[reply]
[d/l]

      RichardK,

      Actually, both outer 'if / else' conditional statements could be reduced to just 'return ...' since each previous test did a 'return...' if the test was 'true'.

        BTW that's an interesting result that elsif is quicker, did you test them in isolation?
      Interestingly, use of the 'elsif' gave the most performance improvement! Someone on PerlMonks many years ago showed how it was better, all I did was remember and continue to use it in my scripts.

        What improvement did the partial binary chop make compared with the elsif?

      Not as much of an improvement as the 'elsif', but since BrowserUk may have more information about the frequency of the inputs, I left it in with the hope that it would help. Another consideration is that BrowserUk uses 64bit Windows and I use mostly 32bit *nix. That's why the benchmarking is critical, since the results may be different in his environment. Please note, that I had to add brackets around the 'return' in order to compile his original script in my environment. YMMV!

      Regards...Ed

      "Well done is better than well said." - Benjamin Franklin

[reply]
Re^2: A better way of lookup?
by BrowserUk (Patriarch) on Apr 27, 2015 at 10:57 UTC

    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:

    <Reveal this spoiler or all in this thread>

    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
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom