Re: Static analyzer run

["Karim Belabas" <Karim.Belabas@math.u-bordeaux1.fr>]

* Lorenz Minder [2009-09-14 10:07]:
> I've run PARI through a static source code analyzer to see if it finds
> any bugs (and to see if the tool is worth anything).
[...]
> * Flx_resultant():  variables still in use were garbage collected.
>   (In the old code, try replacing "if(++cnt == 100)" by "if(++cnt == 1)"
>   to see those problems.)

diff --git a/src/basemath/Flx.c b/src/basemath/Flx.c
--- a/src/basemath/Flx.c
+++ b/src/basemath/Flx.c
@@ -1280,7 +1280,7 @@

     if (both_odd(da,db)) res = p - res;
     if (lb != 1) res = Fl_mul(res, Fl_powu(lb, da - dc, p), p);
-    if (++cnt == 100) { cnt = 0; c = gerepileuptoleaf(av, c); }
+    if (++cnt == 100) { cnt = 0; gerepileall(av, 2, &a, &b); }
     da = db; /* = degpol(a) */
     db = dc; /* = degpol(b) */
   }
diff --git a/src/basemath/base1.c b/src/basemath/

A note on this one: the old code was actually "not completely incorrect"
since a,b are non-recursive objects of bounded size, a priori less
than 100 times the stack space used up in a the 2 loop iterations during
which they must survive. A simple avma = av would have been fine (and
better).

This technique of using for a very limited time an object that has just
been reclaimed by the garbage collector is not infrequent in our code,
and mandatorily flagged with a /* HACK */ comment. It saves a little
time by avoiding an actual gerepile.

The code becomes completely wrong if you replace 100 by a much smaller
number of course. Or if the Flx_rem implementation is replaced by
something needing much more stack space (Newton + FTT, say). So I agree
that in this case, the code should be fixed.


The true culprit is of course the stack/gerepile model here. We'd much rather
have the successive Flx_rem() store their result in pre-allocated storage
(whose size is easy to estimate; only the 2 last results need to be kept),
instead of endlessly adding to the stack then reclaiming garbage in
either hackish or inefficient way.

It's actually very simple to implement such an Flx_remz(a, b, z)
function (stores Flx_rem(a, b) in pre-allocated z), because in the case
where this would be difficult (Newton), the current code already calls a
gerepile, which could be replaced by a copy at not coѕe. >> TODO :-).

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`