Re: filling area by color atack safety

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. ;)