Re: filling area by color atack safety

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
}