Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Michael S <already5chosen@yahoo.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety
Date: Fri, 29 Mar 2024 15:21:41 +0200
Organization: A noiseless patient Spider
Lines: 61
Message-ID: <20240329162141.00006c81@yahoo.com>
References: <ut3669$21eur$1@i2pn2.org>
	<86h6h3nvyz.fsf@linuxsc.com>
	<865xxiok09.fsf@linuxsc.com>
	<20240319131842.00002138@yahoo.com>
	<utbuk3$qed7$1@dont-email.me>
	<20240319191859.00004bc8@yahoo.com>
	<86bk79m10l.fsf@linuxsc.com>
	<20240324202758.00001b75@yahoo.com>
	<86frwfjs0n.fsf@linuxsc.com>
	<20240325012844.0000685b@yahoo.com>
	<867chlk1zf.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 29 Mar 2024 13:21:47 +0100 (CET)
Injection-Info: dont-email.me; posting-host="1c8415fced5d144b3aa5dafe4e72b2bb";
	logging-data="320293"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19EKFdwR9Dzv2Svcj1eUV+Vzxmpsn2zC6c="
Cancel-Lock: sha1:h4Lse/l7RTok7f+EMmyMFJcl+x8=
X-Newsreader: Claws Mail 4.1.1 (GTK 3.24.34; x86_64-w64-mingw32)
Bytes: 3708

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.