Path: ...!news.mixmin.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: Wed, 20 Mar 2024 10:01:10 -0700
Organization: A noiseless patient Spider
Lines: 125
Message-ID: <86zfusltwp.fsf@linuxsc.com>
References: <ut3669$21eur$1@i2pn2.org> <86h6h3nvyz.fsf@linuxsc.com> <865xxiok09.fsf@linuxsc.com> <20240319131842.00002138@yahoo.com> <86o7b9ms7d.fsf@linuxsc.com> <20240320115416.00001ab5@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: dont-email.me; posting-host="7a780175fd21d30328a8a78d1217a04c";
	logging-data="1691175"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18HN6izNvnBJAm7RtylDoGC/Dg6Ms0SoOI="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:zPy4KAYvWysBif8+x2C+DY+xNAo=
	sha1:jK4OmUc0hm36MqKi5jhv1tnvUJk=
Bytes: 5867

Michael S <already5chosen@yahoo.com> writes:

> On Tue, 19 Mar 2024 21:40:22 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:
>>
>>> On Mon, 18 Mar 2024 22:42:14 -0700
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>>
>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>>
>>>> [...]
>>>>
>>>> Here is the refinement that uses a resizing rather than
>>>> fixed-size buffer.
>>>> [code]
>>>
>>> This variant is significantly slower than Malcolm's.
>>> 2x slower for solid rectangle, 6x slower for snake shape.
>>
>> Slower with some shapes, faster in others.
>
> In my small test suit I found no cases where this specific code is
> measurably faster than code of Malcolm.

My test cases include pixel fields of 32k by 32k, with for
example filling the entire field starting at the center point.
Kind of a stress test but it turned up some interesting results.

> I did find one case in which they are approximately equal.  I call
> it "slalom shape" and it's more or less designed to be the worst
> case for algorithms that are trying to speed themselves by take
> advantage of straight lines.
> The slalom shape is generated by following code:
> [code]

Thanks, I may try that.

>> In any case
>> the code was written for clarity of presentation, with
>> no attention paid to low-level performance.
>
> Yes, your code is easy to understand.  Could have been easier
> still if persistent indices had more meaningful names.

I have a different view on that question.  However I take your
point.

> In other post I showed optimized variant of your algorithm:  -
> 4-neighbors loop unrolled.  Majority of the speed up come not from
> unrolling itself, but from specialization of in-rectangle check
> enabled by unroll.
>  - Todo queue implemented as circular buffer.
>  - Initial size of queue increased.
> This optimized variant is more competitive with 'line-grabby'
> algorithms in filling solid shapes and faster than them in
> 'slalom' case.

Yes, unrolling is an obvious improvement.  I deliberately chose a
simple (and non-optimized) method to make it easier to see how it
works.  Simple optimizations are left as an exercise for the
reader. :)

> Generally, I like your algorithm.
> It was surprising for me that queue can work better than stack, my
> intuition suggested otherwise, but facts are facts.

Using a stack is like a depth-first search, and a queue is like a
breadth-first search.  For a pixel field of size N x N, doing a
depth-first search can lead to memory usage of order N**2,
whereas a breadth-first search has a "frontier" at most O(N).
Another way to think of it is that breadth-first gets rid of
visited nodes as fast as it can, but depth-first keeps them
around for a long time when everything is reachable from anywhere
(as will be the case in large simple reasons).

>>> Besides, I don't think that use of VLA in library code is a good
>>> idea.  VLA is optional in latest C standards.  And incompatible
>>> with C++.
>>
>> The code uses a variably modified type, not a variable length
>> array.
>
> I am not sufficiently versed in C Standard terminology to see a
> difference.
> Aren't they both introduced in C99 and made optional in later
> standards?

Ben explained the difference.  I posted a short followup to his
explanation.  And yes, as of C11 VLAs and VMTs are both optional
(it would be nice if a new C standard put back the requirement
of variably modified types).

>> Again, the choice is for clarity of presentation.  If
>> someone wants to get rid of the variably modified types, it's
>> very easy to do, literally a five minute task.
>
> Yes, that's what it took for me.
> But I knew that variably modified types exist, even if I didn't know
> that they are called such.
> OTOH, many (majority?) of C programmers never heard about them.

Something that surprised me is that some C programmers don't
know what compound literals are, even though they have been
around more than 20 years.  I'm not inclined to try to cater
to people who program in C but aren't at least aware of what
was done more than 20 years ago.

>> Anyway the interface is poorly designed to start with, [...]
>
> That's true.  [...]

Yes!  Hoo rah!

>> If someone wants to use the functionality from C++, it's
>> easy enough to write a C wrapper function to do that.
>> IMO C++ has diverged sufficiently from C so that there
>> is little to be gained by trying to make code interoperable
>> between the two languages.
>
> From the practical perspective, the biggest obstacle is that your
> code can't be compiled with popular Microsoft compilers.

Some people might consider that a plus rather than a minus. ;)