On Wed, 20 Mar 2024 07:27:38 -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:
> >
>
> > 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.
>

To be fair, none of presented algorithms is abysmally slow.
When compared by number of visited points, they all appear to be within
factor of 2 or 2.5 of each other.
Some of them for some patterns could be 10-15 times slower than
others, but it does not happen for all patterns and when it happens
it's because of problematic implementation rather because of
differences in algorithms.
Even original naive recursive algorithm is not too slow when
implemented in optimized asm - 2.2x slower than the fastest for solid
square shape and closer than that for other shapes.

The big difference between algorithms is not a speed, but amount of
auxiliary memory used in the worst case. Your algorithm appears to be
the best in that department, Malcolm's algorithm it's also quite good
and all others (plain recursion, stacks, my deferred stack, all my
cross variants, lines-oriented recursion of : Peter 'Shaggy'
Haywood) are a lot worse.

But even by that metric, the difference between different
implementations of the same algorithm is often much bigger than
difference between algorithms.

For example, solid 200x200 image with starting point in the corner
recolored by code presented in first Malcolm's post (not his own
algorithm, but recursive algorithm that he presented as a reference
point) on x86-64/gcc consumes 5,094,784 bytes of stack. After small
modification (all non-changing parameters aggregated in structure
and passed by reference) the footprint falls to 2,547,328 B.
Coding the same algorithm (well, almost the same) in asm reduces it to
32,0000 B. Coding it with explicit stack cuts it to 40,000 B. Now I
didn't actually coded it, but I know how to compress explicit stack
down to 2 bits per level of recursion. If implemented, it would be
10,000B, i.e. comparable with much more economical algorithm of Malcolm
and 512x smaller than original implementation of [well, almost] the
same algorithm!

Michael S <already5chosen@yahoo.com> writes:

> On Wed, 20 Mar 2024 07:27:38 -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:
>>> [...]
>>> 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.
>
> To be fair, none of presented algorithms is abysmally slow. When
> compared by number of visited points, they all appear to be within
> factor of 2 or 2.5 of each other.

Certainly "abysmally slow" is subjective, but working in a large
pixel field, filling the whole field starting at the center,
Malcolm's code runs slower than my unoptimized code by a factor of
10 (and a tad slower than that compared to my optimized code).

> Some of them for some patterns could be 10-15 times slower than
> others, but it does not happen for all patterns and when it
> happens it's because of problematic implementation rather because
> of differences in algorithms.

In the case of Malcolm's code I think it's the algorithm, because
it doesn't scale linearly. Malcolm's code runs faster than mine
for small colorings, but slows down dramatically as the image
being colored gets bigger.

> The big difference between algorithms is not a speed, but amount of
> auxiliary memory used in the worst case. Your algorithm appears to be
> the best in that department, [...]

Yes, my unoptimized algorithm was designed to use as little
memory as possible. The optimized version traded space for
speed: it runs a little bit faster but incurs a non-trivial cost
in terms of space used. I think it's still not too bad, an upper
bound of a small multiple of N for an NxN pixel field.

> But even by that metric, the difference between different
> implementations of the same algorithm is often much bigger than
> difference between algorithms.

If I am not mistaken the original naive recursive algorithm has a
space cost that is O( N**2 ) for an NxN pixel field. The big-O
difference swamps everything else, just like the big-O difference
in runtime does for that metric.

> For example, solid 200x200 image with starting point in the corner
> [...]

On small pixel fields almost any algorithm is probably not too
bad. These days any serious algorithm should scale well up
to at least 4K by 4K, and tested up to at least 16K x 16K.
Tricks that make some things faster for small images sometimes
fall on their face when confronted with a larger image. My code
isn't likely to win many races on small images, but on large
images I expect it will always be competitive even if it doesn't
finish in first place.

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>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.

I was referring to the term of art used in POSIX, where
unlimited simply means that the operating system doesn't
limit them (and as I pointed out, physical limits, including
address space size (which is often only 48 bits, regardless
of the 64-bit pointer space)) will dominate.

$ ulimit -a
address space limit (Kibytes) (-M) unlimited
core file size (blocks) (-c) 0
cpu time (seconds) (-t) unlimited
data size (Kibytes) (-d) unlimited
file size (blocks) (-f) unlimited
locks (-x) unlimited

On 3/24/2024 1:26 PM, Tim Rentsch wrote:
> Michael S <already5chosen@yahoo.com> writes:
>
>> On Wed, 20 Mar 2024 07:27:38 -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:
>>>> [...]
>>>> 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.
>>
>> To be fair, none of presented algorithms is abysmally slow. When
>> compared by number of visited points, they all appear to be within
>> factor of 2 or 2.5 of each other.
>
> Certainly "abysmally slow" is subjective, but working in a large
> pixel field, filling the whole field starting at the center,
> Malcolm's code runs slower than my unoptimized code by a factor of
> 10 (and a tad slower than that compared to my optimized code).
>
>> Some of them for some patterns could be 10-15 times slower than
>> others, but it does not happen for all patterns and when it
>> happens it's because of problematic implementation rather because
>> of differences in algorithms.
>
> In the case of Malcolm's code I think it's the algorithm, because
> it doesn't scale linearly. Malcolm's code runs faster than mine
> for small colorings, but slows down dramatically as the image
> being colored gets bigger.
>
>> The big difference between algorithms is not a speed, but amount of
>> auxiliary memory used in the worst case. Your algorithm appears to be
>> the best in that department, [...]
>
> Yes, my unoptimized algorithm was designed to use as little
> memory as possible. The optimized version traded space for
> speed: it runs a little bit faster but incurs a non-trivial cost
> in terms of space used. I think it's still not too bad, an upper
> bound of a small multiple of N for an NxN pixel field.
>
>> But even by that metric, the difference between different
>> implementations of the same algorithm is often much bigger than
>> difference between algorithms.
>
> If I am not mistaken the original naive recursive algorithm has a
> space cost that is O( N**2 ) for an NxN pixel field. The big-O
> difference swamps everything else, just like the big-O difference
> in runtime does for that metric.
>
>
>> For example, solid 200x200 image with starting point in the corner
>> [...]
>
> On small pixel fields almost any algorithm is probably not too
> bad. These days any serious algorithm should scale well up
> to at least 4K by 4K, and tested up to at least 16K x 16K.
> Tricks that make some things faster for small images sometimes
> fall on their face when confronted with a larger image. My code
> isn't likely to win many races on small images, but on large
> images I expect it will always be competitive even if it doesn't
> finish in first place.

This might be relevant:

https://developer.download.nvidia.com/video/gputechconf/gtc/2019/presentation/s9111-a-new-direct-connected-component-labeling-and-analysis-algorithm-for-gpus.pdf

On Sun, 24 Mar 2024 10:24:45 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

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

Yes, I see. It is close to min(width,height)*4.
Thank you.

On Sun, 24 Mar 2024 13:26:16 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Michael S <already5chosen@yahoo.com> writes:
>
> > On Wed, 20 Mar 2024 07:27:38 -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:
> >>> [...]
> >>> 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.
> >
> > To be fair, none of presented algorithms is abysmally slow. When
> > compared by number of visited points, they all appear to be within
> > factor of 2 or 2.5 of each other.
>
> Certainly "abysmally slow" is subjective, but working in a large
> pixel field, filling the whole field starting at the center,
> Malcolm's code runs slower than my unoptimized code by a factor of
> 10 (and a tad slower than that compared to my optimized code).
>
> > Some of them for some patterns could be 10-15 times slower than
> > others, but it does not happen for all patterns and when it
> > happens it's because of problematic implementation rather because
> > of differences in algorithms.
>
> In the case of Malcolm's code I think it's the algorithm, because
> it doesn't scale linearly. Malcolm's code runs faster than mine
> for small colorings, but slows down dramatically as the image
> being colored gets bigger.
>
> > The big difference between algorithms is not a speed, but amount of
> > auxiliary memory used in the worst case. Your algorithm appears to
> > be the best in that department, [...]
>
> Yes, my unoptimized algorithm was designed to use as little
> memory as possible. The optimized version traded space for
> speed: it runs a little bit faster but incurs a non-trivial cost
> in terms of space used. I think it's still not too bad, an upper
> bound of a small multiple of N for an NxN pixel field.
>
> > But even by that metric, the difference between different
> > implementations of the same algorithm is often much bigger than
> > difference between algorithms.
>
> If I am not mistaken the original naive recursive algorithm has a
> space cost that is O( N**2 ) for an NxN pixel field. The big-O
> difference swamps everything else, just like the big-O difference
> in runtime does for that metric.
>
>
> > For example, solid 200x200 image with starting point in the corner
> > [...]
>
> On small pixel fields almost any algorithm is probably not too
> bad. These days any serious algorithm should scale well up
> to at least 4K by 4K, and tested up to at least 16K x 16K.
> Tricks that make some things faster for small images sometimes
> fall on their face when confronted with a larger image. My code
> isn't likely to win many races on small images, but on large
> images I expect it will always be competitive even if it doesn't
> finish in first place.

You are right. At 1920*1080 except for few special patterns, your
code is faster than Malcolm's by factor of 1.5x to 1.8. Same for 4K.
Auxiliary memory arrays of Malcolm are still quite small at these image
sizes, but speed suffers.
I wonder if it is a problem of algorithm or of implementation. Since I
still didn't figure out his idea, I can't improve his implementation in
order check it.

One thing that I were not expecting at this bigger pictures, is good
performance of simple recursive algorithm. Of course, not of original
form of it, but of variation with explicit stack.
For many shapes it has quite large memory footprint and despite that it
is not slow. Probably the stack has very good locality of reference.

Here is the code:

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

typedef unsigned char Color;

int floodfill4(
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;

const size_t w = width;
Color* image_end = &image[w*height];

size_t x = x0;
Color* row = &image[w*y0];
if (row[x] != old)
return 0;

const ptrdiff_t INITIAL_STACK_SZ = 256;
unsigned char* stack = malloc(INITIAL_STACK_SZ*sizeof(*stack));
if (!stack)
return -1;
unsigned char* sp = stack;
unsigned char* end_stack = &stack[INITIAL_STACK_SZ];

enum { ST_LEFT, ST_RIGHT, ST_UP, ST_DOWN, ST_BEG };

recursive_call:
row[x] = new;
if (sp==end_stack) {
ptrdiff_t size = sp - stack;
ptrdiff_t new_size = size+size/2;
unsigned char* new_stack = realloc(stack, new_size *
sizeof(*stack)); if (!new_stack) {
free(stack);
return -1;
}
stack = new_stack;
sp = &stack[size];
end_stack = &stack[new_size];
}

for (unsigned state = ST_BEG;;) {
switch (state) {
case ST_BEG:

++x;
if (x != width) {
if (row[x] == old) {
*sp++ = ST_RIGHT; goto recursive_call; // recursive call
}
}
case ST_RIGHT:
--x;

if (x > 0) {
--x;
if (row[x] == old) {
*sp++ = ST_LEFT; goto recursive_call; // recursive call
}
case ST_LEFT:
++x;
}

if (row != image) {
row -= w;
if (row[x] == old) {
*sp++ = ST_UP; goto recursive_call; // recursive call
}
case ST_UP:
row += w;
}

row += w;
if (row != image_end) {
if (row[x] == old) {
*sp++ = ST_DOWN; goto recursive_call; // recursive call
}
case ST_DOWN:
}
row -= w;
break;
}

if (sp == stack)
break;

state = *--sp; // pop stack (back to caller)
}

free(stack);
return 1; // done
}

On Mon, 25 Mar 2024 01:28:44 +0300
Michael S <already5chosen@yahoo.com> wrote:

> On Sun, 24 Mar 2024 13:26:16 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
> > Michael S <already5chosen@yahoo.com> writes:
> >
> > > On Wed, 20 Mar 2024 07:27:38 -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:
> > >>> [...]
> > >>> 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.
> > >
> > > To be fair, none of presented algorithms is abysmally slow. When
> > > compared by number of visited points, they all appear to be within
> > > factor of 2 or 2.5 of each other.
> >
> > Certainly "abysmally slow" is subjective, but working in a large
> > pixel field, filling the whole field starting at the center,
> > Malcolm's code runs slower than my unoptimized code by a factor of
> > 10 (and a tad slower than that compared to my optimized code).
> >
> > > Some of them for some patterns could be 10-15 times slower than
> > > others, but it does not happen for all patterns and when it
> > > happens it's because of problematic implementation rather because
> > > of differences in algorithms.
> >
> > In the case of Malcolm's code I think it's the algorithm, because
> > it doesn't scale linearly. Malcolm's code runs faster than mine
> > for small colorings, but slows down dramatically as the image
> > being colored gets bigger.
> >
> > > The big difference between algorithms is not a speed, but amount
> > > of auxiliary memory used in the worst case. Your algorithm
> > > appears to be the best in that department, [...]
> >
> > Yes, my unoptimized algorithm was designed to use as little
> > memory as possible. The optimized version traded space for
> > speed: it runs a little bit faster but incurs a non-trivial cost
> > in terms of space used. I think it's still not too bad, an upper
> > bound of a small multiple of N for an NxN pixel field.
> >
> > > But even by that metric, the difference between different
> > > implementations of the same algorithm is often much bigger than
> > > difference between algorithms.
> >
> > If I am not mistaken the original naive recursive algorithm has a
> > space cost that is O( N**2 ) for an NxN pixel field. The big-O
> > difference swamps everything else, just like the big-O difference
> > in runtime does for that metric.
> >
> >
> > > For example, solid 200x200 image with starting point in the corner
> > > [...]
> >
> > On small pixel fields almost any algorithm is probably not too
> > bad. These days any serious algorithm should scale well up
> > to at least 4K by 4K, and tested up to at least 16K x 16K.
> > Tricks that make some things faster for small images sometimes
> > fall on their face when confronted with a larger image. My code
> > isn't likely to win many races on small images, but on large
> > images I expect it will always be competitive even if it doesn't
> > finish in first place.
>
> You are right. At 1920*1080 except for few special patterns, your
> code is faster than Malcolm's by factor of 1.5x to 1.8. Same for 4K.
> Auxiliary memory arrays of Malcolm are still quite small at these
> image sizes, but speed suffers.
> I wonder if it is a problem of algorithm or of implementation. Since I
> still didn't figure out his idea, I can't improve his implementation
> in order check it.
>
> One thing that I were not expecting at this bigger pictures, is good
> performance of simple recursive algorithm. Of course, not of original
> form of it, but of variation with explicit stack.
> For many shapes it has quite large memory footprint and despite that
> it is not slow. Probably the stack has very good locality of
> reference.
>
> Here is the code:
> <snip>

The most robust code that I found so far that performs well both with
small pictures and with large and huge, is a variation on the same
theme of explicit stack, may be, more properly called trace back.
It operates on 2x2 squares instead of individual pixels.
The worst case auxiliary memory footprint of this variant is rather big,
up to picture_size/4 bytes. The code is *not* simple, but complexity
appears to be necessary for robust performance with various shapes and
sizes.

Todo queue based variants have very low memory footprint and perform
well for as long as recolored shape fits in the fast levels of
cache hierarchy, but suffer sharp slowdown when shape grows beyond
that. It seems, the problem of this algorithms is that the front
of recoloring is interleaved and focus of processing jumps randomly
across the front which leads to poor locality and to trashing of the
cache. May be, for huge pictures some sort of priority queue will
perform better than simple FIFO ? May be, implemented as binary heap?
https://en.wikipedia.org/wiki/Binary_heap

Thought are interesting, but it's unlikely that it could lead to faster
code than one presented below.

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

typedef unsigned char Color;

static __inline
unsigned check_column(Color *row, size_t x, size_t w, Color *end_image,
Color old)
{ unsigned b = row[x+0] == old ? 1<<0 : 0;
if (row+w != end_image && row[x+w] == old)
b |= 1 << 2;
return b;
}

static __inline
unsigned check_row(Color *row, size_t x, size_t w, Color old)
{ unsigned b = row[x+0] == old ? 1<<0 : 0;
if (x+1 != w && row[x+1] == old)
b |= 1 << 1;
return b;
}

int floodfill4(
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;

const size_t w = width;

size_t col0 = x0;
Color* row0 = &image[w * y0];
if (row0[col0] != old)
return 0;

int offs = 0;
if (y0 & 1) {
row0 -= w;
offs = 2;
}
if (col0 & 1) {
col0 -= 1;
offs |= 1;
}

Color* end_image = &image[w * height];

const ptrdiff_t INITIAL_STACK_SZ = 256;
unsigned char* stack = malloc(INITIAL_STACK_SZ*sizeof(*stack));
if (!stack)
return -1;
unsigned char* sp = stack;
unsigned char* end_stack = &stack[INITIAL_STACK_SZ];

enum {
// state
ST_LEFT, ST_RIGHT, ST_UP, ST_DOWN,
ST_BEG,
STATE_BITS = 3,
// mask
MSK_B00 = 1 << 2, MSK_B01 = 1 << 3,
MSK_B10 = 1 << 4, MSK_B11 = 1 << 5,
MSK_B0x = MSK_B00 | MSK_B01,
MSK_B1x = MSK_B10 | MSK_B11,
MSK_Bx0 = MSK_B00 | MSK_B10,
MSK_Bx1 = MSK_B01 | MSK_B11,
MSK_Bxx = MSK_Bx0 | MSK_Bx1,
MSK_BITS = MSK_Bxx,
// from
FROM_LEFT = 0 << 6,
FROM_RIGHT = 1 << 6,
FROM_UP = 2 << 6,
FROM_DOWN = 3 << 6,
FROM_BITS = 3 << 6,
};

unsigned bit_mask0 = check_row(row0, col0, w, old)*MSK_B00;
if (row0+w != end_image)
bit_mask0 |= check_row(row0+w, col0, w, old)*MSK_B10;
static const unsigned char kill_diag_tab[4][2] = {
{MSK_B01 | MSK_B10, ~MSK_B11},
{MSK_B00 | MSK_B11, ~MSK_B10},
{MSK_B00 | MSK_B11, ~MSK_B01},
{MSK_B01 | MSK_B10, ~MSK_B00},
};
if ((bit_mask0 & kill_diag_tab[offs][0])==0)
bit_mask0 &= kill_diag_tab[offs][1];

for (int rep = 0; rep < 2; ++rep) {
unsigned bit_mask = bit_mask0;
Color* row = row0;
size_t x = col0;
unsigned from = rep == 0 ? FROM_DOWN : FROM_LEFT;

recursive_call:
if (bit_mask & MSK_B00) row[x+0] = new;
if (bit_mask & MSK_B01) row[x+1] = new;
if (bit_mask & MSK_B10) row[x+w+0] = new;
if (bit_mask & MSK_B11) row[x+w+1] = new;

if (sp==end_stack) {
ptrdiff_t size = sp - stack;
ptrdiff_t new_size = size+size/2;
unsigned char* new_stack = realloc(stack, new_size *
sizeof(*stack));
if (!new_stack) {
free(stack);
return -1;
}
stack = new_stack;
sp = &stack[size];
end_stack = &stack[new_size];
}

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

> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
>> 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.
>
> I was referring to the term of art used in POSIX, where
> unlimited simply means that the operating system doesn't
> limit them [.. elaboration ..]

The earlier sentence was confusing, as the sentence construction
suggested "unlimited" was a general term rather than one with a
specific meaning in POSIX. In any case thank you for the
education.

Michael S <already5chosen@yahoo.com> writes:

>> [..various fill algorithms and how they scale..]
>
> One thing that I were not expecting at this bigger pictures, is good
> performance of simple recursive algorithm. Of course, not of original
> form of it, but of variation with explicit stack.
> For many shapes it has quite large memory footprint and despite that it
> is not slow. Probably the stack has very good locality of reference.
>
> [algorithm]

You are indeed a very clever fellow. I'm impressed.

Intrigued by your idea, I wrote something along the same lines,
only shorter and (at least for me) a little easier to grok.
If someone is interested I can post it.

I see you have also done a revised algorithm based on the same
idea, but more elaborate (to save on runtime footprint?).
Still working on formulating a response to that one...

On Thu, 28 Mar 2024 23:04:36 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Michael S <already5chosen@yahoo.com> writes:
>
> >> [..various fill algorithms and how they scale..]
> >
> > One thing that I were not expecting at this bigger pictures, is good
> > performance of simple recursive algorithm. Of course, not of
> > original form of it, but of variation with explicit stack.
> > For many shapes it has quite large memory footprint and despite
> > that it is not slow. Probably the stack has very good locality of
> > reference.
> >
> > [algorithm]
>
> You are indeed a very clever fellow. I'm impressed.
>

Yes, the use of switch is clever :(
It more resemble computed GO TO in old FORTRAN or indirect jumps in asm
than idiomatic C switch. But it is a legal* C.

> Intrigued by your idea, I wrote something along the same lines,
> only shorter and (at least for me) a little easier to grok.
> If someone is interested I can post it.

If non-trivially different, why not?

>
> I see you have also done a revised algorithm based on the same
> idea, but more elaborate (to save on runtime footprint?).
> Still working on formulating a response to that one...

The original purpose of enhancement was to amortize non-trivial and
probably not very fast call stack emulation logic over more than one
pixel. 2x2 just happens to be the biggest block that still has very
simple in-block recoloring logic. ~4x reduction in the size of
auxiliary memory is just a pleasant side effect.

Exactly the same 4x reduction in memory size could have been achieved
with single-pixel variant by using packed array for 2-bit state
(==trace back) stack elements. But it would be the same or slower than
original while the enhanced variant is robustly faster than original.

After implementing the first enhancement I paid attention that at 4K
size the timing (per pixel) for few of my test cases is significantly
worse than at smaller images. So, I added another enhancement aiming to
minimize cache trashing effects by never looking back at immediate
parent of current block. The info about location of the parent nicely
fitted into remaining 2 bits of stack octet.

------
* - the versions I posted are not exactly legal C; they are illegal C
non-rejected by gcc. But they can be trivially made into legal C by
adding semicolon after one of the case labels.

Michael S <already5chosen@yahoo.com> writes:

> On Thu, 28 Mar 2024 23:04:36 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:
>>
>>>> [..various fill algorithms and how they scale..]
>>>
>>> One thing that I were not expecting at this bigger pictures, is
>>> good performance of simple recursive algorithm. Of course, not of
>>> original form of it, but of variation with explicit stack. For
>>> many shapes it has quite large memory footprint and despite that
>>> it is not slow. Probably the stack has very good locality of
>>> reference.
>>>
>>> [algorithm]
>>
>> You are indeed a very clever fellow. I'm impressed.
>
> Yes, the use of switch is clever :(

In my view the cleverness is how "recursion" is accomplished by a
means of a combination of using a stack to store a "return address"
and restoring state by undoing a change rather than storing the
old value. Using a switch() is just a detail (and to my way of
thinking how the switch() is done here obscures the basic idea and
makes the code harder to understand, but never mind that).

> It more resemble computed GO TO in old FORTRAN or indirect jumps
> in asm than idiomatic C switch. But it is a legal* C.

I did program in FORTRAN briefly but don't remember ever using
computed GO TO. And yes, I found that missing semicolon and put it
back. Is there some reason you don't always use -pedantic? I
pretty much always do.

>> Intrigued by your idea, I wrote something along the same lines,
>> only shorter and (at least for me) a little easier to grok.
>> If someone is interested I can post it.
>
> If non-trivially different, why not?

I hope to soon but am unable to right now (and maybe for a week
or so due to circumstances beyond my control). For sure the
code is different; whether it is non-trivially different I
leave for others to judge.

>> I see you have also done a revised algorithm based on the same
>> idea, but more elaborate (to save on runtime footprint?).
>> Still working on formulating a response to that one...
>
> The original purpose of enhancement was to amortize non-trivial
> and probably not very fast call stack emulation logic over more
> than one pixel. 2x2 just happens to be the biggest block that
> still has very simple in-block recoloring logic. ~4x reduction in
> the size of auxiliary memory is just a pleasant side effect.
>
> Exactly the same 4x reduction in memory size could have been
> achieved with single-pixel variant by using packed array for 2-bit
> state (==trace back) stack elements. But it would be the same or
> slower than original while the enhanced variant is robustly faster
> than original.

An alternate idea is to use a 64-bit integer for 32 "top of stack"
elements, or up to 32 I should say, and a stack with 64-bit values.
Just an idea, it may not turn out to be useful.

The few measurements I have done don't show a big difference in
performance between the two methods. But I admit I wasn't paying
close attention, and like I said only a few patterns of filling were
exercised.

> After implementing the first enhancement I paid attention that at
> 4K size the timing (per pixel) for few of my test cases is
> significantly worse than at smaller images. So, I added another
> enhancement aiming to minimize cache trashing effects by never
> looking back at immediate parent of current block. The info about
> location of the parent nicely fitted into remaining 2 bits of
> stack octet.

The idea of not going back to the originator (what you call the
parent) is something I developed independently before looking at
your latest code (and mostly I still haven't). Seems like a good
idea.

Two further comments.

One, the new code is a lot more complicated than the previous
code. I'm not sure the performance gain is worth the cost
in complexity. What kind of speed improvements do you see,
in terms of percent?

Two, and more important, the new algorithm still uses O(NxN) memory
for an N by N pixel field. We really would like to get that down to
O(N) memory (and of course run just as fast). Have you looked into
how that might be done?

Michael S <already5chosen@yahoo.com> writes:

[...]

> The most robust code that I found so far that performs well both
> with small pictures and with large and huge, is a variation on the
> same theme of explicit stack, may be, more properly called trace
> back. It operates on 2x2 squares instead of individual pixels.
>
> The worst case auxiliary memory footprint of this variant is rather
> big, up to picture_size/4 bytes. The code is *not* simple, but
> complexity appears to be necessary for robust performance with
> various shapes and sizes.
>
> [...]

I took a cursory look just now, after reading your other later
posting. I think I have a general sense, especially in conjunction
with the explanatory comments.

I'm still hoping to find a method that is both fast and has
good memory use, which is to say O(N) for an NxN pixel field.

Something that would help is to have a library of test cases,
by which I mean patterns to be colored, so that a set of
methods could be tried, and timed, over all the patterns in
the library. Do you have something like that? So far all
my testing has been ad hoc.

Incidentally, it looks like your code assumes X varies more rapidly
than Y, so a "by row" order, whereas my code assumes Y varies more
rapidly than X, a "by column" order. The difference doesn't matter
as long as the pixel field is square and the test cases either are
symmetric about the X == Y axis or duplicate a non-symmetric pattern
about the X == Y axis. I would like to be able to run comparisons
between different methods and get usable results without having
to jump around because of different orientations. I'm not sure
how to accommodate that.

On Fri, 29 Mar 2024 23:58:26 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

>
> I did program in FORTRAN briefly but don't remember ever using
> computed GO TO. And yes, I found that missing semicolon and put it
> back. Is there some reason you don't always use -pedantic? I
> pretty much always do.
>

Just a habit.
In "real" work, as opposed to hobby, I use gcc almost exclusively for
small embedded targets and quite often with 3-rd party libraries in
source form. In such environment rising warnings level above -Wall
would be counterproductive, because it would be hard to see relevant
warning behind walls of false alarms.
May be, for hobby, where I have full control on everything, switching
to -Wpedantic is not a bad idea.

>
> An alternate idea is to use a 64-bit integer for 32 "top of stack"
> elements, or up to 32 I should say, and a stack with 64-bit values.
> Just an idea, it may not turn out to be useful.
>

That's just a detail of how to do pack/unpack with minimal
overhead. It does not change the principle that 'packed' version would
be less memory hungry but on modern PC with GBs of RAM it will not be
faster than original.
Memory footprint can directly affect speed when access patterns have
poor locality or when the rate of access exceeds 10-20 GB/s. In our
case locality of stack access is very good and the rate of stack
access, even on ultra fast processor, is less than 1 GB/s.

> The few measurements I have done don't show a big difference in
> performance between the two methods. But I admit I wasn't paying
> close attention, and like I said only a few patterns of filling were
> exercised.
>
> > After implementing the first enhancement I paid attention that at
> > 4K size the timing (per pixel) for few of my test cases is
> > significantly worse than at smaller images. So, I added another
> > enhancement aiming to minimize cache trashing effects by never
> > looking back at immediate parent of current block. The info about
> > location of the parent nicely fitted into remaining 2 bits of
> > stack octet.
>
> The idea of not going back to the originator (what you call the
> parent) is something I developed independently before looking at
> your latest code (and mostly I still haven't). Seems like a good
> idea.
>

I call it a principle of Lot's wife.
That is yet another reason to not grow blocks above 2x2.
For bigger blocks it does not apply.

> Two further comments.
>
> One, the new code is a lot more complicated than the previous
> code. I'm not sure the performance gain is worth the cost
> in complexity. What kind of speed improvements do you see,
> in terms of percent?
>

On my 11 y.o. and not top-of-the-line even then home PC for 4K
image (3840 x 2160) with cross-in-cross shape that I took from one of
your previous post, it is 2.43 times faster.
I don't remember how it compares on more modern systems. Anyway, right
now I have no test systems more modern than 3 y.o. Zen3.

> Two, and more important, the new algorithm still uses O(NxN) memory
> for an N by N pixel field. We really would like to get that down to
> O(N) memory (and of course run just as fast). Have you looked into
> how that might be done?

Using this particular principle of not saving (x,y) in auxiliary
storage, I don't believe that it is possible to have a footprint
smaller than O(W*H).

On Sat, 30 Mar 2024 00:54:19 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Michael S <already5chosen@yahoo.com> writes:
>
> [...]
>
> > The most robust code that I found so far that performs well both
> > with small pictures and with large and huge, is a variation on the
> > same theme of explicit stack, may be, more properly called trace
> > back. It operates on 2x2 squares instead of individual pixels.
> >
> > The worst case auxiliary memory footprint of this variant is rather
> > big, up to picture_size/4 bytes. The code is *not* simple, but
> > complexity appears to be necessary for robust performance with
> > various shapes and sizes.
> >
> > [...]
>
> I took a cursory look just now, after reading your other later
> posting. I think I have a general sense, especially in conjunction
> with the explanatory comments.
>
> I'm still hoping to find a method that is both fast and has
> good memory use, which is to say O(N) for an NxN pixel field.
>
> Something that would help is to have a library of test cases,
> by which I mean patterns to be colored, so that a set of
> methods could be tried, and timed, over all the patterns in
> the library. Do you have something like that? So far all
> my testing has been ad hoc.
>

I am not 100% sure about the meaning of 'ad hoc', but I'd guess that
mine are ad hoc too. Below are shapes that I use apart from solid
rectangles. I run them at 5 sizes: 25x19, 200x200, 1280x720, 1920x1080,
3840x2160. That is certainly not enough for correction tests, but feel
that it is sufficient for speed tests.

static void make_standing_snake(
unsigned char *image,
int width, int height,
unsigned char background_c,
unsigned char pen_c)
{ for (int y = 0; y < height; ++y) {
unsigned char* p = &image[y*width];
if (y % 2 == 0) {
memset(p, pen_c, width);
} else {
memset(p, background_c, width);
if (y % 4 == 1)
p[width-1] = pen_c;
else
p[0] = pen_c;
}
}
}

static void make_prostrate_snake(
unsigned char *image,
int width, int height,
unsigned char background_c,
unsigned char pen_c)
{ memset(image, background_c, sizeof(*image)*width*height);
// vertical bars
for (int y = 0; y < height; ++y)
for (int x = 0; x < width; x += 2)
image[y*width+x] = pen_c;

// connect bars at top
for (int x = 3; x < width; x += 4)
image[x] = pen_c;

// connect bars at bottom
for (int x = 1; x < width; x += 4)
image[(height-1)*width+x] = pen_c;
}

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;
}
for (int x = n_col*3; x < width; ++x)
image[x] = image[n_col*3-1];

// 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; p += width; }
}

// 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
// P P P P B B
unsigned char *b_row = &image[width*(height-1)];
for (int col = 0; col < n_col; ++col) {
unsigned char c = (col & 1)==1 ? background_c : pen_c;
b_row[col*3+0] = pen_c;
b_row[col*3+1] = c;
b_row[col*3+2] = c;
}
for (int x = n_col*3; x < width; ++x)
b_row[x] = b_row[n_col*3-1];

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

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

// leftmost column
// P
// B
// B
// P
// P
// P
for (int row = 0; row < n_row; ++row) {
unsigned char c = (row & 1)==0 ? background_c : pen_c;
image[(row*3+0)*width] = pen_c;
image[(row*3+1)*width] = c;
image[(row*3+2)*width] = c;
}
for (int y = n_row*3; y < height; ++y)
image[y*width] = image[(n_row*3-1)*width];

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

// near-rightmost column
// P
// B
// B
for (int row = 0; row < n_row; ++row) {
for (int x = n_col*4+1; x < width-1; ++x) {
unsigned char* p = &image[row*width*3+x];
p[0*width] = pen_c;
p[1*width] = background_c;
p[2*width] = background_c;
}
}

// rightmost column
// P
// P
// P
// P
// B
// B
unsigned char *r_col = &image[width-1];
for (int row = 0; row < n_row; ++row) {
unsigned char c = (row & 1)==1 ? background_c : pen_c;
r_col[(row*3+0)*width] = pen_c;
r_col[(row*3+1)*width] = c;
r_col[(row*3+2)*width] = c;
}
for (int y = n_row*3; y < height; ++y)
r_col[y*width] = r_col[(n_row*3-1)*width];

// bottom rows
for (int y = n_row*3; y < height; ++y) {
for (int x = 1; x < width-1; ++x)
image[y*width+x] = background_c;
}
}

static void make_crosss_in_cross(
unsigned char* image,
int width,
int height,
int xc,
int yc,
unsigned char background_c,
unsigned char pen_c)
{ memset(image, pen_c, width*height);

if (xc > 1 && xc+1 < width-1 && yc > 1 && yc+1 < height-1) {
memset(&image[(yc-1)*width+1], background_c, xc-1);
memset(&image[(yc+1)*width+1], background_c, xc-1);
memset(&image[(yc-1)*width+xc+1], background_c, width-xc-2);
memset(&image[(yc+1)*width+xc+1], background_c, width-xc-2);
for (int y = 1; y < yc; ++y) {
image[y*width+xc-1] = background_c;
image[y*width+xc+1] = background_c;
}
for (int y = yc+1; y < height-1; ++y) {
image[y*width+xc-1] = background_c;
image[y*width+xc+1] = background_c;
}
}
}

> Incidentally, it looks like your code assumes X varies more rapidly
> than Y, so a "by row" order, whereas my code assumes Y varies more
> rapidly than X, a "by column" order.

It is not so much about what I assume as about what is cheaper for
CPU hardware.

> The difference doesn't matter
> as long as the pixel field is square and the test cases either are
> symmetric about the X == Y axis or duplicate a non-symmetric pattern
> about the X == Y axis. I would like to be able to run comparisons
> between different methods and get usable results without having
> to jump around because of different orientations. I'm not sure
> how to accommodate that.

Michael S <already5chosen@yahoo.com> writes:

> On Thu, 28 Mar 2024 23:04:36 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

>> Intrigued by your idea, I wrote something along the same lines,
>> only shorter and (at least for me) a little easier to grok.
>> If someone is interested I can post it.
>
> If non-trivially different, why not?

Here is the code:

void
stack_fill( UI w0, UI h0, UC pixels[], Point p0, UC old, UC new ){
U64 w = ( assert( w0 > 0 ), w0 );
U64 h = ( assert( h0 > 0 ), h0 );
U64 px = ( assert( p0.x < w ), p0.x );
U64 py = ( assert( p0.y < h ), p0.y );

UC *x0 = ( assert( pixels ), pixels );
UC *x = x0 + px*h;
UC *xm = x0 + h*w - h;

U64 y0 = 0;
U64 y = py;
U64 ym = h-1;

UC *s0 = malloc( sizeof *s0 );
UC *s = s0;
UC *sn = s0 ? s0+1 : s0;

if( s0 && x[y] == old ) do {
x[y] = new;
if( s == sn ){
U64 s_offset = s - s0;
U64 n = (sn-s0+1) *3 /2;
UC *new_s0 = realloc( s0, n * sizeof *new_s0 );

if( ! new_s0 ) break;
s0 = new_s0, s = s0 + s_offset, sn = s0 + n;
}

if( y < ym && x[y+1] == old ){
y += 1, *s++ = 2; continue; UNDO_UP:
y -= 1;
}
if( y > y0 && x[y-1] == old ){
y -= 1, *s++ = 3; continue; UNDO_DOWN:
y += 1;
}
if( x < xm && y[x+h] == old ){
x += h, *s++ = 0; continue; UNDO_LEFT:
x -= h;
}
if( x > x0 && y[x-h] == old ){
x -= h, *s++ = 1; continue; UNDO_RIGHT:
x += h;
}

if( s == s0 ) break;

switch( *--s & 3 ){
case 0: goto UNDO_LEFT;
case 1: goto UNDO_RIGHT;
case 2: goto UNDO_UP;
case 3: goto UNDO_DOWN;
}
} while( 1 );

free( s0 );
}

On Sat, 30 Mar 2024 21:15:06 +0300
Michael S <already5chosen@yahoo.com> wrote:

> On Fri, 29 Mar 2024 23:58:26 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
> >
> > One, the new code is a lot more complicated than the previous
> > code. I'm not sure the performance gain is worth the cost
> > in complexity. What kind of speed improvements do you see,
> > in terms of percent?
> >
>
> On my 11 y.o. and not top-of-the-line even then home PC for 4K
> image (3840 x 2160) with cross-in-cross shape that I took from one of
> your previous post, it is 2.43 times faster.
> I don't remember how it compares on more modern systems. Anyway, right
> now I have no test systems more modern than 3 y.o. Zen3.
>
>

I tested on newer hardware - Intel Coffee Lake (Xeon-E 2176G) and AMD
Zen3 (EPYC 7543P).
Here I no longer see significant drop in speed of the 1x1 variant at 4K
size, but I still see that more complicated variant provides nice speed
up. Up to 1.56x on Coffee Lake and up to 3x on Zen3.

On Sun, 24 Mar 2024 10:24:45 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

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

It seems that in worst case the strict FIFO algorithm is the same as
the rest of them, i.e. O(NN) where NN is the number of re-colored
points. Below is an example of the shape for which I measured memory
consumption for 3840x2160 image almost exactly 4x as much as for
1920x1080.

static void make_fractal_tree_recursive(
unsigned char* image,
int width,
int nx,
int ny,
unsigned char pen_c)
{ if (nx < 3 && ny < 3) {
// small rectangle - solid fill
for (int y = 0; y < ny; ++y)
for (int x = 0; x < nx; ++x)
image[width*y+x] = pen_c;
return;
}
if (nx >= ny) {
int xc = (nx-1)/2;
if (xc - 1 > 0) { // left sub-plot
make_fractal_tree_recursive(image, width, xc - 1, ny, pen_c);
}
if (xc + 2 < nx) { // right sub-plot
make_fractal_tree_recursive(&image[xc+2], width,
nx - (xc + 2), ny, pen_c);
}
// draw vertical cross
for (int y = 0; y < ny; ++y)
image[width*y+xc] = pen_c;
int yc = (ny-1)/2;
image[width*yc+xc-1] = pen_c;
image[width*yc+xc+1] = pen_c;
} else {
int yc = (ny-1)/2;
if (yc - 1 > 0) { // upper sub-plot
make_fractal_tree_recursive(image, width, nx, yc - 1, pen_c);
}
if (yc + 2 < ny) { // lower sub-plot
make_fractal_tree_recursive(&image[(yc+2)*width], width, nx,
ny -(yc + 2), pen_c);
}
// draw horizontal cross
for (int x = 0; x < nx; ++x)
image[width*yc+x] = pen_c;
int xc = (nx-1)/2;
image[width*(yc-1)+xc] = pen_c;
image[width*(yc+1)+xc] = pen_c;
}
}

static void make_fractal_tree(
unsigned char* image,
int width,
int height,
unsigned char background_c,
unsigned char pen_c)
{ memset(image, background_c, width*height);
make_fractal_tree_recursive(image, width, width, height, pen_c);
}

Michael S <already5chosen@yahoo.com> writes:

> On Sat, 30 Mar 2024 00:54:19 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
[...]
>> Something that would help is to have a library of test cases,
>> by which I mean patterns to be colored, so that a set of
>> methods could be tried, and timed, over all the patterns in
>> the library. Do you have something like that? So far all
>> my testing has been ad hoc.
>
> I am not 100% sure about the meaning of 'ad hoc', but I'd guess
> that mine are ad hoc too. Below are shapes that I use apart from
> solid rectangles. I run them at 5 sizes: 25x19, 200x200,
> 1280x720, 1920x1080, 3840x2160. That is certainly not enough for
> correction tests, but feel that it is sufficient for speed tests.
>
> [code]

I got these, thank you.

Here is a pattern generating function I wrote for my own
testing. Disclaimer: slightly changed from my original
source, hopefully any errors inadvertently introduced can
be corrected easily. Also, it uses the value 0 for the
background and the value 1 for the pattern to be colored.

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

typedef unsigned char Pixel;

extern void
ellipse_with_hole( Pixel *field, unsigned w, unsigned h ){
size_t i, j;
double wc = w/2, hc = h/2;

double a = (w > h ? wc : hc) -1;
double b = (w > h ? hc : wc) -1;

double b3 = 1+6*b/8;
double radius = b/2.5;
double cx = w > h ? wc : b3+1;
double cy = w > h ? b3+1 : hc;

double focus = sqrt( a*a - b*b );
double f1x = w > h ? wc - focus : wc;
double f1y = w > h ? hc : hc - focus;
double f2x = w > h ? wc + focus : wc;
double f2y = w > h ? hc : hc + focus;

memset( field, 0, w*h );

for( i = 0; i < w; i++ ){
for( j = 0; j < h; j++ ){
double dx = i - cx, dy = j - cy;
double r2 = radius * radius;
if( dx * dx + dy*dy <= r2 ) continue;
double dx1 = i - f1x, dy1 = j - f1y;
double dx2 = i - f2x, dy2 = j - f2y;
double sum2 = a*2;
double d1 = sqrt( dx1*dx1 + dy1*dy1 );
double d2 = sqrt( dx2*dx2 + dy2*dy2 );
if( d1 + d2 > 2*a ) continue;
field[ i+j*w ] = 1;
}}
}

Michael S <already5chosen@yahoo.com> writes:

> On Fri, 29 Mar 2024 23:58:26 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> I did program in FORTRAN briefly but don't remember ever using
>> computed GO TO. And yes, I found that missing semicolon and put it
>> back. Is there some reason you don't always use -pedantic? I
>> pretty much always do.
>
> Just a habit.
> In "real" work, as opposed to hobby, I use gcc almost exclusively for
> small embedded targets and quite often with 3-rd party libraries in
> source form. In such environment rising warnings level above -Wall
> would be counterproductive, because it would be hard to see relevant
> warning behind walls of false alarms.
> May be, for hobby, where I have full control on everything, switching
> to -Wpedantic is not a bad idea.

My experience with third party libraries is that sometimes they use
extensions, probably mostly gcc-isms. Not much to be done in that
case. Of course turning on -pedantic could be done selectively.

It might be worth an experiment of turning off -Wall while turning
on -pedantic to see how big or how little the problem is.

>> The idea of not going back to the originator (what you call the
>> parent) is something I developed independently before looking at
>> your latest code (and mostly I still haven't). Seems like a good
>> idea.
>
> I call it a principle of Lot's wife.
> That is yet another reason to not grow blocks above 2x2.
> For bigger blocks it does not apply.

Here is an updated version of my "stacking" code. On my test
system (and I don't even know exactly what CPU it has, probably
about 5 years old) this code runs about 30% faster than your 2x2
version, averaged across all patterns and all sizes above the
smallest ones (25x19 and 19x25).

#include <assert.h>
#include <stdlib.h>

typedef unsigned char UC, Color;
typedef size_t Index, Count;
typedef struct { Index x, y; } Point;

extern Count
stack_plus( UC *field, Index w, Index h, Point p0, Color old, Color new ){
Index px = ( assert( p0.x < w ), p0.x );
Index py = ( assert( p0.y < h ), p0.y );

Index x0 = 0;
Index x = px;
Index xm = w-1;

UC *y0 = field;
UC *y = y0 + py*w;
UC *ym = y0 + h*w - w;

UC *s0 = malloc( 8 * sizeof *s0 );
UC *s = s0;
UC *sn = s0 ? s0+8 : s0;

Count r = 0;

if( s0 ) goto START_FOUR;

while( s != s0 ){
switch( *--s & 15 ){
case 0: goto UNDO_START_LEFT;
case 1: goto UNDO_START_RIGHT;
case 2: goto UNDO_START_UP;
case 3: goto UNDO_START_DOWN;

case 4: goto UNDO_LEFT_DOWN;
case 5: goto UNDO_LEFT_LEFT;
case 6: goto UNDO_LEFT_UP;

case 7: goto UNDO_UP_LEFT;
case 8: goto UNDO_UP_UP;
case 9: goto UNDO_UP_RIGHT;

case 10: goto UNDO_RIGHT_UP;
case 11: goto UNDO_RIGHT_RIGHT;
case 12: goto UNDO_RIGHT_DOWN;

case 13: goto UNDO_DOWN_RIGHT;
case 14: goto UNDO_DOWN_DOWN;
case 15: goto UNDO_DOWN_LEFT;
}

START_FOUR:
if( y[x] != old ) continue;
y[x] = new; r++;
if( x < xm && y[x+1] == old ){
x += 1, *s++ = 0; goto START_LEFT; UNDO_START_LEFT:
x -= 1;
}
if( x > x0 && y[x-1] == old ){
x -= 1, *s++ = 1; goto START_RIGHT; UNDO_START_RIGHT:
x += 1;
}
if( y < ym && x[y+w] == old ){
y += w, *s++ = 2; goto START_UP; UNDO_START_UP:
y -= w;
}
if( y > y0 && x[y-w] == old ){
y -= w, *s++ = 3; goto START_DOWN; UNDO_START_DOWN:
y += w;
}
continue;

START_LEFT:
y[x] = new; r++;
if( s == sn ){
Index s_offset = s - s0;
Index n = (sn-s0+1) *3 /2;
UC *new_s0 = realloc( s0, n * sizeof *new_s0 );

if( ! new_s0 ) break;
s0 = new_s0, s = s0 + s_offset, sn = s0 + n;
}
if( x < xm && y[x+1] == old ){
x += 1, *s++ = 5; goto START_LEFT; UNDO_LEFT_LEFT:
x -= 1;
}
if( y > y0 && x[y-w] == old ){
y -= w, *s++ = 4; goto START_DOWN; UNDO_LEFT_DOWN:
y += w;
}
if( y < ym && x[y+w] == old ){
y += w, *s++ = 6; goto START_UP; UNDO_LEFT_UP:
y -= w;
}
continue;

START_UP:
y[x] = new; r++;
if( s == sn ){
Index s_offset = s - s0;
Index n = (sn-s0+1) *3 /2;
UC *new_s0 = realloc( s0, n * sizeof *new_s0 );

if( ! new_s0 ) break;
s0 = new_s0, s = s0 + s_offset, sn = s0 + n;
}
if( x < xm && y[x+1] == old ){
x += 1, *s++ = 7; goto START_LEFT; UNDO_UP_LEFT:
x -= 1;
}
if( x > x0 && y[x-1] == old ){
x -= 1, *s++ = 9; goto START_RIGHT; UNDO_UP_RIGHT:
x += 1;
}
if( y < ym && x[y+w] == old ){
y += w, *s++ = 8; goto START_UP; UNDO_UP_UP:
y -= w;
}
continue;

START_RIGHT:
y[x] = new; r++;
if( s == sn ){
Index s_offset = s - s0;
Index n = (sn-s0+1) *3 /2;
UC *new_s0 = realloc( s0, n * sizeof *new_s0 );

if( ! new_s0 ) break;
s0 = new_s0, s = s0 + s_offset, sn = s0 + n;
}
if( x > x0 && y[x-1] == old ){
x -= 1, *s++ = 11; goto START_RIGHT; UNDO_RIGHT_RIGHT:
x += 1;
}
if( y < ym && x[y+w] == old ){
y += w, *s++ = 10; goto START_UP; UNDO_RIGHT_UP:
y -= w;
}
if( y > y0 && x[y-w] == old ){
y -= w, *s++ = 12; goto START_DOWN; UNDO_RIGHT_DOWN:
y += w;
}
continue;

START_DOWN:
y[x] = new; r++;
if( s == sn ){
Index s_offset = s - s0;
Index n = (sn-s0+1) *3 /2;
UC *new_s0 = realloc( s0, n * sizeof *new_s0 );

if( ! new_s0 ) break;
s0 = new_s0, s = s0 + s_offset, sn = s0 + n;
}
if( x > x0 && y[x-1] == old ){
x -= 1, *s++ = 13; goto START_RIGHT; UNDO_DOWN_RIGHT:
x += 1;
}
if( x < xm && y[x+1] == old ){
x += 1, *s++ = 15; goto START_LEFT; UNDO_DOWN_LEFT:
x -= 1;
}
if( y > y0 && x[y-w] == old ){
y -= w, *s++ = 14; goto START_DOWN; UNDO_DOWN_DOWN:
y += w;
}
continue;

}

return free( s0 ), r;
}

Michael S <already5chosen@yahoo.com> writes:

> On Sat, 30 Mar 2024 21:15:06 +0300
> Michael S <already5chosen@yahoo.com> wrote:
>
>> On Fri, 29 Mar 2024 23:58:26 -0700
>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>
>>> One, the new code is a lot more complicated than the previous
>>> code. I'm not sure the performance gain is worth the cost
>>> in complexity. What kind of speed improvements do you see,
>>> in terms of percent?
>>
>> On my 11 y.o. and not top-of-the-line even then home PC for 4K
>> image (3840 x 2160) with cross-in-cross shape that I took from one of
>> your previous post, it is 2.43 times faster.
>> I don't remember how it compares on more modern systems. Anyway, right
>> now I have no test systems more modern than 3 y.o. Zen3.
>
> I tested on newer hardware - Intel Coffee Lake (Xeon-E 2176G) and AMD
> Zen3 (EPYC 7543P).
> Here I no longer see significant drop in speed of the 1x1 variant at 4K
> size, but I still see that more complicated variant provides nice speed
> up. Up to 1.56x on Coffee Lake and up to 3x on Zen3.

On my test system the numbers are closer and also more evenly
balanced: ratios range from about 0.70 to about 1.40, roughly
evenly split with the 2x2 version somewhat better. There was
one outlier at approximately 1.48. More precisely, the ratios
have an average of 1.06 (which means the 1x1 version is about
6 percent slower on average), with a standard deviation of 0.21.

Michael S <already5chosen@yahoo.com> writes:

> On Sun, 24 Mar 2024 10:24:45 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> 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.

Before I do anything else I should correct a bug in my earlier
FIFO algorithm. The initialization of the variable jx should
read

Index const jx = used*3 < open ? k : j+open/3 &m;

rather than what it used to. (The type may have changed but that
is incidental; what matters is the value of the initializing
expression.) I don't know what I was thinking when I wrote the
previous version, it's just completely wrong.

> It seems that in worst case the strict FIFO algorithm is the same as
> the rest of them, i.e. O(NN) where NN is the number of re-colored
> points. Below is an example of the shape for which I measured memory
> consumption for 3840x2160 image almost exactly 4x as much as for
> 1920x1080.

I agree, the empirical evidence here and in my own tests is quite
compelling.

That said, the constant factor for the FIFO algorithm is lower
than the stack-based algorithms, even taking into account the
difference in sizes for queue and stack elements. Moreover cases
where FIFO algorithms are O( NxN ) are unusual and sparse,
whereas the stack-based algorithms tend to use a lot of memory
in lots of common and routine cases. On the average FIFO
algorithms typically use a lot less memory (or so I conjecture).

> [code to generate fractal tree pattern]

Thank you for this. I incorporated it into my set of test
patterns more or less as soon as it was posted.

Now that I have taken some time to play around with different
algorithms and have been more systematic in doing speed
comparisons between different algorithms, on different patterns,
and with a good range of sizes, I have some general thoughts
to offer.

Stack-based methods tend to do well on long skinny patterns and
tend to do not as well on fatter patterns such as circles or
squares. The fractal pattern is ideal for a stack-based method.
Conversely, patterns that are mostly solid shapes don't fare as
well under stack-based methods, at least not the ones that have
been posted in this thread, and also they tend to use more memory
in those cases.

I've been playing around with a more elaborate, mostly FIFO
method, in hopes of getting something that offers the best
of both worlds. The results so far are encouraging, but a
fair amount of tuning has been necessary (and perhaps more
still is), and comparisons have been done on just the one
test server I have available. So I don't know how well it
would hold up on other hardware, including especially more
recent hardware. Under these circumstances I feel it is
premature to post actual code, especially since the code
is still in flux.

This topic has been more interesting that I was expecting, and
also more challenging. I have a strong rule against writing
functions more than about 60 lines long. For the problem of
writing an acceptably quick flood-fill algorithm, I think it would
at the very least be a lot of work to write code to do that while
still observing a limit on function length of even 100 lines, let
alone 60.

On Wed, 10 Apr 2024 19:47:11 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Michael S <already5chosen@yahoo.com> writes:
>
> > On Sun, 24 Mar 2024 10:24:45 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >
> >> 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.
>
> Before I do anything else I should correct a bug in my earlier
> FIFO algorithm. The initialization of the variable jx should
> read
>
> Index const jx = used*3 < open ? k : j+open/3 &m;
>

I lost track, sorry. I can not find your code that contains line
similar to this.
Can you point to specific post?

> rather than what it used to. (The type may have changed but that
> is incidental; what matters is the value of the initializing
> expression.) I don't know what I was thinking when I wrote the
> previous version, it's just completely wrong.
>
> > It seems that in worst case the strict FIFO algorithm is the same as
> > the rest of them, i.e. O(NN) where NN is the number of re-colored
> > points. Below is an example of the shape for which I measured
> > memory consumption for 3840x2160 image almost exactly 4x as much as
> > for 1920x1080.
>
> I agree, the empirical evidence here and in my own tests is quite
> compelling.
>

BTW, I am no longer agree with myself about "the rest of them".
By now, I know at least one method that is O(W*log(H)). It is even
quite fast for majority of my test shapes. Unfortunately, [in its
current form] it is abysmally slow (100x) for minority of tests.
[In it's current form] it has other disadvantages as well like
consuming non-trivial amount of memory when handling small spot in the
big image. But that can be improved. I am less sure that worst-case
speed can be improved enough to make it generally acceptable.

I think, I said enough for you to figure out a general principle of
this algorithm. I don't want to post code here before I try few
improvements.

> That said, the constant factor for the FIFO algorithm is lower
> than the stack-based algorithms, even taking into account the
> difference in sizes for queue and stack elements. Moreover cases
> where FIFO algorithms are O( NxN ) are unusual and sparse,
> whereas the stack-based algorithms tend to use a lot of memory
> in lots of common and routine cases. On the average FIFO
> algorithms typically use a lot less memory (or so I conjecture).
>
> > [code to generate fractal tree pattern]
>
> Thank you for this. I incorporated it into my set of test
> patterns more or less as soon as it was posted.
>
> Now that I have taken some time to play around with different
> algorithms and have been more systematic in doing speed
> comparisons between different algorithms, on different patterns,
> and with a good range of sizes, I have some general thoughts
> to offer.
>
> Stack-based methods tend to do well on long skinny patterns and
> tend to do not as well on fatter patterns such as circles or
> squares. The fractal pattern is ideal for a stack-based method.
> Conversely, patterns that are mostly solid shapes don't fare as
> well under stack-based methods, at least not the ones that have
> been posted in this thread, and also they tend to use more memory
> in those cases.
>

Indeed, with solid shapes it uses more memory. But at least in my tests
on my hardware with this sort of shapes it is easily faster than
anything else. The difference vs the best of the rest is especially big
at 4K images on AMD Zen3 based hardware, but even on Intel Skylake which
generally serves as equalizer between different algorithms, the speed
advantage of 2x2 stack is significant.

> I've been playing around with a more elaborate, mostly FIFO
> method, in hopes of getting something that offers the best
> of both worlds. The results so far are encouraging, but a
> fair amount of tuning has been necessary (and perhaps more
> still is), and comparisons have been done on just the one
> test server I have available. So I don't know how well it
> would hold up on other hardware, including especially more
> recent hardware. Under these circumstances I feel it is
> premature to post actual code, especially since the code
> is still in flux.
>
> This topic has been more interesting that I was expecting, and
> also more challenging.

That's not the first time in my practice where problems with simple
formulation begots interesting challenges.
Didn't Donald Knuth wrote 300 or 400 pages about sorting and still
ended up quite far away from exhausting the topic?

> I have a strong rule against writing
> functions more than about 60 lines long. For the problem of
> writing an acceptably quick flood-fill algorithm, I think it would
> at the very least be a lot of work to write code to do that while
> still observing a limit on function length of even 100 lines, let
> alone 60.

So why not break it down to smaller pieces ?
Myself, I have no rules. In my real work I am quite happy with
dispatchers of network messages that are 250-300 lines long. But if I
had this sort of rules, I'd certainly decompose.

Michael S <already5chosen@yahoo.com> writes:

(I'm replying in pieces.)

> On Wed, 10 Apr 2024 19:47:11 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Before I do anything else I should correct a bug in my earlier
>> FIFO algorithm. The initialization of the variable jx should
>> read
>>
>> Index const jx = used*3 < open ? k : j+open/3 &m;
>
> I lost track, sorry. I can not find your code that contains line
> similar to this.
> Can you point to specific post?

Easier for me just to repost the corrected algorithm. The
type UC is an unsigned char, the types Index and Count are
size_t (or maybe unsigned long long), the type U32 is a
32-bit unsigned type.

Please excuse any minor glitches, I have done some hand
editing to take out various bits of diagnostic code.

extern Count
fifo_fill( UC *field, Index w, Index h, Point p0, UC old, UC new ){
Index const xm = w-1;
Index const ym = h-1;

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

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

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

while( j != k ){
Index used = j < k ? k-j : k+n-j;
Index open = n - used;
if( open < used/16 ){
Index new_n = n*2;
Index new_m = new_n-1;
Index 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;
}
assert( (k-j&m) == used && open+used == n );

Index const jx = used*3 < open ? k : j+open/3 &m; // here it is!
while( j != jx ){
if( (k-j&m) > mm ) mm = k-j&m;
U32 p = todo[j]; j = j+1 &m;
x = p >> 16, y = p & 0xFFFF;
if( x > 0 && field[ x-1 + y*w ] == old ){
todo[k] = x-1<<16 | y, k = k+1&m, field[ x-1 + y*w ] = new;
}
if( y > 0 && field[ x + (y-1)*w ] == old ){
todo[k] = x<<16 | y-1, k = k+1&m, field[ x + (y-1)*w ] = new;
}
if( x < xm && field[ x+1 + y*w ] == old ){
todo[k] = x+1<<16 | y, k = k+1&m, field[ x+1 + y*w ] = new;
}
if( y < ym && field[ x + (y+1)*w ] == old ){
todo[k] = x<<16 | y+1, k = k+1&m, field[ x + (y+1)*w ] = new;
}
}
}

return free( todo ), 0;
}

Michael S <already5chosen@yahoo.com> writes:

> On Wed, 10 Apr 2024 19:47:11 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:

>>> It seems that in worst case the strict FIFO algorithm is the same
>>> as the rest of them, i.e. O(NN) where NN is the number of
>>> re-colored points. Below is an example of the shape for which I
>>> measured memory consumption for 3840x2160 image almost exactly 4x
>>> as much as for 1920x1080.
>>
>> I agree, the empirical evidence here and in my own tests is quite
>> compelling.
>
> BTW, I am no longer agree with myself about "the rest of them".
> By now, I know at least one method that is O(W*log(H)). It is even
> quite fast for majority of my test shapes. Unfortunately, [in its
> current form] it is abysmally slow (100x) for minority of tests.
> [In it's current form] it has other disadvantages as well like
> consuming non-trivial amount of memory when handling small spot in the
> big image. But that can be improved. I am less sure that worst-case
> speed can be improved enough to make it generally acceptable.
>
> I think, I said enough for you to figure out a general principle of
> this algorithm. I don't want to post code here before I try few
> improvements.

Thank you for the implied compliment. At this point I think the
probability that I will figure it out anytime soon is pretty low.

Michael S <already5chosen@yahoo.com> writes:

> On Wed, 10 Apr 2024 19:47:11 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Stack-based methods tend to do well on long skinny patterns and
>> tend to do not as well on fatter patterns such as circles or
>> squares. The fractal pattern is ideal for a stack-based method.
>> Conversely, patterns that are mostly solid shapes don't fare as
>> well under stack-based methods, at least not the ones that have
>> been posted in this thread, and also they tend to use more memory
>> in those cases.
>
> Indeed, with solid shapes it uses more memory. But at least in my
> tests on my hardware with this sort of shapes it is easily faster
> than anything else. The difference vs the best of the rest is
> especially big at 4K images on AMD Zen3 based hardware, but even on
> Intel Skylake which generally serves as equalizer between different
> algorithms, the speed advantage of 2x2 stack is significant.

This comment makes me wonder if I should post my timing results.
Maybe I will (and including an appropriate disclaimer).

I do timings over these sizes:

25 x 19
19 x 25
200 x 200
1280 x 760
760 x 1280
1920 x 1080
1080 x 1920
3840 x 2160
2160 x 3840
4096 x 4096
38400 x 21600
21600 x 38400
32767 x 32767
32768 x 32768

with these patterns:

fractal
slalom
rotated slalom
horizontal snake and vertical snake
cross in cross
donut aka ellipse with hole
entire field starting from center

If you have other patterns to suggest that would be great,
I can try to incorporate them (especially if there is
code to generate the pattern).

Patterns are allowed to include a nominal start point,
otherwise I can make an arbitrary choice and assign one.