fluffykitty wrote:Try using 32-bit integers and bitwise operators to compute 32 cells in parallel. (Or does this language that you're using not have bitwise operators? If so, um....run?)
Bit-twiddling does seem to be the method of choice among fast Life simulators -- Life32, QuickLife, etc.
If that's a little too ugly to tackle with your current coding scheme, there's an intermediate algorithm that I _think_ would speed things up a bit (no pun intended). Is Delphi/Object Pascal relatively quick at maintaining sorted lists, and determining whether an item is in a list or not?
If so, then maybe you can just keep a list of the ON cells, check if any of them should be turned OFF due to too many or two few neighbors, and check if any of the cells neighboring the active list have exactly three neighbors themselves and should be added to the active list for the next generation.
Then... if on some step the active list doesn't change, the pattern has stabilized and there's no need to do any more work. A little more checking will catch p2 stabilization, and that's also probably worth the extra overhead.
In general, the first thing to try to avoid is the very common case where a pattern dies out or becomes boring, and yet the generation algorithm blindly goes on checking every neighbor of every individual cell for the full 41 ticks, to see if something different will happen this time around (!).
Your mileage may vary, but even just figuring out how to avoid all those iteration steps on the boring OFF cells in the corners of your grid bounding box, might be enough to speed things up a little.
The next step up on the way to bit-twiddling optimization might be to divide the grid into reasonable-sized tiles, and be able to certify each one separately as p2 stabilized (so it doesn't need any more attention unless a neighboring active tile is changing.) That's probably too much to tackle for this particular project, though -- you might as well just jump straight to the bit-twiddling solution.
The biggest improvement for the least amount of work seems like it would be re-implementing CopperSearch using an existing library, probably simsim314's Life API
. You could certainly learn C/C++ enough to get that working -- I'm not saying it won't be painful, but I bet people here would be happy to help (if they don't get impatient and do the whole rewrite themselves).
If you really had to, you could probably stick with Delphi, and use C wrappers for LifeAPI calls
. That makes it harder for most people to help with the coding, though, and on balance it's likely to be an unnecessary headache.
Alternatively, just make the minor adjustments to the old apgsearch Python script, which calls Golly. Maybe that won't be much of a speed increase, but at least you get all the cataloguing and censusing functionality for free, and everyone can stop worrying about throwing away perfectly good p8 or p15 spaceships...!