Re: filling area by color atack safety

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

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

I did a little more investigation gradually modifying Tim's code
for improved performance without changing the basic principle of
the algorithm. [...] 

 
Here is a rendition of my latest and fastest refinement.
 

WOW, you really opened up your bag of tricks!
Power-of-two sized circular buffers is something that I tend to use on
smaller systems, like DSPs or MCUs rather than on "big" computers. But,
of course, on "big" computers it also helps.
Packing {x,y} into 32-bit word is a bit dirty. I'd guess that we can
justify it by claiming that original code although has similar
limitation of width*height <= INT_MAX.
Removal of FIFO empty and almost-full tests in the inner loop helps
solid shapes, but appears to slow down "drawn" shapes. Since solid
shapes are the slowest to fill, it is probably a good trade-off.

Overall, it is faster than my implementation of your algorithm. Esp. so
for solid shapes. Esp. of esp. so on Intel Skylake CPUs where speed up
is up to 1.75x.

More complicated 'St. George Cross' algorithms are still faster for
solid shapes and for shapes dominated by long horizontal or long
vertical lines. But they are ... well ... more complicated.
And [on Skylake] their worst case ('slalom' shape) is somewhat slower in
absolute sense than the worst case of your code (a solid bar).