Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: David Brown <david.brown@hesbynett.no>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Sun, 17 Mar 2024 17:45:16 +0100
Organization: A noiseless patient Spider
Lines: 111
Message-ID: <ut76ms$3kal7$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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 17 Mar 2024 16:45:16 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="212cee952392c1402e125e2adac79188";
	logging-data="3812007"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18/TZGy73Q91SbKGHzses/1zdjj0ArDe0M="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:xEsj8UwHJ/nY7Xr3hSObJDwCClo=
In-Reply-To: <ut4cnc$2ut2t$1@dont-email.me>
Content-Language: en-GB
Bytes: 5727

On 16/03/2024 16:09, Malcolm McLean wrote:
> On 16/03/2024 14:40, David Brown wrote:
>> On 16/03/2024 12:33, Malcolm McLean wrote:
>>
>>> And here's some code I wrote a while ago. Use that as a pattern. But 
>>> not sure how well it works. Haven't used it for a long time.
>>>
>>> https://github.com/MalcolmMcLean/binaryimagelibrary/blob/master/drawbinary.c
>>>
>>
>> Your implementation is a mess, /vastly/ more difficult to prove 
>> correct than the OP's original one, and unlikely to be very much 
>> faster (it will certainly scale in the same way in both time and 
>> memory usage).
>>
> Now is this David Brown being David Borwn, ot its it actaully ture?

I don't know who "David Borwn" might be, nor what "ture" means.  If you 
can't type, and can't spell, then at least pay the group the respect of 
using a spell-checker.

> It's not designed to be eay to prove correct, that's true. And the 
> maintain it's mess is that we are managing the queue manually for speed.

It is badly designed code.  It is a jumble of wildly different concepts, 
thrown together in one huge function with no structure or organisation, 
and with meaningless names for the variables and absurd names for the 
parameters.

The OP's code is simple and obvious, as is its correctness (assuming 
reasonable definitions of the pixel access and setting functions) and 
its time and space requirements.  Yours is not.

Your algorithm could be used in a proper implementation, with separate 
functions to handle the different parts (such as the stack).  The 
algorithm itself is not bad, it's the implementation that is the main 
problem.

> 
> But the naive recursive algorithm is O(N) (N = pixels to flood), and 
> inherently we can't beat that without special hardware. 

Assuming you are measuring the number of pixels read or written here, 
then that is, I think, correct.

> The recursive 
> one tends to be slow because calls are expensive. 

Yes, I agree that recursion can be slow (unless it is simple enough for 
the compiler to turn it into a loop).  And it typically takes more stack 
space than you'd need for a dedicated queue.  But whether or not that 
makes a significant difference depends on the code in question, and how 
much work you are doing within the code.  If step of the algorithm takes 
a lot of time anyway, the call overhead will be of less relevance.

I would expect that your code would be several times faster than the 
OP's, with similar scaling.  But the OP's is understandable and easily 
seen to be correct, unlike yours, and correctness trumps speed every time.

And starting from a correct recursive version, it's possible to improve 
on it in many ways while retaining correctness.

> And mine makes calls 
> to malloc() and realloc to manage the queue. And of course whilst we 
> might blow the stack, we are much less likely to run out of heap.

True.

> 
> And it's been tweaked abit in hacky way to make it faster on real 
> images. And whilst it's still going to work, is it out of date?
> 

I have no idea if your code is "out of date" or not.  It seems to be 
written for images consisting of unsigned chars, so I a not sure it was 
ever designed for real-world images.

What is clear is that you have taken an okay algorithm - not state of 
the art, but not the worst - and made a dog's breakfast of an 
implementation in your attempts to micro-optimise.  This means you have 
code that can't be easily analysed or seen to be correct, cannot be 
improved algorithmically, and cannot be expanded or gain new features 
without a massive re-write.

> And I need to run some tests, don't I?
> 

If you like.


>  >
>> There are a variety of different flood-fill algorithms, with different 
>> advantages and disadvantages.  Speeds will often depend as much on the 
>> way the get/set pixel code works, especially if the flood-fill is on 
>> live displayed data rather than in a buffer off-screen.  But typically 
>> you need to get a /lot/ more advanced (i.e., not your algorithm) to 
>> improve on the OP's version by an order of magnitude, so if speed is 
>> not essential but understanding that it is correct is important, then 
>> it makes more sense to stick to the original recursive version.
>>
> 
> What are these / lot / more advanced algorithms? Maybe they exist. But 
> don't people deserve some sort of link?
> 

<https://gprivate.com/6a2yp>

I don't know if it is fair to call them a /lot/ more advanced, but 
certainly a bit more advanced.  And certainly better implementations are 
possible.