Michael S <already5chosen@yahoo.com> writes:

> On Wed, 10 Apr 2024 19:47:11 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

>> This topic has been more interesting that I was expecting, and
>> also more challenging.
>
> That's not the first time in my practice where problems with
> simple formulation begots interesting challenges.
> Didn't Donald Knuth wrote 300 or 400 pages about sorting and
> still ended up quite far away from exhausting the topic?

In my copy of volume 3 of TAOCP, the chapter on sorting takes up
388 pages. On the other hand, only 108 pages of that deals with
what we normally think of as sorting algorithms today, and even
that part is longer than it needs to be because of Knuth's
exhaustive (and exhausting) writing style. Don Knuth would
never write a book in the style of The C Programming Language.

Michael S <already5chosen@yahoo.com> writes:

> On Wed, 10 Apr 2024 19:47:11 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> I have a strong rule against writing
>> functions more than about 60 lines long. For the problem of
>> writing an acceptably quick flood-fill algorithm, I think it would
>> at the very least be a lot of work to write code to do that while
>> still observing a limit on function length of even 100 lines, let
>> alone 60.
>
> So why not break it down to smaller pieces ?

The better algorithms I have done are long and also make liberal
use of goto's. Maybe it isn't impossible to break one or more
of these algorithms into smaller pieces, but C doesn't make it
easy.

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

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.

I'm curious to know how your 2x2 algorithm compares to my
second (longer) stack-based algorithm when run on the Zen3.
On my test hardware they are roughly comparable, depending
on size and pattern. My curiosity includes the fatter
patterns as well as the long skinny ones.

Michael S <already5chosen@yahoo.com> writes:

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

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

I test large sizes for three reasons. One, even if viewable
area is smaller, virtual displays might be much larger. Two,
to see how the algorithms scale. Three, larger areas have
relatively less influence from edge effects.

Also I have now added

275 x 25 25 x 275
400 x 300 300 x 400
640 x 480 480 x 640
1600 x 900 900 x 1600
16000 x 9000 9000 x 16000

> and I only test landscape sizes. May be, I'd add portrait option
> to see anisotropic behaviors.

I decided to do both, one, for symmetry (and there are still some
applications for portrait mode), and two, to see whether that has
an effect on behavior (indeed my latest algorithm is anisotropic,
so it is good to test the flipped sizes).

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

By "fractal" I meant fractal tree. Sorry if that was confusing.

> 4. + entire field starting from corner

I used to do that but took it out as redundant. I've added
it back now. :)

> It seems, neither of us tests the cases in which linear dimensions
> of the shape are much smaller than those of the field.

Shouldn't make a difference (for any of the algorithms shown) as
long as there is at least a 1 pixel border around the pattern.
Maybe I will add that variation (ick, a lot of work). By the
way the donut pattern already has a 1 pixel border, ie, does
not touch any edge.

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

Ahh, this is what you meant by greed. A nice set of patterns.
I wrote a variation where the "line width" as well as the
"hole width" is variable, and added a bunch of those to my
tests (so a full timing suite now runs for several hours).

On Fri, 12 Apr 2024 11:59:25 -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.
>
> I'm curious to know how your 2x2 algorithm compares to my
> second (longer) stack-based algorithm when run on the Zen3.
> On my test hardware they are roughly comparable, depending
> on size and pattern. My curiosity includes the fatter
> patterns as well as the long skinny ones.

This particular server turned off right now.
Hopefully, next Monday I would be able to test on it.
It would help if in the mean time you point me to specific post with
code.

Michael S <already5chosen@yahoo.com> writes:

> On Fri, 12 Apr 2024 11:59:25 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> I'm curious to know how your 2x2 algorithm compares to my
>> second (longer) stack-based algorithm when run on the Zen3.
>> On my test hardware they are roughly comparable, depending
>> on size and pattern. My curiosity includes the fatter
>> patterns as well as the long skinny ones.
>
> This particular server turned off right now.
> Hopefully, next Monday I would be able to test on it.
> It would help if in the mean time you point me to specific post
> with code.

Does this help? Message-ID: <8634ru3ofo.fsf@linuxsc.com>

On Sat, 13 Apr 2024 10:54:46 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Michael S <already5chosen@yahoo.com> writes:
>
> > On Fri, 12 Apr 2024 11:59:25 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >
> >> I'm curious to know how your 2x2 algorithm compares to my
> >> second (longer) stack-based algorithm when run on the Zen3.
> >> On my test hardware they are roughly comparable, depending
> >> on size and pattern. My curiosity includes the fatter
> >> patterns as well as the long skinny ones.
> >
> > This particular server turned off right now.
> > Hopefully, next Monday I would be able to test on it.
> > It would help if in the mean time you point me to specific post
> > with code.
>
> Does this help? Message-ID: <8634ru3ofo.fsf@linuxsc.com>

Yes, it is.

On Fri, 12 Apr 2024 11:59:25 -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.
>
> I'm curious to know how your 2x2 algorithm compares to my
> second (longer) stack-based algorithm when run on the Zen3.
> On my test hardware they are roughly comparable, depending
> on size and pattern. My curiosity includes the fatter
> patterns as well as the long skinny ones.

Finally found the time for speed measurements.

I tested four algorithms:
1. stack_2x2 - stack-like processing where each element is 2x2 rectangle
with Lot's wife amendment.
2. stack_timr1 - first variant of stack by Tim Rentsch
3. stack_timr2 - second variant of stack by Tim Rentsch
4. queue_timr - "take no prisoners" queue by Tim Rentsch, the one with
power-of-two circular buffer, (x,y) packed to 32 bits and inner loop
optimized for solid shapes.

Tests were run on four CPUs
1. IVB - Intel Core i7-3570 at 3700 MHz. As far as CPUs are going,
rather old thing.
2. HSW - Intel Xeon E3-1271 v3 at 4000 MHz. Only couple of years
younger than above.
3. SKC - Intel Xeon E-2176G at 4250 MHz. Significantly younger, but
microarchitecture exists since 2015.
4. ZN3 - AMD EPYC 7543P at 3700 MHz. The only one on my roaster whose
microarchitecture can be considered relatively modern.

As you can see, with exception of the oldest CPU, your 2d stack variant
is not an improvement over the first.

What surprised me after I put all results together, was a poor showing
of SKC. I can't remember any other of my microbenchmarks (and I do
plenty) were this CPU was so decisively beaten by its older cousin.

The columns are as following:
1. Shape name
2. Starting point (x,y)
3. Number of points to recolor
4. total test duration, seconds
5. time per pixel - normalized to image area, nsec
6. time per pixel - normalized to number of points to recolor, nsec

IVB,stack_2x2:
[25 x 19] * 421054
Solid square ( 12, 9) 475 0.547 2.73 2.73
Solid square ( 0, 0) 475 0.537 2.68 2.68
standing snake-like shape ( 0, 0) 259 0.522 2.61 4.79
prostrate snake-like shape ( 0, 0) 259 0.528 2.64 4.84
slalom shape ( 0, 0) 233 0.459 2.29 4.68
slalom shape(rotated) ( 0, 0) 223 0.455 2.27 4.85
cross-in-cross ( 0, 0) 403 0.515 2.57 3.04
fractal tree ( 12, 0) 247 0.469 2.34 4.51
greed(2) ( 0, 0) 367 0.558 2.79 3.61
greed(3) ( 0, 0) 283 0.463 2.31 3.89
greed(4) ( 0, 0) 223 0.399 1.99 4.25
donut ( 23, 9) 238 0.305 1.52 3.04
[200 x 200] * 5002
Solid square ( 100, 100) 40000 0.461 2.30 2.30
Solid square ( 0, 0) 40000 0.460 2.30 2.30
standing snake-like shape ( 0, 0) 20100 0.382 1.91 3.80
prostrate snake-like shape ( 0, 0) 20100 0.474 2.37 4.71
slalom shape ( 0, 0) 19802 0.435 2.17 4.39
slalom shape(rotated) ( 0, 0) 19802 0.450 2.25 4.54
cross-in-cross ( 0, 0) 39216 0.470 2.35 2.40
fractal tree ( 99, 0) 18674 0.432 2.16 4.62
greed(2) ( 0, 0) 30000 0.458 2.29 3.05
greed(3) ( 0, 0) 22311 0.413 2.06 3.70
greed(4) ( 0, 0) 17500 0.348 1.74 3.98
donut ( 199, 100) 25830 0.315 1.57 2.44
[1280 x 720] * 218
Solid square ( 640, 360) 921600 0.450 2.24 2.24
Solid square ( 0, 0) 921600 0.450 2.24 2.24
standing snake-like shape ( 0, 0) 461160 0.371 1.85 3.69
prostrate snake-like shape ( 0, 0) 461440 0.469 2.33 4.66
slalom shape ( 0, 0) 460082 0.437 2.18 4.36
slalom shape(rotated) ( 0, 0) 460800 0.448 2.23 4.46
cross-in-cross ( 0, 0) 917616 0.452 2.25 2.26
fractal tree ( 639, 0) 445860 0.460 2.29 4.73
greed(2) ( 0, 0) 691200 0.468 2.33 3.11
greed(3) ( 0, 0) 512160 0.406 2.02 3.64
greed(4) ( 0, 0) 403200 0.344 1.71 3.91
donut (1279, 360) 655856 0.326 1.62 2.28
[1920 x 1080] * 98
Solid square ( 960, 540) 2073600 0.453 2.23 2.23
Solid square ( 0, 0) 2073600 0.457 2.25 2.25
standing snake-like shape ( 0, 0) 1037340 0.374 1.84 3.68
prostrate snake-like shape ( 0, 0) 1037760 0.474 2.33 4.66
slalom shape ( 0, 0) 1036800 0.443 2.18 4.36
slalom shape(rotated) ( 0, 0) 1036800 0.452 2.22 4.45
cross-in-cross ( 0, 0) 2067616 0.457 2.25 2.26
fractal tree ( 959, 0) 1034612 0.453 2.23 4.47
greed(2) ( 0, 0) 1555200 0.450 2.21 2.95
greed(3) ( 0, 0) 1152000 0.407 2.00 3.61
greed(4) ( 0, 0) 907200 0.346 1.70 3.89
donut (1919, 540) 1477788 0.326 1.60 2.25
[3840 x 2160] * 26
Solid square (1920,1080) 8294400 0.500 2.32 2.32
Solid square ( 0, 0) 8294400 0.539 2.50 2.50
standing snake-like shape ( 0, 0) 4148280 0.449 2.08 4.16
prostrate snake-like shape ( 0, 0) 4149120 0.746 3.46 6.92
slalom shape ( 0, 0) 4147200 0.703 3.26 6.52
slalom shape(rotated) ( 0, 0) 4147200 0.537 2.49 4.98
cross-in-cross ( 0, 0) 8282416 0.518 2.40 2.41
fractal tree (1919, 0) 4135652 0.514 2.38 4.78
greed(2) ( 0, 0) 6220800 0.533 2.47 3.30
greed(3) ( 0, 0) 4608000 0.468 2.17 3.91
greed(4) ( 0, 0) 3628800 0.386 1.79 4.09
donut (3839,1080) 5919706 0.356 1.65 2.31

IVB,stack_timr1:
[25 x 19] * 421054
Solid square ( 12, 9) 475 1.132 5.66 5.66
Solid square ( 0, 0) 475 1.171 5.85 5.85
standing snake-like shape ( 0, 0) 259 0.724 3.62 6.64
prostrate snake-like shape ( 0, 0) 259 0.712 3.56 6.53
slalom shape ( 0, 0) 233 0.632 3.16 6.44
slalom shape(rotated) ( 0, 0) 223 0.632 3.16 6.73
cross-in-cross ( 0, 0) 403 0.931 4.65 5.49
fractal tree ( 12, 0) 247 0.537 2.68 5.16
greed(2) ( 0, 0) 367 0.866 4.33 5.60
greed(3) ( 0, 0) 283 0.724 3.62 6.08
greed(4) ( 0, 0) 223 0.618 3.09 6.58
donut ( 23, 9) 238 0.632 3.16 6.31
[200 x 200] * 5002
Solid square ( 100, 100) 40000 0.764 3.82 3.82
Solid square ( 0, 0) 40000 0.759 3.79 3.79
standing snake-like shape ( 0, 0) 20100 0.389 1.94 3.87
prostrate snake-like shape ( 0, 0) 20100 0.400 2.00 3.98
slalom shape ( 0, 0) 19802 0.388 1.94 3.92
slalom shape(rotated) ( 0, 0) 19802 0.388 1.94 3.92
cross-in-cross ( 0, 0) 39216 0.763 3.81 3.89
fractal tree ( 99, 0) 18674 0.372 1.86 3.98
greed(2) ( 0, 0) 30000 0.591 2.95 3.94
greed(3) ( 0, 0) 22311 0.445 2.22 3.99
greed(4) ( 0, 0) 17500 0.345 1.72 3.94
donut ( 199, 100) 25830 0.517 2.58 4.00
[1280 x 720] * 218
Solid square ( 640, 360) 921600 0.793 3.95 3.95
Solid square ( 0, 0) 921600 0.868 4.32 4.32
standing snake-like shape ( 0, 0) 461160 0.420 2.09 4.18
prostrate snake-like shape ( 0, 0) 461440 0.441 2.20 4.38
slalom shape ( 0, 0) 460082 0.434 2.16 4.33
slalom shape(rotated) ( 0, 0) 460800 0.429 2.14 4.27
cross-in-cross ( 0, 0) 917616 0.801 3.99 4.00
fractal tree ( 639, 0) 445860 0.389 1.94 4.00
greed(2) ( 0, 0) 691200 0.614 3.06 4.07
greed(3) ( 0, 0) 512160 0.424 2.11 3.80
greed(4) ( 0, 0) 403200 0.334 1.66 3.80
donut (1279, 360) 655856 0.572 2.85 4.00
[1920 x 1080] * 98
Solid square ( 960, 540) 2073600 0.793 3.90 3.90
Solid square ( 0, 0) 2073600 0.909 4.47 4.47
standing snake-like shape ( 0, 0) 1037340 0.415 2.04 4.08
prostrate snake-like shape ( 0, 0) 1037760 0.442 2.18 4.35
slalom shape ( 0, 0) 1036800 0.431 2.12 4.24
slalom shape(rotated) ( 0, 0) 1036800 0.425 2.09 4.18
cross-in-cross ( 0, 0) 2067616 0.843 4.15 4.16
fractal tree ( 959, 0) 1034612 0.395 1.94 3.90
greed(2) ( 0, 0) 1555200 0.614 3.02 4.03
greed(3) ( 0, 0) 1152000 0.430 2.12 3.81
greed(4) ( 0, 0) 907200 0.341 1.68 3.84
donut (1919, 540) 1477788 0.571 2.81 3.94
[3840 x 2160] * 26
Solid square (1920,1080) 8294400 0.923 4.28 4.28
Solid square ( 0, 0) 8294400 1.109 5.14 5.14
standing snake-like shape ( 0, 0) 4148280 0.521 2.42 4.83
prostrate snake-like shape ( 0, 0) 4149120 1.186 5.50 10.99
slalom shape ( 0, 0) 4147200 0.938 4.35 8.70
slalom shape(rotated) ( 0, 0) 4147200 0.545 2.53 5.05
cross-in-cross ( 0, 0) 8282416 0.999 4.63 4.64
fractal tree (1919, 0) 4135652 0.433 2.01 4.03
greed(2) ( 0, 0) 6220800 0.738 3.42 4.56
greed(3) ( 0, 0) 4608000 0.529 2.45 4.42
greed(4) ( 0, 0) 3628800 0.417 1.93 4.42
donut (3839,1080) 5919706 0.666 3.09 4.33

Michael S <already5chosen@yahoo.com> writes:

[...]

> Finally found the time for speed measurements. [...]

I got these. Thank you.

The format used didn't make it easy to do any automated
processing. I was able to get around that, although it
would have been nicer if that had been easier.

The results you got are radically different than my own,
to the point where I wonder if there is something else
going on.

Considering that, since I now have no way of doing any
useful measuring, it seems there is little point in any
further development or investigation on my part. It's
been fun, even if ultimately inconclusive.

On Wed, 17 Apr 2024 10:47:25 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Michael S <already5chosen@yahoo.com> writes:
>
> [...]
>
> > Finally found the time for speed measurements. [...]
>
> I got these. Thank you.
>
> The format used didn't make it easy to do any automated
> processing. I was able to get around that, although it
> would have been nicer if that had been easier.
>
> The results you got are radically different than my own,
> to the point where I wonder if there is something else
> going on.
>

What are your absolute result?
Are they much faster, much slower or similar to mine?
Also it would help if you find out characteristics of your test
hardware.

> Considering that, since I now have no way of doing any
> useful measuring, it seems there is little point in any
> further development or investigation on my part. It's
> been fun, even if ultimately inconclusive.

I am still interested in combination of speed that does not suck
with O(N) worst-case memory footprint.
I already have couple of variants of the former, but so far they are
all unreasonably slow - ~5 times slower than the best.

Michael S <already5chosen@yahoo.com> writes:

> On Wed, 17 Apr 2024 10:47:25 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:
>>
>> [...]
>>
>>> Finally found the time for speed measurements. [...]
>>
>> I got these. Thank you.
>>
>> The format used didn't make it easy to do any automated
>> processing. I was able to get around that, although it
>> would have been nicer if that had been easier.
>>
>> The results you got are radically different than my own,
>> to the point where I wonder if there is something else
>> going on.
>
> What are your absolute result?
> Are they much faster, much slower or similar to mine?
> Also it would help if you find out characteristics of your
> test hardware.

I think trying to look at those wouldn't tell me anything
helpful. Too many unknowns. And still no way to test or
measure any changes to the various algorithms.

>> Considering that, since I now have no way of doing any
>> useful measuring, it seems there is little point in any
>> further development or investigation on my part. It's
>> been fun, even if ultimately inconclusive.
>
> I am still interested in combination of speed that does
> not suck with O(N) worst-case memory footprint.
> I already have couple of variants of the former,

Did you mean you some algorithms whose worst case memory
behavior is strictly less than O( total number of pixels )?

I think it would be helpful to adopt a standard terminology
where the pixel field is of size M x N, otherwise I'm not
sure what O(N) refers to.

> but so
> far they are all unreasonably slow - ~5 times slower than
> the best.

I'm no longer working on the problem but I'm interested to
hear what you come up with.

On Fri, 19 Apr 2024 14:59:20 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Michael S <already5chosen@yahoo.com> writes:
>
> > On Wed, 17 Apr 2024 10:47:25 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >
> >> Michael S <already5chosen@yahoo.com> writes:
> >>
> >> [...]
> >>
> >>> Finally found the time for speed measurements. [...]
> >>
> >> I got these. Thank you.
> >>
> >> The format used didn't make it easy to do any automated
> >> processing. I was able to get around that, although it
> >> would have been nicer if that had been easier.
> >>
> >> The results you got are radically different than my own,
> >> to the point where I wonder if there is something else
> >> going on.
> >
> > What are your absolute result?
> > Are they much faster, much slower or similar to mine?
> > Also it would help if you find out characteristics of your
> > test hardware.
>
> I think trying to look at those wouldn't tell me anything
> helpful. Too many unknowns. And still no way to test or
> measure any changes to the various algorithms.
>

Frankly, I don't understand.
If you have troubles with testing on shared hardware then you can
always test on the hardware that you own and has full control.
Even if it is a little old, the trends tend to be the same. At least I
clearly see the same trends on my almost 12 y.o. home PC and on
relatively modern EPYC3.

> >> Considering that, since I now have no way of doing any
> >> useful measuring, it seems there is little point in any
> >> further development or investigation on my part. It's
> >> been fun, even if ultimately inconclusive.
> >
> > I am still interested in combination of speed that does
> > not suck with O(N) worst-case memory footprint.
> > I already have couple of variants of the former,
>
> Did you mean you some algorithms whose worst case memory
> behavior is strictly less than O( total number of pixels )?
>
> I think it would be helpful to adopt a standard terminology
> where the pixel field is of size M x N, otherwise I'm not
> sure what O(N) refers to.
>

No, I mean O(max(M,N)) plus possibly some logarithmic component that
loses significance when images grow bigger.
More so, if bounding rectangle of the shape is A x B then I'd like
memory requirements to be O(max(A,B)), but so far it does not appear to
be possible, or at least not possible without significant complications
and further slowdown. So, as an intermediate goal I am willing to
accept that allocation would be O(max(M,N)). but amount of touched
memory is O(max(A,B)).

> > but so
> > far they are all unreasonably slow - ~5 times slower than
> > the best.
>
> I'm no longer working on the problem but I'm interested to
> hear what you come up with.

On Sat, 20 Apr 2024 21:10:23 +0300
Michael S <already5chosen@yahoo.com> wrote:

> On Fri, 19 Apr 2024 14:59:20 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
> >
> > Did you mean you some algorithms whose worst case memory
> > behavior is strictly less than O( total number of pixels )?
> >
> > I think it would be helpful to adopt a standard terminology
> > where the pixel field is of size M x N, otherwise I'm not
> > sure what O(N) refers to.
> >
>
> No, I mean O(max(M,N)) plus possibly some logarithmic component that
> loses significance when images grow bigger.
> More so, if bounding rectangle of the shape is A x B then I'd like
> memory requirements to be O(max(A,B)), but so far it does not appear
> to be possible, or at least not possible without significant
> complications and further slowdown. So, as an intermediate goal I am
> willing to accept that allocation would be O(max(M,N)). but amount of
> touched memory is O(max(A,B)).
>
> > > but so
> > > far they are all unreasonably slow - ~5 times slower than
> > > the best.
> >
> > I'm no longer working on the problem but I'm interested to
> > hear what you come up with.
>
>

Here is what I had in mind.
I tried to optimize as little as I can in order to make it as simple
as I can. Unfortunately, I am not particularly good at it, so, code
still contains few unnecessary "tricks" that make understanding a
little harder.
The code uses VLA and recursion for the same purpose of making it less
tricky.
If desired, the memory footprint could be easily reduced by factor of 8
through use of packed bit arrays instead arrays of _Bool.

Even in this relatively crude form for majority of shapes this code is
blazingly fast.
Unfortunately, in the worst case (both 'slalom' shapes) an execution
time is O(max(A,B)**3) which makes it unfit as general-purpose routine.
At the moment I don't see a solution for this problem. Overall, it's
probably a dead end.

#include <stddef.h>
#include <string.h>

typedef unsigned char Color;

struct floodfill4_state {
Color* image;
ptrdiff_t width;
_Bool *l_todo, *r_todo, *u_todo, *d_todo;
int nx, ny;
int x, y;
Color old_color, new_color;
};

enum {
more_r = 1, more_l = 2, more_d = 4, more_u = 8,
more_lr = more_r+more_l, more_ud=more_u+more_d,
};

static
int floodfill4_expand_lr(struct floodfill4_state* s, int exp_x,
_Bool* src_todo, _Bool* exp_todo, int lr);
static
int floodfill4_expand_ud(struct floodfill4_state* s, int exp_x,
_Bool* src_todo, _Bool* exp_todo, int ud);

int floodfill4(Color* image, int width, int height, int x, int y,
Color old_color, Color new_color)
{ if (width <= 0 || height <= 0)
return 0;

if (x < 0 || x >= width || y < 0 || y >= height)
return 0;

Color* beg = &image[(size_t)width*y+x];
if (*beg != old_color)
return 0;

*beg = new_color;
// Color* last_row = &image[(size_t)width*(height-1)];
_Bool lr_todo[2][height];
_Bool ud_todo[2][width];

struct floodfill4_state s = {
.image = beg,
.width = width,
.l_todo = &lr_todo[0][y],
.r_todo = &lr_todo[1][y],
.u_todo = &ud_todo[0][x],
.d_todo = &ud_todo[1][x],
.x = 0, .y = 0, .nx = 1, .ny = 1,
.old_color = old_color,
.new_color = new_color,
};
*s.l_todo = *s.r_todo = *s.u_todo = *s.d_todo = 1;

// expansion loop
for (int more = more_lr+more_ud; more != 0;) {
if (more & more_lr) {
_Bool exp_todo[s.ny];
do {
if (more & more_r) {
while (x+s.nx != width) {
// try to expand to the right
s.x = s.nx-1;
int ret = floodfill4_expand_lr(&s, s.nx, s.r_todo,
exp_todo, more_r);
if (!ret)
break;
more |= ret;
++s.nx;
}
more &= ~more_r;
}
if (more & more_l) {
while (x != 0) {
// try to expand to the left
s.x = 0;
int ret = floodfill4_expand_lr(&s, -1, s.l_todo, exp_todo,
more_l);
if (!ret)
break;
more |= ret;
++s.nx;
--s.image;
--s.u_todo;
--s.d_todo;
--x;
}
more &= ~more_l;
}
} while (more & more_lr);
}

if (more & more_ud) {
_Bool exp_todo[s.nx];
do {
if (more & more_d) {
while (y+s.ny != height) {
// try to expand down
s.y = s.ny-1;
int ret = floodfill4_expand_ud(&s, s.ny, s.d_todo,
exp_todo, more_d);
if (!ret)
break;
more |= ret;
++s.ny;
}
more &= ~more_d;
}
if (more & more_u) {
while (y != 0) {
// try to expand up
s.y = 0;
int ret = floodfill4_expand_ud(&s, -1, s.u_todo, exp_todo,
more_u);
if (!ret)
break;
more |= ret;
++s.ny;
s.image -= s.width;
--s.l_todo;
--s.r_todo;
--y;
}
more &= ~more_u;
}
} while (more & more_ud);
}
}
return 1;
}

// floodfill4_core - floodfill4 recursively in divide and conquer
fashion
// s.*-todo arrays initialized by caller. floodfill4_core sets values
// in that indicate need for further action, but never clears values
// that were already set
static void floodfill4_core(const struct floodfill4_state* arg)
{ const int nx = arg->nx;
const int ny = arg->ny;
if (nx+ny == 2) { // nx==ny==1
*arg->l_todo = *arg->r_todo = *arg->u_todo = *arg->d_todo = 1;
*arg->image = arg->new_color;
return;
}

struct floodfill4_state args[2];
args[0] = args[1] = *arg;
if (nx > ny) {
// split vertically
_Bool todo[2][ny];
const int hx = nx / 2;

args[0].r_todo = todo[0];
args[0].nx = hx;

args[1].image += hx;
args[1].l_todo = todo[1];
args[1].u_todo += hx;
args[1].d_todo += hx;
args[1].nx = nx-hx;

int todo_i;
int x0 = arg->x;
if (x0 < hx) { // update left field
memset(todo[0], 0, ny*sizeof(todo[0][0]));
floodfill4_core(&args[0]);
todo_i = 0;
} else { // update right field
memset(todo[1], 0, ny*sizeof(todo[0][0]));
args[1].x = x0 - hx;
floodfill4_core(&args[1]);
todo_i = 1;
}

args[0].x = hx-1;
args[1].x = 0;
for (;;) {
// look for contact points on destination edge
_Bool *todo_src = todo[todo_i];
Color *edge_dst = &arg->image[hx-todo_i];
int y;
for (y = 0; y < ny; edge_dst += arg->width, ++y) {
if (todo_src[y] && *edge_dst == arg->old_color) // contact found
break;
}
if (y == ny)
break;

todo_i = 1 - todo_i;
memset(todo[todo_i], 0, ny*sizeof(todo[0][0]));
do {
args[todo_i].y = y;
floodfill4_core(&args[todo_i]);
edge_dst += arg->width;
for (y = y+1; y < ny; edge_dst += arg->width, ++y) {
if (todo_src[y] && *edge_dst == arg->old_color) // contact
found
break;
}
} while (y < ny);
}
} else { // ny >= nx
// split horizontally
_Bool todo[2][nx];
const int hy = ny / 2;
Color* edge = &arg->image[arg->width*hy];

args[0].d_todo = todo[0];
args[0].ny = hy;

args[1].image = edge;
args[1].u_todo = todo[1];
args[1].l_todo += hy;
args[1].r_todo += hy;
args[1].ny = ny-hy;

int todo_i;
int y0 = arg->y;
if (y0 < hy) { // update up field
memset(todo[0], 0, nx*sizeof(todo[0][0]));
floodfill4_core(&args[0]);
todo_i = 0;
} else { // update down field
args[1].y = y0 - hy;
memset(todo[1], 0, nx*sizeof(todo[0][0]));
floodfill4_core(&args[1]);
todo_i = 1;
}

args[0].y = hy-1;
args[1].y = 0;
for (;;) {
// look for contact points on destination edge
_Bool *todo_src = todo[todo_i];
Color *edge_dst = todo_i ? edge - arg->width : edge;
int x;
for (x = 0; x < nx; ++x) {
if (todo_src[x] && edge_dst[x] == arg->old_color) // contact
found
break;
}
if (x == nx)
break;