Path: ...!2.eu.feeder.erje.net!feeder.erje.net!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 - worst memory size Date: Thu, 11 Apr 2024 15:20:33 +0300 Organization: A noiseless patient Spider Lines: 144 Message-ID: <20240411152033.00007173@yahoo.com> References: <86h6h3nvyz.fsf@linuxsc.com> <865xxiok09.fsf@linuxsc.com> <20240319131842.00002138@yahoo.com> <86o7b9ms7d.fsf@linuxsc.com> <20240320115416.00001ab5@yahoo.com> <86zfusltwp.fsf@linuxsc.com> <20240324193352.000062e9@yahoo.com> <86jzlrk0f6.fsf@linuxsc.com> <20240405173033.00006145@yahoo.com> <868r1k1uq8.fsf@linuxsc.com> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Injection-Date: Thu, 11 Apr 2024 14:20:37 +0200 (CEST) Injection-Info: dont-email.me; posting-host="948a3d46d314eac708dbd3a3c8e1a9c2"; logging-data="1721437"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19+9U22G0khCfWZoQLdcm99EL6Evzbz404=" Cancel-Lock: sha1:VXB0FTeZFHPOP2f+YxVRzJnDPh4= X-Newsreader: Claws Mail 3.19.1 (GTK+ 2.24.33; x86_64-w64-mingw32) Bytes: 7874 On Wed, 10 Apr 2024 19:47:11 -0700 Tim Rentsch wrote: > Michael S writes: > > > On Sun, 24 Mar 2024 10:24:45 -0700 > > Tim Rentsch wrote: > > > >> Michael S writes: > >> > >>> On Wed, 20 Mar 2024 10:01:10 -0700 > >>> Tim Rentsch wrote: > >>> > >>>> Michael S writes: > >> > >> [...] > >> > >>>>> 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). > >>> > >>> For my test cases the FIFO depth of your algorithm never exceeds > >>> min(width,height)*2+2. I wonder if existence of this or similar > >>> limit can be proven theoretically. > >> > >> I believe it is possible to prove the strict FIFO algorithm is > >> O(N) for an N x N pixel field, but I haven't tried to do so in > >> any rigorous way, nor do I know what the constant is. It does > >> seem to be larger than 2. > > Before I do anything else I should correct a bug in my earlier > FIFO algorithm. The initialization of the variable jx should > read > > Index const jx = used*3 < open ? k : j+open/3 &m; > I lost track, sorry. I can not find your code that contains line similar to this. Can you point to specific post? > rather than what it used to. (The type may have changed but that > is incidental; what matters is the value of the initializing > expression.) I don't know what I was thinking when I wrote the > previous version, it's just completely wrong. > > > It seems that in worst case the strict FIFO algorithm is the same as > > the rest of them, i.e. O(NN) where NN is the number of re-colored > > points. Below is an example of the shape for which I measured > > memory consumption for 3840x2160 image almost exactly 4x as much as > > for 1920x1080. > > I agree, the empirical evidence here and in my own tests is quite > compelling. > BTW, I am no longer agree with myself about "the rest of them". By now, I know at least one method that is O(W*log(H)). It is even quite fast for majority of my test shapes. Unfortunately, [in its current form] it is abysmally slow (100x) for minority of tests. [In it's current form] it has other disadvantages as well like consuming non-trivial amount of memory when handling small spot in the big image. But that can be improved. I am less sure that worst-case speed can be improved enough to make it generally acceptable. I think, I said enough for you to figure out a general principle of this algorithm. I don't want to post code here before I try few improvements. > That said, the constant factor for the FIFO algorithm is lower > than the stack-based algorithms, even taking into account the > difference in sizes for queue and stack elements. Moreover cases > where FIFO algorithms are O( NxN ) are unusual and sparse, > whereas the stack-based algorithms tend to use a lot of memory > in lots of common and routine cases. On the average FIFO > algorithms typically use a lot less memory (or so I conjecture). > > > [code to generate fractal tree pattern] > > Thank you for this. I incorporated it into my set of test > patterns more or less as soon as it was posted. > > Now that I have taken some time to play around with different > algorithms and have been more systematic in doing speed > comparisons between different algorithms, on different patterns, > and with a good range of sizes, I have some general thoughts > to offer. > > Stack-based methods tend to do well on long skinny patterns and > tend to do not as well on fatter patterns such as circles or > squares. The fractal pattern is ideal for a stack-based method. > Conversely, patterns that are mostly solid shapes don't fare as > well under stack-based methods, at least not the ones that have > been posted in this thread, and also they tend to use more memory > in those cases. > Indeed, with solid shapes it uses more memory. But at least in my tests on my hardware with this sort of shapes it is easily faster than anything else. The difference vs the best of the rest is especially big at 4K images on AMD Zen3 based hardware, but even on Intel Skylake which generally serves as equalizer between different algorithms, the speed advantage of 2x2 stack is significant. > I've been playing around with a more elaborate, mostly FIFO > method, in hopes of getting something that offers the best > of both worlds. The results so far are encouraging, but a > fair amount of tuning has been necessary (and perhaps more > still is), and comparisons have been done on just the one > test server I have available. So I don't know how well it > would hold up on other hardware, including especially more > recent hardware. Under these circumstances I feel it is > premature to post actual code, especially since the code > is still in flux. > > This topic has been more interesting that I was expecting, and > also more challenging. That's not the first time in my practice where problems with simple formulation begots interesting challenges. Didn't Donald Knuth wrote 300 or 400 pages about sorting and still ended up quite far away from exhausting the topic? > I have a strong rule against writing > functions more than about 60 lines long. For the problem of > writing an acceptably quick flood-fill algorithm, I think it would > at the very least be a lot of work to write code to do that while > still observing a limit on function length of even 100 lines, let > alone 60. So why not break it down to smaller pieces ? Myself, I have no rules. In my real work I am quite happy with dispatchers of network messages that are 250-300 lines long. But if I had this sort of rules, I'd certainly decompose.