Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re: High Performance Game of Life

by tybalt89 (Curate)
on Aug 11, 2017 at 22:36 UTC ( #1197284=note: print w/replies, xml ) Need Help??


in reply to High Performance Game of Life

And now for something completely different :)

This was written to see if I could use perl's logical string operations to do the calculations need for Life.

Of course, what I really wanted was a string oriented byte-by-byte add ( a +. to go along with the brand new |. and &. ) but I couldn't find one (sigh).

However, this is a way to use three bits in the byte as a sum, provided only one bit is added at a time.
Consider the 8 bits of a byte to be 0011SSSN where the 'S' bits are the sum and a new bit 'N' is added (actually or'd) as the bottom bit. (Why the two '1' bits? Because the character '0' is 00110000 as binary and '1' is 00110001 as binary, and we can do calculations such that the result is immediately printable. We don't, but we could :)

Now if I 'or' in a neighbor character it will only (potentially) change the 'N' bit. For each neighbor, I only have to add that bit to the sum (in SSS) and then clear the bottom bit for the next neighbor.

This turns out to be a simple tr/1357/2468/ translation.

(But tybalt89, you say, you only have a three bit counter and there are eight neighbors, you can't hold a count that high. Answer: I don't have to, since any count four or greater will result in a dead cell, I only have to count to four.)

After processing all eight neighbors, the center cell is then or'd in to give the state of the neighbor count along with the state of the center cell, which can the be translated to "alive or dead" for the next generation.

In this scheme, you need to specify the size of the grid in advance, and any live cells at the grid edge get killed to avoid wraparound'


So how does this do on the challenge - simple, it fails. (Oh good, I can avoid being hired :)

You did say you wanted "to see how others go about it".

Notes:

It's "live cell count" speed invariant, as opposed to techniques that keep only live cells.
I stopped performance testing because I ran into Heisenberg problems, i.e. output seriously affects speed.
It's not infinite size, or even semi-infinite, unless you've got a really, really, really big machine.
It should probably be moved to GPUs but a) I don't have a GPU to test on, and b) it probably already has been.


I usually run it without the override lines, and uncommented print statements. It autosizes to the terminal it is running in, (at least on ArchLinux and xterm), and of course increase the number of generations.



OK, I have to go cook supper, and I'm really tired of typing, so I'll submit at this point, and look for comments later...

#!/usr/bin/perl # http://perlmonks.org/?node_id=1197250 # Conway's life eyepopslikeamosquito use strict; use warnings; use Time::HiRes 'time'; my $w = qx(tput cols) + 0; # probably linux only :) my $h = qx(tput lines) - 7; # strange offset because of my REPL # override for comparison with node results $w = int sqrt 3e6; $h = int 1 + 3e6 / $w; my $board = '0' x $w x $h; my $mask = '0' x $w . ('0' . "\xff" x ($w - 2) . '0') x ($h - 2) . '0' + x $w; # build starting state sub place { my ($x, $y, $pattern) = @_; my $offset = $y * $w + $x; for ( $pattern =~ /.+/g ) { substr $board, $offset, length $_, $_; $offset += $w; } } place( 4, 4, <<END =~ tr/-O/01/r ); # glider gun ------------------------O----------- ----------------------O-O----------- ------------OO------OO------------OO -----------O---O----OO------------OO OO--------O-----O---OO-------------- OO--------O---O-OO----O-O----------- ----------O-----O-------O----------- -----------O---O-------------------- ------------OO---------------------- END place( $w >> 1, $h >> 1, <<END =~ tr/-O/01/r ); # switch engine ---------- -------O-- -----O-OO- -----O-O-- -----O---- ---O------ -O-O------ ---------- END my $generations = 0; my @offsets = ( 1, 2, $w, $w + 2, $w * 2, $w * 2 + 1, $w * 2 + 2 ); my $pad = '0' x ($w + 1); #print "\e[H\e[J"; # clear screen #print "\e[H", $board =~ tr/01/ O/r, "-" x $w, "$generations\n"; my $starttime = time; for (1..2) # loop over generations { $generations++; my $all = $pad . $board . $pad; my $sum = $all =~ tr/1/2/r; # first o +ffset ( $sum |= substr $all, $_ ) =~ tr/1357/2468/ for @offsets; # other 7 $board |= $mask & $sum; # prevent overflow at edges $board =~ tr/1-9/000011100/; # determine alive or dead #print "\e[H", $board =~ tr/01/ O/r, "-" x $w, "$generations\n"; } my $time = time - $starttime; printf "\nw %d h %d cells %d time %.2f generations %d gen/sec %d" . " nanoseconds/cell/gen %d\n", $w, $h, $w * $h, $time, $generations, $generations / $time, $time / ($w * $h) / $generations *1e9;

Replies are listed 'Best First'.
Re^2: High Performance Game of Life
by zentara (Archbishop) on Aug 12, 2017 at 13:25 UTC
    ..oO i wonder if some engineering school would accept this project as a Phd thesis? Conway's Game of Life, with GUI visualization, optimized with assembly language routines. :-)

    I'm not really a human, but I play one on earth. ..... an animated JAPH

      Conway's Game of Life, with GUI visualization, optimized with assembly language routines. :-)

      Been done, minus the assembly bits (but I'm sure patches would be welcome): golly.sourceforge.net

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (10)
As of 2017-10-22 21:33 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My fridge is mostly full of:

















    Results (275 votes). Check out past polls.

    Notices?