Re: filling area by color atack safety

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

Michael S <already5chosen@yahoo.com> writes:
 

On Tue, 19 Mar 2024 11:57:53 +0000
Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
 

 

The nice thing about Tim's method is that we can expect that
performance depends on number of recolored pixels and almost
nothing else. 

 
One aspect that I consider a significant plus is my code never
does poorly.  Certainly it isn't the fastest in all cases, but
it's never abysmally slow.
 

To be fair, none of presented algorithms is abysmally slow.
When compared by number of visited points, they all appear to be within
factor of 2 or 2.5 of each other.
Some of them for some patterns could be 10-15 times slower than
others, but it does not happen for all patterns and when it happens
it's because of problematic implementation rather because of
differences in algorithms.
Even original naive recursive algorithm is not too slow when
implemented in optimized asm - 2.2x slower than the fastest for solid
square shape and closer than that for other shapes.

The big difference between algorithms is not a speed, but amount of
auxiliary memory used in the worst case. Your algorithm appears to be
the best in that department, Malcolm's algorithm it's also quite good
and all others (plain recursion, stacks, my deferred stack, all my
cross variants, lines-oriented recursion of : Peter 'Shaggy'
Haywood) are a lot worse.

But even by that metric, the difference between different
implementations of the same algorithm is often much bigger than
difference between algorithms.

For example, solid 200x200 image with starting point in the corner
recolored by code presented in first Malcolm's post (not his own
algorithm, but recursive algorithm that he presented as a reference
point) on x86-64/gcc consumes 5,094,784 bytes of stack. After small
modification (all non-changing parameters aggregated in structure
and passed by reference) the footprint falls to 2,547,328 B.
Coding the same algorithm (well, almost the same) in asm reduces it to
32,0000 B. Coding it with explicit stack cuts it to 40,000 B. Now I
didn't actually coded it, but I know how to compress explicit stack
down to 2 bits per level of recursion. If implemented, it would be
10,000B, i.e. comparable with much more economical algorithm of Malcolm
and 512x smaller than original implementation of [well, almost] the
same algorithm!