Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??

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;

In reply to Re: High Performance Game of Life by tybalt89
in thread High Performance Game of Life by eyepopslikeamosquito

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others romping around the Monastery: (3)
As of 2024-06-22 06:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?
    erzuuli‥ 🛈The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.