I just finished a program for university. It was a challenge where we had to create an implementation of John Conway's Game of Life and make it as fast as possible. Since I found the challenge to be fun and interesting, I'm posting it here for all of you.
The basic rules of the game are explained here:
http://en.wikipedia.org/wiki/Conway's_Game_of_Life
Your objective is to implement a program that runs this simulation as fast as possible. Measure of performance is
a) the number of CPU cycles used and
b) the physical time used. (Mean of three runs.)
The program will be executed for 3000 generations on two different patterns on two different machines. Each result will be given a score relative to the results of my reference implementation. (8 results: two measurements over two starting patterns and two machines) The mean of the score is the final result. Implementations that produce an incorrect result are disqualified. Implementations that need more than two minutes for a run are disqualified, too. I'm not that patient.
The program must be able to read and write a simple textual file format. This file holds two whitespace-separated numbers per line, which form a coordinate pair designating a cell that is alive.
The above specifies that the cell at (100,24) is alive, as is the cell at (-24, 51).Code:100 24 -24 51
Input to the programs will be given in this format, and the program must produce this format as output (either to stdout or a configurable file name). The order of points is irrelevant; the file will be sorted before any comparison is done.
The machine specifications are:
1)
Intel Core Duo (32-bit instruction set, SSSE3 support, dual core)
1 GB RAM
2)
AMD Athlon64 (64-bit instruction set, SSE2 support, single core)
1 GB RAM
The target compiler is GCC 4.1 or GCC 4.2 (depends on what I'll be using when the contest ends) on a Linux system. There is no need to make it portable to other platforms.
The project must include a simple way of building. You can use GNU autotools/make, SCons, Boost.Build or a custom shell script (Bourne shell or bash). Compilations must be possible with one, at most two, simple commands. (e.g. "./configure; make" or "bjam").
You may use C or C++. If you use C++, you may expect the Boost libraries to be available, both 1.34.1 and 1.35. (Hopefully it will be released by then.)
Implementations based on hashlife are forbidden, sorry. This advanced algorithm is so superior that it would be pointless to compare it against the other possibilities.
This is an optimization challenge. Optimize your algorithms, and optimize your instructions. Every cycle counts.
The contest ends at 0:00, April 21th. Have fun!
I will post a few test input/output files soon.