Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Re^2: High Performance Game of Life

by eyepopslikeamosquito (Chancellor)
on Aug 12, 2017 at 09:32 UTC ( #1197299=note: print w/replies, xml ) Need Help??


in reply to Re: High Performance Game of Life
in thread High Performance Game of Life

Very instructive.

In C++, it was faster not to attempt anything like that with temporary variables (I tried), but instead to just leave the duplicated values and let the optimizer do it for you. Plus, of course, function call overhead can be eliminated via inline functions and macros.

In Perl, on the other hand, the compiler must run very fast, and doesn't attempt many of the optimizations of a C++ compiler run at high optimization levels.

Replies are listed 'Best First'.
Re^3: High Performance Game of Life
by marioroy (Priest) on Aug 12, 2017 at 10:25 UTC

    Hi eyepopslikeamosquito,

    On my laptop, the following shaves 4 seconds from one-time stringification per key.

    # Return the list of dead cells surrounding a cell sub get_dead_cells { my ( $cells, $x0, $y0 ) = ( shift->{Cells}, @_ ); my ( $x1, $x2, $y1, $y2 ) = ( $x0 - 1, $x0 + 1, $y0 - 1, $y0 + 1 ); my ( $k1, $k2, $k3, $k4, $k5, $k6, $k7, $k8 ); ( ( $k1 = "$x1:$y1" ) x !( 0 + exists $cells->{ $k1 } ), ( $k2 = "$x1:$y0" ) x !( 0 + exists $cells->{ $k2 } ), ( $k3 = "$x1:$y2" ) x !( 0 + exists $cells->{ $k3 } ), ( $k4 = "$x0:$y1" ) x !( 0 + exists $cells->{ $k4 } ), ( $k5 = "$x0:$y2" ) x !( 0 + exists $cells->{ $k5 } ), ( $k6 = "$x2:$y1" ) x !( 0 + exists $cells->{ $k6 } ), ( $k7 = "$x2:$y0" ) x !( 0 + exists $cells->{ $k7 } ), ( $k8 = "$x2:$y2" ) x !( 0 + exists $cells->{ $k8 } ) ); }

    To not allocate the key variables each time, another 2 seconds reduction is possible with the state feature.

    use feature 'state'; # Return the list of dead cells surrounding a cell sub get_dead_cells { my ( $cells, $x0, $y0 ) = ( shift->{Cells}, @_ ); my ( $x1, $x2, $y1, $y2 ) = ( $x0 - 1, $x0 + 1, $y0 - 1, $y0 + 1 ); state ( $k1, $k2, $k3, $k4, $k5, $k6, $k7, $k8 ); ( ( $k1 = "$x1:$y1" ) x !( 0 + exists $cells->{ $k1 } ), ( $k2 = "$x1:$y0" ) x !( 0 + exists $cells->{ $k2 } ), ( $k3 = "$x1:$y2" ) x !( 0 + exists $cells->{ $k3 } ), ( $k4 = "$x0:$y1" ) x !( 0 + exists $cells->{ $k4 } ), ( $k5 = "$x0:$y2" ) x !( 0 + exists $cells->{ $k5 } ), ( $k6 = "$x2:$y1" ) x !( 0 + exists $cells->{ $k6 } ), ( $k7 = "$x2:$y0" ) x !( 0 + exists $cells->{ $k7 } ), ( $k8 = "$x2:$y2" ) x !( 0 + exists $cells->{ $k8 } ) ); }

    Regards, Mario

      Hi eyepopslikeamosquito,

      Here is Organism.pm modified to use pack/unpack, plus slight optimization applied to insert_cells.

      package Organism; use strict; use warnings; use feature 'state'; sub count { return scalar keys %{ shift->{Cells} }; } # Input a list of [ x, y ] coords sub insert_cells { my $cells = shift->{Cells}; for my $r (@_) { $cells->{ pack 'ii', @{$r} } = undef } } # Return sorted list of cells in the Organism. # Used for verification and testing the state of the organism. sub get_live_cells { sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] } map { [ unpack 'ii', $_ ] } keys %{ shift->{Cells} }; } # Return the list of dead cells surrounding a cell sub get_dead_cells { my ( $cells, $x0, $y0 ) = ( shift->{Cells}, @_ ); my ( $x1, $x2, $y1, $y2 ) = ( $x0 - 1, $x0 + 1, $y0 - 1, $y0 + 1 ); state ( $k1, $k2, $k3, $k4, $k5, $k6, $k7, $k8 ); ( ( $k1 = pack 'ii', $x1, $y1 ) x !( 0 + exists $cells->{ $k1 } ), ( $k2 = pack 'ii', $x1, $y0 ) x !( 0 + exists $cells->{ $k2 } ), ( $k3 = pack 'ii', $x1, $y2 ) x !( 0 + exists $cells->{ $k3 } ), ( $k4 = pack 'ii', $x0, $y1 ) x !( 0 + exists $cells->{ $k4 } ), ( $k5 = pack 'ii', $x0, $y2 ) x !( 0 + exists $cells->{ $k5 } ), ( $k6 = pack 'ii', $x2, $y1 ) x !( 0 + exists $cells->{ $k6 } ), ( $k7 = pack 'ii', $x2, $y0 ) x !( 0 + exists $cells->{ $k7 } ), ( $k8 = pack 'ii', $x2, $y2 ) x !( 0 + exists $cells->{ $k8 } ) ) +; } sub get_num_live { my ( $cells, $x0, $y0 ) = ( shift->{Cells}, @_ ); my ( $x1, $x2, $y1, $y2 ) = ( $x0 - 1, $x0 + 1, $y0 - 1, $y0 + 1 ); ( 0 + exists $cells->{ pack 'ii', $x1, $y1 } ) + ( 0 + exists $cells->{ pack 'ii', $x1, $y0 } ) + ( 0 + exists $cells->{ pack 'ii', $x1, $y2 } ) + ( 0 + exists $cells->{ pack 'ii', $x0, $y1 } ) + ( 0 + exists $cells->{ pack 'ii', $x0, $y2 } ) + ( 0 + exists $cells->{ pack 'ii', $x2, $y1 } ) + ( 0 + exists $cells->{ pack 'ii', $x2, $y0 } ) + ( 0 + exists $cells->{ pack 'ii', $x2, $y2 } ); } sub tick { my $self = shift; my %new_cells; for my $c (keys %{ $self->{Cells} }) { # Get the (up to 8) dead cells surrounding the cell my @zcells = $self->get_dead_cells( unpack 'ii', $c ); # Check the live cell # Note: next line equivalent to nlive == 2 || nlive == 3 @zcells == 5 || @zcells == 6 and $new_cells{$c} = undef; # Check the dead cells for my $z (@zcells) { $self->get_num_live( unpack 'ii', $z ) == 3 and $new_cells{$z +} = undef; } } $self->{Cells} = \%new_cells; } sub new { my $class = shift; my %init_self = ( Cells => {} ); bless \%init_self, $class; } 1;

      Regards, Mario

        Update: pack 'i2' is more efficient than pack 'ii'

        Organism.pm optimized with pack/unpack 'i2' and inlining critical paths.

        package Organism; use strict; use warnings; use feature 'state'; sub count { return scalar keys %{ shift->{Cells} }; } # Input a list of [ x, y ] coords sub insert_cells { my $cells = shift->{Cells}; for my $r (@_) { $cells->{ pack 'i2', @{$r} } = undef } } # Return sorted list of cells in the Organism. # Used for verification and testing the state of the organism. sub get_live_cells { sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] } map { [ unpack 'i2', $_ ] } keys %{ shift->{Cells} }; } # Return the list of dead cells surrounding a cell sub get_dead_cells { my ( $cells, $x0, $y0 ) = ( shift->{Cells}, @_ ); my ( $x1, $x2, $y1, $y2 ) = ( $x0 - 1, $x0 + 1, $y0 - 1, $y0 + 1 ); state ( $k1, $k2, $k3, $k4, $k5, $k6, $k7, $k8 ); ( ( $k1 = pack 'i2', $x1, $y1 ) x !( 0 + exists $cells->{ $k1 } ), ( $k2 = pack 'i2', $x1, $y0 ) x !( 0 + exists $cells->{ $k2 } ), ( $k3 = pack 'i2', $x1, $y2 ) x !( 0 + exists $cells->{ $k3 } ), ( $k4 = pack 'i2', $x0, $y1 ) x !( 0 + exists $cells->{ $k4 } ), ( $k5 = pack 'i2', $x0, $y2 ) x !( 0 + exists $cells->{ $k5 } ), ( $k6 = pack 'i2', $x2, $y1 ) x !( 0 + exists $cells->{ $k6 } ), ( $k7 = pack 'i2', $x2, $y0 ) x !( 0 + exists $cells->{ $k7 } ), ( $k8 = pack 'i2', $x2, $y2 ) x !( 0 + exists $cells->{ $k8 } ) ) +; } sub tick { my $self = shift; my $cells = $self->{Cells}; my %new_cells; for my $c (keys %{ $cells }) { # Get the (up to 8) dead cells surrounding the cell my @zcells = $self->get_dead_cells( unpack 'i2', $c ); # Check the live cell # Note: next line equivalent to nlive == 2 || nlive == 3 @zcells == 5 || @zcells == 6 and $new_cells{$c} = undef; # Check the dead cells for my $z (@zcells) { state ( $x0, $x1, $x2, $y0, $y1, $y2 ); ( $x0, $y0 ) = unpack 'i2', $z; ( $x1, $x2, $y1, $y2 ) = ( $x0 - 1, $x0 + 1, $y0 - 1, $y0 + 1 + ); # Get num live ( ( 0 + exists $cells->{ pack 'i2', $x1, $y1 } ) + ( 0 + exists $cells->{ pack 'i2', $x1, $y0 } ) + ( 0 + exists $cells->{ pack 'i2', $x1, $y2 } ) + ( 0 + exists $cells->{ pack 'i2', $x0, $y1 } ) + ( 0 + exists $cells->{ pack 'i2', $x0, $y2 } ) + ( 0 + exists $cells->{ pack 'i2', $x2, $y1 } ) + ( 0 + exists $cells->{ pack 'i2', $x2, $y0 } ) + ( 0 + exists $cells->{ pack 'i2', $x2, $y2 } ) ) == 3 and $new_cells{$z} = undef; } } $self->{Cells} = \%new_cells; } sub new { my $class = shift; my %init_self = ( Cells => {} ); bless \%init_self, $class; } 1;

        Regards, Mario

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1197299]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (5)
As of 2017-12-18 05:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    What programming language do you hate the most?




















    Results (467 votes). Check out past polls.

    Notices?