9/14/2023 0 Comments Conway game of life rtsTo better understand this, I've added some instrumentation to the C version of each of these algorithms. Doing this suggests moving to 8 cell chunks should be 3.4x faster. When I compared these a few days ago, I had rather simplistically just multiplied the List Life figure by 8 to make them comparable. List Life with 8-cell chunks is 266 cycles (per 8 cells) This is somewhat of a surprise, as my cycle counting lead me to believe the Life88 kernel would be about 3x faster.Īs an estimate of the kernel complexity, I had simply counted 6502 cycles: (On a 225MHz 6502 Co Pro, with rendering turned down to once every 32 frames to focus on just the life algorithms) List Life with 8-cell chunks takes 82s (212 generations/sec) List Life takes 71s (245 generations/sec) Running the "rabbits" pattern to 17400 generation: What's rather surprising is that the original list_life is actually a bit faster than the chunked version. List Life with 8-bit chunks using the Kernel of Life88 for computation I've got to the point now where I can try the three different algorithms with arbitrary RLE patterns: the clever avoidance of shifts, in marshalling the partial bytes into the appropriate collections, to deal with the overlapping windows the extreme benefit of using lookup tables to transform a byte into a byte (I think there are 7 page-sized lookup tables in the code) Last edited by BigEd on Sun 5:03 pm, edited 1 time in total.Ī couple of things stand out for me, having looked a bit more at the Life88 diagram I expect there's a lot more to be said, about algorithms used and ideas for improving them!įile comment: Data flow in Life88, drawn by DaveB it's interesting to find a good way to partition computation and display, on a two-processor Acorn BBC. modern life programs use huge datastructures, huge tables, and 32-bit or 64-bit arithmetic, none of which are much help for a 6502. a combination of a list with a bitmap gives the best result a list structure allows for a much larger universe the fastest evaluation is on a finite grid Here's a video of some patterns running on these programs. Indeed, Dave has a great diagram of the innards of the present code - see attached. There are ways to improve this, which Dave is presently pursuing. A friend of mine made available his 6502 code from 1988, which uses a different list-based approach, turning out to be faster than Dave's version but with a universe of 1k by 1k. This ends up having a smaller universe, but is the fastest we've seen, especially on small patterns. Litwr brought in his Xlife-8 implementations, which use some of the tactics from the Unix program Xlife, again ported from C to 6502. This turns out to be nice and fast and offers a large 32k by 32k universe. a version for the Atom was ported by Dave to the Beeb's second processor, and then converted to use Tony Finch's List Life algorithm, which had to be ported from C to 6502. ![]() In addition to commercial and type-in offerings, three implementations have jumped out in the recent discussion: We (André and I) posted about this previously. There are questions of how to display the board, which are platform specific, and then there are questions of how to compute the next generation, which are algorithmic and where 6502 coding skill can really make a difference. But of course other 6502 machines also have seen implementations, so Dave (hoglet) and I thought it would be good to discuss here. Recently we've had an interesting thread going, over on Stardot, about implementations of Conway's Game of Life on Acorn machines.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |