Path: ...!news.mixmin.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, 18 Mar 2024 14:40:07 +0200
Organization: A noiseless patient Spider
Lines: 135
Message-ID: <20240318144007.00005e71@yahoo.com>
References: <ut3669$21eur$1@i2pn2.org>
	<ut4020$2s8ov$1@dont-email.me>
	<87wmq2jn7s.fsf@bsb.me.uk>
	<ut4ba7$2uits$1@dont-email.me>
	<SqlJN.144025$CYpe.59290@fx40.iad>
	<ut4tsj$3291j$1@dont-email.me>
	<ut4vf6$32n1u$1@dont-email.me>
	<ut7j8h$3mt70$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Injection-Info: dont-email.me; posting-host="e438cc7fdcf3a4669168787da7dbc3da";
	logging-data="3825776"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/RRs6bGOiOVLhhxyAGAPJKFHSL0+gGCkI="
Cancel-Lock: sha1:GSls15pPUsEtFIAFguZ6Cq47DV8=
X-Newsreader: Claws Mail 3.19.1 (GTK+ 2.24.33; x86_64-w64-mingw32)
Bytes: 5136

On Sun, 17 Mar 2024 13:19:29 -0700
"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> wrote:

> On 3/16/2024 1:29 PM, Chris M. Thomasson wrote:
> > On 3/16/2024 1:02 PM, Malcolm McLean wrote: =20
> >> On 16/03/2024 18:21, Scott Lurndal wrote: =20
> >>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: =20
> >>>> On 16/03/2024 13:55, Ben Bacarisse wrote: =20
> >>>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
> >>>>> =20
> >>>>>> Recursion make programs harder to reason about and prove
> >>>>>> correct. =20
> >>>>>
> >>>>> Are you prepared to offer any evidence to support this
> >>>>> astonishing statement or can we just assume it's another
> >>>>> Malcolmism?=20
> >>>>
> >>>> Example given. A recursive algorithm which is hard to reason
> >>>> about and =20
> >>>
> >>> Perhaps hard for _you_ to reason about.=C2=A0 That doesn't
> >>> generalize to every other programmer that might read that
> >>> code.
> >>>
> >>> =20
> >> =C2=A0From experience this one blows the stack, but not always.
> >> Sometimes it's OK to use. =20
> >=20
> > Blowing the stack is not good at all. However, sometimes, I
> > consider a recursive algorithm easier to understand. So, I build it
> > first... Get it working, _then_ think about an iterative
> > solution... =20
>=20
> Gaining the iterative solution from a working recursive solution is
> the fun part!
>=20
> :^)
>=20

I did.
After a bit of polish applied to corners (on x86-64) it consumes
approximately 60 times less extra memory than recursive variant of
Malcolm and is approximately 2.5 faster than non-naive recursion.
But it still decisively slower than Malcolm's non-recursive code:
~4x for 'snake' shape, ~2x for solid rectangle.
Malcolm's algorithm is simply better than recursive one.
Most likely because it visits already re-colored pixels less often.

For those interested, here is 'explicit stack' variant of recursive
algorithm:


int floodfill_r_explicite_stack(
  unsigned char *grey,
  int width, int height,
  int x, int y,
  unsigned char target, unsigned char dest)
{
  if (x < 0 || x >=3D width || y < 0 || y >=3D height)
    return 0;
  if (grey[y*width+x] !=3D target)
    return 0;

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

  enum { ST_LEFT, ST_RIGHT, ST_UP, ST_DOWN, };
  for (;;) {
    do {
      if (grey[y*width+x] !=3D target)
        break; // back to caller

      grey[y*width+x] =3D dest;
      x -=3D 1;
      // push state to stack
      if (sp =3D=3D end_stack) { // allocate more stack space
        ptrdiff_t old_sz =3D sp-stack;
        ptrdiff_t new_sz =3D old_sz + old_sz/2;
        stack =3D realloc(stack, new_sz*sizeof(*stack));
        if (!stack)
          return -1;
        sp =3D &stack[old_sz];
        end_stack  =3D &stack[new_sz];
      }
      *sp++ =3D ST_LEFT; // recursive call
    } while (x >=3D 0);

    for (;;) {
      if (sp =3D=3D stack) { // we are back at top level
        free(stack);
        return 1; // done
      }

      char state =3D *--sp; // pop stack (back to caller)
      switch (state) {
        case ST_LEFT:
          x +=3D 2;
          if (x < width) {
            *sp++ =3D ST_RIGHT; // recursive call
            break;
          }
          // fall throw

        case ST_RIGHT:
          x -=3D 1;
          y -=3D 1;
          if (y >=3D 0) {
            *sp++ =3D ST_UP; // recursive call
            break;
          }
          // fall throw

        case ST_UP:
          y +=3D 2;
          if (y < height) {
            *sp++ =3D ST_DOWN; // recursive call
            break;
          }
          // fall throw

        case ST_DOWN:
          y -=3D 1;
          continue;  // back to caller
      }
      break;
    }
  }
}