Re: filling area by color atack safety

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 :(
It more resemble computed GO TO in old FORTRAN or indirect jumps in asm
than idiomatic C switch. But it is a legal* C.

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

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 versions I posted are not exactly legal C; they are illegal C
non-rejected by gcc. But they can be trivially made into legal C by
adding semicolon after one of the case labels.