Path: ...!weretis.net!feeder6.news.weretis.net!feeder8.news.weretis.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: Wed, 20 Mar 2024 11:54:16 +0200
Organization: A noiseless patient Spider
Lines: 216
Message-ID: <20240320115416.00001ab5@yahoo.com>
References: <ut3669$21eur$1@i2pn2.org>
	<86h6h3nvyz.fsf@linuxsc.com>
	<865xxiok09.fsf@linuxsc.com>
	<20240319131842.00002138@yahoo.com>
	<86o7b9ms7d.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: quoted-printable
Injection-Info: dont-email.me; posting-host="92be935da1beff2666dcf9ddcb3e2080";
	logging-data="1476478"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18Wc8bSX+3p2JIgiNUaZSSwaxf9ZgYH05A="
Cancel-Lock: sha1:4WpqMmHtGjGHxw7IR2nKdHRBetg=
X-Newsreader: Claws Mail 3.19.1 (GTK+ 2.24.33; x86_64-w64-mingw32)
Bytes: 8524

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

> Michael S <already5chosen@yahoo.com> writes:
>=20
> > On Mon, 18 Mar 2024 22:42:14 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> > =20
> >> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> >>
> >> [...]
> >>
> >> Here is the refinement that uses a resizing rather than
> >> fixed-size buffer.
> >>
> >>
> >> typedef     unsigned char               Color;
> >> typedef     unsigned int                UI;
> >> typedef     struct { UI x, y; }         Point;
> >> typedef     unsigned int                Index;
> >>
> >> static  _Bool  change_it( UI w, UI h, Color [w][h], Point, Color,
> >> Color );
> >>
> >> void
> >> fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old,
> >> Color new ){ static const Point deltas[4] =3D  {  {1,0}, {0,1},
> >> {-1,0}, {0,-1},  };  UI     k      =3D  0;
> >>   UI     n      =3D  17;
> >>   Point *todo   =3D  malloc( n * sizeof *todo );
> >>
> >>     if(  todo  &&  change_it( w, h, pixels, p0, old, new )  )
> >> todo[k++] =3D p0;
> >>
> >>     while(  k > 0  ){
> >>         Index j =3D n-k;
> >>         memmove( todo + j, todo, k * sizeof *todo );
> >>         k =3D 0;
> >>
> >>         while(  j < n  ){
> >>             Point p =3D todo[ j++ ];
> >>             for(  Index i =3D 0;  i < 4;  i++  ){
> >>                 Point q =3D { p.x + deltas[i].x, p.y + deltas[i].y };
> >>                 if(  ! change_it( w, h, pixels, q, old, new )  )
> >> continue;  todo[ k++ ] =3D q;
> >>             }
> >>
> >>             if(  j-k < 3  ){
> >>                 Index new_n =3D n+n/4;
> >>                 Index new_j =3D new_n - (n-j);
> >>                 Point *t =3D realloc( todo, new_n * sizeof *t );
> >>                 if(  !t  ){  k =3D 0;  break;  }
> >>                 memmove( t + new_j, t + j, (n-j) * sizeof *t );
> >>                 todo =3D t,  n =3D new_n,  j =3D new_j;
> >>             }
> >>         }
> >>     }
> >>
> >>     free( todo );
> >> }
> >>
> >> _Bool
> >> change_it( UI w, UI h, Color pixels[w][h], Point p, Color old,
> >> Color new ){ if(  p.x >=3D w  ||  p.y >=3D h  ||  pixels[p.x][p.y] !=3D
> >> old  ) return  0;  return  pixels[p.x][p.y] =3D new,  1;
> >> } =20
> >
> > This variant is significantly slower than Malcolm's.
> > 2x slower for solid rectangle, 6x slower for snake shape. =20
>=20
> Slower with some shapes, faster in others.

In my small test suit I found no cases where this specific code is
measurably faster than code of Malcolm.
I did find one case in which they are approximately equal. I call it
"slalom shape" and it's more or less designed to be the worst case for
algorithms that are trying to speed themselves by take advantage of
straight lines.
The slalom shape is generated by following code:

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

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

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

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

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

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

> In any case
> the code was written for clarity of presentation, with
> no attention paid to low-level performance.
>

Yes, your code is easy to understand. Could have been easier still if
persistent indices had more meaningful names.
In other post I showed optimized variant of your algorithm:
 - 4-neighbors loop unrolled. Majority of the speed up come not from
unrolling itself, but from specialization of in-rectangle check
enabled by unroll.=20
 - Todo queue implemented as circular buffer.=20
 - Initial size of queue increased.
This optimized variant is more competitive with 'line-grabby'
algorithms in filling solid shapes and faster than them in 'slalom'
case.

Generally, I like your algorithm.=20
It was surprising for me that queue can work better than stack, my
intuition suggested otherwise, but facts are facts.

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

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

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


> > Besides, I don't think that use of VLA in library code is a good
> > idea. VLA is optional in latest C standards.  And incompatible with
> > C++. =20
>=20
> The code uses a variably modified type, not a variable length
> array.=20
========== REMAINDER OF ARTICLE TRUNCATED ==========