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

[tybalt89]

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 :(

[marioroy]

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

[marioroy]

Update 1: Added results for the original version and initial improvements.
Update 2: Added results from tbench1-infinite.pl using Game::Life::Infinite::Board.
Update 3: Added results for C++, Organism.h and tbench1.cpp.

In this thread, we've learned that pack i2 is faster than pack ii. Furthermor, functions having inner loops benefit greatly by inlining critical paths. In essence this is what we've done. The pack i2 solution fully optimized is found here, by tybalt89. The mapping of two numbers into one can be found here. Similarly, a shorter implementation by tybalt89 is found here. The fastest time was noted for each run with nothing else running in the background.

The maximum key length for $c, obtained separately, is 7, 12, and 18 for pack i2, the mapping of two numbers, and the shorter solution by tybalt89, respectively. The fix for the latter solution, when running cperl on 64-bit hardware, is using 30 bits instead of 32, described here.

The x and y tmp files were made using eyepopslikeamosquito's createblinker.pl script, found at the top of this thread.

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

Benchmark results were captured on a 2.6 GHz laptop (i7 Haswell). I apologize for not having something older to benchmark on. If anything, the OP's machine is faster than mine. ;-)

Results:

c++              138 MB    4 secs

               mem size   v5.26.0   v5.24.2   v5.22.4

infinite       7,548 MB  122 secs  119 secs  133 secs
original         704 MB  167 secs  168 secs  180 secs
improvements     744 MB   57 secs   57 secs   63 secs
optimized i2   1,543 MB   38 secs   39 secs   40 secs
2 nums into 1  1,510 MB   39 secs   40 secs   42 secs
shorter impl   1,661 MB   40 secs   42 secs   44 secs

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 = 1500000
time taken: 116 secs   - infinite board
time taken: 163 secs   - original
time taken:  54 secs   - improvements
time taken:  36 secs   - optimized pack i2
time taken:  37 secs   - two numbers into one
time taken:  37 secs   - shorter implementation

Pack returns unreadable data, but is fast. Readable keys may be preferred for storing into a DB. Stringification "$x:$y" is one way. Unfortunately, that requires split to extract the values and a text field versus numeric if storing into a DB. Bit manipulation is another way.

Running Game::Life::Infinite::Board consumes lots of memory. If possible, check for 8 ~ 10 gigabytes of available memory to minimize the OS from swapping. It also takes ~ 10 seconds during global cleanup while exiting.

eyepopslikeamosquito, infinite isn't running ~ 2x slower as reported here for 1.5 million cells. My laptop has 1600 MHz RAM and verified available memory before running.

Regards, Mario

[tybalt89]

New entry.

Hey, it passes all the tests :)

hehehe

package Organism;

# based on http://perlmonks.org/?node_id=1197284

use strict;
use warnings;

sub count
  {
  return shift->{config}[0] =~ tr/1//;
  }

# Input a list of [ x, y ] coords
sub insert_cells
  {
  my $extra = 3;
  my $self = shift;
  my $xl = my $xh = $_[0][0]; # find cell limits
  my $yl = my $yh = $_[0][1];
  for (@_)
    {
    my ($x, $y) = @$_;
    $xl > $x and $xl = $x;
    $xh < $x and $xh = $x;
    $yl > $y and $yl = $y;
    $yh < $y and $yh = $y;
    }
  my $xoffset = $xl - $extra; # get sizes and insert live cells
  my $w = $xh - $xl + 2 * $extra;
  my $yoffset = $yl - $extra;
  my $h = $yh - $yl + 2 * $extra;
  my $grid = '0' x $w x $h;
  for (@_)
    {
    my ($x, $y) = @$_;
    substr $grid, $x - $xoffset + ($y - $yoffset) * $w, 1, '1';
    }
  $self->{config} = [ $grid, $w, $h, $xoffset, $yoffset ];
  }

# 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;
  my ( $grid, $w, $h, $xoffset, $yoffset ) = @{ $self->{config} };
  my @cells;
  push @cells, [ $-[0] % $w + $xoffset, int( $-[0] / $w ) + $yoffset ]
    while $grid =~ /1/g;
  sort { $a->[0] <=> $b->[0] || $a->[1] <=> $b->[1] } @cells;
  }

sub tick
  {
  my $self = shift;
  my ( $grid, $w, $h ) = @{ $self->{config} };
  my $all = '0' x ($w + 1) . $grid;
  my $sum = $all =~ tr/1/2/r;
  ( $sum |= substr $all, $_ ) =~ tr/1357/2468/ for
    1, 2, $w, $w + 2, $w * 2, $w * 2 + 1, $w * 2 + 2; # other 7 neighb
+ors
  $grid = substr $grid | $sum, 0, $w * $h;
  $self->{config}[0] = $grid =~ tr/1-9/000011100/r; # dead or alive
  }

sub new {
   my $class = shift;
   my %init_self = ( );
   bless \%init_self, $class;
}

1;

[eyepopslikeamosquito]

Re having an old PC - and rubbing salt into tybalt89's wounds - please note that my (Haswell 4770K-powered) home PC is unchanged from when I mentioned it over three years ago in The 10**21 Problem (Part 2) and so is getting rather old and creaky now. Definitely due for an upgrade. :)

Though my ancient PC does have 32 GB of memory (and so there is no swapping), given my very slow benchmark results with Game::Life::Infinite::Board, I'm suspicious that my doddering, ancient memory is starting to fail, due to being so old. This may be contributing to the significantly different results I am seeing.

When running:

perl tbench1.pl x.tmp 2

with my originally shortened Organism.pm:

package Organism;

use strict;
# use warnings;

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} };
}

sub tick {
   my $self  = shift;
   my $cells = $self->{Cells};
   my ( $k1, $k2, $k3, $k4, $k5, $k6, $k7, $k8,
        $x0, $x1, $x2, $y0, $y1, $y2, %new_cells );

   for my $c (keys %{ $cells }) {
      # Get the (up to 8) dead cells surrounding the cell
      ( $x0, $y0 ) = unpack 'i2', $c;
      ( $x1, $x2, $y1, $y2 ) = ( $x0 - 1, $x0 + 1, $y0 - 1, $y0 + 1 );
      my @zcells = (
         ($k1 = pack 'i2', $x1, $y1) x !(exists $cells->{$k1}),
         ($k2 = pack 'i2', $x1, $y0) x !(exists $cells->{$k2}),
         ($k3 = pack 'i2', $x1, $y2) x !(exists $cells->{$k3}),
         ($k4 = pack 'i2', $x0, $y1) x !(exists $cells->{$k4}),
         ($k5 = pack 'i2', $x0, $y2) x !(exists $cells->{$k5}),
         ($k6 = pack 'i2', $x2, $y1) x !(exists $cells->{$k6}),
         ($k7 = pack 'i2', $x2, $y0) x !(exists $cells->{$k7}),
         ($k8 = pack 'i2', $x2, $y2) x !(exists $cells->{$k8}) );

      # 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) {
         ( $x0, $y0 ) = unpack 'i2', $z;
         ( $x1, $x2, $y1, $y2 ) = ( $x0 - 1, $x0 + 1, $y0 - 1, $y0 + 1
+ );
         # Get num live
         (   ( exists $cells->{ pack 'i2', $x1, $y1 } )
           + ( exists $cells->{ pack 'i2', $x1, $y0 } )
           + ( exists $cells->{ pack 'i2', $x1, $y2 } )
           + ( exists $cells->{ pack 'i2', $x0, $y1 } )
           + ( exists $cells->{ pack 'i2', $x0, $y2 } )
           + ( exists $cells->{ pack 'i2', $x2, $y1 } )
           + ( exists $cells->{ pack 'i2', $x2, $y0 } )
           + ( 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;

I get 62 seconds, while after making the excellent improvements suggested by tybalt89 I get 80 seconds.

package Organism;

use strict;
# use warnings;

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} };
}

sub tick {
   my $self  = shift;
   my $cells = $self->{Cells};
   my ( $k1, $k2, $k3, $k4, $k5, $k6, $k7, $k8,
        $x0, $x1, $x2, $y0, $y1, $y2, %new_cells, %dead_cells );

   for my $c (keys %{ $cells }) {
      # Get the (up to 8) dead cells surrounding the cell
      ( $x0, $y0 ) = unpack 'i2', $c;
      ( $x1, $x2, $y1, $y2 ) = ( $x0 - 1, $x0 + 1, $y0 - 1, $y0 + 1 );
      $dead_cells{$_}++ for my @zcells = (
         ($k1 = pack 'i2', $x1, $y1) x !(exists $cells->{$k1}),
         ($k2 = pack 'i2', $x1, $y0) x !(exists $cells->{$k2}),
         ($k3 = pack 'i2', $x1, $y2) x !(exists $cells->{$k3}),
         ($k4 = pack 'i2', $x0, $y1) x !(exists $cells->{$k4}),
         ($k5 = pack 'i2', $x0, $y2) x !(exists $cells->{$k5}),
         ($k6 = pack 'i2', $x2, $y1) x !(exists $cells->{$k6}),
         ($k7 = pack 'i2', $x2, $y0) x !(exists $cells->{$k7}),
         ($k8 = pack 'i2', $x2, $y2) x !(exists $cells->{$k8}) );

      # 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 %init_self = ( Cells => {} );
   bless \%init_self, $class;
}

1;

Update: These tests were run with perl v5.24.0:

This is perl 5, version 24, subversion 0 (v5.24.0) built for MSWin32-x
+64-multi-thread

Need to upgrade that ancient Perl. :)

Update: After upgrading to perl v5.26.0, both are faster: (62 secs, 80 secs) improved to (53 secs, 71 secs).

[tybalt89]

To get decent times for testing purposes with the smaller number of blinkers, increase the number of ticks.