dr Discussion Thread

For scripts to aid with computation or simulation in cellular automata.
Post Reply
Sokwe
Moderator
Posts: 1631
Joined: July 9th, 2009, 2:44 pm

dr Discussion Thread

Post by Sokwe » January 4th, 2020, 1:38 am

This is a thread for discussing the drifter search program dr, by Dean Hickerson. The following zip file contains the C source code and knownrotors file, as well as a documentation file that describes some, but not all of the options. Some further options are described within the source code.
dr.zip
(122.24 KiB) Downloaded 36 times
Unfortunately, the knownrotors file only contains rotors discovered up to October 2015. I will update this post if anyone provides an updated knownrotors file.

Some other resources related to dr:
  • I made a small modification to dr. The source code for this modification is here.
  • Bob Shemyakin wrote an application (available here) for editing the knownrotors file. However, the knownrotors file provided with the application is more out-of-date than the file in the .zip above.
-Matthias Merzenich

Hooloovoo
Posts: 37
Joined: July 11th, 2015, 8:59 pm

Re: dr Discussion Thread

Post by Hooloovoo » January 4th, 2020, 4:26 pm

Could someone with access to the wiki add dr to the LifeWiki:Life Links page? The Drifter page could also use a link to this thread.

EDIT by dvgrn: Done! If you'd like to have editing access to the LifeWiki yourself, just create a 'Hooloovoo' user there and let me know.

Hooloovoo
Posts: 37
Joined: July 11th, 2015, 8:59 pm

Re: dr Discussion Thread

Post by Hooloovoo » January 5th, 2020, 3:22 pm

Since I'm using dr to smash oscillators together I need to run it a lot of times. Depending on the specific oscillators, a single pair can take from hundreds to thousands of runs, with each run taking (again depending on specifics) around 5 seconds on average, or a couple hours for the whole run.

I used perf stat to see there was any particular performance bottlenecks, and it showed "57.57% frontend cycles idle" and that 5.56% of branch predictions are missed. On modern CPUs, 5.5% is an atrociously bad BP miss rate: stalling a deep pipeline and re-decoding instructions is very expensive.

I used valgrind's cachegrind profiler (which can profile BP misses in addition to caches) to find where exactly dr was spending its time. Assuming cachegrind's statistics are accurate, 54% of its time is spent in listneighbors, and 18% is in consistify. There are two particularly bad hotspots in listneighbors: one is while evolving the pattern, and one while sorting the evolved pattern by number of UNK neighbors.

Everything appears to stem from the use of lists of (row,column) pairs, and the use of a lot of branches for operations on them. I don't see any immediately obvious solution, though I suspect that arrays of flags to mark what has changed each gen would be more efficient. It looks like it would require a decent amount of modifications.

Post Reply