Re: recursive algorithms and stack overflow

[Marc Nieper-Wißkirchen]

Am Mi., 26. Aug. 2020 um 12:13 Uhr schrieb Bruno Haible <bruno@clisp.org>:

> [CCing bug-gnulib and Marc Nieper-Wißkirchen.]
>
> Paul Eggert wrote in <https://bugs.gnu.org/42931>:
> > Bug#42931 prompted me to change the way
> > that the Gnulib diffseq module recurses so that the stack size is O(log N)
> > rather than O(N). I installed this change into Gnulib, here:
> >
> > https://git.savannah.gnu.org/cgit/gnulib.git/commit/?id=7aadb23803a8fb71d07e6e87ffb1ca510d86f8ef
>
> Similarly, there was a bug report against libcroco [1] recently, because
> libcroco's CSS matching is recursive and can thus trigger stack overflow.
>
> It seems this is something to watch out, when we have recursive algorithms
> (which is quite frequent). Data sizes of 100 MB (or even just 100 KB) are
> considered "small" by today's computation means; if they can trigger stack
> overflow, users are unhappy.

I agree with all the points made. (And that's why a language with
proper tail calls like Scheme is so convenient.)

> Possible mitigations are:
>   - Use iteration instead of recursion when possible - like here in diffseq.h,
>   - Use iteration with a simulated heap-allocated stack - it would be useful
>     to have the stack module in Gnulib for this (Marc?),

I am sorry for my silence. I haven't forgotten about this project. I
will submit a patch hopefully soon.

Marc