On Tue, 19 Mar 2024 21:43:33 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Michael S <already5chosen@yahoo.com> writes:
>
> > On Tue, 19 Mar 2024 11:57:53 +0000
> > Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
> >
> >> No. Mine takes horizontal scan lines and extends them, then places
> >> the pixels above and below in a queue to be considered as seeds for
> >> the next scan line. (It's not mine, but I don't know who invented
> >> it. It wasn't me.)
> >>
> >> Tim, now what does it do? Essentially it's the recursive fill
> >> algorithm but with the data only on the stack instead of the call
> >> and the data. And todo is actually a queue rather than a stack.
> >>
> >> Now why would it be slower? Probaby because you usually only hit a
> >> pixel three times with mine - once below, once above, and once for
> >> the scan line itself, while you consider it 5 times for Tim's -
> >> once for each neighbour and once for itself. Then horizontally
> >> adjacent pixels are more likely to be in the same cache line than
> >> vertically adjacent pixels, so processing images in scan lines
> >> tends to be a bit faster.
> >
> > Below is a variant of recursive algorithm that is approximately as
> > fast as your code (1.25x faster for filling solid rectangle, 1.43x
> > slower for filling snake shape).
> > The code is a bit long, but I hope that the logic is still obvious
> > and there is no need to prove correctness. [...]
>
> To me it looks like this recursive algorithm doesn't find all
> pixels that need coloring in some situations.

Yesterday night I had few doubts myself, but after further thinking
came to conclusion that it it works in all situations.

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.
> >>
> >>
> >> typedef unsigned char Color;
> >> typedef unsigned int UI;
> >> typedef struct { UI x, y; } Point;
> >> typedef unsigned int Index;
> >>
> >> static _Bool change_it( UI w, UI h, Color [w][h], Point, Color,
> >> Color );
> >>
> >> void
> >> fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old,
> >> Color new ){ static const Point deltas[4] = { {1,0}, {0,1},
> >> {-1,0}, {0,-1}, }; UI k = 0;
> >> UI n = 17;
> >> Point *todo = malloc( n * sizeof *todo );
> >>
> >> if( todo && change_it( w, h, pixels, p0, old, new ) )
> >> todo[k++] = p0;
> >>
> >> while( k > 0 ){
> >> Index j = n-k;
> >> memmove( todo + j, todo, k * sizeof *todo );
> >> k = 0;
> >>
> >> while( j < n ){
> >> Point p = todo[ j++ ];
> >> for( Index i = 0; i < 4; i++ ){
> >> Point q = { p.x + deltas[i].x, p.y + deltas[i].y };
> >> if( ! change_it( w, h, pixels, q, old, new ) )
> >> continue; todo[ k++ ] = q;
> >> }
> >>
> >> if( j-k < 3 ){
> >> Index new_n = n+n/4;
> >> Index new_j = new_n - (n-j);
> >> Point *t = realloc( todo, new_n * sizeof *t );
> >> if( !t ){ k = 0; break; }
> >> memmove( t + new_j, t + j, (n-j) * sizeof *t );
> >> todo = t, n = new_n, j = new_j;
> >> }
> >> }
> >> }
> >>
> >> free( todo );
> >> }
> >>
> >> _Bool
> >> change_it( UI w, UI h, Color pixels[w][h], Point p, Color old,
> >> Color new ){ if( p.x >= w || p.y >= h || pixels[p.x][p.y] !> >> old ) return 0; return pixels[p.x][p.y] = new, 1;
> >> }
> >
> > 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.
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:

static
void make_slalom(
unsigned char *image,
int width, int height,
unsigned char background_c,
unsigned char pen_c)
{ const int n_col = width/3;
const int n_row = (height-3)/4;

// top row
// P B B P P P
for (int col = 0; col < n_col; ++col) {
unsigned char c = (col & 1)==0 ? background_c : pen_c;
image[col*3] = pen_c; image[col*3+1] = c; image[col*3+2] = c;
}

// main image: consists of 3x4 blocks filled by following pattern
// P B B
// P P B
// B P B
// P P B
for (int row = 0; row < n_row; ++row) {
for (int col = 0; col < n_col; ++col) {
unsigned char* p = &image[(row*4+1)*width+col*3];
p[0] = pen_c; p[1] = background_c; p[2] = background_c;
p += width;
p[0] = pen_c; p[1] = pen_c; p[2] = background_c;
p += width;
p[0] = background_c; p[1] = pen_c; p[2] = background_c;
p += width;
p[0] = pen_c; p[1] = pen_c; p[2] = background_c;
}
}

// near-bottom rows
// P B B
for (int y = n_row*4+1; y < height-1; ++y) {
for (int col = 0; col < n_col; ++col) {
unsigned char* p = &image[y*width+col*3];
p[0] = pen_c; p[1] = background_c; p[2] = background_c;
}
}

// bottom row - all P
memset(&image[(height-1)*width], pen_c, width);

// rightmost columns
for (int x = n_col*3; x < width; ++x) {
for (int y = 0; y < height-1; ++y)
image[y*width+x] = background_c;
}
}

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

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.

> > Is it the same algorithm?
>
> Sorry, the same algorithm as what? The same as Malcolm's?

Yes, that what I meant.
Still didn't find guts to try to understand what Malcolm's code is
doing.

> Definitely not. The same as my other posting that does
> not do dynamic reallocation? Yes in the sense that if the
> allocated array is large enough to begin with then no
> reallocations are needed.
>

> > 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?

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

> Anyway the
> interface is poorly designed to start with, there are bigger
> problems than just whether a variably modified type is used.
> (I chose the interface I did to approximate the interface
> used in Malcolm's code.)
>

That's true.
The biggest problem of Malcolm's interface is that logical width of the
image is the same as physical width (a.k.a. line pitch, in LAPACK
it is called the first dimension). These parameters should be separate.

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

On Wed, 20 Mar 2024 00:30:56 +0100
fir <fir@grunge.pl> wrote:

> Michael S wrote:
> > On Wed, 20 Mar 2024 00:03:04 +0100
> > fir <fir@grunge.pl> wrote:
> >> im not quite sure what you do here.. pass the structure? in fact
> >> the thing you name context you may not pass at all just make is
> >> standalone static variables becouse they/it is the same for whole
> >> "branch" (given recursive branch of recolorisation)
> >>
> >> something like
> >>
> >> int old_color = 0xff0000;
> >> int new_color = 0x00ff00;
> >>
> >> void RecolorizePixelAndAdjacentPixels(int x, int y)
> >> {
> >> //...
> >> }
> >>
> >>
> >
> > Not thred-safe.
> >
> some thread safe as previous,

The same as your previous.
But I was modifying Malcolm's recursive variant rather than yours.
Malcolm's was thread-safe.

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:
....
>> >> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
....
>> >> static _Bool change_it( UI w, UI h, Color [w][h], Point, Color,
>> >> Color );

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

A VLA is a declared object -- an array with a size that is not a
compile-time constant. A variably modified type is just a type, not an
object. Obviously one can use such a type to declare a VLA, but when it
is the type of a function parameter, there need be no declared object
with that type. Usually the associated function argument will have been
dynamically allocated.

> Aren't they both introduced in C99 and made optional in later
> standards?

I think so but that's a shame since VMTs are very helpful for writing
array code. They avoid the need to keep calculating the index with
multiplications.

Making both optional was a classic case of throwing the baby out with
the bath water. Few of the objections raised about VLAs apply to VMTs.

--
Ben.

On 20/03/2024 10:23, Ben Bacarisse wrote:
> 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:
> ...
>>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> ...
>>>>> static _Bool change_it( UI w, UI h, Color [w][h], Point, Color,
>>>>> Color );
>
>>>> 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.
>
> A VLA is a declared object -- an array with a size that is not a
> compile-time constant. A variably modified type is just a type, not an
> object. Obviously one can use such a type to declare a VLA, but when it
> is the type of a function parameter, there need be no declared object
> with that type. Usually the associated function argument will have been
> dynamically allocated.
>
>> Aren't they both introduced in C99 and made optional in later
>> standards?
>
> I think so but that's a shame since VMTs are very helpful for writing
> array code. They avoid the need to keep calculating the index with
> multiplications.
>
> Making both optional was a classic case of throwing the baby out with
> the bath water. Few of the objections raised about VLAs apply to VMTs.
>
VMT = variabley modified type.
--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm

Michael S wrote:
> On Wed, 20 Mar 2024 00:30:56 +0100
> fir <fir@grunge.pl> wrote:
>
>> Michael S wrote:
>>> On Wed, 20 Mar 2024 00:03:04 +0100
>>> fir <fir@grunge.pl> wrote:
>>>> im not quite sure what you do here.. pass the structure? in fact
>>>> the thing you name context you may not pass at all just make is
>>>> standalone static variables becouse they/it is the same for whole
>>>> "branch" (given recursive branch of recolorisation)
>>>>
>>>> something like
>>>>
>>>> int old_color = 0xff0000;
>>>> int new_color = 0x00ff00;
>>>>
>>>> void RecolorizePixelAndAdjacentPixels(int x, int y)
>>>> {
>>>> //...
>>>> }
>>>>
>>>>
>>>
>>> Not thred-safe.
>>>
>> some thread safe as previous,
>
> The same as your previous.
> But I was modifying Malcolm's recursive variant rather than yours.
> Malcolm's was thread-safe.
>
>
>
sure, i dont always read into peoples code.. i just wanted to say it
seems you pass this context structure or pointer to it down the stack
each call - it is not necessary

On Wed, 20 Mar 2024 13:44:04 +0100
fir <fir@grunge.pl> wrote:

> Michael S wrote:
> > On Wed, 20 Mar 2024 00:30:56 +0100
> > fir <fir@grunge.pl> wrote:
> >
> >> Michael S wrote:
> >>> On Wed, 20 Mar 2024 00:03:04 +0100
> >>> fir <fir@grunge.pl> wrote:
> >>>> im not quite sure what you do here.. pass the structure? in fact
> >>>> the thing you name context you may not pass at all just make is
> >>>> standalone static variables becouse they/it is the same for whole
> >>>> "branch" (given recursive branch of recolorisation)
> >>>>
> >>>> something like
> >>>>
> >>>> int old_color = 0xff0000;
> >>>> int new_color = 0x00ff00;
> >>>>
> >>>> void RecolorizePixelAndAdjacentPixels(int x, int y)
> >>>> {
> >>>> //...
> >>>> }
> >>>>
> >>>>
> >>>
> >>> Not thred-safe.
> >>>
> >> some thread safe as previous,
> >
> > The same as your previous.
> > But I was modifying Malcolm's recursive variant rather than yours.
> > Malcolm's was thread-safe.
> >
> >
> >
> sure, i dont always read into peoples code.. i just wanted to say it
> seems you pass this context structure or pointer to it

Yes, pointer. That's the whole point of my modification of
Malcolm's code - to copy one pointer instead of 5 variables that
are never changed.

> down the stack
> each call - it is not necessary

Not necessary if you don't want it thread-safe. Necessary otherwise.

Michael S <already5chosen@yahoo.com> writes:

> On Tue, 19 Mar 2024 21:43:33 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
[...]

>> To me it looks like this recursive algorithm doesn't find all
>> pixels that need coloring in some situations.
>
> Yesterday night I had few doubts myself, but after further thinking
> came to conclusion that it it works in all situations.

Sorry, my bad. I did some experiments to convince myself
the algorithm sometimes doesn't work, but it turns out the
results showed a problem in the experiments rather than
the algorithm. :/

Michael S wrote:
> On Wed, 20 Mar 2024 13:44:04 +0100
> fir <fir@grunge.pl> wrote:
>
>> Michael S wrote:
>>> On Wed, 20 Mar 2024 00:30:56 +0100
>>> fir <fir@grunge.pl> wrote:
>>>
>>>> Michael S wrote:
>>>>> On Wed, 20 Mar 2024 00:03:04 +0100
>>>>> fir <fir@grunge.pl> wrote:
>>>>>> im not quite sure what you do here.. pass the structure? in fact
>>>>>> the thing you name context you may not pass at all just make is
>>>>>> standalone static variables becouse they/it is the same for whole
>>>>>> "branch" (given recursive branch of recolorisation)
>>>>>>
>>>>>> something like
>>>>>>
>>>>>> int old_color = 0xff0000;
>>>>>> int new_color = 0x00ff00;
>>>>>>
>>>>>> void RecolorizePixelAndAdjacentPixels(int x, int y)
>>>>>> {
>>>>>> //...
>>>>>> }
>>>>>>
>>>>>>
>>>>>
>>>>> Not thred-safe.
>>>>>
>>>> some thread safe as previous,
>>>
>>> The same as your previous.
>>> But I was modifying Malcolm's recursive variant rather than yours.
>>> Malcolm's was thread-safe.
>>>
>>>
>>>
>> sure, i dont always read into peoples code.. i just wanted to say it
>> seems you pass this context structure or pointer to it
>
> Yes, pointer. That's the whole point of my modification of
> Malcolm's code - to copy one pointer instead of 5 variables that
> are never changed.
>
>> down the stack
>> each call - it is not necessary
>
> Not necessary if you don't want it thread-safe. Necessary otherwise.
>
>
>
okay, if you say so, i dont use threads as i dont like them so i dont
know (and dont want to know) ;c

Michael S wrote:
> On Wed, 20 Mar 2024 01:13:10 +0100
> fir <fir@grunge.pl> wrote:
>>
>> i asked the topic here as i felt i got no time to rethink if it will
>> blow my progranm or not but that 30 minurtes task was for 30 minutes
>> not for a multi hour discusion
>>
>
> So you got the answer rather quickly and the answer is:
> "Yes, in the worst case it can consume a lot of stack. Don't use this
> simple and elegant algorithm unless you have full control both on size
> of the images and on size of the stack and on size of the stack frame
> generates by compiler for each recursive call."
>
>
ye, may conclusion would here be rather

put stack to 100 or even 150 MB and forget... then worry if the code
(of recolorisation) work too slow

(i know howewer this is potential bug af is someone would want then
recolorise of very big area there still would be stack overflow, but
this is unlikely)

Michael S <already5chosen@yahoo.com> writes:

> On Tue, 19 Mar 2024 11:57:53 +0000
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
>
>> On 19/03/2024 11:18, Michael S wrote:
>>
>>> 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.

[...]

> I did a little more investigation gradually modifying Tim's code
> for improved performance without changing the basic principle of
> the algorithm. [...]

I appreciate your doing this. I developed independently a
couple of versions along similar lines.

> So far, this algorithm is fastest among all "local" algorithms
> that I tried. By "local" I mean algorithms that don't try to
> recolor more than one pixel at time.
>
> "Non-local" algorithms i.e. yours and my recursive algorithm that
> recolors St. George cross, are somewhat faster, [...].

I was confused by this statement at first but now I see that
"yours" refers to Malcolm's algorithm.

> The nice thing about Tim's method is that we can expect that
> performance depends on number of recolored pixels and almost
> nothing else.

One aspect that I consider a significant plus is my code never
does poorly. Certainly it isn't the fastest in all cases, but
it's never abysmally slow.

> The second nice thing is that it is easy to understand. Not as
> easy as original recursive method, but easier than the rest of
> them.
>
> If you or somebody else is interested, here is [micro]optimized
> variant: [...]

Good show. I will try to get my latest version posted soon.

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> 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:
>
> ...
>
>>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
> ...
>
>>>>> static _Bool change_it( UI w, UI h, Color [w][h], Point, Color,
>>>>> Color );
>>>>
>>>> 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.
>
> A VLA is a declared object -- an array with a size that is not a
> compile-time constant. A variably modified type is just a type,
> not an object. Obviously one can use such a type to declare a
> VLA, but when it is the type of a function parameter, there need
> be no declared object with that type. Usually the associated
> function argument will have been dynamically allocated.

Also ordinary local variables can be declared to have a variably
modified type (the type not necessarily having been introduced
separately), often a benefit for code that is dealing with
multi-dimensional arrays.

>> Aren't they both introduced in C99 and made optional in later
>> standards?
>
> I think so but that's a shame since VMTs are very helpful for
> writing array code. They avoid the need to keep calculating the
> index with multiplications.

C11 added a pre-defined preprocessor macro __STDC_NO_VLA__, which
implementations can define to be 1 "intended to indicate that the
implementation does not support variable length arrays or variably
modified types." It's amusing to note that an implementation can
support VLAs and VMTs but still define the macro if they are not
intended to be supported. ;)

> Making both optional was a classic case of throwing the baby out
> with the bath water. Few of the objections raised about VLAs
> apply to VMTs.

Agree 100%.

Someone who wants to take a stand on this issue might to consider
adding the following lines

#if __STDC_NO_VLA__
#error Substandard implementation detected
#endif

at various places around their source code.

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

Michael S <already5chosen@yahoo.com> writes:

[...]

> I did a little more investigation gradually modifying Tim's code
> for improved performance without changing the basic principle of
> the algorithm. [...]

Here is a rendition of my latest and fastest refinement.

#include <stdlib.h>

typedef unsigned char UC;
typedef unsigned UI;
typedef unsigned U32;
typedef unsigned long long U64;
typedef struct { UI x, y; } Point;

void
faster_fill( UI w0, UI h0, UC pixels[], Point p0, UC old, UC new ){
U64 const w = w0;
U64 const h = h0;
U64 const xm = w-1;
U64 const ym = h-1;

U64 j = 0;
U64 k = 0;
U64 n = 1u << 10;
U64 m = n-1;
U32 *todo = malloc( n * sizeof *todo );
U64 x = p0.x;
U64 y = p0.y;

if( !todo || x >= w || y >= h || pixels[ x*h+y ] != old ) return;

todo[ k++ ] = x<<16 | y;

while( j != k ){
U64 used = j < k ? k-j : k+n-j;
U64 open = n - used;
if( open < used / 16 ){
U64 new_n = n*2;
U64 new_m = new_n-1;
U64 new_j = j < k ? j : j+n;
U32 *t = realloc( todo, new_n * sizeof *t );
if( ! t ) break;
if( j != new_j ) memcpy( t+new_j, t+j, (n-j) * sizeof *t );
todo = t, n = new_n, m = new_m, j = new_j, open = n-used;
}

U64 const jx = used <= 3*open ? k : j+open/3 &m;
while( j != jx ){
UI p = todo[j]; j = j+1 &m;
x = p >> 16, y = p & 0xFFFF;
if( x > 0 && pixels[ x*h-h + y ] == old ){
todo[k] = x-1<<16 | y, k = k+1&m, pixels[ x*h-h +y ] = new;
}
if( y > 0 && pixels[ x*h + y-1 ] == old ){
todo[k] = x<<16 | y-1, k = k+1&m, pixels[ x*h +y-1 ] = new;
}
if( x < xm && pixels[ x*h+h + y ] == old ){
todo[k] = x+1<<16 | y, k = k+1&m, pixels[ x*h+h +y ] = new;
}
if( y < ym && pixels[ x*h + y+1 ] == old ){
todo[k] = x<<16 | y+1, k = k+1&m, pixels[ x*h +y+1 ] = new;
}
}
}

free( todo );
}

On Wed, 20 Mar 2024 10:26:58 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Michael S <already5chosen@yahoo.com> writes:
>
> [...]
>
> > I did a little more investigation gradually modifying Tim's code
> > for improved performance without changing the basic principle of
> > the algorithm. [...]
>
> Here is a rendition of my latest and fastest refinement.
>

WOW, you really opened up your bag of tricks!
Power-of-two sized circular buffers is something that I tend to use on
smaller systems, like DSPs or MCUs rather than on "big" computers. But,
of course, on "big" computers it also helps.
Packing {x,y} into 32-bit word is a bit dirty. I'd guess that we can
justify it by claiming that original code although has similar
limitation of width*height <= INT_MAX.
Removal of FIFO empty and almost-full tests in the inner loop helps
solid shapes, but appears to slow down "drawn" shapes. Since solid
shapes are the slowest to fill, it is probably a good trade-off.

Overall, it is faster than my implementation of your algorithm. Esp. so
for solid shapes. Esp. of esp. so on Intel Skylake CPUs where speed up
is up to 1.75x.

More complicated 'St. George Cross' algorithms are still faster for
solid shapes and for shapes dominated by long horizontal or long
vertical lines. But they are ... well ... more complicated.
And [on Skylake] their worst case ('slalom' shape) is somewhat slower in
absolute sense than the worst case of your code (a solid bar).

Michael S <already5chosen@yahoo.com> writes:

> On Wed, 20 Mar 2024 10:26:58 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:
>>
>> [...]
>>
>>> I did a little more investigation gradually modifying Tim's code
>>> for improved performance without changing the basic principle of
>>> the algorithm. [...]
>>
>> Here is a rendition of my latest and fastest refinement.
>
> WOW, you really opened up your bag of tricks!

That I did, that I did. :)

I can do this kind of stuff when I need to. Usually I don't need
to.

> Power-of-two sized circular buffers is something that I tend to
> use on smaller systems, like DSPs or MCUs rather than on "big"
> computers. But, of course, on "big" computers it also helps.

Bitwise '&' is simply faster than '%'. Also, bitwise '&' works
on unsigned types in the event that there is wraparound, but '%'
probably doesn't.

> Packing {x,y} into 32-bit word is a bit dirty. I'd guess that we
> can justify it by claiming that original code although has similar
> limitation of width*height <= INT_MAX.

Yes, it is a bit dirty. In practice pixel fields almost never get
above 16 bits in each direction, and the code is easy enough to
change (by putting two 32-bit quantities into a 64-bit type) if
it becomes necessary to accommodate an enormous pixel field.

> Removal of FIFO empty and almost-full tests in the inner loop helps
> solid shapes, but appears to slow down "drawn" shapes. Since solid
> shapes are the slowest to fill, it is probably a good trade-off.

Taking those tests out of the inner loop helps when there is big
frontier set, because the tests don't have to be done as often.
When the frontier set is small, as we would expect for long
skinny shapes, doing that doesn't help as much (and of course
other overhead may make it worse in such cases).

> Overall, it is faster than my implementation of your algorithm.
> Esp. so for solid shapes. Esp. of esp. so on Intel Skylake CPUs
> where speed up is up to 1.75x.
>
> More complicated 'St. George Cross' algorithms are still faster
> for solid shapes and for shapes dominated by long horizontal or
> long vertical lines. But they are ... well ... more complicated.
> And [on Skylake] their worst case ('slalom' shape) is somewhat
> slower in absolute sense than the worst case of your code (a solid
> bar).

I played around with a "non-local" (in your terminology) version
of my most recently posted code, and discovered some things.
First the non-local version is somewhat faster on some shapes,
but noticeably slower on others. The non-local version is more
sensitive to which starting point is chosen. In a way it looks
similar to what happens with compression algorithms - some cases
get better, others get decidedly worse. I didn't do a lot of
experiments in an effort to determine what the range or relative
proportions of the different behaviors are.

After thinking about it a bit, it seems to me that a local-only
method is "more queue-like" and a non-local method is "more
stack-like". Using a pure queue plods along very predictably,
never getting much better or much worse. Being more stack-like
sometimes gets a speedup, but sometimes stumbles into the pit of
despair, which in the worse case needs a lot of memory and does
more memory shuffling. So for a general algorithm I'd opt for a
local-only method. Later on it might be good to use a more
tailored algorithm for special cases, if we can identify which
cases are special in a way that isn't too expensive.

Groovy hepcat fir was jivin' in comp.lang.c on Wed, 20 Mar 2024 11:48
am. It's a cool scene! Dig it.

> i was slightly thinking a bit of this recursion more generally and
> i observed that those very long depth chains are kinda problem of this
> recursion becouse maybe it is more fitted to be run parrallel

I wasn't going to post this here, since it's really an algorithm
issue, rather than a C issue. But the thread seems to have gone on for
some time with you seeming to be unable to solve this. So I'll give you
this as a clue.
The (or, at least, a) solution is only partially recursive. What I
have used is a line-based algorithm, each line being filled iteratively
(in a simple loop) from left to right. Recursion from line to line
completes the algorithm. Thus, the recursion level is greatly reduced.
And you should find that this approach fills an area of any shape.
Note, however, that for some pathological cases (very large and
complex shapes), this can still create a fairly large level of
recursion. Maybe a more complex approach can deal with this. What I
present here is just a very simple one which, in most cases, should
have a level of recursion well within reason.
I use a two part approach. The first part (called floodfill in the
code below) just sets up for the second part. The second part (called
r_floodfill here, for recursive floodfill) does the actual work, but is
only called by floodfill(). It goes something like this (although this
is incomplete, untested and not code I've actually used, just an
example):

static void r_floodfill(unsigned y, unsigned x, pixel_t new_clr, pixel_t
old_clr)
{ unsigned start, end;

/* Find start and end of line within floodfill area. */
start = end = x;
while(old_clr == get_pixel(y, start - 1))
--start;
while(old_clr == get_pixel(y, end + 1))
++end;

/* Fill line with new colour. */
for(x = start; x <= end; x++)
set_pixel(y, x, new_clr);

/* Run along again, checking pixel colours above and below,
and recursing if appropriate. */
for(x = start; x <= end; x++)
{
if(old_clr == get_pixel(y - 1, x))
r_floodfill(y - 1, x, new_clr, old_clr);
if(old_clr == get_pixel(y + 1, x))
r_floodfill(y + 1, x, new_clr, old_clr);
}
}

void floodfill(unsigned y, unsigned x, pixel_t new_clr)
{ pixel_t old_clr = get_pixel(y, x);

/* Only proceed if colours differ. */
if(new_clr != old_clr)
r_floodfill(y, x, new_clr, old_clr);
}

To use this, simply call floodfill() passing the coordinates of the
starting point for the fill (y and x) and the fill colour (new_clr).

--

----- Dig the NEW and IMPROVED news sig!! -----

-------------- Shaggy was here! ---------------
Ain't I'm a dawg!!

On Fri, 22 Mar 2024 13:04:39 +1100
Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> wrote:

> Groovy hepcat fir was jivin' in comp.lang.c on Wed, 20 Mar 2024 11:48
> am. It's a cool scene! Dig it.
>
> > i was slightly thinking a bit of this recursion more generally and
> > i observed that those very long depth chains are kinda problem of
> > this recursion becouse maybe it is more fitted to be run parrallel
>
> I wasn't going to post this here, since it's really an algorithm
> issue, rather than a C issue. But the thread seems to have gone on for
> some time with you seeming to be unable to solve this. So I'll give
> you this as a clue.
> The (or, at least, a) solution is only partially recursive. What I
> have used is a line-based algorithm, each line being filled
> iteratively (in a simple loop) from left to right. Recursion from
> line to line completes the algorithm. Thus, the recursion level is
> greatly reduced. And you should find that this approach fills an area
> of any shape. Note, however, that for some pathological cases (very
> large and complex shapes), this can still create a fairly large level
> of recursion. Maybe a more complex approach can deal with this. What I
> present here is just a very simple one which, in most cases, should
> have a level of recursion well within reason.
> I use a two part approach. The first part (called floodfill in the
> code below) just sets up for the second part. The second part (called
> r_floodfill here, for recursive floodfill) does the actual work, but
> is only called by floodfill(). It goes something like this (although
> this is incomplete, untested and not code I've actually used, just an
> example):
>
> static void r_floodfill(unsigned y, unsigned x, pixel_t new_clr,
> pixel_t old_clr)
> {
> unsigned start, end;
>
> /* Find start and end of line within floodfill area. */
> start = end = x;
> while(old_clr == get_pixel(y, start - 1))
> --start;
> while(old_clr == get_pixel(y, end + 1))
> ++end;
>
> /* Fill line with new colour. */
> for(x = start; x <= end; x++)
> set_pixel(y, x, new_clr);
>
> /* Run along again, checking pixel colours above and below,
> and recursing if appropriate. */
> for(x = start; x <= end; x++)
> {
> if(old_clr == get_pixel(y - 1, x))
> r_floodfill(y - 1, x, new_clr, old_clr);
> if(old_clr == get_pixel(y + 1, x))
> r_floodfill(y + 1, x, new_clr, old_clr);
> }
> }
>
> void floodfill(unsigned y, unsigned x, pixel_t new_clr)
> {
> pixel_t old_clr = get_pixel(y, x);
>
> /* Only proceed if colours differ. */
> if(new_clr != old_clr)
> r_floodfill(y, x, new_clr, old_clr);
> }
>
> To use this, simply call floodfill() passing the coordinates of the
> starting point for the fill (y and x) and the fill colour (new_clr).
>

It looks like anisotropic variant of my St. George Cross algorithm.
Or like recursive variant of Malcolm's algorithm.
Being anisotropic, it has higher amount of glass jaws. In particular,
it would be very slow for not uncommon 'jail window' patterns.
* *** *** *** ***
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
*** *** *** *** *

Also, implementation is still recursive and the worst-case recursion
depth is still O(N), where N is total number of recolored pixels, so
unlike many other solutions presented here, you didn't solve fir's
original problem.
And in presented form it's not thread-safe. Which is not a problem for
fir, but nonn-desirable for the rest of us.

Conclusion: sorry, you aren't going to get a cookie for your effort.

On Fri, 22 Mar 2024 17:55:26 +0300
Michael S <already5chosen@yahoo.com> wrote:

> On Fri, 22 Mar 2024 13:04:39 +1100
> Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> wrote:
>
> >
> > To use this, simply call floodfill() passing the coordinates of
> > the starting point for the fill (y and x) and the fill colour
> > (new_clr).
>
> It looks like anisotropic variant of my St. George Cross algorithm.
> Or like recursive variant of Malcolm's algorithm.
> Being anisotropic, it has higher amount of glass jaws. In particular,
> it would be very slow for not uncommon 'jail window' patterns.
> * *** *** *** ***
> * * * * * * * * *
> * * * * * * * * *
> * * * * * * * * *
> * * * * * * * * *
> * * * * * * * * *
> * * * * * * * * *
> * * * * * * * * *
> * * * * * * * * *
> *** *** *** *** *
>
> Also, implementation is still recursive and the worst-case recursion
> depth is still O(N), where N is total number of recolored pixels, so
> unlike many other solutions presented here, you didn't solve fir's
> original problem.
> And in presented form it's not thread-safe. Which is not a problem for
> fir, but nonn-desirable for the rest of us.
>
> Conclusion: sorry, you aren't going to get a cookie for your effort.
>

So, what is my own practical answer?
Assuming that speed is not a top priority and that simplicity
is pretty high on priority scale and that it should work with big
images and default stack size under Windows, I will go with following
not particularly fast and not particularly slow algorithm that I call
"deferred stack". That is, it's mostly explicit stack, but (explicit)
recursion is deferred until all four neighbors of current pixel saved
on todo stack.
"Not particularly slow" means that I did see cases where some other
algorithms is 2 times faster, but had never seen 3x difference.
In case x and y are known to fit in uint16_t, UI type could be redefined
accordingly. It will make execution faster, but not by much.

#include <stdlib.h>
#include <stddef.h>
#include <string.h>

typedef unsigned char Color;
typedef int UI;

int floodfill_r(
Color *image,
int width,
int height,
int x0,
int y0,
Color old,
Color new)
{ if (width < 0 || height < 0)
return 0;

if (x0 < 0 || x0 >= width || y0 < 0 || y0 >= height)
return 0;

size_t x = x0;
size_t y = y0;
if (image[y*width+x] != old)
return 0;

const ptrdiff_t INITIAL_TODO_SIZE = 128;
struct Point { UI x, y; } ;
struct Point *todo = malloc(INITIAL_TODO_SIZE * sizeof *todo );
if (!todo)
return -1;
struct Point* todo_end = &todo[INITIAL_TODO_SIZE];

todo[0].x = x; todo[0].y = y;
struct Point* sp = &todo[1];
do {
x = sp[-1].x; y = sp[-1].y;
--sp;
if (image[y*width+x] == old) {
image[y*width+x] = new;
if (x > 0 && image[y*width+x-1] == old) {
sp->x = x - 1; sp->y = y; ++sp;
}
if (y > 0 && image[y*width+x-width] == old) {
sp->x = x; sp->y = y - 1; ++sp;
}
if (x+1 < width && image[y*width+x+1] == old) {
sp->x = x + 1; sp->y = y; ++sp;
}
if (y+1 < height && image[y*width+x+width] == old) {
sp->x = x; sp->y = y + 1; ++sp;
}

if (todo_end-sp < 4) {
ptrdiff_t used = sp-todo;
ptrdiff_t size = todo_end - todo;
size += size/4;
struct Point* new_todo = realloc(todo, size * sizeof *todo );
if(!new_todo) {
free(todo);
return -1;
}
todo = new_todo;
sp = &todo[used];
todo_end = &todo[size];
}
}
} while (sp != todo);

free( todo );
return 1;
}

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On 17/03/2024 11:25, Ben Bacarisse wrote:
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>
>>> On 16/03/2024 13:55, Ben Bacarisse wrote:
>>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>>>
>>>>> Recursion make programs harder to reason about and prove correct.
>>>> Are you prepared to offer any evidence to support this astonishing
>>>> statement or can we just assume it's another Malcolmism?
>>>
>>> Example given. A recursive algorithm which is hard to reason about and
>>> prove correct, because we don't really know whether under perfectly
>>> reasonable assumptions it will or will not blow the stack.
>> Had you offered a proof that your code neither "blows the stack" nor
>> runs out of any other resource we'd have a starting point for
>> comparison, but you have not done that.
>> Mind you, had you done that, we would have something that might
>> eventually become only one piece of evidence for what is an
>> astonishingly general remark. Broadly applicable remarks require either
>> broadly applicable evidence or a wealth of distinct cases.
>> Your "rule" suggests that all reasoning is impeded by the presence of
>> recursion and I don't think you can support that claim. This is
>> characteristic of many of your remarks -- they are general "rules" that
>> often remain rules even when there is evidence to the contrary.
>> I'll make another point in the hope of clarifying the matter. An
>> algorithm or code is usually proved correct (or not!) under the
>> assumption that it has adequate resources -- usually time and storage.
>> Further reasoning may then be done to determine the resource
>> requirements since this is so often dependent on context. This
>> separation is helpful as you don't usually want to tie "correctness" to
>> some specific installation. The code might run on a system with a
>> dynamically allocated stack, for example, that has very similar
>> limitations to "heap" memory.
>> To put is more generally, we often want to prove properties of code that
>> are independent of physical constraints. Your remark includes this kind
>> reasoning. Did you intend it to?
>>
> The convetional wisdom is the opposite, But here, conventional wisdom
> fails. Because heaps are unlimited whilst stacks are not.

I put off answering for enough time that I now don't care anymore. I
think that's a win for everyone.

--
Ben.

Peter 'Shaggy' Haywood wrote:
> Groovy hepcat fir was jivin' in comp.lang.c on Wed, 20 Mar 2024 11:48
> am. It's a cool scene! Dig it.
>
>> i was slightly thinking a bit of this recursion more generally and
>> i observed that those very long depth chains are kinda problem of this
>> recursion becouse maybe it is more fitted to be run parrallel
>
> I wasn't going to post this here, since it's really an algorithm
> issue, rather than a C issue. But the thread seems to have gone on for
> some time with you seeming to be unable to solve this. So I'll give you
> this as a clue.
> The (or, at least, a) solution is only partially recursive. What I
> have used is a line-based algorithm, each line being filled iteratively
> (in a simple loop) from left to right. Recursion from line to line
> completes the algorithm. Thus, the recursion level is greatly reduced.
> And you should find that this approach fills an area of any shape.
> Note, however, that for some pathological cases (very large and
> complex shapes), this can still create a fairly large level of
> recursion. Maybe a more complex approach can deal with this. What I
> present here is just a very simple one which, in most cases, should
> have a level of recursion well within reason.
> I use a two part approach. The first part (called floodfill in the
> code below) just sets up for the second part. The second part (called
> r_floodfill here, for recursive floodfill) does the actual work, but is
> only called by floodfill(). It goes something like this (although this
> is incomplete, untested and not code I've actually used, just an
> example):
>
> static void r_floodfill(unsigned y, unsigned x, pixel_t new_clr, pixel_t
> old_clr)
> {
> unsigned start, end;
>
> /* Find start and end of line within floodfill area. */
> start = end = x;
> while(old_clr == get_pixel(y, start - 1))
> --start;
> while(old_clr == get_pixel(y, end + 1))
> ++end;
>
> /* Fill line with new colour. */
> for(x = start; x <= end; x++)
> set_pixel(y, x, new_clr);
>
> /* Run along again, checking pixel colours above and below,
> and recursing if appropriate. */
> for(x = start; x <= end; x++)
> {
> if(old_clr == get_pixel(y - 1, x))
> r_floodfill(y - 1, x, new_clr, old_clr);
> if(old_clr == get_pixel(y + 1, x))
> r_floodfill(y + 1, x, new_clr, old_clr);
> }
> }
>
> void floodfill(unsigned y, unsigned x, pixel_t new_clr)
> {
> pixel_t old_clr = get_pixel(y, x);
>
> /* Only proceed if colours differ. */
> if(new_clr != old_clr)
> r_floodfill(y, x, new_clr, old_clr);
> }
>
> To use this, simply call floodfill() passing the coordinates of the
> starting point for the fill (y and x) and the fill colour (new_clr).
>

well this is ok improvement for consideration - i hovever resolved a
problem even in 3 ways as you could note reading more carefully
1) put a stack to 100 MB and forget
2) ui wrote strightforward iteretive version (in draft) (this with
AddPixel(.. )
3) i noticed that the best method would be to introduce so called call
queue in c (probably best solution imo)

>Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>

>> The convetional wisdom is the opposite, But here, conventional wisdom
>> fails. Because heaps are unlimited whilst stacks are not.

That's not actually true. The size of both are bounded, yes.

It's certainly possible (in POSIX, anyway) for the stack bounds
to be unlimited (given sufficient real memory and/or backing
store) and the heap size to be bounded. See 'setrlimit'.

scott@slp53.sl.home (Scott Lurndal) writes:

>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>
>>> The convetional wisdom is the opposite, But here, conventional wisdom
>>> fails. Because heaps are unlimited while stacks are not.
>
> That's not actually true. The size of both are bounded, yes.
>
> It's certainly possible (in POSIX, anyway) for the stack bounds
> to be unlimited (given sufficient real memory and/or backing
> store) and the heap size to be bounded. See 'setrlimit'.

The sizes of both heaps and stacks are bounded, because
pointers have a fixed number of bits. Certainly these
sizes can be very very large, but they are not unbounded.

On Wed, 20 Mar 2024 10:01:10 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

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

For my test cases the FIFO depth of your algorithm never exceeds
min(width,height)*2+2. I wonder if existence of this or similar limit
can be proven theoretically.

Michael S <already5chosen@yahoo.com> writes:

> On Wed, 20 Mar 2024 10:01:10 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:

[...]

>>> 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).
>
> For my test cases the FIFO depth of your algorithm never exceeds
> min(width,height)*2+2. I wonder if existence of this or similar
> limit can be proven theoretically.

I believe it is possible to prove the strict FIFO algorithm is
O(N) for an N x N pixel field, but I haven't tried to do so in
any rigorous way, nor do I know what the constant is. It does
seem to be larger than 2.

As for finding a worst case, try this (expressed in pseudo code):

let pc = { width/2, height/2 }
// assume pixel field 'field' starts out as all zeroes
color 8 "legs" with the value '1' as follows:

leg from { 1, pc.y-1 } to { pc.x -1, pc.y-1 }
leg from { 1, pc.y+1 } to { pc.x -1, pc.y+1 }
leg from { px.x + 1, pc.y-1 } to { width-2, pc.y-1 }
leg from { px.x + 1, pc.y+1 } to { width-2, pc.y+1 }

leg from { px.x - 1, 1 } to { px.x -1, pc.y-1 }
leg from { px.x + 1, 1 } to { px.x +1, pc.y-1 }
leg from { px.x - 1, pc.y+1 } to { px.x -1, height/2 }
leg from { px.x + 1, pc.y+1 } to { px.x +1, height/2 }

So the pixel field should look like this (with longer legs for a
bigger pixel field), with '-' being 0 and '*' being 1:

+-----------------------+
| - - - - - - - - - - - |
| - - - - * - * - - - - |
| - - - - * - * - - - - |
| - - - - * - * - - - - |
| - * * * * - * * * * - |
| - - - - - - - - - - - |
| - * * * * - * * * * - |
| - - - - * - * - - - - |
| - - - - * - * - - - - |
| - - - - * - * - - - - |
| - - - - - - - - - - - |
+-----------------------+

Now start coloring at the center point with a new value
of 2.