Implementing Conway's Life
Tony Finch
are well-known?
Tony.
--
f.a.n.finch <d...@dotat.at> http://dotat.at/
COLWYN BAY TO THE MULL OF GALLOWAY INCLUDING THE ISLE OF MAN: MAINLY SOUTH 4
OR 5 SOON VEERING NORTH 5 OR 6 BUT THEN GRADUALLY EASING AND VEERING EAST TO
SOUTHEAST 3 OR 4, BECOMING SOUTHEAST 5 OR 6 LATER.
Tim Tyler
> How many of the techniques in http://dotat.at/prog/misc/life.html
> are well-known?
Some relevant resources - which contain descriptions of quite a number of
techniques related to optimising Life implementations, but which you
didn't reference - may help with that.
http://public.planetmirror.com/pub/gpbb/gpbb17.pdf
http://public.planetmirror.com/pub/gpbb/gpbb18.pdf
http://hensel.lifepatterns.net/lifeapplet.html
--
__________
|im |yler http://timtyler.org/ t...@tt1lock.org Remove lock to reply.
George Maydwell
>How many of the techniques in http://dotat.at/prog/misc/life.html
>are well-known?
>
>Tony.
How well do the techniques work in practice? Have you run any cellular
automata benchmark tests?
George Maydwell
--
Modern Cellular Automata: www.collidoscope.com/modernca
Collidoscope Hexagonal Screensaver: www.collidoscope.com
Tony Finch
>
>How well do the techniques work in practice? Have you run any cellular
>automata benchmark tests?
On my computer, xlife (with the X bits hacked out) does 10,000 generations
of the puffer train in exactly 1 minute. Mine takes 22 seconds.
Tony.
--
f.a.n.finch <d...@dotat.at> http://dotat.at/
MALIN HEBRIDES: NORTHERLY VEERING SOUTHEASTERLY 3 OR 4, INCREASING 5 TO 7,
PERHAPS GALE 8 LATER. SHOWERS THEN RAIN. GOOD BECOMING MODERATE.
David Eppstein
Tony Finch <d...@dotat.at> wrote:
> >How well do the techniques work in practice? Have you run any cellular
> >automata benchmark tests?
>
> On my computer, xlife (with the X bits hacked out) does 10,000 generations
> of the puffer train in exactly 1 minute. Mine takes 22 seconds.
How quickly does Rokicki's hlife <http://tomas.rokicki.com/hlife/> run
the same pattern for the same number of generations?
--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
Tony Finch
>
>How quickly does Rokicki's hlife <http://tomas.rokicki.com/hlife/> run
>the same pattern for the same number of generations?
I haven't tested yet, but I expect hlife to win by a very large margin
since the puffer train has lots of still life and blinkers to make
Gosper's algorithm look good, and hlife's low-level implementation is
quite good at handling the more random parts.
I'm mostly interested in references to the co-ordinate list approach,
and combinations of it with lookup tables or bitwise addition. I first
implemented what I called listlife in 1994 but parallelising it is new
to me. The bitwise addition approach is well-known -- it was published in
BYTE in January 1979 and I knew about it in 1993. Fortunately my employer
has a copy of that magazine in a library near my office. (There's also
a copy of Gosper's paper in one of the more remote libraries, which I
haven't looked at yet.)
One of the nice things about my algorithm is that the strategic parts
are very light-weight, which is how it wins over XLife. Alan Hensel's
Java life is a suped-up version of the XLife algorithm which benefits
from knowing about still life -- perhaps enough to compensate for the
extra weight, though without a C implementation the numbers cannot be
compared.
Tony.
--
f.a.n.finch <d...@dotat.at> http://dotat.at/
LANDS END TO ST DAVIDS HEAD INCLUDING THE BRISTOL CHANNEL: SOUTHWEST 6 OR 7
VEERING WEST 5 OR 6 ON SATURDAY, OCCASIONALLY 4 AROUND THE SHORE. RAIN,
DRIZZLE AND MIST CLEARING TO SHOWERS ON SATURDAY. MODERATE OR POOR BECOMING
GOOD ON SATURDAY. MODERATE OR ROUGH.
Owen Rees
<tTB*cq...@news.chiark.greenend.org.uk>:
>I'm mostly interested in references to the co-ordinate list approach,
>and combinations of it with lookup tables or bitwise addition. I first
>implemented what I called listlife in 1994 but parallelising it is new
>to me. The bitwise addition approach is well-known -- it was published in
>BYTE in January 1979 and I knew about it in 1993. Fortunately my employer
>has a copy of that magazine in a library near my office. (There's also
>a copy of Gosper's paper in one of the more remote libraries, which I
>haven't looked at yet.)
In 1975, the Computer Science Tripos students at Cambridge were set an
assessed exercise to implement a Life player. The coordinate list idea
was described to me by my assessor (Ken Moody IIRC) when my attempt was
marked (I had used a much less efficient linked list system). I don't
know whether or not the idea was written down anywhere.
When I decided to implement a Life player some years later, I started
with the coordinate list idea, but very soon switched from the
coordinates themselves to the difference between coordinates
(essentially run-length encoding the dead cells/rows). The first
implementation was for an Acorn Electron, I then did a Xerox Lisp
version, and eventually one in C for the Atari ST (which can still be
found on the net). The Atari implementation dates back to 1993 -
according to the notes I still have lurking around, I uploaded v3 of the
player to the Atari archive in December 1993. I did a version which
processed multiple cells in parallel, but that was never published. I
still have notes on the performance numbers on an Atari STe, but they
are not easy to compare to something running on a PC.
I still have the code, and I did once port the basic generation
functions to run under Windows, but converting the graphics and UI
seemed to be too much effort when there are plenty of high performance
Life implementations for PCs.
>One of the nice things about my algorithm is that the strategic parts
>are very light-weight, which is how it wins over XLife. Alan Hensel's
>Java life is a suped-up version of the XLife algorithm which benefits
>from knowing about still life -- perhaps enough to compensate for the
>extra weight, though without a C implementation the numbers cannot be
>compared.
Try Alan Hensel's Life 1.06 for MS-DOS if you want something to compare
with for speed.
Comparing the performance of the underlying algorithms is difficult
given how much of the time is spent handling the display.
--
Owen Rees - opinions expressed here are mine; for a full disclaimer
visit <http://homepages.tesco.net/~owen.rees/index.html#disclaimer>
for e-mail use "owen.rees at tesco.net" instead of the From address
Tim Tyler
> Try Alan Hensel's Life 1.06 for MS-DOS if you want something to compare
> with for speed.
>
> Comparing the performance of the underlying algorithms is difficult
> given how much of the time is spent handling the display.
The Java implementation [http://hensel.lifepatterns.net/] has
generations/frame and frame/seconds settings that effectively
allow you to turn off the display.
It might be fun to include it in any benchmarking - even though it
is written in a different language.
Tony Finch
>
>In 1975, the Computer Science Tripos students at Cambridge were set an
>assessed exercise to implement a Life player. The coordinate list idea
>was described to me by my assessor (Ken Moody IIRC) when my attempt was
>marked (I had used a much less efficient linked list system). I don't
>know whether or not the idea was written down anywhere.
I'll add him to my list of people to talk with.
Did LifeLine include much discussion of algorithms?
>and eventually one in C for the Atari ST (which can still be
>found on the net)
Google only knows one broken link to it.
>Try Alan Hensel's Life 1.06 for MS-DOS if you want something to compare
>with for speed.
I can't examine it properly without source code.
Tony.
--
f.a.n.finch <d...@dotat.at> http://dotat.at/
NORTH UTSIRE: SOUTH VEERING WEST 4 OR 5 OCCASIONALLY 6. RAIN. MAINLY MODERATE.
Paul Chapman
> In 1975, the Computer Science Tripos students at Cambridge were set an
> assessed exercise to implement a Life player.
Much more interesting than anything they gave us in 1978-9. :)
> When I decided to implement a Life player some years later, I started
> with the coordinate list idea, but very soon switched from the
> coordinates themselves to the difference between coordinates
> (essentially run-length encoding the dead cells/rows). The first
> implementation was for an Acorn Electron ...
I implemented a very similar algorithm on the BBC Micro with Z80 second
processor, and then later on the Archimedes.
However, I discovered a couple of years ago that it doesn't begin to compare
with Hensel's algorithm (as implemented in Life 32).
Earlier this year I came up with a combination of run-length and Hensel-type
parallelism. I recently sent a brief description to a friend, and I reprint
part of that email here:
>>
The (2^32-16)x(2^32-16) universe is divided up into 2-by-12 bricks of cells.
Here are two rows of bricks (making up 4 rows of cells):
... XXXXXXXXXXXX XXXXXXXXXXXX ...
... XXXXXXXXXXXX XXXXXXXXXXXX ...
... XXXXXXXXXXXX XXXXXXXXXXXX ...
... XXXXXXXXXXXX XXXXXXXXXXXX ...
Any brick with at least one live cell in it is represented as a 24-bit mask
in a 32-bit word (the details are unimportant; the spare bits are needed for
flags, etc).
Runs of empty bricks are represented as (32-bit or 64-bit) run-counts.
Furthermore, the rows of bricks (each row has (2^32-16)/12 bricks) are laid
end to end, so runs of empty bricks can continue over many rows. Thus the
empty universe is just one run-count of (2^32-16)*(2^32-16)/24.
The two next-gen algorithms (Even and Odd) scan two rows at a time. Each
builds a new brick out of parts of 4 original bricks (using a lookup table,
etc) as follows:
Even Odd
11 222222222222 111111111111 22
1Q QQQQQQQQQQQ2 1RRRRRRRRRRR R2
3Q QQQQQQQQQQQ4 3RRRRRRRRRRR R4
33 444444444444 333333333333 44
As you can see, the new brick is offset diagonally from the original bricks.
The algorithms are so arranged so that the Odd algorithm reverses the offset
of the Even algorithm.
<<
I am now using a pure 32-bit version of the algorithm (written in C/C++) for
practical work. For the time being, a universe of 321048x321048 seems to be
adequate. :)
Performance-wise, even the 64-bit algorithm did about the same as Life32 on
large P30-based engineered patterns. Life32 still outperforms my 32-bit
version by a factor of about 3 for random patterns, probably because of the
advantage Hensel's algorithm has on small areas which are stable or
period-2.
The working set of values should fit in the seven available x86 registers,
but MSVC++ makes a hash of the code generation. I may have to recode in
assembler to get the performance up, when I hope it would compare with
Life32.
I haven't yet compared with Life 1.06. I will do so when I get the
competitive urge again. :)
Cheers, Paul
Tony Finch
>
>However, I discovered a couple of years ago that it doesn't begin to compare
>with Hensel's algorithm (as implemented in Life 32).
I'm currently not concerned about the performance of linear life
algorithms, given that 90% of the time is spent in the display code. I
clearly need to learn more about X... If you aren't displaying every
generation then Gosper's HashLife is a much more satisfying algorithm.
Tony.
--
f.a.n.finch <d...@dotat.at> http://dotat.at/
FAIR ISLE FAEROES: SOUTHWEST VEERING NORTHWEST 5 TO 7, OCCASIONALLY GALE 8,
DECREASING 3 OR 4 LATER. OCCASIONAL RAIN OR WINTRY SHOWERS. GOOD OCCASIONALLY
MODERATE.
Paul Chapman
> I'm currently not concerned about the performance of linear life
> algorithms, given that 90% of the time is spent in the display code.
Life32 has a "benchmark" facility which runs a pattern as fast as possible
without display. I provide both displaying and nondisplaying entry points
in my DLL. When I do benchmarks, I concentrate on nondispaying comparisons;
when displaying, there's little to choose between my implementation and
Life32's (with DirectX turned off).
> I
> clearly need to learn more about X... If you aren't displaying every
> generation then Gosper's HashLife is a much more satisfying algorithm.
Yes, if you are doing long-range runs: HLife completed a run of my Life
Computer in 70 seconds which would have taken Life32 about three weeks. :)
At the moment, however, I'm trying to write code which examines short-term
behaviour of a LOT of patterns and is able to intelligently analyze
outcomes, eg for stability, periodicity, or even a central periodic remnant
plus some centrifugal spaceships. And is able to do so quickly. In this
case, a library of routines which can do a range of manipulations (eg
"matches", "xor", "get bounding box") using a suitable Life-pattern
representation is best.
I'm also exchanging data between Smalltalk and C, so the single contiguous
buffer for my representation simplifies things a lot.
Cheers, Paul