Am Mi., 26. Aug. 2020 um 12:13 Uhr schrieb Bruno Haible <br...@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