Path: ...!news.mixmin.net!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: Wed, 20 Mar 2024 10:01:10 -0700 Organization: A noiseless patient Spider Lines: 125 Message-ID: <86zfusltwp.fsf@linuxsc.com> References: <86h6h3nvyz.fsf@linuxsc.com> <865xxiok09.fsf@linuxsc.com> <20240319131842.00002138@yahoo.com> <86o7b9ms7d.fsf@linuxsc.com> <20240320115416.00001ab5@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: dont-email.me; posting-host="7a780175fd21d30328a8a78d1217a04c"; logging-data="1691175"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18HN6izNvnBJAm7RtylDoGC/Dg6Ms0SoOI=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:zPy4KAYvWysBif8+x2C+DY+xNAo= sha1:jK4OmUc0hm36MqKi5jhv1tnvUJk= Bytes: 5867 Michael S writes: > On Tue, 19 Mar 2024 21:40:22 -0700 > Tim Rentsch wrote: > >> Michael S writes: >> >>> On Mon, 18 Mar 2024 22:42:14 -0700 >>> Tim Rentsch wrote: >>> >>>> Tim Rentsch writes: >>>> >>>> [...] >>>> >>>> Here is the refinement that uses a resizing rather than >>>> fixed-size buffer. >>>> [code] >>> >>> This variant is significantly slower than Malcolm's. >>> 2x slower for solid rectangle, 6x slower for snake shape. >> >> Slower with some shapes, faster in others. > > In my small test suit I found no cases where this specific code is > measurably faster than code of Malcolm. My test cases include pixel fields of 32k by 32k, with for example filling the entire field starting at the center point. Kind of a stress test but it turned up some interesting results. > I did find one case in which they are approximately equal. I call > it "slalom shape" and it's more or less designed to be the worst > case for algorithms that are trying to speed themselves by take > advantage of straight lines. > The slalom shape is generated by following code: > [code] Thanks, I may try that. >> In any case >> the code was written for clarity of presentation, with >> no attention paid to low-level performance. > > Yes, your code is easy to understand. Could have been easier > still if persistent indices had more meaningful names. I have a different view on that question. However I take your point. > In other post I showed optimized variant of your algorithm: - > 4-neighbors loop unrolled. Majority of the speed up come not from > unrolling itself, but from specialization of in-rectangle check > enabled by unroll. > - Todo queue implemented as circular buffer. > - Initial size of queue increased. > This optimized variant is more competitive with 'line-grabby' > algorithms in filling solid shapes and faster than them in > 'slalom' case. Yes, unrolling is an obvious improvement. I deliberately chose a simple (and non-optimized) method to make it easier to see how it works. Simple optimizations are left as an exercise for the reader. :) > Generally, I like your algorithm. > It was surprising for me that queue can work better than stack, my > intuition suggested otherwise, but facts are facts. Using a stack is like a depth-first search, and a queue is like a breadth-first search. For a pixel field of size N x N, doing a depth-first search can lead to memory usage of order N**2, whereas a breadth-first search has a "frontier" at most O(N). Another way to think of it is that breadth-first gets rid of visited nodes as fast as it can, but depth-first keeps them around for a long time when everything is reachable from anywhere (as will be the case in large simple reasons). >>> Besides, I don't think that use of VLA in library code is a good >>> idea. VLA is optional in latest C standards. And incompatible >>> with C++. >> >> The code uses a variably modified type, not a variable length >> array. > > I am not sufficiently versed in C Standard terminology to see a > difference. > Aren't they both introduced in C99 and made optional in later > standards? Ben explained the difference. I posted a short followup to his explanation. And yes, as of C11 VLAs and VMTs are both optional (it would be nice if a new C standard put back the requirement of variably modified types). >> Again, the choice is for clarity of presentation. If >> someone wants to get rid of the variably modified types, it's >> very easy to do, literally a five minute task. > > Yes, that's what it took for me. > But I knew that variably modified types exist, even if I didn't know > that they are called such. > OTOH, many (majority?) of C programmers never heard about them. Something that surprised me is that some C programmers don't know what compound literals are, even though they have been around more than 20 years. I'm not inclined to try to cater to people who program in C but aren't at least aware of what was done more than 20 years ago. >> Anyway the interface is poorly designed to start with, [...] > > That's true. [...] Yes! Hoo rah! >> If someone wants to use the functionality from C++, it's >> easy enough to write a C wrapper function to do that. >> IMO C++ has diverged sufficiently from C so that there >> is little to be gained by trying to make code interoperable >> between the two languages. > > From the practical perspective, the biggest obstacle is that your > code can't be compiled with popular Microsoft compilers. Some people might consider that a plus rather than a minus. ;)