Path: ...!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 - worst memory size
Date: Fri, 12 Apr 2024 11:13:05 +0300
Organization: A noiseless patient Spider
Lines: 94
Message-ID: <20240412111305.00004bf2@yahoo.com>
References: <ut3669$21eur$1@i2pn2.org>
	<86h6h3nvyz.fsf@linuxsc.com>
	<865xxiok09.fsf@linuxsc.com>
	<20240319131842.00002138@yahoo.com>
	<86o7b9ms7d.fsf@linuxsc.com>
	<20240320115416.00001ab5@yahoo.com>
	<86zfusltwp.fsf@linuxsc.com>
	<20240324193352.000062e9@yahoo.com>
	<86jzlrk0f6.fsf@linuxsc.com>
	<20240405173033.00006145@yahoo.com>
	<868r1k1uq8.fsf@linuxsc.com>
	<20240411152033.00007173@yahoo.com>
	<86o7afyxnk.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 12 Apr 2024 10:13:12 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="37f308e7a2375b7c2eef0e4b685e814c";
	logging-data="2361407"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+TfQBjy7plKIr2ABhHp1a/adz74kNbeEk="
Cancel-Lock: sha1:fG9/E5cuUzL4aEmOvN1amCLnpF0=
X-Newsreader: Claws Mail 4.1.1 (GTK 3.24.34; x86_64-w64-mingw32)
Bytes: 4406

On Thu, 11 Apr 2024 22:09:51 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

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

I didn't went that far up (ended at 4K) and I only test landscape sizes.
May be, I'd add portrait option to see anisotropic behaviors.
For bigger sizes, correctness is interesting, speed - not so much, since
they are unlikely to be edited in interactive manner.

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

My suit is about the same with following exceptions:
1. I didn't add donut yet 
2. + 3 greeds with cell size 2, 3 and 4
3. + fractal tree
4. + entire field starting from corner
It seems, neither of us tests the cases in which linear dimensions of
the shape are much smaller than those of the field.

static void make_grid(
  unsigned char *image,
  int width, int height,
  unsigned char background_c,
  unsigned char pen_c, int cell_sz)
{
  for (int y = 0; y < height; ++y) {
    unsigned char* p = &image[y*width];
    if (y % cell_sz == 0) {
      memset(p, pen_c, width);
    } else {
      for (int x = 0; x < width; ++x)
        p[x] = x % cell_sz ? background_c : pen_c;
    }
  }
}