Repository navigation
Integrate recurses without bound and takes the process down, and it is a 2.5.0 regression #1232
Description
Activity
- added a commit that references this issue
on Sep 9, 2026 The crash is fixed, and the corpus run no longer dies. Two changes, both merged:
- #1233 bounds the descent, so a runaway declines instead of overflowing the stack.
- #1234 recognises a cycle at the first repeat, keyed on the integrand with its variable renamed to one canonical name — which is the whole trick, since
Variable.CreateUniquemakes each level alpha-equivalent to the last rather than equal to it.
A run now passes the point at which it previously aborted and carries on well past it. Full suite green on both changes: 8,499 and 1,485.
The bound alone was not enough, and that is worth recording
My first fix was the depth bound on its own. It stopped the process dying and left the run crawling, because this descent branches: 32 levels of a cycle is still an enormous search. Measured over Rubi's independent test suites, problems 1400–1450:
build those fifty v2.4.044 s depth bound alone 985 s with the cycle guard 37 s I also chose the bound badly at first — 64, picked on the reasoning that a bound only has to stop the overflow. Instrumenting the descent showed the deepest answered integral reaches 13 (
x^5*cosh(x)), with the next at 8 and 7 and everything else at 4 or less. 32 is what that measurement supports.What is left, which I have not fixed
The integrator is still much slower than
v2.4.0on some hard integrands, and it is not a cycle. After the guard, two more sections stall:problems v2.4.0now 1450–1500 52 s 810 s 1550–1600 48 s over 20 minutes, not waited out These are not cycles — the guard would catch those — so this is genuine exponential search, and the depth bound at 32 leaves a lot of room to branch in. Tightening it towards the measured maximum of 13 would cut the search, and the cost of doing that is answers: I have not established the deepest descent over the whole corpus, only over twenty-three integrands, so I have not tightened it on a guess.
The full corpus run therefore has not completed, and I am not claiming a coverage figure for 2.5.0. The last complete run is
v2.4.0's, taken today on the same machine with the same flags: 599 of 1774 solved, 0 wrong, 0 error, 58 timeout.So: the crash is gone, and the responsiveness regression against 2.4.0 is real, measured, and still open. Reopening or filing separately is your call — I have left this issue open rather than closing it on the half I fixed.
Reopening: #1233 carried
Fixes #1232and closed this on merge, but only the crash is fixed. The responsiveness regression measured in the comment above is still open, and a closing keyword cannot be qualified — that is my mistake in the PR body rather than a decision.Retracting the second half of my previous comment. There is no slowdown regression — I measured it wrong, and the opposite is true.
I claimed the integrator was much slower than
v2.4.0on hard integrands, on the strength ofintbenchsection wall-times: problems 1450–1500 taking 810 seconds against 52. That comparison is worthless, because I was running the full unit suite on the same machine at the same time as the corpus run. It inflated the very sections I then compared, and I noted the suite itself running 8m54s against its usual 5m44s without drawing the obvious conclusion.Measured properly instead — the seventeen hardest integrands from that part of the corpus, one process, no other load, two runs of each arm back to back:
run 1 run 2 v2.4.072,017 ms 71,390 ms 2.5.053,159 ms 47,996 ms 2.5.0 is about 30% faster, not slower. Per integrand, where it moves at all it moves the same way:
integrand v2.4.02.5.01/(x*(-4+x^2)^4)17,946 ms 8,472 ms 1/(-1+x^3)^27,072 ms 3,496 ms x^3/(-1+x)^125,286 ms 2,300 ms x^3/(1+x)^104,049 ms 1,422 ms x^2*sqrt(5-x^2)2,565 ms 676 ms 1/((2+x)^3*(3+x)^4)34,489 ms 33,861 ms The last row is the honest caveat: partial fractions over repeated factors with high powers is slow in both, around half a minute for that one. That is a real limitation and always was one. It is not a regression, and it is not what this issue is about.
I also tested the hypothesis I had formed before measuring — that the memo added in #1157 was being defeated by the same fresh-variable naming as the cycle, so subproblems were recomputed across substitution branches. Making the memo alpha-invariant (keyed on the integrand with its variable canonicalised, answer stored in those terms) is correct and does work, and it is worth 6%: 50,521 ms against 47,319 ms. That is not the cause of anything, so I have not opened a PR for it. Happy to if you want the 6%.
So this issue is fully fixed
The stack overflow was real, was a regression, and is fixed by #1233 and #1234. Nothing else here is. Closing it, and correcting the 2.5.0 release notes, which repeat the wrong claim.
Two things I got wrong on the way, recorded because they are the sort of thing that repeats: I picked the depth bound at 64 by reasoning rather than measuring and had to bring it to 32 after instrumenting it, and I compared timings taken under different machine load, which is the one comparison this project's own notes say never to make.
Integratecan recurse without bound and take the process down. A stack overflow is not an exception a caller can handle: the process aborts, and everything it had not finished is lost.Found by
work/intbenchagainst Rubi's Independent test suites at a 5-second budget. The run died withSIGABRT(exit 134) partway through, and the harness correctly refused to publish a report from it.It is a regression in 2.5.0
The same corpus, the same flags (
--families=0 --per-file=100000 --budget=5), on the same machine:v2.4.0(de7189b1)2.5.0(6a97c071)So this is not a long-standing limitation of a hard corpus. Something in the 108 commits between them removed whatever was bounding it.
The recursion
Thousands of frames, alternating two methods:
Why the memo does not stop it, which is the part worth writing down
ComputeIndefiniteIntegralhas a memo keyed on(expr, x, integrateByParts), added in #1157. It cannot fire on a cycle, and not only for the usual reason that the entry is written after the recursive call returns.SolveBySubstitutionnames its new variable withVariable.CreateUnique:So every level integrates with respect to a fresh variable. The key differs at every level even when the level is the same problem under a new name, so the memo sees a brand-new question each time. A set of already-visited shapes would fail for the same reason: the shapes are alpha-equivalent, not equal.
That is why the fix is a depth bound rather than a visited set. A depth bound does not care what the levels are called.
Not reachable from the generated shapes
work/crashcheckruns 1,890 cases, each in a child process, and reports 0 crashes, 0 hangs and 0 unexpected exceptions on the same commit. It takes a genuinely hard integrand, which bounds who hits this — worth saying so the severity is not overstated.One hypothesis died on the way: I suspected the new fractional-power substitution and probed
e^(x^(1/3)),1/(4+x+sqrt(1+x))andx^3/(1+x)^10. All three return.The fix
A bound on the descent, and a refusal when it is reached. Declining is a legitimate answer here and a wrong one is not: an unevaluated
integral(...)says "I could not settle this", which is true, where an aborted process says nothing at all.One detail that is easy to get wrong: a
nullproduced by running out of descent must not be written into the memo, because the same key reached from less deep may well be answerable. A non-null answer is safe to keep whatever happened elsewhere, since an antiderivative that was found is correct however deep the search that found it went.