Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: filling area by color atack safety Date: Fri, 29 Mar 2024 23:58:26 -0700 Organization: A noiseless patient Spider Lines: 97 Message-ID: <86y1a0i4tp.fsf@linuxsc.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> <20240329162141.00006c81@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Sat, 30 Mar 2024 06:58:29 +0100 (CET) Injection-Info: dont-email.me; posting-host="8552662d97416c03078d7b971fbb1163"; logging-data="911328"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18eJqKSEhl4jLRHViBKOKWDlBDGoQMWoLs=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:u+4C0FEmqOfLuatrm9ZKnzjHXQA= sha1:RwZ2k04dosBOYKA+L/eNshj8grQ= Bytes: 5529 Michael S writes: > 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 :( In my view the cleverness is how "recursion" is accomplished by a means of a combination of using a stack to store a "return address" and restoring state by undoing a change rather than storing the old value. Using a switch() is just a detail (and to my way of thinking how the switch() is done here obscures the basic idea and makes the code harder to understand, but never mind that). > It more resemble computed GO TO in old FORTRAN or indirect jumps > in asm than idiomatic C switch. But it is a legal* C. I did program in FORTRAN briefly but don't remember ever using computed GO TO. And yes, I found that missing semicolon and put it back. Is there some reason you don't always use -pedantic? I pretty much always do. >> 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 hope to soon but am unable to right now (and maybe for a week or so due to circumstances beyond my control). For sure the code is different; whether it is non-trivially different I leave for others to judge. >> 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. An alternate idea is to use a 64-bit integer for 32 "top of stack" elements, or up to 32 I should say, and a stack with 64-bit values. Just an idea, it may not turn out to be useful. The few measurements I have done don't show a big difference in performance between the two methods. But I admit I wasn't paying close attention, and like I said only a few patterns of filling were exercised. > 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 idea of not going back to the originator (what you call the parent) is something I developed independently before looking at your latest code (and mostly I still haven't). Seems like a good idea. Two further comments. One, the new code is a lot more complicated than the previous code. I'm not sure the performance gain is worth the cost in complexity. What kind of speed improvements do you see, in terms of percent? Two, and more important, the new algorithm still uses O(NxN) memory for an N by N pixel field. We really would like to get that down to O(N) memory (and of course run just as fast). Have you looked into how that might be done?