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.
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:
dr Discussion Thread
dr Discussion Thread
-Matthias Merzenich
Re: dr Discussion Thread
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.
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.
Re: dr Discussion Thread
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.
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.
-
hotcrystal0
- Posts: 4337
- Joined: July 3rd, 2020, 5:32 pm
- Location: wherever you think I am
Re: dr Discussion Thread
does dr work in non-CGoL rules? I want to know if it can work in B3/S23-a5.
wherever I go on the internet I bring with myself nothing but problems.
Code: Select all
x = 192, y = 53, rule = B3/S23
33$42b4o$41b6o$40b2ob4o$41b2o3$41b2o$39bo6bo$38bo8bo$38bo8bo$38b9o3$42b
4o$41b6o$40b2ob4o$41b2o!Re: dr Discussion Thread
dr only works with Life-like CA. Hickerson did make a modification that works with Just Friends by modifying the nxgen() function as can be seen in the source code, but the modification is incomplete:hotcrystal0 wrote: ↑September 30th, 2025, 6:05 pmdoes dr work in non-CGoL rules? I want to know if it can work in B3/S23-a5.
Dean Hickerson wrote: I've partially modified the drifter searcher to handle the Just Friends
rule. It would be difficult to change the part that grows the stable
background so that it could handle nontotalistic rules, so I just changed
the part that evolves the drifter; the program uses B2/S12 for the
background rule. Anything that the program finds will work in Just
Friends, but there are probably interesting things that it can't find.
-Matthias Merzenich