3 ms·
While it absolutely doesn't hold a candle to 32 bytes :) I'm reminded of the 1691-byte IOCCC entry from 1991 which drew the Game of Life on the root X server wi
by exikyut 7y ago
While it absolutely doesn't hold a candle to 32 bytes :) I'm reminded of the 1691-byte IOCCC entry from 1991 which drew the Game of Life on the root X server window without using Xlib.
I'm completely naive about Life implementations, and I've always been curious if the approach used by this entry is especially interesting; it's certainly a fascinating read (https://www.ioccc.org/1991/davidguy.hint https://www.ioccc.org/1991/davidguy.hint):
The algorithm used to compute the next generation is based on the observation that a cell's state in the next generation is a boolean function of its current state, and the states of its 8 neighbors (ie, a boolean function from 9 bits to 1 bit). This function can be computed by a boolean circuit. In addition, intermediate values computed by the circuit can be shared between neighboring cells, reducing the number of gates per cell required.
These ideas have been used before, to compute the next generation through a series of bit blits. Instead of doing this, we map values in the circuit to bits in registers, so that the next generation can be computed efficiently within registers, minimizing memory accesses.
As a result, the computation of the next generation is performed with about 1.6 instructions per life cell, consisting of .125 memory accesses, .17 shifts, and 1.3 logic operations. The net result is that the time to transfer the bits to the X server, and for the X server to draw them on the screen, dominates the time to compute the next generation.
I'm not sure what I did last time I tried to get this working and failed; it works great on Debian 10 with GCC 8.3 etc:
$ wget https://www.ioccc.org/1991/davidguy.fix.c https://www.ioccc.org/1991/davidguy.fix.c
$ gcc -o davidguy davidguy.fix.c -m32
$ xhost +
$ ./davidguy
If your X server is not :0, change the last character of the ".slo.-W00,tmhw.W/" string to be one less
in ASCII to the display number (ie 0 -> /, 1 -> 0, 2 -> 1, etc).
The main reason I added this comment was out of curiosity about the technical competence/interestingness of the implementation.
- fanf2 7y agoThis general technique is (or was) called SWAR for SIMD-within-a-register, before CPUs had actual SIMD registers and instructions. I played around with bit-parallel Game of Life a while back, calling it LIAR (Life In A Register). If you are doing really fast hashlife then the very low level supercell representations can be small bitmaps for which LIAR works nicely. https://fanf.livejournal.com/93032.html https://fanf.livejournal.com/93032.html