Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Michael S 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: <86h6h3nvyz.fsf@linuxsc.com> <865xxiok09.fsf@linuxsc.com> <20240319131842.00002138@yahoo.com> <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 wrote: > Michael S 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.