How to optimize code using binary, variable lookup and foreach?

Viewed 183

How can I optimize this Perl script?

It takes "days of the week" such as "Mon and "Tue" or "Wed, Thu and Sun" and simply returns an integer to represent them.

use strict;
use feature qw(signatures);
use warnings;
no warnings qw(experimental::signatures);
my $DAYS_OF_WEEK_LOOKUP = ( { mon  =>  1, tue  =>  2, wed  =>  4, thu  =>  8, fri  => 16, sat  => 32, sun  => 64 });

my $days_of_week_integer= days_of_week_to_int (['zzz', 'Sun', 'Mon', 'Tue', 'Wed', 'Thu', 'fri', 'SAT']);
print "$days_of_week_integer\n";


sub days_of_week_to_int ($days) {
  my $day_of_week = 0;
  foreach my $key (@$days)  {
    $day_of_week += $DAYS_OF_WEEK_LOOKUP->{lc($key)} if $DAYS_OF_WEEK_LOOKUP->{lc($key)};
  }
  return $day_of_week if $day_of_week < 128;
  return;
}

I am always looking to understand how to optimize my code better and gain experience from seasoned developers. The script works perfectly well and well it's in Perl so it already runs very fast.

However, I can't help feeling there is a more optimum "Perl way" of achieving the same result and I wondered if anyone felt the same and could show me the way. Small tips are important tips!

Thank you to everybody and I add the final code here with the benchmarks. This is my original code with the extra overhead stripped but faithful to the original with the polar bear code.

use strict;
use Benchmark ':all';

my $polar_bitmap = 0x01;
my @polar_days_of_week = qw/Mon Tue Wed Thu Fri Sat Sun/;         # USA/Canada week days order
my $orig_DAYS_OF_WEEK_LOOKUP = ( { Mon  =>  1, Tue  =>  2, Wed  =>  4, Thu  =>  8, Fri  => 16, Sat  => 32, Sun  => 64 });
my %polar_DAYS_OF_WEEK_LOOKUP = map { $_ => ( $polar_bitmap <<= 1 ) / 2 } @polar_days_of_week;

my @days;
@days  = qw/Mon Wed Tue Sat Sun Thu/;

print "orig  : " . (orig_days_of_week_to_int(@days)) . "\n";
print "polar : " . (polar_days_to_mask    ( \@days)) . "\n";

@days = qw/Mon Sat Sun Thu/;

print "polar : " . (polar_days_to_mask(\@days)) . "\n";
print "orig  : " . (orig_days_of_week_to_int(@days)) . "\n";

@days = qw/Mon Wed Tue Sat Sun Thu/;

cmpthese(-3, {
    orginal  => sub { orig_days_of_week_to_int(@days) },
    polar_b  => sub { polar_days_to_mask(\@days)      },
});

exit 0;

sub polar_days_to_mask {
    my $days = shift;
    my $mask;

    $mask ^= $polar_DAYS_OF_WEEK_LOOKUP{$_} for @$days;

    return $mask;
}

sub orig_days_of_week_to_int  {
  my @days = @_;
  my $day_of_week = 0;
  foreach my $key (@days)  {
    $day_of_week += $orig_DAYS_OF_WEEK_LOOKUP->{$key};
  }
  return $day_of_week;
}

And the output:

orig  : 111
polar : 111
polar : 105
orig  : 105
             Rate orginal polar_b
orginal 1411082/s      --    -41%
polar_b 2398719/s     70%      --

I've added the code above just in case I messed anything up as you always should be careful with BenchMarks! :-)

And to show that above point... I thought I would test it with a LINODE node that I have...

            Rate orginal polar_b
orginal 741061/s      --    -25%
polar_b 992490/s     34%      --

Actually, compared to my HP bare-metal at home... the LINODE gives me say 34% consistently and my home machine 70%. (same o/s, same versions)

So there you are...be wary of Benchmarks!

Never the less, part man, part bear, part AI, the Polar solution was coool.

3 Answers

I haven't done any benchmarking, but I think this is cleaner (Notes in comments):

#!/usr/bin/env perl
use strict;
use warnings;
use experimental qw/signatures/; # Instead of use feature and no warnings
use feature qw/say/;
use List::Util qw/sum0/;

# Plain hash instead of hashref
my %DAYS_OF_WEEK_LOOKUP = ( mon => 1, tue => 2, wed => 4, thu => 8,
                            fri => 16, sat => 32, sun => 64 );

# Function takes a list of values instead of a single arrayref
my $days_of_week_integer = days_of_week_to_int('zzz', 'Sun', 'Mon',
                                               'Tue', 'Wed', 'Thu', 'fri', 'SAT');

# say instead of "print "$foo\n"
say $days_of_week_integer;

sub days_of_week_to_int (@days) {
    no warnings qw/uninitialized/; # Turn off warning about undef values
    # Sum up the results of a hash slice instead of using an explicit loop
    my $day_of_week = sum0 @DAYS_OF_WEEK_LOOKUP{map { lc } @days};
    return $day_of_week < 128 ? $day_of_week : undef;
}

There can be a small measure of speedup with tweaks: use a map instead of manual iteration and add numbers using a library, use a test that short-circuits and so is done rarely in this case instead of an if test every time. More importantly, that may be a bit more readable.

use warnings;
use strict;
use feature 'say';

use List::Util qw(sum0);
use Benchmark qw(cmpthese);

my $runfor = shift // 3;

my $DAYS_OF_WEEK = { mon => 1, tue => 2, wed => 4, thu => 8, fri => 16, 
    sat => 32, sun => 64 };    

sub add_days_hr {
    my $days = shift;
    my $ndow = sum0 map { $DAYS_OF_WEEK->{lc($_)} // () } @$days;
    return $ndow < 128 ? $ndow : undef;
}

sub dow_to_int {  # original code (from question)
    my $days = shift;
    my $day_of_week = 0;
    foreach my $key (@$days)  {
        $day_of_week += $DAYS_OF_WEEK->{lc($key)} if $DAYS_OF_WEEK->{lc($key)};
    }   
    return $day_of_week if $day_of_week < 128;
    return;
}
    
my @test_days = qw(zzz Sun Mon Tue Wed Thu fri SAT);

cmpthese( -$runfor, { 
    add_days_hr => sub { add_days_hr( \@test_days ) },
    dow_to_int  => sub { dow_to_int ( \@test_days ) },
});

Prints, on an old laptop with 5.16

                Rate  dow_to_int add_days_hr
dow_to_int  526696/s          --        -12%
add_days_hr 599792/s         14%          --

This can be made a little faster yet by using a a hash instead of hashref to avoid dereferencing and by using flat input list (array instead of arrayref) which needn't be dereferenced, but that's already eating into the intended interface for small gains.

If this is done repeatedly it can be sped up more by inlining it, since sub calls are spendy in Perl.


On a server, with two more cases

                 Rate   add_other  dow_to_int add_days_hr    add_days
add_slice    900635/s          --         -5%        -17%        -21%
dow_to_int   952705/s          6%          --        -12%        -16%
add_days_hr 1079487/s         20%         13%          --         -5%
add_days    1133645/s         26%         19%          5%          --

Legend: add_slice is a solution using slice (from Shawn's), dow_to_int the original code (as above), add_days_hr the solution above, and add_days the same one but using a hash for the lookup (not hashref)

# These two need %DAYS_OF_WEEK hash
my %DAYS_OF_WEEK = ( mon => 1, tue => 2, wed => 4, thu => 8, fri => 16,
    sat => 32, sun => 64 );

sub add_slice {  # from Shawn's answer
    my $days = shift;
    no warnings qw/uninitialized/;
    my $day_of_week = sum0 @DAYS_OF_WEEK{map { lc } @$days};
    return $day_of_week < 128 ? $day_of_week : undef;
}

sub add_days {   # With hash lookup instead of hashref, otherwise same
    my $days = shift;
    my $ndow = sum map { $DAYS_OF_WEEK{lc($_)} // () } @$days;
    return $ndow < 128 ? $ndow : undef;
}

It looks like OP attempts to generate bitmask for week days based on provided sample code.

Please investigate following code snippet which is provided for demonstration purpose only. Feel free to strip unneeded parts with demo output.

Note: the code utilizes USA/Canada day order, for Europe move Sun to the end of the list

use strict;
use warnings;
use feature qw(say);

my $bitmap = 0x01;
my @days_of_week = qw/Sun Mon Tue Wed Thu Fri Sat/;         # USA/Canada week days order
my %DAYS_OF_WEEK_LOOKUP = map { $_ => ( $bitmap <<= 1 ) / 2 } @days_of_week;

my @days = qw/Mon Wed Thu Sat/;

say '
 Result
---------------';
printf "Days: %s\n", join(',',@days);
printf "Mask: 0b%08b\n", days_to_mask(\@days);

exit 0;

sub days_to_mask {
    my $days = shift;
    my $mask;
    
    $mask ^= $DAYS_OF_WEEK_LOOKUP{$_} for @$days;
    
    return $mask;
}

Output

 Result
---------------
Days: Mon,Wed,Thu,Sat
Mask: 0b01011010

Reference: ISO 8601, ref ISO 8601, Wiki ISO 8601

Related