Re: filling area by color atack safety

Michael S <already5chosen@yahoo.com> writes:

On Thu, 28 Mar 2024 23:04:36 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>

Michael S <already5chosen@yahoo.com> writes:
>

[..various fill algorithms and how they scale..]

>
One thing that I were not expecting at this bigger pictures, is
good performance of simple recursive algorithm.  Of course, not of
original form of it, but of variation with explicit stack.  For
many shapes it has quite large memory footprint and despite that
it is not slow.  Probably the stack has very good locality of
reference.
>
[algorithm]

>
You are indeed a very clever fellow.  I'm impressed.

>
Yes, the use of switch is clever :(

In my view the cleverness is how "recursion" is accomplished by a
means of a combination of using a stack to store a "return address"
and restoring state by undoing a change rather than storing the
old value.  Using a switch() is just a detail (and to my way of
thinking how the switch() is done here obscures the basic idea and
makes the code harder to understand, but never mind that).

It more resemble computed GO TO in old FORTRAN or indirect jumps
in asm than idiomatic C switch.  But it is a legal* C.

I did program in FORTRAN briefly but don't remember ever using
computed GO TO.  And yes, I found that missing semicolon and put it
back.  Is there some reason you don't always use -pedantic?  I
pretty much always do.

Intrigued by your idea, I wrote something along the same lines,
only shorter and (at least for me) a little easier to grok.
If someone is interested I can post it.

>
If non-trivially different, why not?

I hope to soon but am unable to right now (and maybe for a week
or so due to circumstances beyond my control).  For sure the
code is different;  whether it is non-trivially different I
leave for others to judge.

I see you have also done a revised algorithm based on the same
idea, but more elaborate (to save on runtime footprint?).
Still working on formulating a response to that one...

>
The original purpose of enhancement was to amortize non-trivial
and probably not very fast call stack emulation logic over more
than one pixel.  2x2 just happens to be the biggest block that
still has very simple in-block recoloring logic. ~4x reduction in
the size of auxiliary memory is just a pleasant side effect.
>
Exactly the same 4x reduction in memory size could have been
achieved with single-pixel variant by using packed array for 2-bit
state (==trace back) stack elements.  But it would be the same or
slower than original while the enhanced variant is robustly faster
than original.

An alternate idea is to use a 64-bit integer for 32 "top of stack"
elements, or up to 32 I should say, and a stack with 64-bit values.
Just an idea, it may not turn out to be useful.

The few measurements I have done don't show a big difference in
performance between the two methods.  But I admit I wasn't paying
close attention, and like I said only a few patterns of filling were
exercised.

After implementing the first enhancement I paid attention that at
4K size the timing (per pixel) for few of my test cases is
significantly worse than at smaller images.  So, I added another
enhancement aiming to minimize cache trashing effects by never
looking back at immediate parent of current block.  The info about
location of the parent nicely fitted into remaining 2 bits of
stack octet.

The idea of not going back to the originator (what you call the
parent) is something I developed independently before looking at
your latest code (and mostly I still haven't).  Seems like a good
idea.

Two further comments.

One, the new code is a lot more complicated than the previous
code.  I'm not sure the performance gain is worth the cost
in complexity.  What kind of speed improvements do you see,
in terms of percent?

Two, and more important, the new algorithm still uses O(NxN) memory
for an N by N pixel field.  We really would like to get that down to
O(N) memory (and of course run just as fast).  Have you looked into
how that might be done?