On Sat, Jul 27, 2024 at 12:38:30AM +0200, Ralf Hemmecke wrote: > I have some big computation that fails after about 5 hours claiming that > there is not enough stack space. That FriCAS was compiled with > "--dynamic-space-size 23906". > > I tried to figure out where all that space was used and hit recip in > sttaylor.spad. In particular, the function iDiv looked suspicious to me. > > iDiv : (ST A, ST A, A) -> ST A > iDiv(x, rst_y, ry0) == delay > empty? x => empty() > c0 := frst x * ry0 > concat(c0, iDiv(rst x - c0*rst_y, rst_y, ry0)) > > In my understanding that means that for every new computed coefficient of > the result of recip(x), there are two new streams created, namely > "c0*rst_y" and "rst x - c0*rst_y". > > I might be wrong, but that looked to me like wasting memory, because the > initial segments of these streams are not needed anymore, once the > respective coefficient is computed, but I suspect(ed) that the memory is not > freed.
AFAICS this is essentially the same problem that we had with multiplication of power series (see doc/sttaylor.txt). Actual reasons, look more subtle. Unreferenced things are supposed to be garbage collected. Once 'iDiv' is done computing element number n in the answer it should not look at earlier elements. Basically after that there should be something like 2*n streams, but they should take O(n) space because nobody is supposed to look at earlier elements and streams should just reduce to functions which deliver rest of the stream. Computing element n + 1 should adance those 2*n streams by one step, effectively discarding intermediate results and only delivering the resulting coefficient. And of course, 2 more streams are created. At least when using sbcl empirical observation indicates that memory use increases quadratically. > Anyway, I suggest another implementation, that uses the inversion formula > directly, and only keeps a list of the computed coefficients in reverse > order for further computation. > > With that implementation, my lengthy computation finished successfully. > > The implementation can be found in my branch > "wip/improve-stream-division". > > https://github.com/hemmecke/fricas/tree/wip/improve-stream-division > (patch attached) > > I took care that the timings are basically the same. > See attached testfile. > > Is there a chance that this could make it into FriCAS? Yes, this looks reasonable. ATM main trouble I see are longish lines and differen code style. For example instread of restDiv(a: ST A, u: A, n: I, k: I, ra: ST A, b: ST A, revc: List A): ST A == delay ... I would write something like restDiv(a : ST A, u : A, n : I, k : I, ra : ST A, b : ST A, revc : List A) : ST A == delay ... It makes sense to run a bit more tests, I will do this and come back to this in a day ar two. -- Waldek Hebisch -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/fricas-devel/ZqUL1T6UrQRFawtg%40fricas.org.
