Re: filling area by color atack safety

On 18/03/2024 17:42, Scott Lurndal wrote:

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

On 18/03/2024 16:28, David Brown wrote:

On 18/03/2024 10:26, Malcolm McLean wrote:
>
It is completely normal for correctness proofs to make assumptions about
things like resources.  An analysis of your code for correctness would
also generally assume that the heap would be big enough - if the heap
runs out, your code will not correctly flood-fill the image.  Analysis
of efficiency in time and space is a separate issue - related, but
separate.  Things like maximum recursion depth (and heap size) are very
implementation-specific, and thus need to be considered separately from
the algorithm itself.
>

>
It's trivial to engineer a system with a large stack and very small
heap. But unlikley anyone would actually do so on a system on which
floodfill would run.

 The first sentence is correct.  Although with modern systems, 'small'
is relative (my 12 year old workstation has 16GB RAM) and defaults
to an 8MB stack, which can easily be increased on a per process or
per user basis.
 The second is your opinion.   What evidence do you have that
your opinion is fact?

It seems the most likely. People don't run programs whose sole purpose is to floodfill, so that they can request a huge stack.
It will likely be part of a much larger application with conventional stack usage.
The floodfill may be part of a library, and itself wrapped by another library that the application knows about.
It is even possible that when the application is built, it doesn't know that a floodfill routine is to be called. (For example, an interpreter that will run a program that /might/ call a floodfill routine.)
As the author of such a routine, you don't want to have to rely on a stack large enough to cope with, say, a 30Mpix image which might need a 30M-deep maximum call-depth, which could easily use up 500MB of memory. stack.