Something else again. apgmera's currently got a problem where it crashes with a stack overflow when running on certain rules. I first noticed this on March 13 during alpha-testing, running version 3.04 on B3678/S35678 using seed m_W8v7RkVS4Gg4.
Calcyman investigated, and identified the offending soup, #947595:
Code: Select all
x = 16, y = 16, rule = B3678/S35678
ooboobbobbbbobbb$
oooooboboobboobb$
ooobooobbbboobbb$
bbbboobobbboooob$
ooooooobbboobbbo$
oooobooobboobbbb$
oobbboobooboobbb$
bbbobboobobobobb$
ooobboooboooobob$
boooobobobooobbb$
bboobbbbbobooobb$
bbobooobobbbbbbo$
oobboobbbbbbobbo$
ooobooooooobbobb$
bbobbboboboobobo$
boobbbbbbobbbobb!
As well as the exact location where everything goes kaboom:
Code: Select all
(gdb) bt full
#0 0x00000000004138d8 in SoupSearcher::separate (this=0x7ffde841e920, universe=0x7ffde841e700, proceedNonetheless=false,
curralgo=0x7868f0, suffix=...) at main.cpp:1278
j = 0
coords = 0x7ffde78a1200
i = 0
intList = {<std::_Vector_base<int, std::allocator<int> >> = {
_M_impl = {<std::allocator<int>> = {<__gnu_cxx::new_allocator<int>> = {<No data fields>}, <No data fields>},
_M_start = 0x7f1ebca72010, _M_finish = 0x7f1ebdbaee10, _M_end_of_storage = 0x7f1ebea72010}}, <No data fields>}
population = 1505635
ll = 4518783
gliderstatus = 0
annoyance = 0
x = 21
y = 0
sqt = 0xfddf78
nGliders = 0
nBeehives = 0
He said:
Calcyman wrote:
That is to say, it's currently trying to process an object with a population of 1505635, namely that huge growth pattern.
It strikes me that the segfault is caused by attempting to declare the (local, therefore on the stack!) array coords with a size of over 12 megabytes. Replacing this with a std::vector<int> seems to circumvent the segfault, but the program subsequently takes forever trying to run this enormous object for thousands of generations in QuickLife.
These stack overflows have occasionally reared their head since then in various rules, including the higher symmetries of Day & Night. With some rules they're not a big deal; with others they occurs so frequently that soup-searching those rules is all but impossible.
I got bitten by this (or at least SOME stack overflow) again today after (foolishly, perhaps) deciding to poke at B368/S12578. Dave Eppstein mentions this rule in "Growth and Decay in Life-like cellular automata", saying:
David Eppstein wrote:
B368/S12578 like HighLife supports a simple replicator, in the form of a 1 × 5 block of cells; it copies itself every 13 time steps. This replicator may be used to form oscillators of arbitrarily high periods; combinations of these oscillators can form guns for a small c/8 diagonal spaceship supported by this rule. As with HighLife, it seems likely that push-pull reactions can be used to form spaceships with arbitrarily slow speeds. However, with random initial conditions, this rule forms regions of chaotic activity interspersed with other regions of small oscillators and still lifes (Fig. 6.10), indicating a mixture of Class II and Class III behavior.
(That spaceship is
glider 1297.)
The rule is extremely slow to search in apgmera, thanks to replicators and PATHOLOGICALs, and the stack overflow eventually happened after about 10 hours and 328 soups, and ~43000 objects. (Not to mention about a million lines of debug output.
) The seed used was m_f8A3KfGPE84g.
For the benefit of anyone wanting to investigate similar rules in the future, here's a pack I used to a) produce said debug output and b) submit results after 250,000 objects had been censused (that bit's entirely untested, and knowing me therefore will likely not actually work). Note that this applies on top of 3.28-ab7.
Code: Select all
diff -Nru playingaround-cffe/main.cpp b368s12578-cffe/main.cpp
--- playingaround-cffe/main.cpp 2016-07-12 01:19:12.067791100 +0200
+++ b368s12578-cffe/main.cpp 2016-07-13 17:30:01.429069400 +0200
@@ -32,6 +32,7 @@
#define EXIT_USERQUIT 1
#define EXIT_HAULSDONE 2
#define EXIT_TIMESUP 3
+#define EXIT_OBJECTSDONE 4
clock_t programStartupTime;
int quietLevel = 0;
@@ -226,14 +227,19 @@
std::vector<std::pair<double, double> > pairlist;
std::vector<std::pair<double, double> > pairlist2;
double cumpop = 1.0;
+
+ std::cout << "powerlyse(): entering, stepsize = " << stepsize << ", numsteps = " << numsteps << ", startgen = " << startgen << std::endl;
for (int i = 0; i < numsteps; i++) {
+ if(!(i % 100)) {
+ std::cout << "powerlyse(): step = " << i << ", population = " << curralgo->getPopulation().toint() << "..." << std::endl;
+ }
runPattern(curralgo, stepsize);
cumpop += curralgo->getPopulation().toint();
pairlist.push_back(std::make_pair(std::log(i*stepsize+startgen), std::log(cumpop)));
pairlist2.push_back(std::make_pair(std::log(i+1), std::log(cumpop)));
}
-
+
double power = regress(pairlist);
double power2 = regress(pairlist2);
@@ -248,6 +254,8 @@
} else {
return "zz_QUADRATIC";
}
+
+ std::cout << "powerlyse(): finished." << std::endl;
}
@@ -585,7 +593,11 @@
*/
int stabilise3(vlife* curralgo) {
+ std::cout << "stabilise3(): entering" << std::endl;
+
int pp = naivestab_awesome(curralgo);
+
+ std::cout << "stabilise3(): naivestab_awesome returned " << pp << std::endl;
if (pp > 0) {
return pp;
@@ -598,7 +610,12 @@
int generation = 0;
+ std::cout << "stabilise3(): running for 4000 steps..." << std::endl;
+
for (int j = 0; j < 4000; j++) {
+
+ if(!(j % 100))
+ std::cout << "stabilise3(): step = " << j << ", population = " << curralgo->totalPopulation() << std::endl;
runPattern(curralgo, 30);
generation += 30;
@@ -644,8 +661,12 @@
}
std::cout << "Failed to detect periodic behaviour!" << std::endl;
+
+ std::cout << "stabilise3(): running pattern for 65536 steps..." << std::endl;
runPattern(curralgo, 65536);
+
+ std::cout << "stabilise3(): ...done." << std::endl;
return 1280;
@@ -663,14 +684,15 @@
int period = -1;
int xdisplacement = 0;
int ydisplacement = 0;
-
+
+ std::cout << "getRepresentation(): maxperiod = " << maxperiod << std::endl;
+
if (getBoundingBox(curralgo, bbOrig)) {
uint64_t hash1 = hash_rectangle(curralgo, bbOrig[0], bbOrig[1], bbOrig[2], bbOrig[3]);
int pop1 = curralgo->getPopulation().toint();
for (int i = 1; i <= maxperiod; i++) {
-
runPattern(curralgo, 1);
int boundingBox[4];
@@ -695,11 +717,16 @@
if (period <= 0) {
// std::cout << "Object is aperiodic (population = " << initpop << ")." << std::endl;
+ std::cout << "getRepresentation(): aperiodic object, calling linearlyse()..." << std::endl;
repr = linearlyse(curralgo, 4100);
+ std::cout << "getRepresentation(): ...done." << std::endl;
if (repr[0] != 'y') {
+ std::cout << "getRepresentation(): not a yl pattern, calling powerlyse()..." << std::endl;
repr = powerlyse(curralgo, 32, 8000, 5380);
+ std::cout << "getRepresentation(): ...done." << std::endl;
}
} else {
+ std::cout << "getRepresentation(): detected period = " << period << std::endl;
// std::cout << "Object has period " << period << "." << std::endl;
std::ostringstream ss;
std::string barecode = canonise(curralgo, period);
@@ -731,6 +758,8 @@
bounds[0] = period;
bounds[1] = xdisplacement;
bounds[2] = ydisplacement;
+
+ std::cout << "getRepresentation(): finished, repr = " << repr << std::endl;
return repr;
@@ -1116,6 +1145,8 @@
int top = celllist[1];
int right = celllist[0];
int bottom = celllist[1];
+
+ std::cout << "classify(): entering, population = " << population << std::endl;
for (int i = 0; i < ll; i += 2) {
if (left > celllist[i])
@@ -1165,8 +1196,13 @@
curralgo->endofpattern();
int bounds[3];
+
+ std::cout << "classify(): calling getRepresentation()..." << std::endl;
+
// repr = getRepresentation(curralgo, 4000, bounds);
repr = getRepresentation(curralgo, 1280, bounds);
+
+ std::cout << "classify(): ...done." << std::endl;
if (repr.compare("PATHOLOGICAL") == 0) {
// std::cout << "Pathological object at " << left << ", " << top << ", " << right << ", " << bottom << std::endl;
@@ -1179,17 +1215,25 @@
// Periodic object:
if (bounds[1] == 0 && bounds[2] == 0) {
// Still-life or oscillator:
+ std::cout << "classify(): calling pseudoBangBang() on still life or oscillator..." << std::endl;
elements = pseudoBangBang(curralgo, bounds[0], false);
+ std::cout << "classify(): ...done." << std::endl;
} else {
// Spaceship:
if (bounds[0] <= 8) {
#ifdef GLIDERS_EXIST
- if (bounds[0] == 4)
+ if (bounds[0] == 4) {
+ std::cout << "classify(): calling sss()..." << std::endl;
elements = sss(curralgo);
+ std::cout << "classify(): ...done." << std::endl;
+ }
#endif
- if (elements.size() == 0)
+ if (elements.size() == 0) {
+ std::cout << "classify(): calling pseudoBangBang() on spaceship..." << std::endl;
elements = pseudoBangBang(curralgo, bounds[0], true);
+ std::cout << "classify(): ...done." << std::endl;
+ }
} else {
elements.push_back(repr);
}
@@ -1228,6 +1272,8 @@
uint64_t cachearray[I_HEIGHT];
uint64_t emptymatrix[I_HEIGHT];
+
+ std::cout << "separate(): entering, proceedNonetheless = " << proceedNonetheless << ", suffix = " << suffix << std::endl;
memset(emptymatrix,0, I_HEIGHT * sizeof(uint64_t));
@@ -1236,10 +1282,16 @@
std::vector<std::string> objlist;
std::vector<int> gcoordlist;
std::vector<Incube*> gpointerlist;
+
+ std::cout << "separate(): iterating over tiles..." << std::endl;
+ std::cout << "separate(): number of tiles = " << std::distance(universe->tiles.begin(), universe->tiles.end()) << std::endl;
std::map<std::pair<int, int>, Incube>::iterator it;
for (it = universe->tiles.begin(); it != universe->tiles.end(); it++)
{
+
+ std::cout << "separate(): tiles left = " << std::distance(it, universe->tiles.end()) << std::endl;
+
memset(cachearray, 0, I_HEIGHT * sizeof(uint64_t));
// std::cout << "blah2" << std::endl;
@@ -1262,7 +1314,10 @@
gcoordlist.push_back(y);
gpointerlist.push_back(sqt);
} else if (gliderstatus == 0) {
+
+ std::cout << "separate(): calling universe->getComponent()..." << std::endl;
vector<int> intList = universe->getComponent(sqt,x,y);
+ std::cout << "separate(): ...done." << std::endl;
int population = intList.back();
int ll = intList.size() - 1;
@@ -1290,7 +1345,9 @@
}
}
+ std::cout << "separate(): calling classify..." << std::endl;
pathologicals += classify(coords, population, objlist, curralgo);
+ std::cout << "separate(): ...done." << std::endl;
#ifdef STANDARD_LIFE
}
#endif
@@ -1311,8 +1368,12 @@
}
}
}
+
+ std::cout << "separate(): ...done." << std::endl;
int gl = gpointerlist.size();
+
+ std::cout << "separate(): checking for gliders..." << std::endl;
for (int i = 0; i < gl; i++) {
int x = gcoordlist[2*i];
@@ -1326,6 +1387,8 @@
}
}
}
+
+ std::cout << "separate(): ...done." << std::endl;
bool ignorePathologicals = false;
@@ -1416,13 +1479,15 @@
#endif
}
}
+
+ std::cout << "separate(): finished." << std::endl;
return false;
}
void censusSoup(std::string seedroot, std::string suffix, lifealgo* curralgo) {
-
+
vlife btq;
btq.tilesProcessed = 0;
@@ -1430,14 +1495,19 @@
hashsoup(imp, seedroot + suffix, SYMMETRY);
+ std::cout << "censusSoup(): entering, seedroot = " << seedroot << ", suffix = " << suffix << std::endl;
+ std::cout << "censusSoup(): attempting to stabilize..." << std::endl;
int duration = stabilise3(imp);
+ std::cout << "censusSoup(): stabilise3 finished, duration = " << duration << std::endl;
bool failure = true;
int attempt = 0;
// Repeat until there are no pathological objects, or until five attempts have elapsed:
while (failure) {
-
+
+ std::cout << "censusSoup(): attempt " << attempt << std::endl;
+
failure = false;
if (imp->totalPopulation()) {
@@ -1445,26 +1515,38 @@
// Convert to LifeHistory:
vlife universe;
copycells(imp, &universe, true);
-
+
+ std::cout << "censusSoup() running in LifeHistory..." << std::endl;
+
for (int j = 0; j < duration/2; j++) {
universe.run2gens(true);
}
-
+
+ std::cout << "censusSoup(): ...done." << std::endl;
+
incubator icb;
copycells(&universe, &icb);
-
+
+ std::cout << "censusSoup(): attempting to separate..." << std::endl;
// failure = separate(&universe, (attempt >= 5), curralgo, suffix);
failure = separate(&icb, (attempt >= 5), curralgo, suffix);
+ std::cout << "censusSoup(): separate finished, failure = " << failure << std::endl;
}
// Pathological object detected:
if (failure) {
+ std::cout << "censusSoup(): detected pathological object!" << std::endl;
attempt += 1;
+ std::cout << "censusSoup(): running pattern for 10000 generations..." << std::endl;
runPattern(imp, 10000);
+ std::cout << "censusSoup(): ...done." << std::endl;
duration = 4000;
}
}
+
+ std::cout << "censusSoup(): finished." << std::endl;
+
}
@@ -1797,6 +1879,15 @@
if(seconds)
if(((double) (curr_clock - programStartupTime) / CLOCKS_PER_SEC) > seconds)
quit = EXIT_TIMESUP;
+
+
+ long long totobjs = 0;
+ std::vector<std::pair<long long, std::string> > censusList = soup.getSortedList(totobjs);
+
+ std::cout << "Objects censused so far: " << totobjs << std::endl;
+
+ if(totobjs > 250000)
+ quit = EXIT_OBJECTSDONE;
}
if ((i % n == 0) || quit) {
Here's the stackdump (note that Cygwin doesn't produce proper coredumps):
Code: Select all
Exception: STATUS_STACK_OVERFLOW at rip=00100429736
rax=00000000000039F0 rbx=000000000003EF3D rcx=00000000FFE030D0
rdx=000006FF710A0010 rsi=000000060207D598 rdi=00000000FFFF80D0
r8 =00000000FFFF807C r9 =00000001801523B0 r10=0000000100000000
r11=00000003FDE1F852 r12=000000060207D598 r13=0000000000000004
r14=0000000000000030 r15=0000000000000062
rbp=00000000FFFF8150 rsp=00000000FFFF80B8
program=C:\cygwin64\home\User\devel\apgmera\b368s12578-cffe\apgmera.exe, pid 6700, thread unknown (0x104C)
cs=0033 ds=002B es=002B fs=0053 gs=002B ss=002B
Stack trace:
Frame Function Args
000FFFF8150 00100429736 (0010042D4BA, 000FFFF80E0, 00601EE9470, 00200000000)
000FFFF8150 000001F79F0 (000FFFF80E0, 00601EE9470, 00200000000, 00100000001)
000FFFF8150 00000688560 (00601EE9470, 00200000000, 00100000001, 00000000002)
000FFFF8150 0010042D4BA (000FFFFC500, 003FDE88720, 0060003B060, 000FFFFC4E0)
000000007D0 0010042A9BA (0018031D1B8, 000FFFFC6F0, 0060003B060, 000FFFFC740)
000FFFFC700 0010040C41E (000FFFFCB00, 000FFFFCB10, 00100000001, 00100000001)
003FDE7BBE0 0010043C592 (000FFFFCC00, 0018034A930, 00180068491, 0000000002F)
000FFFFCCC0 00180047BD2 (00000000000, 00000000000, 00000000000, 00000000000)
00000000000 0018004591C (00000000000, 00000000000, 00000000000, 00000000000)
000FFFFFFF0 001800459B4 (00000000000, 00000000000, 00000000000, 00000000000)
End of stack trace
I don't know if it's the same stack overflow, but -- TL;DR, would be great to see these fixed.
We could remove the upload functionality and send the results with Python in the next release to make it cross-platform, I think...