Re: fdo 37341 MAXRECURSION reached in ScFormulaCell::Interpret
Hi Winfried,
On Wednesday, 2013-07-24 11:34:27 +0200, Winfried Donkers wrote:
I set MAXRECURSION to 4, made a simple spreadsheet (A2:=A1+1, A3:=A2=1, etc.)
and started 'Goal Seeking'.
With the target at A5 and the variable cell at A1, the recursion count
reached 4 every time Interpret() was called from BackSolver(); BackSolver()
was called once and a valid solution was found (as expected).
With the target at A6 and the variable cell at A1, the recursion count
reached 5 every time Interpret() was called from BackSolver(); Interpret()
was called a zillion times and I aborted the application (more or less as
expected).
I changed a littel bit in the code of ScFormulaCell::Interpret():
if (rRecursionHelper.GetRecursionCount() MAXRECURSION)
{
bRunning = true;
rRecursionHelper.SetInRecursionReturn( true);
return; //line added for testing
}
I changed this so that Interpret does not continue its recursive work, as it
seems to do.
With the target at A6 and the variable cell at A1, the recursion count
reached 5, Interpret() was called once from BackSolver(); BackSolver() was
called twice; Goal Seek reported a failure (circular reference), but (better
than expected).
Inserting a return at that place of course eliminates the entire
recursion/circular handling.
To me, it _seems_ as if reaching the maximum recusrion count is not handled
correctly in ScFormulaCell::Interpret().
Before I start digging in the wrong direction and messing up things that I
shouldn't touch I would very much like your expert opinion ;-)
The recursion itself is handled correctly, the added problem here is
1) we also have a circular dependency (which standalone combined with
recursion should be handled gracefully)
2) the goal seek is triggered by ScDocument::Solver() creating an
ScFormulaCell and start Interpret() on it, in
ScInterpreter::ScBackSolver() the goal seek's defined formula cell is
set dirty over and over again until the confifuration's limit is
reached
The zillion times Interpret() was called probably were from
ScBackSolver() and if each results in a recursion with circular
references the calls to Interpret() multiply.
I'd investigate first why the loop in ScInterpreter::ScBackSolver()
isn't terminated, i.e. why changing the start value does not alter the
result. If it is correct that it doesn't change anymore than
ScBackSolver() will have to detect that.
If the culprit seems to be within ScFormulaCell::Interpret() then, well,
... I can't say much else would help than stepping through these calls
and keeping track of what called which in what state. The old code had
some debugging/tracing facilities that generated a .dot file from within
ScFormulaCell::Interpret() but unfortunately got completely removed with
5ff49e8ce958deb8217880b2aaf2bd41a567e8a1 (these are the cases where
I don't understand blind removal of #ifdef'ed code) so for testing
purposes you might want to revive the part of
sc/source/core/data/cell.cxx of that change into
sc/source/core/data/formulacell.cxx
Note that that debug code was unmaintained for a long while even before
its removal and needs (probably heavy) adaption to the current code, but
it may be a starting point for how to generate a track of the call
chain.
Eike
--
LibreOffice Calc developer. Number formatter stricken i18n transpositionizer.
GPG key ID: 0x65632D3A - 2265 D7F3 A7B0 95CC 3918 630B 6A6C D5B7 6563 2D3A
For key transition see http://erack.de/key-transition-2013-01-10.txt.asc
Support the FSFE, care about Free Software! https://fsfe.org/support/?erack
pgp_CNXJbeXTk.pgp
Description: PGP signature
___
LibreOffice mailing list
LibreOffice@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/libreoffice
Re: fdo 37341 MAXRECURSION reached in ScFormulaCell::Interpret
Hi, On Thursday, 2013-07-11 23:05:40 -0400, Kohei Yoshida wrote: Actually, I'm just wondering why that code is even in ScInterpreter. The goalseek functionality is not a cell function, and I would expect a code like that to be outside of ScInterpreter. Dating back to prehistoric times it is a cell function, it is just not offered in the UI. Hell, it would even still be saved as GOALSEEK without ODFF namespace prefix, which I just prepared to change with 35a230af3f2e847983174cf65c567e04212791dc But yes, this unnecessarily complicates things. Eike -- LibreOffice Calc developer. Number formatter stricken i18n transpositionizer. GPG key ID: 0x65632D3A - 2265 D7F3 A7B0 95CC 3918 630B 6A6C D5B7 6563 2D3A For key transition see http://erack.de/key-transition-2013-01-10.txt.asc Support the FSFE, care about Free Software! https://fsfe.org/support/?erack pgpj4iJ2ppATD.pgp Description: PGP signature ___ LibreOffice mailing list LibreOffice@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/libreoffice
fdo 37341 MAXRECURSION reached in ScFormulaCell::Interpret
Hi, Presently I'm looking at bug fdo 37341, which reports calc to hang when Goal Seek (sc/source/core/tool/interpr2.cxx, ScInterpreter::ScBackSolver()) is used. The cause of the problem is not that too many iterations are needed, but that MAXRECURSION in sc/source/core/data/formulacell.cxx, ScFormulaCell::Interpret() is reached. Increasing MAXRECURSION 'solves' the problem. I think increasing MAXRECURSION from its present value (400) to 800 is no problem. 10 years ago its value was 500 and in the past 1 years the available memory has been more than doubled. But that does not really solve the problem, it only shifts the point where the problem will show. Shouldn't a global error (or at least warning) be generated when MAXRECURSION is reached? After all, the result of ScFormulaCell::Interpret() is not correct in that case. Unfortunately, I can't quite grasp the recursion/interation process in ScFormulaCell::Interpret(), so I can't generate the appropiate error. Do you have any suggestions about how to properly solve this? To me just increasing MAXRECURSION to 800 is a dirty hack. Winfried ___ LibreOffice mailing list LibreOffice@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/libreoffice
Re: fdo 37341 MAXRECURSION reached in ScFormulaCell::Interpret
Hi Winfried, On Thursday, 2013-07-11 08:02:13 +0200, Winfried Donkers wrote: Presently I'm looking at bug fdo 37341, which reports calc to hang when Goal Seek (sc/source/core/tool/interpr2.cxx, ScInterpreter::ScBackSolver()) is used. The cause of the problem is not that too many iterations are needed, but that MAXRECURSION in sc/source/core/data/formulacell.cxx, ScFormulaCell::Interpret() is reached. Increasing MAXRECURSION 'solves' the problem. It may cure the symptom in this specific case, but does not solve the problem. I think increasing MAXRECURSION from its present value (400) to 800 is no problem. 10 years ago its value was 500 and in the past 1 years the available memory has been more than doubled. You're misreading history ;-) The past value can't be compared as the entire mechanism how recursions are handled has changed. The previous 500 was that if there were more than 500 recursions the entire calculation chain set an error at the formula cells involved. The new mechanism first attempts a recursion up to MAXRECURSION and if it reaches the limit it unwinds the stack, remembers formula cells involved and continues from the point it left to find the end of the recursion and start calculation from that side. Increasing MAXRECURSION would set the threshhold higher at the cost that if it is reached more time would be wasted in calculating the recursion before detecting that threshhold. Shouldn't a global error (or at least warning) be generated when MAXRECURSION is reached? After all, the result of ScFormulaCell::Interpret() is not correct in that case. I presume it is the combination of BackSolver iteration and recursion. Setting an error if MAXRECURSION is reached is not appropriate. Unfortunately, I can't quite grasp the recursion/interation process in ScFormulaCell::Interpret(), so I can't generate the appropiate error. That thing is a beast and time consuming to debug. To understand what it does it would help to set MAXRECURSION to 5 or so and have a few more simple recursing formula cells to step through. (A9:=A8 A8:=A7 ...) Setting up a simple BackSolver scenario that kicks in badly with the reduced limit might be equally challenging.. Eike -- LibreOffice Calc developer. Number formatter stricken i18n transpositionizer. GPG key ID: 0x65632D3A - 2265 D7F3 A7B0 95CC 3918 630B 6A6C D5B7 6563 2D3A For key transition see http://erack.de/key-transition-2013-01-10.txt.asc Support the FSFE, care about Free Software! https://fsfe.org/support/?erack pgpHoX9WjfuBw.pgp Description: PGP signature ___ LibreOffice mailing list LibreOffice@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/libreoffice
