From Newsgroup: comp.lang.c

On Sun, 24 Mar 2024 10:24:45 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Michael S <already5chosen@yahoo.com> writes:

On Wed, 20 Mar 2024 10:01:10 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Michael S <already5chosen@yahoo.com> writes:

[...]

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

Using a stack is like a depth-first search, and a queue is like a
breadth-first search. For a pixel field of size N x N, doing a
depth-first search can lead to memory usage of order N**2,
whereas a breadth-first search has a "frontier" at most O(N).
Another way to think of it is that breadth-first gets rid of
visited nodes as fast as it can, but depth-first keeps them
around for a long time when everything is reachable from anywhere
(as will be the case in large simple reasons).

For my test cases the FIFO depth of your algorithm never exceeds min(width,height)*2+2. I wonder if existence of this or similar
limit can be proven theoretically.

I believe it is possible to prove the strict FIFO algorithm is
O(N) for an N x N pixel field, but I haven't tried to do so in
any rigorous way, nor do I know what the constant is. It does
seem to be larger than 2.

It seems that in worst case the strict FIFO algorithm is the same as
the rest of them, i.e. O(NN) where NN is the number of re-colored
points. Below is an example of the shape for which I measured memory consumption for 3840x2160 image almost exactly 4x as much as for
1920x1080.

static void make_fractal_tree_recursive(
unsigned char* image,
int width,
int nx,
int ny,
unsigned char pen_c)
{
if (nx < 3 && ny < 3) {
// small rectangle - solid fill
for (int y = 0; y < ny; ++y)
for (int x = 0; x < nx; ++x)
image[width*y+x] = pen_c;
return;
}
if (nx >= ny) {
int xc = (nx-1)/2;
if (xc - 1 > 0) { // left sub-plot
make_fractal_tree_recursive(image, width, xc - 1, ny, pen_c);
}
if (xc + 2 < nx) { // right sub-plot
make_fractal_tree_recursive(&image[xc+2], width,
nx - (xc + 2), ny, pen_c);
}
// draw vertical cross
for (int y = 0; y < ny; ++y)
image[width*y+xc] = pen_c;
int yc = (ny-1)/2;
image[width*yc+xc-1] = pen_c;
image[width*yc+xc+1] = pen_c;
} else {
int yc = (ny-1)/2;
if (yc - 1 > 0) { // upper sub-plot
make_fractal_tree_recursive(image, width, nx, yc - 1, pen_c);
}
if (yc + 2 < ny) { // lower sub-plot
make_fractal_tree_recursive(&image[(yc+2)*width], width, nx,
ny -(yc + 2), pen_c);
}
// draw horizontal cross
for (int x = 0; x < nx; ++x)
image[width*yc+x] = pen_c;
int xc = (nx-1)/2;
image[width*(yc-1)+xc] = pen_c;
image[width*(yc+1)+xc] = pen_c;
}
}

static void make_fractal_tree(
unsigned char* image,
int width,
int height,
unsigned char background_c,
unsigned char pen_c)
{
memset(image, background_c, width*height);
make_fractal_tree_recursive(image, width, width, height, pen_c);
}


--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

Michael S <already5chosen@yahoo.com> writes:

On Sun, 24 Mar 2024 10:24:45 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Michael S <already5chosen@yahoo.com> writes:

On Wed, 20 Mar 2024 10:01:10 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Michael S <already5chosen@yahoo.com> writes:

[...]

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

Using a stack is like a depth-first search, and a queue is like a
breadth-first search. For a pixel field of size N x N, doing a
depth-first search can lead to memory usage of order N**2,
whereas a breadth-first search has a "frontier" at most O(N).
Another way to think of it is that breadth-first gets rid of
visited nodes as fast as it can, but depth-first keeps them
around for a long time when everything is reachable from anywhere
(as will be the case in large simple reasons).

For my test cases the FIFO depth of your algorithm never exceeds
min(width,height)*2+2. I wonder if existence of this or similar
limit can be proven theoretically.

I believe it is possible to prove the strict FIFO algorithm is
O(N) for an N x N pixel field, but I haven't tried to do so in
any rigorous way, nor do I know what the constant is. It does
seem to be larger than 2.

Before I do anything else I should correct a bug in my earlier
FIFO algorithm. The initialization of the variable jx should
read

Index const jx = used*3 < open ? k : j+open/3 &m;

rather than what it used to. (The type may have changed but that
is incidental; what matters is the value of the initializing
expression.) I don't know what I was thinking when I wrote the
previous version, it's just completely wrong.

It seems that in worst case the strict FIFO algorithm is the same as
the rest of them, i.e. O(NN) where NN is the number of re-colored
points. Below is an example of the shape for which I measured memory consumption for 3840x2160 image almost exactly 4x as much as for
1920x1080.

I agree, the empirical evidence here and in my own tests is quite
compelling.

That said, the constant factor for the FIFO algorithm is lower
than the stack-based algorithms, even taking into account the
difference in sizes for queue and stack elements. Moreover cases
where FIFO algorithms are O( NxN ) are unusual and sparse,
whereas the stack-based algorithms tend to use a lot of memory
in lots of common and routine cases. On the average FIFO
algorithms typically use a lot less memory (or so I conjecture).

[code to generate fractal tree pattern]

Thank you for this. I incorporated it into my set of test
patterns more or less as soon as it was posted.

Now that I have taken some time to play around with different
algorithms and have been more systematic in doing speed
comparisons between different algorithms, on different patterns,
and with a good range of sizes, I have some general thoughts
to offer.

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.

I've been playing around with a more elaborate, mostly FIFO
method, in hopes of getting something that offers the best
of both worlds. The results so far are encouraging, but a
fair amount of tuning has been necessary (and perhaps more
still is), and comparisons have been done on just the one
test server I have available. So I don't know how well it
would hold up on other hardware, including especially more
recent hardware. Under these circumstances I feel it is
premature to post actual code, especially since the code
is still in flux.

This topic has been more interesting that I was expecting, and
also more challenging. 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.
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

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

Michael S <already5chosen@yahoo.com> writes:

On Sun, 24 Mar 2024 10:24:45 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Michael S <already5chosen@yahoo.com> writes:

On Wed, 20 Mar 2024 10:01:10 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

Michael S <already5chosen@yahoo.com> writes:

[...]

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

Using a stack is like a depth-first search, and a queue is like a
breadth-first search. For a pixel field of size N x N, doing a
depth-first search can lead to memory usage of order N**2,
whereas a breadth-first search has a "frontier" at most O(N).
Another way to think of it is that breadth-first gets rid of
visited nodes as fast as it can, but depth-first keeps them
around for a long time when everything is reachable from anywhere
(as will be the case in large simple reasons).

For my test cases the FIFO depth of your algorithm never exceeds
min(width,height)*2+2. I wonder if existence of this or similar
limit can be proven theoretically.

I believe it is possible to prove the strict FIFO algorithm is
O(N) for an N x N pixel field, but I haven't tried to do so in
any rigorous way, nor do I know what the constant is. It does
seem to be larger than 2.

Before I do anything else I should correct a bug in my earlier
FIFO algorithm. The initialization of the variable jx should
read

Index const jx = used*3 < open ? k : j+open/3 &m;

I lost track, sorry. I can not find your code that contains line
similar to this.
Can you point to specific post?

rather than what it used to. (The type may have changed but that
is incidental; what matters is the value of the initializing
expression.) I don't know what I was thinking when I wrote the
previous version, it's just completely wrong.

It seems that in worst case the strict FIFO algorithm is the same as
the rest of them, i.e. O(NN) where NN is the number of re-colored
points. Below is an example of the shape for which I measured
memory consumption for 3840x2160 image almost exactly 4x as much as
for 1920x1080.

I agree, the empirical evidence here and in my own tests is quite
compelling.

BTW, I am no longer agree with myself about "the rest of them".
By now, I know at least one method that is O(W*log(H)). It is even
quite fast for majority of my test shapes. Unfortunately, [in its
current form] it is abysmally slow (100x) for minority of tests.
[In it's current form] it has other disadvantages as well like
consuming non-trivial amount of memory when handling small spot in the
big image. But that can be improved. I am less sure that worst-case
speed can be improved enough to make it generally acceptable.

I think, I said enough for you to figure out a general principle of
this algorithm. I don't want to post code here before I try few
improvements.

That said, the constant factor for the FIFO algorithm is lower
than the stack-based algorithms, even taking into account the
difference in sizes for queue and stack elements. Moreover cases
where FIFO algorithms are O( NxN ) are unusual and sparse,
whereas the stack-based algorithms tend to use a lot of memory
in lots of common and routine cases. On the average FIFO
algorithms typically use a lot less memory (or so I conjecture).

[code to generate fractal tree pattern]

Thank you for this. I incorporated it into my set of test
patterns more or less as soon as it was posted.

Now that I have taken some time to play around with different
algorithms and have been more systematic in doing speed
comparisons between different algorithms, on different patterns,
and with a good range of sizes, I have some general thoughts
to offer.

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've been playing around with a more elaborate, mostly FIFO
method, in hopes of getting something that offers the best
of both worlds. The results so far are encouraging, but a
fair amount of tuning has been necessary (and perhaps more
still is), and comparisons have been done on just the one
test server I have available. So I don't know how well it
would hold up on other hardware, including especially more
recent hardware. Under these circumstances I feel it is
premature to post actual code, especially since the code
is still in flux.

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?

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 ?
Myself, I have no rules. In my real work I am quite happy with
dispatchers of network messages that are 250-300 lines long. But if I
had this sort of rules, I'd certainly decompose.

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

Michael S <already5chosen@yahoo.com> writes:

(I'm replying in pieces.)

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

Before I do anything else I should correct a bug in my earlier
FIFO algorithm. The initialization of the variable jx should
read

Index const jx = used*3 < open ? k : j+open/3 &m;

I lost track, sorry. I can not find your code that contains line
similar to this.
Can you point to specific post?

Easier for me just to repost the corrected algorithm. The
type UC is an unsigned char, the types Index and Count are
size_t (or maybe unsigned long long), the type U32 is a
32-bit unsigned type.

Please excuse any minor glitches, I have done some hand
editing to take out various bits of diagnostic code.

extern Count
fifo_fill( UC *field, Index w, Index h, Point p0, UC old, UC new ){
Index const xm = w-1;
Index const ym = h-1;

Index j = 0;
Index k = 0;
Index n = 1u << 10;
Index m = n-1;
U32 *todo = malloc( n * sizeof *todo );
Index x = p0.x;
Index y = p0.y;

if( !todo || x >= w || y >= h || field[ x+y*w ] != old ) return 0;

todo[ k++ ] = x<<16 | y;

while( j != k ){
Index used = j < k ? k-j : k+n-j;
Index open = n - used;
if( open < used/16 ){
Index new_n = n*2;
Index new_m = new_n-1;
Index new_j = j < k ? j : j+n;
U32 *t = realloc( todo, new_n * sizeof *t );
if( ! t ) break;
if( j != new_j ) memcpy( t+new_j, t+j, (n-j) * sizeof *t );
todo = t, n = new_n, m = new_m, j = new_j, open = n-used;
}
assert( (k-j&m) == used && open+used == n );

Index const jx = used*3 < open ? k : j+open/3 &m; // here it is!
while( j != jx ){
if( (k-j&m) > mm ) mm = k-j&m;
U32 p = todo[j]; j = j+1 &m;
x = p >> 16, y = p & 0xFFFF;
if( x > 0 && field[ x-1 + y*w ] == old ){
todo[k] = x-1<<16 | y, k = k+1&m, field[ x-1 + y*w ] = new;
}
if( y > 0 && field[ x + (y-1)*w ] == old ){
todo[k] = x<<16 | y-1, k = k+1&m, field[ x + (y-1)*w ] = new;
}
if( x < xm && field[ x+1 + y*w ] == old ){
todo[k] = x+1<<16 | y, k = k+1&m, field[ x+1 + y*w ] = new;
}
if( y < ym && field[ x + (y+1)*w ] == old ){
todo[k] = x<<16 | y+1, k = k+1&m, field[ x + (y+1)*w ] = new;
}
}
}

return free( todo ), 0;
}
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

Michael S <already5chosen@yahoo.com> writes:

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

Michael S <already5chosen@yahoo.com> writes:

It seems that in worst case the strict FIFO algorithm is the same
as the rest of them, i.e. O(NN) where NN is the number of
re-colored points. Below is an example of the shape for which I
measured memory consumption for 3840x2160 image almost exactly 4x
as much as for 1920x1080.

I agree, the empirical evidence here and in my own tests is quite
compelling.

BTW, I am no longer agree with myself about "the rest of them".
By now, I know at least one method that is O(W*log(H)). It is even
quite fast for majority of my test shapes. Unfortunately, [in its
current form] it is abysmally slow (100x) for minority of tests.
[In it's current form] it has other disadvantages as well like
consuming non-trivial amount of memory when handling small spot in the
big image. But that can be improved. I am less sure that worst-case
speed can be improved enough to make it generally acceptable.

I think, I said enough for you to figure out a general principle of
this algorithm. I don't want to post code here before I try few improvements.

Thank you for the implied compliment. At this point I think the
probability that I will figure it out anytime soon is pretty low.
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.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.

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

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.
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

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.
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

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.
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

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




--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.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.
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

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).
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

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.



--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

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>
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

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.

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

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


IVB,stack_timr2:
[25 x 19] * 421054
Solid square ( 12, 9) 475 0.963 4.81 4.81
Solid square ( 0, 0) 475 0.990 4.95 4.95
standing snake-like shape ( 0, 0) 259 0.615 3.07 5.64
prostrate snake-like shape ( 0, 0) 259 0.673 3.36 6.17
slalom shape ( 0, 0) 233 0.761 3.80 7.76
slalom shape(rotated) ( 0, 0) 223 0.815 4.07 8.68
cross-in-cross ( 0, 0) 403 1.160 5.80 6.84
fractal tree ( 12, 0) 247 0.740 3.70 7.12
greed(2) ( 0, 0) 367 1.093 5.46 7.07
greed(3) ( 0, 0) 283 0.762 3.81 6.39
greed(4) ( 0, 0) 223 0.621 3.10 6.61
donut ( 23, 9) 238 0.753 3.76 7.51
[200 x 200] * 5002
Solid square ( 100, 100) 40000 0.587 2.93 2.93
Solid square ( 0, 0) 40000 0.588 2.94 2.94
standing snake-like shape ( 0, 0) 20100 0.299 1.49 2.97
prostrate snake-like shape ( 0, 0) 20100 0.311 1.55 3.09
slalom shape ( 0, 0) 19802 0.481 2.40 4.86
slalom shape(rotated) ( 0, 0) 19802 0.586 2.93 5.92
cross-in-cross ( 0, 0) 39216 0.609 3.04 3.10
fractal tree ( 99, 0) 18674 0.539 2.69 5.77
greed(2) ( 0, 0) 30000 0.909 4.54 6.06
greed(3) ( 0, 0) 22311 0.468 2.34 4.19
greed(4) ( 0, 0) 17500 0.371 1.85 4.24
donut ( 199, 100) 25830 0.418 2.09 3.24
[1280 x 720] * 218
Solid square ( 640, 360) 921600 0.602 3.00 3.00
Solid square ( 0, 0) 921600 0.741 3.69 3.69
standing snake-like shape ( 0, 0) 461160 0.326 1.62 3.24
prostrate snake-like shape ( 0, 0) 461440 0.342 1.70 3.40
slalom shape ( 0, 0) 460082 0.519 2.58 5.17
slalom shape(rotated) ( 0, 0) 460800 0.626 3.12 6.23
cross-in-cross ( 0, 0) 917616 0.666 3.31 3.33
fractal tree ( 639, 0) 445860 0.565 2.81 5.81
greed(2) ( 0, 0) 691200 0.938 4.67 6.23
greed(3) ( 0, 0) 512160 0.491 2.44 4.40
greed(4) ( 0, 0) 403200 0.352 1.75 4.00
donut (1279, 360) 655856 0.450 2.24 3.15
[1920 x 1080] * 98
Solid square ( 960, 540) 2073600 0.611 3.01 3.01
Solid square ( 0, 0) 2073600 0.759 3.74 3.74
standing snake-like shape ( 0, 0) 1037340 0.330 1.62 3.25
prostrate snake-like shape ( 0, 0) 1037760 0.350 1.72 3.44
slalom shape ( 0, 0) 1036800 0.525 2.58 5.17
slalom shape(rotated) ( 0, 0) 1036800 0.636 3.13 6.26
cross-in-cross ( 0, 0) 2067616 0.674 3.32 3.33
fractal tree ( 959, 0) 1034612 0.605 2.98 5.97
greed(2) ( 0, 0) 1555200 0.923 4.54 6.06
greed(3) ( 0, 0) 1152000 0.463 2.28 4.10
greed(4) ( 0, 0) 907200 0.359 1.77 4.04
donut (1919, 540) 1477788 0.431 2.12 2.98
[3840 x 2160] * 26
Solid square (1920,1080) 8294400 0.703 3.26 3.26
Solid square ( 0, 0) 8294400 0.847 3.93 3.93
standing snake-like shape ( 0, 0) 4148280 0.400 1.85 3.71
prostrate snake-like shape ( 0, 0) 4149120 0.815 3.78 7.55
slalom shape ( 0, 0) 4147200 0.871 4.04 8.08
slalom shape(rotated) ( 0, 0) 4147200 0.734 3.40 6.81
cross-in-cross ( 0, 0) 8282416 0.774 3.59 3.59
fractal tree (1919, 0) 4135652 0.658 3.05 6.12
greed(2) ( 0, 0) 6220800 1.023 4.74 6.32
greed(3) ( 0, 0) 4608000 0.554 2.57 4.62
greed(4) ( 0, 0) 3628800 0.451 2.09 4.78
donut (3839,1080) 5919706 0.498 2.31 3.24

IVB,queue_timr:
[25 x 19] * 421054
Solid square ( 12, 9) 475 0.828 4.14 4.14
Solid square ( 0, 0) 475 0.890 4.45 4.45
standing snake-like shape ( 0, 0) 259 0.642 3.21 5.89
prostrate snake-like shape ( 0, 0) 259 0.709 3.54 6.50
slalom shape ( 0, 0) 233 0.589 2.94 6.00
slalom shape(rotated) ( 0, 0) 223 0.573 2.86 6.10
cross-in-cross ( 0, 0) 403 0.713 3.56 4.20
fractal tree ( 12, 0) 247 0.448 2.24 4.31
greed(2) ( 0, 0) 367 0.675 3.37 4.37
greed(3) ( 0, 0) 283 0.512 2.56 4.30
greed(4) ( 0, 0) 223 0.409 2.04 4.36
donut ( 23, 9) 238 0.439 2.19 4.38

[200 x 200] * 5002
Solid square ( 100, 100) 40000 0.893 4.46 4.46
Solid square ( 0, 0) 40000 0.786 3.93 3.93
standing snake-like shape ( 0, 0) 20100 0.555 2.77 5.52
prostrate snake-like shape ( 0, 0) 20100 0.557 2.78 5.54
slalom shape ( 0, 0) 19802 0.571 2.85 5.76
slalom shape(rotated) ( 0, 0) 19802 0.548 2.74 5.53
cross-in-cross ( 0, 0) 39216 0.736 3.68 3.75
fractal tree ( 99, 0) 18674 0.569 2.84 6.09
greed(2) ( 0, 0) 30000 0.615 3.07 4.10
greed(3) ( 0, 0) 22311 0.453 2.26 4.06
greed(4) ( 0, 0) 17500 0.357 1.78 4.08
donut ( 199, 100) 25830 0.531 2.65 4.11

[1280 x 720] * 218
Solid square ( 640, 360) 921600 0.785 3.91 3.91
Solid square ( 0, 0) 921600 0.761 3.79 3.79
standing snake-like shape ( 0, 0) 461160 0.551 2.74 5.48
prostrate snake-like shape ( 0, 0) 461440 0.552 2.75 5.49
slalom shape ( 0, 0) 460082 0.564 2.81 5.62
slalom shape(rotated) ( 0, 0) 460800 0.557 2.77 5.54
cross-in-cross ( 0, 0) 917616 0.755 3.76 3.77
fractal tree ( 639, 0) 445860 0.448 2.23 4.61
greed(2) ( 0, 0) 691200 0.645 3.21 4.28
greed(3) ( 0, 0) 512160 0.481 2.39 4.31
greed(4) ( 0, 0) 403200 0.377 1.88 4.29
donut (1279, 360) 655856 0.572 2.85 4.00

[1920 x 1080] * 98
Solid square ( 960, 540) 2073600 0.854 4.20 4.20
Solid square ( 0, 0) 2073600 0.829 4.08 4.08
standing snake-like shape ( 0, 0) 1037340 0.557 2.74 5.48
prostrate snake-like shape ( 0, 0) 1037760 0.574 2.82 5.64
slalom shape ( 0, 0) 1036800 0.583 2.87 5.74
slalom shape(rotated) ( 0, 0) 1036800 0.563 2.77 5.54
cross-in-cross ( 0, 0) 2067616 0.822 4.05 4.06
fractal tree ( 959, 0) 1034612 0.468 2.30 4.62
greed(2) ( 0, 0) 1555200 0.664 3.27 4.36
greed(3) ( 0, 0) 1152000 0.483 2.38 4.28
greed(4) ( 0, 0) 907200 0.389 1.91 4.38
donut (1919, 540) 1477788 0.617 3.04 4.26

[3840 x 2160] * 26
Solid square (1920,1080) 8294400 1.407 6.52 6.52
Solid square ( 0, 0) 8294400 1.555 7.21 7.21
standing snake-like shape ( 0, 0) 4148280 0.596 2.76 5.53
prostrate snake-like shape ( 0, 0) 4149120 0.851 3.95 7.89
slalom shape ( 0, 0) 4147200 0.802 3.72 7.44
slalom shape(rotated) ( 0, 0) 4147200 0.600 2.78 5.56
cross-in-cross ( 0, 0) 8282416 1.522 7.06 7.07
fractal tree (1919, 0) 4135652 1.151 5.34 10.70
greed(2) ( 0, 0) 6220800 1.410 6.54 8.72
greed(3) ( 0, 0) 4608000 1.450 6.72 12.10
greed(4) ( 0, 0) 3628800 1.432 6.64 15.18
donut (3839,1080) 5919706 1.114 5.17 7.24

HSW,stack_2x2:
[25 x 19] * 421054
Solid square ( 12, 9) 475 0.391 1.95 1.95
Solid square ( 0, 0) 475 0.402 2.01 2.01
standing snake-like shape ( 0, 0) 259 0.389 1.94 3.57
prostrate snake-like shape ( 0, 0) 259 0.351 1.75 3.22
slalom shape ( 0, 0) 233 0.360 1.80 3.67
slalom shape(rotated) ( 0, 0) 223 0.366 1.83 3.90
cross-in-cross ( 0, 0) 403 0.385 1.92 2.27
fractal tree ( 12, 0) 247 0.382 1.91 3.67
greed(2) ( 0, 0) 367 0.416 2.08 2.69
greed(3) ( 0, 0) 283 0.361 1.80 3.03
greed(4) ( 0, 0) 223 0.306 1.53 3.26
donut ( 23, 9) 238 0.225 1.12 2.25
[200 x 200] * 5002
Solid square ( 100, 100) 40000 0.344 1.72 1.72
Solid square ( 0, 0) 40000 0.343 1.71 1.71
standing snake-like shape ( 0, 0) 20100 0.274 1.37 2.73
prostrate snake-like shape ( 0, 0) 20100 0.311 1.55 3.09
slalom shape ( 0, 0) 19802 0.333 1.66 3.36
slalom shape(rotated) ( 0, 0) 19802 0.344 1.72 3.47
cross-in-cross ( 0, 0) 39216 0.352 1.76 1.79
fractal tree ( 99, 0) 18674 0.497 2.48 5.32
greed(2) ( 0, 0) 30000 0.338 1.69 2.25
greed(3) ( 0, 0) 22311 0.317 1.58 2.84
greed(4) ( 0, 0) 17500 0.247 1.23 2.82
donut ( 199, 100) 25830 0.237 1.18 1.83
[1280 x 720] * 218
Solid square ( 640, 360) 921600 0.334 1.66 1.66
Solid square ( 0, 0) 921600 0.332 1.65 1.65
standing snake-like shape ( 0, 0) 461160 0.263 1.31 2.62
prostrate snake-like shape ( 0, 0) 461440 0.342 1.70 3.40
slalom shape ( 0, 0) 460082 0.352 1.75 3.51
slalom shape(rotated) ( 0, 0) 460800 0.346 1.72 3.44
cross-in-cross ( 0, 0) 917616 0.336 1.67 1.68
fractal tree ( 639, 0) 445860 0.437 2.18 4.50
greed(2) ( 0, 0) 691200 0.326 1.62 2.16
greed(3) ( 0, 0) 512160 0.303 1.51 2.71
greed(4) ( 0, 0) 403200 0.245 1.22 2.79
donut (1279, 360) 655856 0.243 1.21 1.70
[1920 x 1080] * 98
Solid square ( 960, 540) 2073600 0.337 1.66 1.66
Solid square ( 0, 0) 2073600 0.335 1.65 1.65
standing snake-like shape ( 0, 0) 1037340 0.265 1.30 2.61
prostrate snake-like shape ( 0, 0) 1037760 0.333 1.64 3.27
slalom shape ( 0, 0) 1036800 0.344 1.69 3.39
slalom shape(rotated) ( 0, 0) 1036800 0.342 1.68 3.37
cross-in-cross ( 0, 0) 2067616 0.338 1.66 1.67
fractal tree ( 959, 0) 1034612 0.472 2.32 4.66
greed(2) ( 0, 0) 1555200 0.328 1.61 2.15
greed(3) ( 0, 0) 1152000 0.305 1.50 2.70
greed(4) ( 0, 0) 907200 0.245 1.21 2.76
donut (1919, 540) 1477788 0.244 1.20 1.68
[3840 x 2160] * 26
Solid square (1920,1080) 8294400 0.375 1.74 1.74
Solid square ( 0, 0) 8294400 0.402 1.86 1.86
standing snake-like shape ( 0, 0) 4148280 0.323 1.50 2.99
prostrate snake-like shape ( 0, 0) 4149120 0.561 2.60 5.20
slalom shape ( 0, 0) 4147200 0.574 2.66 5.32
slalom shape(rotated) ( 0, 0) 4147200 0.407 1.89 3.77
cross-in-cross ( 0, 0) 8282416 0.384 1.78 1.78
fractal tree (1919, 0) 4135652 0.508 2.36 4.72
greed(2) ( 0, 0) 6220800 0.395 1.83 2.44
greed(3) ( 0, 0) 4608000 0.350 1.62 2.92
greed(4) ( 0, 0) 3628800 0.275 1.28 2.91
donut (3839,1080) 5919706 0.262 1.21 1.70

HSW,stack_timr1:
[25 x 19] * 421054
Solid square ( 12, 9) 475 0.801 4.00 4.00
Solid square ( 0, 0) 475 0.845 4.22 4.22
standing snake-like shape ( 0, 0) 259 0.511 2.55 4.69
prostrate snake-like shape ( 0, 0) 259 0.516 2.58 4.73
slalom shape ( 0, 0) 233 0.520 2.60 5.30
slalom shape(rotated) ( 0, 0) 223 0.476 2.38 5.07
cross-in-cross ( 0, 0) 403 0.694 3.47 4.09
fractal tree ( 12, 0) 247 0.414 2.07 3.98
greed(2) ( 0, 0) 367 0.645 3.22 4.17
greed(3) ( 0, 0) 283 0.552 2.76 4.63
greed(4) ( 0, 0) 223 0.476 2.38 5.07
donut ( 23, 9) 238 0.469 2.34 4.68
[200 x 200] * 5002
Solid square ( 100, 100) 40000 0.447 2.23 2.23
Solid square ( 0, 0) 40000 0.444 2.22 2.22
standing snake-like shape ( 0, 0) 20100 0.229 1.14 2.28
prostrate snake-like shape ( 0, 0) 20100 0.250 1.25 2.49
slalom shape ( 0, 0) 19802 0.270 1.35 2.73
slalom shape(rotated) ( 0, 0) 19802 0.260 1.30 2.62
cross-in-cross ( 0, 0) 39216 0.459 2.29 2.34
fractal tree ( 99, 0) 18674 0.260 1.30 2.78
greed(2) ( 0, 0) 30000 0.387 1.93 2.58
greed(3) ( 0, 0) 22311 0.295 1.47 2.64
greed(4) ( 0, 0) 17500 0.231 1.15 2.64
donut ( 199, 100) 25830 0.316 1.58 2.45
[1280 x 720] * 218
Solid square ( 640, 360) 921600 0.457 2.27 2.27
Solid square ( 0, 0) 921600 0.515 2.56 2.56
standing snake-like shape ( 0, 0) 461160 0.248 1.23 2.47
prostrate snake-like shape ( 0, 0) 461440 0.321 1.60 3.19
slalom shape ( 0, 0) 460082 0.312 1.55 3.11
slalom shape(rotated) ( 0, 0) 460800 0.285 1.42 2.84
cross-in-cross ( 0, 0) 917616 0.466 2.32 2.33
fractal tree ( 639, 0) 445860 0.271 1.35 2.79
greed(2) ( 0, 0) 691200 0.406 2.02 2.69
greed(3) ( 0, 0) 512160 0.278 1.38 2.49
greed(4) ( 0, 0) 403200 0.223 1.11 2.54
donut (1279, 360) 655856 0.335 1.67 2.34
[1920 x 1080] * 98
Solid square ( 960, 540) 2073600 0.454 2.23 2.23
Solid square ( 0, 0) 2073600 0.554 2.73 2.73
standing snake-like shape ( 0, 0) 1037340 0.240 1.18 2.36
prostrate snake-like shape ( 0, 0) 1037760 0.317 1.56 3.12
slalom shape ( 0, 0) 1036800 0.306 1.51 3.01
slalom shape(rotated) ( 0, 0) 1036800 0.293 1.44 2.88
cross-in-cross ( 0, 0) 2067616 0.511 2.51 2.52
fractal tree ( 959, 0) 1034612 0.276 1.36 2.72
greed(2) ( 0, 0) 1555200 0.402 1.98 2.64
greed(3) ( 0, 0) 1152000 0.283 1.39 2.51
greed(4) ( 0, 0) 907200 0.224 1.10 2.52
donut (1919, 540) 1477788 0.331 1.63 2.29
[3840 x 2160] * 26
Solid square (1920,1080) 8294400 0.566 2.62 2.62
Solid square ( 0, 0) 8294400 0.708 3.28 3.28
standing snake-like shape ( 0, 0) 4148280 0.337 1.56 3.12
prostrate snake-like shape ( 0, 0) 4149120 0.930 4.31 8.62
slalom shape ( 0, 0) 4147200 0.735 3.41 6.82
slalom shape(rotated) ( 0, 0) 4147200 0.387 1.79 3.59
cross-in-cross ( 0, 0) 8282416 0.630 2.92 2.93
fractal tree (1919, 0) 4135652 0.302 1.40 2.81
greed(2) ( 0, 0) 6220800 0.516 2.39 3.19
greed(3) ( 0, 0) 4608000 0.367 1.70 3.06
greed(4) ( 0, 0) 3628800 0.286 1.33 3.03
donut (3839,1080) 5919706 0.398 1.85 2.59

HSW,stack_timr2:
[25 x 19] * 421054
Solid square ( 12, 9) 475 0.746 3.73 3.73
Solid square ( 0, 0) 475 0.781 3.90 3.90
standing snake-like shape ( 0, 0) 259 0.479 2.39 4.39
prostrate snake-like shape ( 0, 0) 259 0.525 2.62 4.81
slalom shape ( 0, 0) 233 0.546 2.73 5.57
slalom shape(rotated) ( 0, 0) 223 0.532 2.66 5.67
cross-in-cross ( 0, 0) 403 0.804 4.02 4.74
fractal tree ( 12, 0) 247 0.466 2.33 4.48
greed(2) ( 0, 0) 367 0.668 3.34 4.32
greed(3) ( 0, 0) 283 0.552 2.76 4.63
greed(4) ( 0, 0) 223 0.446 2.23 4.75
donut ( 23, 9) 238 0.521 2.60 5.20
[200 x 200] * 5002
Solid square ( 100, 100) 40000 0.432 2.16 2.16
Solid square ( 0, 0) 40000 0.430 2.15 2.15
standing snake-like shape ( 0, 0) 20100 0.223 1.11 2.22
prostrate snake-like shape ( 0, 0) 20100 0.271 1.35 2.70
slalom shape ( 0, 0) 19802 0.360 1.80 3.63
slalom shape(rotated) ( 0, 0) 19802 0.385 1.92 3.89
cross-in-cross ( 0, 0) 39216 0.468 2.34 2.39
fractal tree ( 99, 0) 18674 0.457 2.28 4.89
greed(2) ( 0, 0) 30000 0.468 2.34 3.12
greed(3) ( 0, 0) 22311 0.353 1.76 3.16
greed(4) ( 0, 0) 17500 0.275 1.37 3.14
donut ( 199, 100) 25830 0.340 1.70 2.63
[1280 x 720] * 218
Solid square ( 640, 360) 921600 0.450 2.24 2.24
Solid square ( 0, 0) 921600 0.560 2.79 2.79
standing snake-like shape ( 0, 0) 461160 0.244 1.21 2.43
prostrate snake-like shape ( 0, 0) 461440 0.282 1.40 2.80
slalom shape ( 0, 0) 460082 0.412 2.05 4.11
slalom shape(rotated) ( 0, 0) 460800 0.414 2.06 4.12
cross-in-cross ( 0, 0) 917616 0.497 2.47 2.48
fractal tree ( 639, 0) 445860 0.426 2.12 4.38
greed(2) ( 0, 0) 691200 0.496 2.47 3.29
greed(3) ( 0, 0) 512160 0.373 1.86 3.34
greed(4) ( 0, 0) 403200 0.282 1.40 3.21
donut (1279, 360) 655856 0.312 1.55 2.18
[1920 x 1080] * 98
Solid square ( 960, 540) 2073600 0.437 2.15 2.15
Solid square ( 0, 0) 2073600 0.559 2.75 2.75
standing snake-like shape ( 0, 0) 1037340 0.235 1.16 2.31
prostrate snake-like shape ( 0, 0) 1037760 0.274 1.35 2.69
slalom shape ( 0, 0) 1036800 0.396 1.95 3.90
slalom shape(rotated) ( 0, 0) 1036800 0.407 2.00 4.01
cross-in-cross ( 0, 0) 2067616 0.490 2.41 2.42
fractal tree ( 959, 0) 1034612 0.457 2.25 4.51
greed(2) ( 0, 0) 1555200 0.486 2.39 3.19
greed(3) ( 0, 0) 1152000 0.346 1.70 3.06
greed(4) ( 0, 0) 907200 0.268 1.32 3.01
donut (1919, 540) 1477788 0.297 1.46 2.05
[3840 x 2160] * 26
Solid square (1920,1080) 8294400 0.523 2.43 2.43
Solid square ( 0, 0) 8294400 0.649 3.01 3.01
standing snake-like shape ( 0, 0) 4148280 0.307 1.42 2.85
prostrate snake-like shape ( 0, 0) 4149120 0.614 2.85 5.69
slalom shape ( 0, 0) 4147200 0.666 3.09 6.18
slalom shape(rotated) ( 0, 0) 4147200 0.495 2.30 4.59
cross-in-cross ( 0, 0) 8282416 0.585 2.71 2.72
fractal tree (1919, 0) 4135652 0.435 2.02 4.05
greed(2) ( 0, 0) 6220800 0.583 2.70 3.60
greed(3) ( 0, 0) 4608000 0.426 1.98 3.56
greed(4) ( 0, 0) 3628800 0.342 1.59 3.62
donut (3839,1080) 5919706 0.369 1.71 2.40

HSW,queue_timr:
[25 x 19] * 421054
Solid square ( 12, 9) 475 0.698 3.49 3.49
Solid square ( 0, 0) 475 0.709 3.54 3.54
standing snake-like shape ( 0, 0) 259 0.517 2.58 4.74
prostrate snake-like shape ( 0, 0) 259 0.518 2.59 4.75
slalom shape ( 0, 0) 233 0.478 2.39 4.87
slalom shape(rotated) ( 0, 0) 223 0.447 2.23 4.76
cross-in-cross ( 0, 0) 403 0.577 2.88 3.40
fractal tree ( 12, 0) 247 0.374 1.87 3.60
greed(2) ( 0, 0) 367 0.515 2.57 3.33
greed(3) ( 0, 0) 283 0.409 2.04 3.43
greed(4) ( 0, 0) 223 0.336 1.68 3.58
donut ( 23, 9) 238 0.379 1.89 3.78
[200 x 200] * 5002
Solid square ( 100, 100) 40000 0.662 3.31 3.31
Solid square ( 0, 0) 40000 0.619 3.09 3.09
standing snake-like shape ( 0, 0) 20100 0.443 2.21 4.41
prostrate snake-like shape ( 0, 0) 20100 0.446 2.23 4.44
slalom shape ( 0, 0) 19802 0.440 2.20 4.44
slalom shape(rotated) ( 0, 0) 19802 0.439 2.19 4.43
cross-in-cross ( 0, 0) 39216 0.629 3.14 3.21
fractal tree ( 99, 0) 18674 0.618 3.09 6.62
greed(2) ( 0, 0) 30000 0.477 2.38 3.18
greed(3) ( 0, 0) 22311 0.364 1.82 3.26
greed(4) ( 0, 0) 17500 0.289 1.44 3.30
donut ( 199, 100) 25830 0.482 2.41 3.73
[1280 x 720] * 218
Solid square ( 640, 360) 921600 0.669 3.33 3.33
Solid square ( 0, 0) 921600 0.628 3.13 3.13
standing snake-like shape ( 0, 0) 461160 0.444 2.21 4.42
prostrate snake-like shape ( 0, 0) 461440 0.445 2.21 4.42
slalom shape ( 0, 0) 460082 0.444 2.21 4.43
slalom shape(rotated) ( 0, 0) 460800 0.441 2.20 4.39
cross-in-cross ( 0, 0) 917616 0.631 3.14 3.15
fractal tree ( 639, 0) 445860 0.373 1.86 3.84
greed(2) ( 0, 0) 691200 0.492 2.45 3.27
greed(3) ( 0, 0) 512160 0.377 1.88 3.38
greed(4) ( 0, 0) 403200 0.304 1.51 3.46
donut (1279, 360) 655856 0.505 2.51 3.53
[1920 x 1080] * 98
Solid square ( 960, 540) 2073600 0.711 3.50 3.50
Solid square ( 0, 0) 2073600 0.664 3.27 3.27
standing snake-like shape ( 0, 0) 1037340 0.448 2.20 4.41
prostrate snake-like shape ( 0, 0) 1037760 0.460 2.26 4.52
slalom shape ( 0, 0) 1036800 0.450 2.21 4.43
slalom shape(rotated) ( 0, 0) 1036800 0.448 2.20 4.41
cross-in-cross ( 0, 0) 2067616 0.666 3.28 3.29
fractal tree ( 959, 0) 1034612 0.391 1.92 3.86
greed(2) ( 0, 0) 1555200 0.509 2.50 3.34
greed(3) ( 0, 0) 1152000 0.378 1.86 3.35
greed(4) ( 0, 0) 907200 0.306 1.51 3.44
donut (1919, 540) 1477788 0.517 2.54 3.57
[3840 x 2160] * 26
Solid square (1920,1080) 8294400 1.093 5.07 5.07
Solid square ( 0, 0) 8294400 1.240 5.75 5.75
standing snake-like shape ( 0, 0) 4148280 0.481 2.23 4.46
prostrate snake-like shape ( 0, 0) 4149120 0.643 2.98 5.96
slalom shape ( 0, 0) 4147200 0.597 2.77 5.54
slalom shape(rotated) ( 0, 0) 4147200 0.477 2.21 4.42
cross-in-cross ( 0, 0) 8282416 1.116 5.17 5.18
fractal tree (1919, 0) 4135652 0.937 4.34 8.71
greed(2) ( 0, 0) 6220800 1.133 5.25 7.01
greed(3) ( 0, 0) 4608000 1.102 5.11 9.20
greed(4) ( 0, 0) 3628800 1.020 4.73 10.81
donut (3839,1080) 5919706 0.892 4.14 5.80


SKC,stack_2x2:
[25 x 19] * 421054
Solid square ( 12, 9) 475 0.425 2.12 2.12
Solid square ( 0, 0) 475 0.422 2.11 2.11
standing snake-like shape ( 0, 0) 259 0.376 1.88 3.45
prostrate snake-like shape ( 0, 0) 259 0.370 1.85 3.39
slalom shape ( 0, 0) 233 0.360 1.80 3.67
slalom shape(rotated) ( 0, 0) 223 0.339 1.69 3.61
cross-in-cross ( 0, 0) 403 0.398 1.99 2.35
fractal tree ( 12, 0) 247 0.355 1.77 3.41
greed(2) ( 0, 0) 367 0.400 2.00 2.59
greed(3) ( 0, 0) 283 0.354 1.77 2.97
greed(4) ( 0, 0) 223 0.305 1.52 3.25
donut ( 23, 9) 238 0.243 1.21 2.42
[200 x 200] * 5002
Solid square ( 100, 100) 40000 0.390 1.95 1.95
Solid square ( 0, 0) 40000 0.389 1.94 1.94
standing snake-like shape ( 0, 0) 20100 0.335 1.67 3.33
prostrate snake-like shape ( 0, 0) 20100 0.342 1.71 3.40
slalom shape ( 0, 0) 19802 0.337 1.68 3.40
slalom shape(rotated) ( 0, 0) 19802 0.337 1.68 3.40
cross-in-cross ( 0, 0) 39216 0.400 2.00 2.04
fractal tree ( 99, 0) 18674 0.342 1.71 3.66
greed(2) ( 0, 0) 30000 0.379 1.89 2.53
greed(3) ( 0, 0) 22311 0.320 1.60 2.87
greed(4) ( 0, 0) 17500 0.264 1.32 3.02
donut ( 199, 100) 25830 0.271 1.35 2.10
[1280 x 720] * 218
Solid square ( 640, 360) 921600 0.392 1.95 1.95
Solid square ( 0, 0) 921600 0.391 1.95 1.95
standing snake-like shape ( 0, 0) 461160 0.336 1.67 3.34
prostrate snake-like shape ( 0, 0) 461440 0.344 1.71 3.42
slalom shape ( 0, 0) 460082 0.348 1.73 3.47
slalom shape(rotated) ( 0, 0) 460800 0.333 1.66 3.31
cross-in-cross ( 0, 0) 917616 0.389 1.94 1.94
fractal tree ( 639, 0) 445860 0.344 1.71 3.54
greed(2) ( 0, 0) 691200 0.366 1.82 2.43
greed(3) ( 0, 0) 512160 0.315 1.57 2.82
greed(4) ( 0, 0) 403200 0.262 1.30 2.98
donut (1279, 360) 655856 0.276 1.37 1.93
[1920 x 1080] * 98
Solid square ( 960, 540) 2073600 0.389 1.91 1.91
Solid square ( 0, 0) 2073600 0.389 1.91 1.91
standing snake-like shape ( 0, 0) 1037340 0.333 1.64 3.28
prostrate snake-like shape ( 0, 0) 1037760 0.339 1.67 3.33
slalom shape ( 0, 0) 1036800 0.343 1.69 3.38
slalom shape(rotated) ( 0, 0) 1036800 0.332 1.63 3.27
cross-in-cross ( 0, 0) 2067616 0.390 1.92 1.92
fractal tree ( 959, 0) 1034612 0.347 1.71 3.42
greed(2) ( 0, 0) 1555200 0.370 1.82 2.43
greed(3) ( 0, 0) 1152000 0.316 1.56 2.80
greed(4) ( 0, 0) 907200 0.261 1.28 2.94
donut (1919, 540) 1477788 0.279 1.37 1.93
[3840 x 2160] * 26
Solid square (1920,1080) 8294400 0.429 1.99 1.99
Solid square ( 0, 0) 8294400 0.456 2.11 2.11
standing snake-like shape ( 0, 0) 4148280 0.393 1.82 3.64
prostrate snake-like shape ( 0, 0) 4149120 0.483 2.24 4.48
slalom shape ( 0, 0) 4147200 0.473 2.19 4.39
slalom shape(rotated) ( 0, 0) 4147200 0.394 1.83 3.65
cross-in-cross ( 0, 0) 8282416 0.439 2.04 2.04
fractal tree (1919, 0) 4135652 0.374 1.73 3.48
greed(2) ( 0, 0) 6220800 0.431 2.00 2.66
greed(3) ( 0, 0) 4608000 0.363 1.68 3.03
greed(4) ( 0, 0) 3628800 0.290 1.34 3.07
donut (3839,1080) 5919706 0.304 1.41 1.98

SKC,stack_timr1:
[25 x 19] * 421054
Solid square ( 12, 9) 475 0.863 4.31 4.31
Solid square ( 0, 0) 475 0.913 4.56 4.56
standing snake-like shape ( 0, 0) 259 0.588 2.94 5.39
prostrate snake-like shape ( 0, 0) 259 0.584 2.92 5.36
slalom shape ( 0, 0) 233 0.551 2.75 5.62
slalom shape(rotated) ( 0, 0) 223 0.535 2.67 5.70
cross-in-cross ( 0, 0) 403 0.771 3.85 4.54
fractal tree ( 12, 0) 247 0.449 2.24 4.32
greed(2) ( 0, 0) 367 0.737 3.68 4.77
greed(3) ( 0, 0) 283 0.616 3.08 5.17
greed(4) ( 0, 0) 223 0.535 2.67 5.70
donut ( 23, 9) 238 0.532 2.66 5.31
[200 x 200] * 5002
Solid square ( 100, 100) 40000 0.588 2.94 2.94
Solid square ( 0, 0) 40000 0.588 2.94 2.94
standing snake-like shape ( 0, 0) 20100 0.301 1.50 2.99
prostrate snake-like shape ( 0, 0) 20100 0.316 1.58 3.14
slalom shape ( 0, 0) 19802 0.300 1.50 3.03
slalom shape(rotated) ( 0, 0) 19802 0.298 1.49 3.01
cross-in-cross ( 0, 0) 39216 0.596 2.98 3.04
fractal tree ( 99, 0) 18674 0.303 1.51 3.24
greed(2) ( 0, 0) 30000 0.467 2.33 3.11
greed(3) ( 0, 0) 22311 0.353 1.76 3.16
greed(4) ( 0, 0) 17500 0.281 1.40 3.21
donut ( 199, 100) 25830 0.407 2.03 3.15
[1280 x 720] * 218
Solid square ( 640, 360) 921600 0.570 2.84 2.84
Solid square ( 0, 0) 921600 0.618 3.08 3.08
standing snake-like shape ( 0, 0) 461160 0.285 1.42 2.83
prostrate snake-like shape ( 0, 0) 461440 0.302 1.50 3.00
slalom shape ( 0, 0) 460082 0.287 1.43 2.86
slalom shape(rotated) ( 0, 0) 460800 0.287 1.43 2.86
cross-in-cross ( 0, 0) 917616 0.569 2.83 2.84
fractal tree ( 639, 0) 445860 0.296 1.47 3.05
greed(2) ( 0, 0) 691200 0.454 2.26 3.01
greed(3) ( 0, 0) 512160 0.337 1.68 3.02
greed(4) ( 0, 0) 403200 0.266 1.32 3.03
donut (1279, 360) 655856 0.408 2.03 2.85
[1920 x 1080] * 98
Solid square ( 960, 540) 2073600 0.611 3.01 3.01
Solid square ( 0, 0) 2073600 0.694 3.42 3.42
standing snake-like shape ( 0, 0) 1037340 0.323 1.59 3.18
prostrate snake-like shape ( 0, 0) 1037760 0.341 1.68 3.35
slalom shape ( 0, 0) 1036800 0.325 1.60 3.20
slalom shape(rotated) ( 0, 0) 1036800 0.323 1.59 3.18
cross-in-cross ( 0, 0) 2067616 0.643 3.16 3.17
fractal tree ( 959, 0) 1034612 0.300 1.48 2.96
greed(2) ( 0, 0) 1555200 0.489 2.41 3.21
greed(3) ( 0, 0) 1152000 0.353 1.74 3.13
greed(4) ( 0, 0) 907200 0.279 1.37 3.14
donut (1919, 540) 1477788 0.439 2.16 3.03
[3840 x 2160] * 26
Solid square (1920,1080) 8294400 0.702 3.26 3.26
Solid square ( 0, 0) 8294400 0.801 3.71 3.71
standing snake-like shape ( 0, 0) 4148280 0.391 1.81 3.63
prostrate snake-like shape ( 0, 0) 4149120 0.634 2.94 5.88
slalom shape ( 0, 0) 4147200 0.527 2.44 4.89
slalom shape(rotated) ( 0, 0) 4147200 0.398 1.85 3.69
cross-in-cross ( 0, 0) 8282416 0.751 3.48 3.49
fractal tree (1919, 0) 4135652 0.323 1.50 3.00
greed(2) ( 0, 0) 6220800 0.575 2.67 3.56
greed(3) ( 0, 0) 4608000 0.415 1.92 3.46
greed(4) ( 0, 0) 3628800 0.319 1.48 3.38
donut (3839,1080) 5919706 0.493 2.29 3.20

SKC,stack_timr2:
[25 x 19] * 421054
Solid square ( 12, 9) 475 0.904 4.52 4.52
Solid square ( 0, 0) 475 0.945 4.72 4.72
standing snake-like shape ( 0, 0) 259 0.568 2.84 5.21
prostrate snake-like shape ( 0, 0) 259 0.575 2.87 5.27
slalom shape ( 0, 0) 233 0.564 2.82 5.75
slalom shape(rotated) ( 0, 0) 223 0.527 2.63 5.61
cross-in-cross ( 0, 0) 403 0.874 4.37 5.15
fractal tree ( 12, 0) 247 0.427 2.13 4.11
greed(2) ( 0, 0) 367 0.692 3.46 4.48
greed(3) ( 0, 0) 283 0.569 2.84 4.78
greed(4) ( 0, 0) 223 0.465 2.32 4.95
donut ( 23, 9) 238 0.564 2.82 5.63
[200 x 200] * 5002
Solid square ( 100, 100) 40000 0.657 3.28 3.28
Solid square ( 0, 0) 40000 0.655 3.27 3.27
standing snake-like shape ( 0, 0) 20100 0.333 1.66 3.31
prostrate snake-like shape ( 0, 0) 20100 0.313 1.56 3.11
slalom shape ( 0, 0) 19802 0.344 1.72 3.47
slalom shape(rotated) ( 0, 0) 19802 0.342 1.71 3.45
cross-in-cross ( 0, 0) 39216 0.665 3.32 3.39
fractal tree ( 99, 0) 18674 0.331 1.65 3.54
greed(2) ( 0, 0) 30000 0.468 2.34 3.12
greed(3) ( 0, 0) 22311 0.343 1.71 3.07
greed(4) ( 0, 0) 17500 0.266 1.33 3.04
donut ( 199, 100) 25830 0.444 2.22 3.44
[1280 x 720] * 218
Solid square ( 640, 360) 921600 0.640 3.19 3.19
Solid square ( 0, 0) 921600 0.752 3.74 3.74
standing snake-like shape ( 0, 0) 461160 0.384 1.91 3.82
prostrate snake-like shape ( 0, 0) 461440 0.371 1.85 3.69
slalom shape ( 0, 0) 460082 0.408 2.03 4.07
slalom shape(rotated) ( 0, 0) 460800 0.390 1.94 3.88
cross-in-cross ( 0, 0) 917616 0.698 3.47 3.49
fractal tree ( 639, 0) 445860 0.340 1.69 3.50
greed(2) ( 0, 0) 691200 0.510 2.54 3.38
greed(3) ( 0, 0) 512160 0.377 1.88 3.38
greed(4) ( 0, 0) 403200 0.257 1.28 2.92
donut (1279, 360) 655856 0.459 2.28 3.21
[1920 x 1080] * 98
Solid square ( 960, 540) 2073600 0.690 3.40 3.40
Solid square ( 0, 0) 2073600 0.792 3.90 3.90
standing snake-like shape ( 0, 0) 1037340 0.365 1.80 3.59
prostrate snake-like shape ( 0, 0) 1037760 0.345 1.70 3.39
slalom shape ( 0, 0) 1036800 0.384 1.89 3.78
slalom shape(rotated) ( 0, 0) 1036800 0.375 1.85 3.69
cross-in-cross ( 0, 0) 2067616 0.727 3.58 3.59
fractal tree ( 959, 0) 1034612 0.356 1.75 3.51
greed(2) ( 0, 0) 1555200 0.495 2.44 3.25
greed(3) ( 0, 0) 1152000 0.346 1.70 3.06
greed(4) ( 0, 0) 907200 0.266 1.31 2.99
donut (1919, 540) 1477788 0.476 2.34 3.29
[3840 x 2160] * 26
Solid square (1920,1080) 8294400 0.760 3.52 3.52
Solid square ( 0, 0) 8294400 0.856 3.97 3.97
standing snake-like shape ( 0, 0) 4148280 0.415 1.92 3.85
prostrate snake-like shape ( 0, 0) 4149120 0.483 2.24 4.48
slalom shape ( 0, 0) 4147200 0.516 2.39 4.79
slalom shape(rotated) ( 0, 0) 4147200 0.432 2.00 4.01
cross-in-cross ( 0, 0) 8282416 0.806 3.74 3.74
fractal tree (1919, 0) 4135652 0.380 1.76 3.53
greed(2) ( 0, 0) 6220800 0.568 2.63 3.51
greed(3) ( 0, 0) 4608000 0.400 1.85 3.34
greed(4) ( 0, 0) 3628800 0.321 1.49 3.40
donut (3839,1080) 5919706 0.540 2.50 3.51

SKC,queue_timr:
[25 x 19] * 421054
Solid square ( 12, 9) 475 0.557 2.78 2.78
Solid square ( 0, 0) 475 0.589 2.94 2.94
standing snake-like shape ( 0, 0) 259 0.479 2.39 4.39
prostrate snake-like shape ( 0, 0) 259 0.490 2.45 4.49
slalom shape ( 0, 0) 233 0.464 2.32 4.73
slalom shape(rotated) ( 0, 0) 223 0.427 2.13 4.55
cross-in-cross ( 0, 0) 403 0.491 2.45 2.89
fractal tree ( 12, 0) 247 0.304 1.52 2.92
greed(2) ( 0, 0) 367 0.432 2.16 2.80
greed(3) ( 0, 0) 283 0.348 1.74 2.92
greed(4) ( 0, 0) 223 0.282 1.41 3.00
donut ( 23, 9) 238 0.310 1.55 3.09
[200 x 200] * 5002
Solid square ( 100, 100) 40000 0.536 2.68 2.68
Solid square ( 0, 0) 40000 0.513 2.56 2.56
standing snake-like shape ( 0, 0) 20100 0.405 2.02 4.03
prostrate snake-like shape ( 0, 0) 20100 0.397 1.98 3.95
slalom shape ( 0, 0) 19802 0.409 2.04 4.13
slalom shape(rotated) ( 0, 0) 19802 0.414 2.07 4.18
cross-in-cross ( 0, 0) 39216 0.518 2.59 2.64
fractal tree ( 99, 0) 18674 0.447 2.23 4.79
greed(2) ( 0, 0) 30000 0.391 1.95 2.61
greed(3) ( 0, 0) 22311 0.297 1.48 2.66
greed(4) ( 0, 0) 17500 0.239 1.19 2.73
donut ( 199, 100) 25830 0.383 1.91 2.96
[1280 x 720] * 218
Solid square ( 640, 360) 921600 0.588 2.93 2.93
Solid square ( 0, 0) 921600 0.546 2.72 2.72
standing snake-like shape ( 0, 0) 461160 0.405 2.02 4.03
prostrate snake-like shape ( 0, 0) 461440 0.402 2.00 4.00
slalom shape ( 0, 0) 460082 0.411 2.05 4.10
slalom shape(rotated) ( 0, 0) 460800 0.417 2.08 4.15
cross-in-cross ( 0, 0) 917616 0.541 2.69 2.70
fractal tree ( 639, 0) 445860 0.312 1.55 3.21
greed(2) ( 0, 0) 691200 0.423 2.11 2.81
greed(3) ( 0, 0) 512160 0.323 1.61 2.89
greed(4) ( 0, 0) 403200 0.258 1.28 2.94
donut (1279, 360) 655856 0.413 2.06 2.89
[1920 x 1080] * 98
Solid square ( 960, 540) 2073600 0.713 3.51 3.51
Solid square ( 0, 0) 2073600 0.572 2.81 2.81
standing snake-like shape ( 0, 0) 1037340 0.414 2.04 4.07
prostrate snake-like shape ( 0, 0) 1037760 0.414 2.04 4.07
slalom shape ( 0, 0) 1036800 0.417 2.05 4.10
slalom shape(rotated) ( 0, 0) 1036800 0.425 2.09 4.18
cross-in-cross ( 0, 0) 2067616 0.571 2.81 2.82
fractal tree ( 959, 0) 1034612 0.323 1.59 3.19
greed(2) ( 0, 0) 1555200 0.439 2.16 2.88
greed(3) ( 0, 0) 1152000 0.327 1.61 2.90
greed(4) ( 0, 0) 907200 0.263 1.29 2.96
donut (1919, 540) 1477788 0.455 2.24 3.14
[3840 x 2160] * 26
Solid square (1920,1080) 8294400 0.944 4.38 4.38
Solid square ( 0, 0) 8294400 1.036 4.80 4.80
standing snake-like shape ( 0, 0) 4148280 0.434 2.01 4.02
prostrate snake-like shape ( 0, 0) 4149120 0.590 2.74 5.47
slalom shape ( 0, 0) 4147200 0.551 2.56 5.11
slalom shape(rotated) ( 0, 0) 4147200 0.452 2.10 4.19
cross-in-cross ( 0, 0) 8282416 0.974 4.52 4.52
fractal tree (1919, 0) 4135652 0.413 1.92 3.84
greed(2) ( 0, 0) 6220800 0.813 3.77 5.03
greed(3) ( 0, 0) 4608000 0.662 3.07 5.53
greed(4) ( 0, 0) 3628800 0.543 2.52 5.76
donut (3839,1080) 5919706 0.674 3.13 4.38


ZN3,stack_2x2:
[25 x 19] * 421054
Solid square ( 12, 9) 475 0.408 2.04 2.04
Solid square ( 0, 0) 475 0.382 1.91 1.91
standing snake-like shape ( 0, 0) 259 0.343 1.71 3.15
prostrate snake-like shape ( 0, 0) 259 0.327 1.63 3.00
slalom shape ( 0, 0) 233 0.295 1.47 3.01
slalom shape(rotated) ( 0, 0) 223 0.311 1.55 3.31
cross-in-cross ( 0, 0) 403 0.356 1.78 2.10
fractal tree ( 12, 0) 247 0.310 1.55 2.98
greed(2) ( 0, 0) 367 0.393 1.96 2.54
greed(3) ( 0, 0) 283 0.329 1.64 2.76
greed(4) ( 0, 0) 223 0.285 1.42 3.04
donut ( 23, 9) 238 0.220 1.10 2.20
[200 x 200] * 5002
Solid square ( 100, 100) 40000 0.332 1.66 1.66
Solid square ( 0, 0) 40000 0.333 1.66 1.66
standing snake-like shape ( 0, 0) 20100 0.288 1.44 2.86
prostrate snake-like shape ( 0, 0) 20100 0.286 1.43 2.84
slalom shape ( 0, 0) 19802 0.268 1.34 2.71
slalom shape(rotated) ( 0, 0) 19802 0.288 1.44 2.91
cross-in-cross ( 0, 0) 39216 0.340 1.70 1.73
fractal tree ( 99, 0) 18674 0.344 1.72 3.68
greed(2) ( 0, 0) 30000 0.323 1.61 2.15
greed(3) ( 0, 0) 22311 0.271 1.35 2.43
greed(4) ( 0, 0) 17500 0.223 1.11 2.55
donut ( 199, 100) 25830 0.236 1.18 1.83
[1280 x 720] * 218
Solid square ( 640, 360) 921600 0.327 1.63 1.63
Solid square ( 0, 0) 921600 0.320 1.59 1.59
standing snake-like shape ( 0, 0) 461160 0.281 1.40 2.80
prostrate snake-like shape ( 0, 0) 461440 0.276 1.37 2.74
slalom shape ( 0, 0) 460082 0.266 1.32 2.65
slalom shape(rotated) ( 0, 0) 460800 0.284 1.41 2.83
cross-in-cross ( 0, 0) 917616 0.329 1.64 1.64
fractal tree ( 639, 0) 445860 0.314 1.56 3.23
greed(2) ( 0, 0) 691200 0.317 1.58 2.10
greed(3) ( 0, 0) 512160 0.266 1.32 2.38
greed(4) ( 0, 0) 403200 0.224 1.11 2.55
donut (1279, 360) 655856 0.237 1.18 1.66
[1920 x 1080] * 98
Solid square ( 960, 540) 2073600 0.329 1.62 1.62
Solid square ( 0, 0) 2073600 0.327 1.61 1.61
standing snake-like shape ( 0, 0) 1037340 0.284 1.40 2.79
prostrate snake-like shape ( 0, 0) 1037760 0.283 1.39 2.78
slalom shape ( 0, 0) 1036800 0.277 1.36 2.73
slalom shape(rotated) ( 0, 0) 1036800 0.289 1.42 2.84
cross-in-cross ( 0, 0) 2067616 0.334 1.64 1.65
fractal tree ( 959, 0) 1034612 0.353 1.74 3.48
greed(2) ( 0, 0) 1555200 0.326 1.60 2.14
greed(3) ( 0, 0) 1152000 0.273 1.34 2.42
greed(4) ( 0, 0) 907200 0.235 1.16 2.64
donut (1919, 540) 1477788 0.245 1.21 1.69
[3840 x 2160] * 26
Solid square (1920,1080) 8294400 0.358 1.66 1.66
Solid square ( 0, 0) 8294400 0.394 1.83 1.83
standing snake-like shape ( 0, 0) 4148280 0.338 1.57 3.13
prostrate snake-like shape ( 0, 0) 4149120 0.354 1.64 3.28
slalom shape ( 0, 0) 4147200 0.372 1.72 3.45
slalom shape(rotated) ( 0, 0) 4147200 0.352 1.63 3.26
cross-in-cross ( 0, 0) 8282416 0.365 1.69 1.69
fractal tree (1919, 0) 4135652 0.372 1.72 3.46
greed(2) ( 0, 0) 6220800 0.397 1.84 2.45
greed(3) ( 0, 0) 4608000 0.316 1.47 2.64
greed(4) ( 0, 0) 3628800 0.254 1.18 2.69
donut (3839,1080) 5919706 0.253 1.17 1.64

ZN3,stack_timr1:
[25 x 19] * 421054
Solid square ( 12, 9) 475 0.902 4.51 4.51
Solid square ( 0, 0) 475 0.874 4.37 4.37
standing snake-like shape ( 0, 0) 259 0.521 2.60 4.78
prostrate snake-like shape ( 0, 0) 259 0.545 2.72 5.00
slalom shape ( 0, 0) 233 0.513 2.56 5.23
slalom shape(rotated) ( 0, 0) 223 0.505 2.52 5.38
cross-in-cross ( 0, 0) 403 0.737 3.68 4.34
fractal tree ( 12, 0) 247 0.436 2.18 4.19
greed(2) ( 0, 0) 367 0.675 3.37 4.37
greed(3) ( 0, 0) 283 0.558 2.79 4.68
greed(4) ( 0, 0) 223 0.481 2.40 5.12
donut ( 23, 9) 238 0.514 2.57 5.13
[200 x 200] * 5002
Solid square ( 100, 100) 40000 0.620 3.10 3.10
Solid square ( 0, 0) 40000 0.654 3.27 3.27
standing snake-like shape ( 0, 0) 20100 0.300 1.50 2.98
prostrate snake-like shape ( 0, 0) 20100 0.268 1.34 2.67
slalom shape ( 0, 0) 19802 0.273 1.36 2.76
slalom shape(rotated) ( 0, 0) 19802 0.277 1.38 2.80
cross-in-cross ( 0, 0) 39216 0.592 2.96 3.02
fractal tree ( 99, 0) 18674 0.298 1.49 3.19
greed(2) ( 0, 0) 30000 0.447 2.23 2.98
greed(3) ( 0, 0) 22311 0.340 1.70 3.05
greed(4) ( 0, 0) 17500 0.259 1.29 2.96
donut ( 199, 100) 25830 0.408 2.04 3.16
[1280 x 720] * 218
Solid square ( 640, 360) 921600 0.554 2.76 2.76
Solid square ( 0, 0) 921600 0.609 3.03 3.03
standing snake-like shape ( 0, 0) 461160 0.266 1.32 2.65
prostrate snake-like shape ( 0, 0) 461440 0.262 1.30 2.60
slalom shape ( 0, 0) 460082 0.262 1.30 2.61
slalom shape(rotated) ( 0, 0) 460800 0.264 1.31 2.63
cross-in-cross ( 0, 0) 917616 0.558 2.78 2.79
fractal tree ( 639, 0) 445860 0.283 1.41 2.91
greed(2) ( 0, 0) 691200 0.417 2.08 2.77
greed(3) ( 0, 0) 512160 0.307 1.53 2.75
greed(4) ( 0, 0) 403200 0.241 1.20 2.74
donut (1279, 360) 655856 0.437 2.18 3.06
[1920 x 1080] * 98
Solid square ( 960, 540) 2073600 0.585 2.88 2.88
Solid square ( 0, 0) 2073600 0.732 3.60 3.60
standing snake-like shape ( 0, 0) 1037340 0.308 1.52 3.03
prostrate snake-like shape ( 0, 0) 1037760 0.301 1.48 2.96
slalom shape ( 0, 0) 1036800 0.296 1.46 2.91
slalom shape(rotated) ( 0, 0) 1036800 0.306 1.51 3.01
cross-in-cross ( 0, 0) 2067616 0.665 3.27 3.28
fractal tree ( 959, 0) 1034612 0.297 1.46 2.93
greed(2) ( 0, 0) 1555200 0.466 2.29 3.06
greed(3) ( 0, 0) 1152000 0.309 1.52 2.74
greed(4) ( 0, 0) 907200 0.244 1.20 2.74
donut (1919, 540) 1477788 0.452 2.22 3.12
[3840 x 2160] * 26
Solid square (1920,1080) 8294400 0.709 3.29 3.29
Solid square ( 0, 0) 8294400 0.896 4.15 4.15
standing snake-like shape ( 0, 0) 4148280 0.418 1.94 3.88
prostrate snake-like shape ( 0, 0) 4149120 0.461 2.14 4.27
slalom shape ( 0, 0) 4147200 0.445 2.06 4.13
slalom shape(rotated) ( 0, 0) 4147200 0.443 2.05 4.11
cross-in-cross ( 0, 0) 8282416 0.836 3.88 3.88
fractal tree (1919, 0) 4135652 0.328 1.52 3.05
greed(2) ( 0, 0) 6220800 0.596 2.76 3.68
greed(3) ( 0, 0) 4608000 0.421 1.95 3.51
greed(4) ( 0, 0) 3628800 0.316 1.47 3.35
donut (3839,1080) 5919706 0.536 2.49 3.48

ZN3,stack_timr2:
[25 x 19] * 421054
Solid square ( 12, 9) 475 0.990 4.95 4.95
Solid square ( 0, 0) 475 1.043 5.21 5.21
standing snake-like shape ( 0, 0) 259 0.617 3.08 5.66
prostrate snake-like shape ( 0, 0) 259 0.580 2.90 5.32
slalom shape ( 0, 0) 233 0.558 2.79 5.69
slalom shape(rotated) ( 0, 0) 223 0.549 2.74 5.85
cross-in-cross ( 0, 0) 403 0.831 4.15 4.90
fractal tree ( 12, 0) 247 0.435 2.17 4.18
greed(2) ( 0, 0) 367 0.757 3.78 4.90
greed(3) ( 0, 0) 283 0.630 3.15 5.29
greed(4) ( 0, 0) 223 0.514 2.57 5.47
donut ( 23, 9) 238 0.534 2.67 5.33
[200 x 200] * 5002
Solid square ( 100, 100) 40000 0.762 3.81 3.81
Solid square ( 0, 0) 40000 0.763 3.81 3.81
standing snake-like shape ( 0, 0) 20100 0.386 1.93 3.84
prostrate snake-like shape ( 0, 0) 20100 0.395 1.97 3.93
slalom shape ( 0, 0) 19802 0.390 1.95 3.94
slalom shape(rotated) ( 0, 0) 19802 0.364 1.82 3.67
cross-in-cross ( 0, 0) 39216 0.761 3.80 3.88
fractal tree ( 99, 0) 18674 0.385 1.92 4.12
greed(2) ( 0, 0) 30000 0.549 2.74 3.66
greed(3) ( 0, 0) 22311 0.417 2.08 3.74
greed(4) ( 0, 0) 17500 0.328 1.64 3.75
donut ( 199, 100) 25830 0.510 2.55 3.95
[1280 x 720] * 218
Solid square ( 640, 360) 921600 0.749 3.73 3.73
Solid square ( 0, 0) 921600 0.820 4.08 4.08
standing snake-like shape ( 0, 0) 461160 0.376 1.87 3.74
prostrate snake-like shape ( 0, 0) 461440 0.384 1.91 3.82
slalom shape ( 0, 0) 460082 0.398 1.98 3.97
slalom shape(rotated) ( 0, 0) 460800 0.357 1.78 3.55
cross-in-cross ( 0, 0) 917616 0.750 3.73 3.75
fractal tree ( 639, 0) 445860 0.381 1.90 3.92
greed(2) ( 0, 0) 691200 0.539 2.68 3.58
greed(3) ( 0, 0) 512160 0.408 2.03 3.65
greed(4) ( 0, 0) 403200 0.324 1.61 3.69
donut (1279, 360) 655856 0.536 2.67 3.75
[1920 x 1080] * 98
Solid square ( 960, 540) 2073600 0.848 4.17 4.17
Solid square ( 0, 0) 2073600 1.032 5.08 5.08
standing snake-like shape ( 0, 0) 1037340 0.471 2.32 4.63
prostrate snake-like shape ( 0, 0) 1037760 0.462 2.27 4.54
slalom shape ( 0, 0) 1036800 0.476 2.34 4.68
slalom shape(rotated) ( 0, 0) 1036800 0.452 2.22 4.45
cross-in-cross ( 0, 0) 2067616 0.932 4.59 4.60
fractal tree ( 959, 0) 1034612 0.403 1.98 3.97
greed(2) ( 0, 0) 1555200 0.649 3.19 4.26
greed(3) ( 0, 0) 1152000 0.461 2.27 4.08
greed(4) ( 0, 0) 907200 0.339 1.67 3.81
donut (1919, 540) 1477788 0.588 2.89 4.06
[3840 x 2160] * 26
Solid square (1920,1080) 8294400 0.922 4.28 4.28
Solid square ( 0, 0) 8294400 1.089 5.05 5.05
standing snake-like shape ( 0, 0) 4148280 0.520 2.41 4.82
prostrate snake-like shape ( 0, 0) 4149120 0.548 2.54 5.08
slalom shape ( 0, 0) 4147200 0.539 2.50 5.00
slalom shape(rotated) ( 0, 0) 4147200 0.507 2.35 4.70
cross-in-cross ( 0, 0) 8282416 0.992 4.60 4.61
fractal tree (1919, 0) 4135652 0.428 1.98 3.98
greed(2) ( 0, 0) 6220800 0.709 3.29 4.38
greed(3) ( 0, 0) 4608000 0.518 2.40 4.32
greed(4) ( 0, 0) 3628800 0.417 1.93 4.42
donut (3839,1080) 5919706 0.647 3.00 4.20

ZN3,queue_timr:
[25 x 19] * 421054
Solid square ( 12, 9) 475 0.639 3.19 3.19
Solid square ( 0, 0) 475 0.655 3.27 3.27
standing snake-like shape ( 0, 0) 259 0.437 2.18 4.01
prostrate snake-like shape ( 0, 0) 259 0.441 2.20 4.04
slalom shape ( 0, 0) 233 0.397 1.98 4.05
slalom shape(rotated) ( 0, 0) 223 0.374 1.87 3.98
cross-in-cross ( 0, 0) 403 0.521 2.60 3.07
fractal tree ( 12, 0) 247 0.499 2.49 4.80
greed(2) ( 0, 0) 367 0.778 3.89 5.03
greed(3) ( 0, 0) 283 0.623 3.11 5.23
greed(4) ( 0, 0) 223 0.495 2.47 5.27
donut ( 23, 9) 238 0.344 1.72 3.43
[200 x 200] * 5002
Solid square ( 100, 100) 40000 0.578 2.89 2.89
Solid square ( 0, 0) 40000 0.581 2.90 2.90
standing snake-like shape ( 0, 0) 20100 0.378 1.89 3.76
prostrate snake-like shape ( 0, 0) 20100 0.369 1.84 3.67
slalom shape ( 0, 0) 19802 0.366 1.83 3.70
slalom shape(rotated) ( 0, 0) 19802 0.365 1.82 3.69
cross-in-cross ( 0, 0) 39216 0.577 2.88 2.94
fractal tree ( 99, 0) 18674 0.479 2.39 5.13
greed(2) ( 0, 0) 30000 0.679 3.39 4.52
greed(3) ( 0, 0) 22311 0.547 2.73 4.90
greed(4) ( 0, 0) 17500 0.456 2.28 5.21
donut ( 199, 100) 25830 0.402 2.01 3.11
[1280 x 720] * 218
Solid square ( 640, 360) 921600 0.595 2.96 2.96
Solid square ( 0, 0) 921600 0.596 2.97 2.97
standing snake-like shape ( 0, 0) 461160 0.373 1.86 3.71
prostrate snake-like shape ( 0, 0) 461440 0.377 1.88 3.75
slalom shape ( 0, 0) 460082 0.371 1.85 3.70
slalom shape(rotated) ( 0, 0) 460800 0.362 1.80 3.60
cross-in-cross ( 0, 0) 917616 0.593 2.95 2.96
fractal tree ( 639, 0) 445860 0.474 2.36 4.88
greed(2) ( 0, 0) 691200 0.459 2.28 3.05
greed(3) ( 0, 0) 512160 0.339 1.69 3.04
greed(4) ( 0, 0) 403200 0.447 2.22 5.09
donut (1279, 360) 655856 0.437 2.18 3.06
[1920 x 1080] * 98
Solid square ( 960, 540) 2073600 0.609 3.00 3.00
Solid square ( 0, 0) 2073600 0.611 3.01 3.01
standing snake-like shape ( 0, 0) 1037340 0.383 1.88 3.77
prostrate snake-like shape ( 0, 0) 1037760 0.379 1.87 3.73
slalom shape ( 0, 0) 1036800 0.375 1.85 3.69
slalom shape(rotated) ( 0, 0) 1036800 0.372 1.83 3.66
cross-in-cross ( 0, 0) 2067616 0.610 3.00 3.01
fractal tree ( 959, 0) 1034612 0.455 2.24 4.49
greed(2) ( 0, 0) 1555200 0.468 2.30 3.07
greed(3) ( 0, 0) 1152000 0.348 1.71 3.08
greed(4) ( 0, 0) 907200 0.276 1.36 3.10
donut (1919, 540) 1477788 0.453 2.23 3.13
[3840 x 2160] * 26
Solid square (1920,1080) 8294400 0.717 3.32 3.32
Solid square ( 0, 0) 8294400 0.689 3.19 3.19
standing snake-like shape ( 0, 0) 4148280 0.404 1.87 3.75
prostrate snake-like shape ( 0, 0) 4149120 0.406 1.88 3.76
slalom shape ( 0, 0) 4147200 0.400 1.85 3.71
slalom shape(rotated) ( 0, 0) 4147200 0.394 1.83 3.65
cross-in-cross ( 0, 0) 8282416 0.674 3.13 3.13
fractal tree (1919, 0) 4135652 0.441 2.04 4.10
greed(2) ( 0, 0) 6220800 0.537 2.49 3.32
greed(3) ( 0, 0) 4608000 0.399 1.85 3.33
greed(4) ( 0, 0) 3628800 0.317 1.47 3.36
donut (3839,1080) 5919706 0.491 2.28 3.19




--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

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.
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

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.

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

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.
--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

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.

--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

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;

todo_i = 1 - todo_i;
memset(todo[todo_i], 0, nx*sizeof(todo[0][0]));
do {
args[todo_i].x = x;
floodfill4_core(&args[todo_i]);
for (x = x+1; x < nx; ++x) {
if (todo_src[x] && edge_dst[x] == arg->old_color) // contact
found
break;
}
} while (x < nx);
}
}
}


// return value
// 0 - not expanded
// 1 - expanded, no bounce back
// 2 - expanded, possible bounce back
static
int floodfill4_expand(
Color* pixels, // row or column
ptrdiff_t incr, // distance between adjacent points of pixels
int len,
Color old_color,
Color new_color,
_Bool* src_todo,
_Bool* dst_todo,
_Bool first)
{
for (int i = 0; i < len; pixels += incr, ++i) {
if (src_todo[i] && *pixels == old_color) {
// contact found
if (first)
memset(dst_todo, 0, len*sizeof(*dst_todo));
*pixels = new_color;
dst_todo[i] = 1;
Color* p = pixels - incr;
int k;
for (k = i-1; k >= 0 && *p == old_color; p -= incr, --k) {
*p = new_color;
dst_todo[k] = 1;
}
_Bool more = k != i-1;
for (;;) {
pixels += incr;
for (i = i+1; i < len && *pixels == old_color; pixels += incr,
++i) {
*pixels = new_color;
dst_todo[i] = 1;
more |= src_todo[i] ^ 1;
}
if (i >= len)
break;
pixels += incr;
for (i = i+1; i < len && (!src_todo[i] || *pixels !=
old_color); pixels += incr, ++i);
if (i >= len)
break;
*pixels = new_color;
dst_todo[i] = 1;
Color* p = pixels - incr;
for (k = i-1; *p == old_color; --k, p -= incr) {
*p = new_color;
dst_todo[k] = 1;
}
more |= k != i-1;
}
return more ? 2 : 1;
}
}
return 0; // not expended
}

// return value - more code
static
int floodfill4_expand_lr(struct floodfill4_state* s, int exp_x, _Bool* src_todo, _Bool* exp_todo, int lr)
{
// try to expand to the right or left
const int ny = s->ny;
int ret = floodfill4_expand(&s->image[exp_x], s->width, ny,

old_color, s->new_color, src_todo, exp_todo, 1);

if (!ret)
return 0;

int result = lr;
while (ret == 2) {
Color* p = &s->image[s->x];
_Bool contact = 0;
for (int y = 0; y < ny; p += s->width, ++y) {
if (exp_todo[y] && *p == s->old_color) {
if (!contact)
memset(src_todo, 0, ny*sizeof(*src_todo));
s->y = y;
floodfill4_core(s);
contact = 1;
}
}
if (!contact)
break;
result = more_lr+more_ud;
ret = floodfill4_expand(&s->image[exp_x], s->width, ny,
s->old_color, s->new_color, src_todo, exp_todo, 0);
}

if ((s->u_todo[exp_x] = exp_todo[0])) result |= more_u;
if ((s->d_todo[exp_x] = exp_todo[ny-1])) result |= more_d;
memcpy(src_todo, exp_todo, ny*sizeof(*src_todo));
return result;
}

// return value - more code
static
int floodfill4_expand_ud(struct floodfill4_state* s, int exp_y, _Bool* src_todo, _Bool* exp_todo, int ud)
{
// try to expand up or down
const int nx = s->nx;
int ret = floodfill4_expand(&s->image[s->width*exp_y], 1, nx,

old_color, s->new_color, src_todo, exp_todo, 1);

if (!ret)
return 0;

int result = ud;
while (ret == 2) {
Color* p = &s->image[s->width*s->y];
_Bool contact = 0;
for (int x = 0; x < nx; ++x) {
if (exp_todo[x] && p[x] == s->old_color) {
if (!contact)
memset(src_todo, 0, nx*sizeof(*src_todo));
s->x = x;
floodfill4_core(s);
contact = 1;
}
}
if (!contact)
break;
result = more_lr+more_ud;
ret = floodfill4_expand(&s->image[s->width*exp_y], 1, nx,
s->old_color, s->new_color, src_todo, exp_todo, 0);
}

if ((s->l_todo[exp_y] = exp_todo[0])) result |= more_l;
if ((s->r_todo[exp_y] = exp_todo[nx-1])) result |= more_r;
memcpy(src_todo, exp_todo, nx*sizeof(*src_todo));
return result;
}







--- Synchronet 3.20a-Linux NewsLink 1.114

From Newsgroup: comp.lang.c

On Thu, 25 Apr 2024 17:56:06 +0300
Michael S <already5chosen@yahoo.com> wrote:

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.

A solution (sort of) is in line with the famous quite of David Wheeler
- to turn todo lists from bit maps into arrays of
abscesses-or-ordinates of contact points.

The cost is a memory footprint - 4x bigger than the previous version, 32
times bigger than above-mentioned "packed" variant of the previous
version. But in BigO sense it's the same.

In my tests it reduced the worst case time from O(max(A,B)**3) to O(A*B*log(max(A,B)). Which is non-ideal, but probably acceptable,
because the bad cases should be very rare in practice.

The real trouble is different - I don't know if my "worst case" is
really the worst.

The code below is for presentation of algorithm in both clear and
compact manner, with emphasis on symmetry between x and y directions.
It is not optimal in any sense and can be made no-trivially faster both
by algorithm enhancements an by specialization of critical loops.


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

typedef unsigned char Color;

enum coordinate_axes {
x_i = 0, y_i, // index of pos[], ld[], 1st index of limits[][],
todo[][] };
enum from_to {
from_i = 0, to_i // 2nd index of limits[][], todo[][], I use 0 and 1
more commonly };
enum { // indices of todo[] lists
le_i = x_i*2+from_i, ri_i = x_i*2+to_i,
up_i = y_i*2+from_i, dn_i = y_i*2+to_i,
};

#define IDX2INC(ft_idx) ((int)(ft_idx)*2 - 1)
#define X2Y(axis) ((axis) ^ 1)

typedef struct {
Color* image;
Color old_color, new_color;
ptrdiff_t ld[2]; // {1, width}
int limits[2][2]; // {{0, width-1}, {0, height-1}
} floodfill4_param;

typedef struct {
int *todo[4]; // {left,right, up, down} - first item holds the #
of active entries int limits[2][2]; // {{x0, x1}, {y0, y1}};
int pos[2]; // {x, y}
} floodfill4_state;

static void floodfill4_core(
const floodfill4_param* prm,
const floodfill4_state* arg);
static _Bool floodfill4_expand(
const floodfill4_param* prm,
floodfill4_state* s,
enum coordinate_axes axis, enum from_to ft_idx);

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;

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

int lr_todo[2][height+1];
int ud_todo[2][width+1];
floodfill4_param prm = {
.image = image,
.ld[x_i] = 1,
.ld[y_i] = width,
.limits = {{ 0, width-1}, {0, height-1}},
.old_color = old_color,
.new_color = new_color,
};
floodfill4_state s = {
.todo[le_i] = lr_todo[0],
.todo[ri_i] = lr_todo[1],
.todo[up_i] = ud_todo[0],
.todo[dn_i] = ud_todo[1],
.limits[x_i] = {x, x},
.limits[y_i] = {y, y},
.pos[x_i] = x, .pos[y_i] = y,
};
for (int i = 0; i < 4; ++i)
*s.todo[i] = 0;

// process central 1x1 rectangle
floodfill4_core(&prm, &s);

// expansion loop
for (unsigned idx = 0; idx < 4;) {
if (floodfill4_expand(&prm, &s, idx/2, idx % 2)) { // try to expand
idx = 0; // expansion succeed - restart from beginning
continue;
}
++idx;
}

return 1;
}

static __inline
void floodfill4_add(int* list, int val)
{
int n = list[0];
list[n+1] = val;
list[0] = n + 1;
}

// floodfill4_core - floodfill4 recursively in divide and conquer
fashion // arg->*_todo arrays (lists) initialized by caller.
// floodfill4_core adds to *_todo values that indicate need for further
// action, but never removes anything
static void floodfill4_core(const floodfill4_param* prm, const floodfill4_state* arg) {
const int ni[2] = {
arg->limits[x_i][1]-arg->limits[x_i][0],
arg->limits[y_i][1]-arg->limits[y_i][0],
};
if (ni[x_i] + ni[y_i] == 0) { // nx==ny==1
prm->image[prm->ld[y_i]*arg->limits[y_i][0]+arg->limits[x_i][0]] = prm->new_color; floodfill4_add(arg->todo[le_i], arg->limits[y_i][0]);
floodfill4_add(arg->todo[ri_i], arg->limits[y_i][0]);
floodfill4_add(arg->todo[up_i], arg->limits[x_i][0]);
floodfill4_add(arg->todo[dn_i], arg->limits[x_i][0]);
return;
}

floodfill4_state args[2];
args[0] = args[1] = *arg;
const enum coordinate_axes axis = ni[x_i] > ni[y_i] ?
x_i : // split vertically
y_i ; // split horizontally
int todo[2][ni[X2Y(axis)]+2]; // contacts between halves
const int hpos = (arg->limits[axis][0] + arg->limits[axis][1])/2; //
split point args[0].todo[axis*2+1] = todo[0]; args[0].limits[axis][1]
= hpos; args[1].todo[axis*2+0] = todo[1]; args[1].limits[axis][0] =
hpos + 1; int todo_i = arg->pos[axis] > hpos;
todo[todo_i][0] = 0; // empty todo list
floodfill4_core(prm, &args[todo_i]);
if (todo[todo_i][0] != 0) {
// do ping-pong between halves
args[0].pos[axis] = hpos;
args[1].pos[axis] = hpos+1;
const ptrdiff_t lda = prm->ld[axis];
const ptrdiff_t ldb = prm->ld[X2Y(axis)];
Color* edge = &prm->image[lda*hpos];
do {
// look for contact points on destination edge
int* from = todo[todo_i];
Color *edge_dst = todo_i ? edge : edge + lda;
todo_i = 1 - todo_i;
todo[todo_i][0] = 0;
int np = *from++;
do {
int pos = *from++;
if (edge_dst[pos*ldb] == prm->old_color) { // contact found
args[todo_i].pos[X2Y(axis)] = pos;
floodfill4_core(prm, &args[todo_i]);
}
} while (--np);
} while (todo[todo_i][0] != 0);
}
}

static
_Bool floodfill4_expand(
const floodfill4_param* prm,
floodfill4_state* s,
enum coordinate_axes axis,
enum from_to ft_idx)
{ // try to expand
int* src_todo = s->todo[axis*2+ft_idx];
if (*src_todo == 0)
return 0;

int src_pos = s->limits[axis][ft_idx];
if (src_pos == prm->limits[axis][ft_idx]) {
*src_todo = 0;
return 0;
}

typedef struct {
int pos0, pos1;
} interval_t;

const ptrdiff_t lda = prm->ld[axis];
const ptrdiff_t ldb = prm->ld[X2Y(axis)];
Color* src_col = &prm->image[lda*src_pos];
Color* exp_col = &src_col[lda*IDX2INC(ft_idx)];
const int ort_limit0 = s->limits[X2Y(axis)][0];
const int ort_limit1 = s->limits[X2Y(axis)][1];
const Color c0 = exp_col[ldb*ort_limit0]; // preserve upper corner
const Color c1 = exp_col[ldb*ort_limit1]; // preserve lower corner
interval_t workbuf[(ort_limit1 - ort_limit0+2)/2];
interval_t* wr = workbuf;
s->pos[axis] = src_pos;
int n_todo = src_todo[0];
do {
// look for contact
int pos = src_todo[n_todo--]; // use src_todo as stack, popping
from the top Color* pt = &exp_col[ldb*pos];
if (*pt == prm->old_color) { // contact found
*pt = prm->new_color;
// extend backward
Color* p = pt - ldb;
int pos0;
for (pos0 = pos-1; pos0 >= ort_limit0 && *p == prm->old_color; p
-= ldb, --pos0) *p = prm->new_color;
pos0 += 1;
// extend forward
p = pt + ldb;
int pos1;
for (pos1 = pos+1; pos1 <= ort_limit1 && *p == prm->old_color; p
+= ldb, ++pos1) *p = prm->new_color;
pos1 -= 1;

// add interval to result list
wr->pos0 = pos0;
wr->pos1 = pos1;
++wr;

if (pos0 != pos1) {
// bounce - apply new found interval to original rectangle
src_todo[0] = n_todo;
pos = pos0;
p = &src_col[ldb*pos];
do {
if (*p == prm->old_color) { // contact found
s->pos[X2Y(axis)] = pos;
floodfill4_core(prm, s);
n_todo = src_todo[0];
++pos;
p += ldb;
}
p += ldb;
} while (++pos <= pos1);
}
}
} while (n_todo != 0);

if (wr == workbuf)
return 0; // rectangle not expanded

// rectangle expanded
// handle corners of expanded rectangle
int exp_pos = src_pos + IDX2INC(ft_idx);
s->limits[axis][ft_idx] = exp_pos;
if (exp_col[ldb*ort_limit0] != c0) // corner0 modified
floodfill4_add(s->todo[X2Y(axis)*2+0], exp_pos); // add to todo0
list if (exp_col[ldb*ort_limit1] != c1) // corner1
modified floodfill4_add(s->todo[X2Y(axis)*2+1], exp_pos); // add to
todo1 list

// turn intervals to list
interval_t* rd = workbuf;
int* dst_todo = &src_todo[1];
do {
int pos = rd->pos0;
int pos1 = rd->pos1;
do
*dst_todo++ = pos;
while (++pos <= pos1);
++rd;
} while (rd != wr);
src_todo[0] = dst_todo - src_todo - 1;

return 1;
}




--- Synchronet 3.20a-Linux NewsLink 1.114