Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Mon, 18 Mar 2024 11:36:29 -0700
Organization: A noiseless patient Spider
Lines: 42
Message-ID: <86le6fo09e.fsf@linuxsc.com>
References: <ut3669$21eur$1@i2pn2.org> <ut4020$2s8ov$1@dont-email.me> <ut4b09$2uhpm$1@dont-email.me> <ut4cnc$2ut2t$1@dont-email.me> <ut70b4$3itvb$1@dont-email.me> <20240317182520.00002390@yahoo.com> <20240317193908.00002634@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: dont-email.me; posting-host="392b353a6389bc0498ba35815d55dc9d";
	logging-data="348130"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+XS1zKQtHTWR07MRAT+JvlQPyUXItaywA="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:QSiqVDpktnbZ4pYG1hM8biCxmBo=
	sha1:6Fiphp/UKTKk5kp2E54cHairZ/c=
Bytes: 2680

Michael S <already5chosen@yahoo.com> writes:

> On Sun, 17 Mar 2024 18:25:20 +0200
> Michael S <already5chosen@yahoo.com> wrote:
>
>> On Sun, 17 Mar 2024 14:56:34 +0000
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:

>>> [a floodfill routine posted by Malcolm]

>> [...]
>>
>> [a recursive area fill written by Michael S]
>
> I did my own measurements with snake-like image from my first
> response to Malcolm.  For this shape, recursive version (after my
> improvement) is almost exactly 10 times slower than Malcolm's
> iterative code.  And suspect to stack overflow although a little
> less so than original.

It's hard to write a recursive area fill routine if one wants to
guarantee worst case behavior in all cases.  This problem is not
a good fit to using recursion without there being some kind of
constraints on what the inputs will be.

> Even if in Big Oh sense they are the same, it does look like
> Malcolm's variant is decisively faster in practice.

I've done some tests with Malcolm's code.  Some observations:

It uses more memory than it needs to.

It's anisotropic, which is to say it behaves differently with
respect to changes in width than it does to changes in height.

It doesn't scale well.  In particular worst case performance
scaling is worse than O(N) (as determined experimentally, not
theoretically).

The code is much longer than is needed just to do an area fill.
A small fraction of that is simply layout style, but mostly it's
that the code is more complicated than it needs to be.