Path: ...!3.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Michael S <already5chosen@yahoo.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Mon, 25 Mar 2024 01:28:44 +0300
Organization: A noiseless patient Spider
Lines: 197
Message-ID: <20240325012844.0000685b@yahoo.com>
References: <ut3669$21eur$1@i2pn2.org>
	<86h6h3nvyz.fsf@linuxsc.com>
	<865xxiok09.fsf@linuxsc.com>
	<20240319131842.00002138@yahoo.com>
	<utbuk3$qed7$1@dont-email.me>
	<20240319191859.00004bc8@yahoo.com>
	<86bk79m10l.fsf@linuxsc.com>
	<20240324202758.00001b75@yahoo.com>
	<86frwfjs0n.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 24 Mar 2024 23:28:46 +0100
Injection-Info: dont-email.me; posting-host="f2656d1f9feae47f01e62012b9105a2c";
	logging-data="661105"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+s3/SSvh786TR/R3pqJarUgFomLP+pRJM="
Cancel-Lock: sha1:/YV71c1tqc2TcwXYel9VGKPzPLo=
X-Newsreader: Claws Mail 4.1.1 (GTK 3.24.34; x86_64-w64-mingw32)
Bytes: 7380

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) {
========== REMAINDER OF ARTICLE TRUNCATED ==========