Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: bart <bc@freeuk.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Mon, 18 Mar 2024 18:50:40 +0000
Organization: A noiseless patient Spider
Lines: 45
Message-ID: <uta2ds$aps7$1@dont-email.me>
References: <ut3669$21eur$1@i2pn2.org> <ut4020$2s8ov$1@dont-email.me>
 <ut4b09$2uhpm$1@dont-email.me> <ut4cnc$2ut2t$1@dont-email.me>
 <ut76ms$3kal7$1@dont-email.me> <ut7co3$3lmeo$1@dont-email.me>
 <ut8on5$200c$1@dont-email.me> <ut91bm$3m2q$1@dont-email.me>
 <ut9q3p$8qr8$1@dont-email.me> <ut9tev$9m8a$1@dont-email.me>
 <K1%JN.121223$6ePe.31709@fx42.iad>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 18 Mar 2024 18:50:36 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="9367eb6f87aec8cea9ed2e7f4c193479";
	logging-data="354183"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+e9CsUkMOACUt7yAmQFKJ4"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:oW9pi6H4iFnBY72BGuXLLSBB0bo=
Content-Language: en-GB
In-Reply-To: <K1%JN.121223$6ePe.31709@fx42.iad>
Bytes: 3328

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.