Re: recursive algorithms and stack overflow

Re: recursive algorithms and stack overflow

[Bruno Haible]

[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.

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?),
  - Use a recursion depth counter in some context struct, and check it at
    every recursion.

Do we have a list of the Gnulib modules that use recursion? [2]?

Bruno

[1] https://gitlab.gnome.org/Archive/libcroco/-/issues/8
[2] https://stackoverflow.com/questions/45194527/how-to-get-a-warning-for-using-recursion

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