Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: bart 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: References: 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: Bytes: 3328 On 18/03/2024 17:42, Scott Lurndal wrote: > Malcolm McLean 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.