Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re^12: High Performance Game of Life (updated)

by tybalt89 (Vicar)
on Aug 15, 2017 at 00:13 UTC ( #1197385=note: print w/replies, xml ) Need Help??


in reply to Re^11: High Performance Game of Life (updated)
in thread High Performance Game of Life

I don't have access to a 64-bit perl. However, this is a 32-bit version of combining two 16 bit integers into a 32 bit number. While this runs as long as the coordinates are within range, I can't test it in the 64-bit version.

I like it because all offsets are found with a simple addition inside tick.
All the encode/decode mess is in the input and output routines.

In theory (completely untested), all that's needed is to change the line

my $half = 16; # make 32 for 64-bit perls

to

my $half = 32; # make 32 for 64-bit perls

to make it use the full range of two 32 bit numbers.

So here's the code

package Organism; use strict; use warnings; sub count { return scalar keys %{ shift->{Cells} }; } # Input a list of [ x, y ] coords sub insert_cells { my $self = shift; my $cells = $self->{Cells}; for my $r (@_) { $cells->{ (($r->[0] + $self->{fudge}) << $self->{half}) | ($r->[1] + $self->{fudge}) } = undef } } # Return sorted list of cells in the Organism. # Used for verification and testing the state of the organism. sub get_live_cells { my $self = shift; sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] } map { [ ($_ >> $self->{half}) - $self->{fudge}, ($_ & (1 << $self->{half}) - 1) - $self->{fudge} ] } keys %{ $self->{Cells} }; } sub tick { my $self = shift; my $cells = $self->{Cells}; my @deltas = @{ $self->{deltas} }; my ( %new_cells, %dead_cells ); for my $c (keys %{ $cells }) { # Get the (up to 8) dead cells surrounding the cell $dead_cells{$_}++ for my @zcells = grep !exists $cells->{$_}, map $c + $_, @deltas; # Check the live cell # Note: next line equivalent to nlive == 2 || nlive == 3 @zcells == 5 || @zcells == 6 and $new_cells{$c} = undef; } $dead_cells{$_} == 3 and $new_cells{$_} = undef for keys %dead_cell +s; $self->{Cells} = \%new_cells; } sub new { my $class = shift; my $half = 16; # make 32 for 64-bit perls my $base = 1 << $half; my $fudge = $base >> 1; my @deltas = ($base-1, $base, $base+1, -1, 1, -$base-1, -$base, -$base+1); my %init_self = ( Cells => {}, fudge => $fudge, half => $half, deltas => \@deltas ); bless \%init_self, $class; } 1;

Preliminary testing with 16 bit numbers seemed to show it's about 10% slower than the pack version :(

Replies are listed 'Best First'.
Re^13: High Performance Game of Life (updated)
by marioroy (Priest) on Aug 15, 2017 at 01:38 UTC

    Hi tybalt89. The following was captured from a 64-bit laptop with $half = 32. Unfortunately, cperl is failing for some reason. I also tried $half = 16, same thing. The cell count at end isn't correct. To be sure, I pulled down the latest maint release and tried again.

    $ perl createblinker.pl 500000 -900000 100 >x.tmp 2>y.tmp

    bin/perl

    $ /opt/perl-5.24.2/bin/perl -I. tbench1.pl x.tmp 2 cell count at start = 1500000 run benchmark for 2 ticks cell count at end = 1500000 time taken: 42 secs $ /opt/perl-5.26.0/bin/perl -I. tbench1.pl x.tmp 2 cell count at start = 1500000 run benchmark for 2 ticks cell count at end = 1500000 time taken: 42 secs

    bin/cperl

    $ /opt/cperl-5.24.3c/bin/cperl -I. tbench1.pl x.tmp 2 cell count at start = 1500000 run benchmark for 2 ticks cell count at end = 675003 <-- incorrect time taken: 34 secs $ /opt/cperl-5.26.1c/bin/cperl -I. tbench1.pl x.tmp 2 cell count at start = 1500000 run benchmark for 2 ticks cell count at end = 675003 <-- incorrect time taken: 34 secs

    Regarding cperl, I built it using the following configure options. The source for cperl-maint-5.24c and cperl-maint-5.26c can be found on Github.

    ./Configure -Dprefix=/opt/cperl-5.24.3c -sder -Dusethreads -Dusecperl +-Accflags=-msse4.2 ./Configure -Dprefix=/opt/cperl-5.26.1c -sder -Dusethreads -Dusecperl +-Accflags=-msse4.2

    Regards, Mario

      When testing with the 32 bit version, the range of coordinates should be restricted to what a 16 bit number can hold, from roughly -32000 to 32000 (to be safe :)

      The 32 bit version does pass the tests, and runs OK on my system with a much smaller createblinker.pl range.

      That -900000 is way out of range.

      As for problems with the 64 bit version, sorry I can't help :(

        Update: Found the reason why cperl is failing with 64-bit, described below.

        Hi tybalt89,

        Perl is passing with 32 and 64 bits. Regarding cperl, it is passing 32 bits ($half = 16), but not 64 bits ($half = 32).

        $ perl createblinker.pl 5000 -9000 100 >x.tmp 2>y.tmp

        bin/perl

        $ /opt/perl-5.24.2/bin/perl -I. tbench1.pl x.tmp 2 cell count at start = 15000 run benchmark for 2 ticks cell count at end = 15000 time taken: 0 secs

        bin/cperl

        $ /opt/cperl-5.24.3c/bin/cperl -I. tbench1.pl x.tmp 2 cell count at start = 15000 run benchmark for 2 ticks cell count at end = 6753 <-- fails on 64-bit hw ($half = 32) time taken: 0 secs

        The reason cperl is failing on 64-bit hw ($half = 32) is due to numbers converting to exponential notation.

        # perl createblinker.pl 5 -9 100 >x.tmp 2>y.tmp # print "@zcells\n"; 9223372039002259557 -9.22337203900226e+18 -9.22337203900226e+18, ...

        Running $half = 30 resolves the issue. If you want, $half may be set programmatically.

        # use 30-bits on 64-bit hw for cperl compatibility my $half = ( ( log(~0 + 1) / log(2) ) >= 64 ) ? 30 : 16;

        Regards, Mario

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1197385]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (5)
As of 2018-10-23 16:52 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    When I need money for a bigger acquisition, I usually ...














    Results (125 votes). Check out past polls.

    Notices?