Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #383647 > unrolled thread
| Started by | fir <fir@grunge.pl> |
|---|---|
| First post | 2024-03-16 05:11 +0100 |
| Last post | 2024-05-15 09:57 -0700 |
| Articles | 20 on this page of 167 — 16 participants |
Back to article view | Back to comp.lang.c
filling area by color atack safety fir <fir@grunge.pl> - 2024-03-16 05:11 +0100
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-16 11:33 +0000
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-16 13:55 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-16 14:41 +0000
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-17 10:42 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 03:00 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-18 14:23 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 14:13 -0700
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-19 16:05 +0100
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-19 17:16 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-19 17:33 +0000
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-19 23:07 +0100
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-20 09:29 +0100
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 03:04 -0700
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-16 14:45 +0000
Re: filling area by color atack safety scott@slp53.sl.home (Scott Lurndal) - 2024-03-16 18:21 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-16 20:02 +0000
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-16 13:29 -0700
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-17 13:19 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-18 14:40 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-19 23:23 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 15:32 +0200
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-17 11:25 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-17 12:37 +0000
Re: filling area by color atack safety Kaz Kylheku <433-929-6894@kylheku.com> - 2024-03-17 17:11 +0000
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-23 00:21 +0000
Re: filling area by color atack safety scott@slp53.sl.home (Scott Lurndal) - 2024-03-23 14:43 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-23 11:48 -0700
Re: filling area by color atack safety scott@slp53.sl.home (Scott Lurndal) - 2024-03-24 20:48 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-28 22:51 -0700
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-16 15:40 +0100
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-16 15:09 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-17 14:56 +0000
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 17:42 +0200
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 18:25 +0200
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 19:39 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 11:36 -0700
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-18 18:51 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 23:10 -0700
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-19 12:06 +0000
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 00:03 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 01:17 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 00:30 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 12:06 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 13:44 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 15:44 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 15:17 +0100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 02:15 +0100
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-17 17:45 +0100
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-17 18:28 +0000
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-18 07:58 +0100
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-18 09:26 +0000
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-18 17:28 +0100
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-18 17:25 +0000
Re: filling area by color atack safety scott@slp53.sl.home (Scott Lurndal) - 2024-03-18 17:42 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-18 18:50 +0000
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-19 11:41 +0100
Re: filling area by color atack safety Richard Harnden <richard.nospam@gmail.invalid> - 2024-03-19 12:19 +0000
Re: filling area by color atack safety Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-03-18 11:10 -0700
Keith-world (Was: filling area by color atack safety) gazelle@shell.xmission.com (Kenny McCormack) - 2024-03-18 22:42 +0000
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-19 12:31 +0100
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-18 16:18 -0700
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-19 11:32 +0100
Re: filling area by color atack safety scott@slp53.sl.home (Scott Lurndal) - 2024-03-16 18:25 +0000
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-17 10:31 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-17 12:28 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-17 12:49 +0000
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-17 17:59 +0100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-19 23:52 +0100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 01:36 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 14:46 +0200
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-17 12:54 +0000
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 15:15 +0200
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-17 13:23 +0000
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 15:37 +0200
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-17 18:05 +0100
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-17 14:10 +0000
Re: filling area by color atack safety Spiros Bousbouras <spibou@gmail.com> - 2024-03-17 16:58 +0000
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-17 22:14 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-17 22:21 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 02:30 -0700
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-18 11:08 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 22:54 -0700
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-19 11:41 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-19 21:19 -0700
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 01:13 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 10:41 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 15:20 +0100
Re: filling area by color atack safety Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2024-03-17 14:27 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-17 15:13 +0000
Re: filling area by color atack safety Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> - 2024-03-19 10:57 +1100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 01:26 +0100
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-16 19:13 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-16 20:23 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-16 20:29 +0000
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 01:48 +0100
Re: filling area by color atack safety Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> - 2024-03-22 13:04 +1100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-22 17:55 +0300
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-22 18:31 +0300
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-23 11:06 +0100
Re: filling area by color atack safety Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> - 2024-03-17 18:03 +1100
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 13:09 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 22:42 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-19 13:18 +0200
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-19 11:57 +0000
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-19 15:49 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-19 21:43 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 10:56 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-20 06:51 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-19 19:18 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 09:27 +0100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 09:39 +0100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 09:51 +0100
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-20 07:27 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-24 20:27 +0300
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-24 13:26 -0700
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-24 14:26 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-25 01:28 +0300
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-26 17:52 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-30 00:54 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-30 21:26 +0300
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-09 01:00 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-28 23:04 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-29 15:21 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-29 23:58 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-30 21:15 +0300
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-31 10:54 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-09 02:32 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-09 01:55 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-30 11:59 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-20 10:26 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-21 15:36 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-21 09:47 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-19 21:40 -0700
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-19 21:43 -0700
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-19 21:48 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 11:54 +0200
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-20 10:23 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-20 12:06 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-20 07:52 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-20 10:01 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-24 19:33 +0300
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-24 10:24 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-25 01:04 +0300
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-05 17:30 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-10 19:47 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-11 15:20 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 21:06 -0700
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 21:55 -0700
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 22:09 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-12 11:13 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-13 08:30 -0700
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 22:38 -0700
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 22:43 -0700
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-12 11:59 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-13 20:26 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-13 10:54 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-13 23:11 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-17 10:47 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-17 22:41 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-19 14:59 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-20 21:10 +0300
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-25 17:56 +0300
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-05-03 18:33 +0300
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-06-05 17:45 +0300
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-06-05 17:59 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-05-15 09:57 -0700
Page 8 of 9 — ← Prev page 1 2 3 4 5 6 7 [8] 9 Next page →
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-20 10:01 -0700 |
| Message-ID | <86zfusltwp.fsf@linuxsc.com> |
| In reply to | #383773 |
Michael S <already5chosen@yahoo.com> writes: > On Tue, 19 Mar 2024 21:40:22 -0700 > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > >> Michael S <already5chosen@yahoo.com> writes: >> >>> On Mon, 18 Mar 2024 22:42:14 -0700 >>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>> >>>> Tim Rentsch <tr.17687@z991.linuxsc.com> 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. ;)
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-24 19:33 +0300 |
| Message-ID | <20240324193352.000062e9@yahoo.com> |
| In reply to | #383800 |
On Wed, 20 Mar 2024 10:01:10 -0700 Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > Michael S <already5chosen@yahoo.com> writes: > > > On Tue, 19 Mar 2024 21:40:22 -0700 > > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > > > >> Michael S <already5chosen@yahoo.com> writes: > >> > >>> On Mon, 18 Mar 2024 22:42:14 -0700 > >>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > >>> > >>>> Tim Rentsch <tr.17687@z991.linuxsc.com> 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). > 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.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-24 10:24 -0700 |
| Message-ID | <86jzlrk0f6.fsf@linuxsc.com> |
| In reply to | #383959 |
Michael S <already5chosen@yahoo.com> writes:
> On Wed, 20 Mar 2024 10:01:10 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> 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.
As for finding a worst case, try this (expressed in pseudo code):
let pc = { width/2, height/2 }
// assume pixel field 'field' starts out as all zeroes
color 8 "legs" with the value '1' as follows:
leg from { 1, pc.y-1 } to { pc.x -1, pc.y-1 }
leg from { 1, pc.y+1 } to { pc.x -1, pc.y+1 }
leg from { px.x + 1, pc.y-1 } to { width-2, pc.y-1 }
leg from { px.x + 1, pc.y+1 } to { width-2, pc.y+1 }
leg from { px.x - 1, 1 } to { px.x -1, pc.y-1 }
leg from { px.x + 1, 1 } to { px.x +1, pc.y-1 }
leg from { px.x - 1, pc.y+1 } to { px.x -1, height/2 }
leg from { px.x + 1, pc.y+1 } to { px.x +1, height/2 }
So the pixel field should look like this (with longer legs for a
bigger pixel field), with '-' being 0 and '*' being 1:
+-----------------------+
| - - - - - - - - - - - |
| - - - - * - * - - - - |
| - - - - * - * - - - - |
| - - - - * - * - - - - |
| - * * * * - * * * * - |
| - - - - - - - - - - - |
| - * * * * - * * * * - |
| - - - - * - * - - - - |
| - - - - * - * - - - - |
| - - - - * - * - - - - |
| - - - - - - - - - - - |
+-----------------------+
Now start coloring at the center point with a new value
of 2.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-25 01:04 +0300 |
| Message-ID | <20240325010432.0000460b@yahoo.com> |
| In reply to | #383962 |
On Sun, 24 Mar 2024 10:24:45 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Michael S <already5chosen@yahoo.com> writes:
>
> > On Wed, 20 Mar 2024 10:01:10 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >
> >> Michael S <already5chosen@yahoo.com> 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.
>
> As for finding a worst case, try this (expressed in pseudo code):
>
> let pc = { width/2, height/2 }
> // assume pixel field 'field' starts out as all zeroes
> color 8 "legs" with the value '1' as follows:
>
> leg from { 1, pc.y-1 } to { pc.x -1, pc.y-1 }
> leg from { 1, pc.y+1 } to { pc.x -1, pc.y+1 }
> leg from { px.x + 1, pc.y-1 } to { width-2, pc.y-1 }
> leg from { px.x + 1, pc.y+1 } to { width-2, pc.y+1 }
>
> leg from { px.x - 1, 1 } to { px.x -1, pc.y-1 }
> leg from { px.x + 1, 1 } to { px.x +1, pc.y-1 }
> leg from { px.x - 1, pc.y+1 } to { px.x -1, height/2 }
> leg from { px.x + 1, pc.y+1 } to { px.x +1, height/2 }
>
>
> So the pixel field should look like this (with longer legs for a
> bigger pixel field), with '-' being 0 and '*' being 1:
>
> +-----------------------+
> | - - - - - - - - - - - |
> | - - - - * - * - - - - |
> | - - - - * - * - - - - |
> | - - - - * - * - - - - |
> | - * * * * - * * * * - |
> | - - - - - - - - - - - |
> | - * * * * - * * * * - |
> | - - - - * - * - - - - |
> | - - - - * - * - - - - |
> | - - - - * - * - - - - |
> | - - - - - - - - - - - |
> +-----------------------+
>
> Now start coloring at the center point with a new value
> of 2.
Yes, I see. It is close to min(width,height)*4.
Thank you.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-04-05 17:30 +0300 |
| Subject | Re: filling area by color atack safety - worst memory size |
| Message-ID | <20240405173033.00006145@yahoo.com> |
| In reply to | #383962 |
On Sun, 24 Mar 2024 10:24:45 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Michael S <already5chosen@yahoo.com> writes:
>
> > On Wed, 20 Mar 2024 10:01:10 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >
> >> Michael S <already5chosen@yahoo.com> 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.
>
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.
static void make_fractal_tree_recursive(
unsigned char* image,
int width,
int nx,
int ny,
unsigned char pen_c)
{
if (nx < 3 && ny < 3) {
// small rectangle - solid fill
for (int y = 0; y < ny; ++y)
for (int x = 0; x < nx; ++x)
image[width*y+x] = pen_c;
return;
}
if (nx >= ny) {
int xc = (nx-1)/2;
if (xc - 1 > 0) { // left sub-plot
make_fractal_tree_recursive(image, width, xc - 1, ny, pen_c);
}
if (xc + 2 < nx) { // right sub-plot
make_fractal_tree_recursive(&image[xc+2], width,
nx - (xc + 2), ny, pen_c);
}
// draw vertical cross
for (int y = 0; y < ny; ++y)
image[width*y+xc] = pen_c;
int yc = (ny-1)/2;
image[width*yc+xc-1] = pen_c;
image[width*yc+xc+1] = pen_c;
} else {
int yc = (ny-1)/2;
if (yc - 1 > 0) { // upper sub-plot
make_fractal_tree_recursive(image, width, nx, yc - 1, pen_c);
}
if (yc + 2 < ny) { // lower sub-plot
make_fractal_tree_recursive(&image[(yc+2)*width], width, nx,
ny -(yc + 2), pen_c);
}
// draw horizontal cross
for (int x = 0; x < nx; ++x)
image[width*yc+x] = pen_c;
int xc = (nx-1)/2;
image[width*(yc-1)+xc] = pen_c;
image[width*(yc+1)+xc] = pen_c;
}
}
static void make_fractal_tree(
unsigned char* image,
int width,
int height,
unsigned char background_c,
unsigned char pen_c)
{
memset(image, background_c, width*height);
make_fractal_tree_recursive(image, width, width, height, pen_c);
}
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-04-10 19:47 -0700 |
| Subject | Re: filling area by color atack safety - worst memory size |
| Message-ID | <868r1k1uq8.fsf@linuxsc.com> |
| In reply to | #384179 |
Michael S <already5chosen@yahoo.com> writes:
> On Sun, 24 Mar 2024 10:24:45 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:
>>
>>> On Wed, 20 Mar 2024 10:01:10 -0700
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>>
>>>> Michael S <already5chosen@yahoo.com> 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;
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.
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.
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. 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.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-04-11 15:20 +0300 |
| Subject | Re: filling area by color atack safety - worst memory size |
| Message-ID | <20240411152033.00007173@yahoo.com> |
| In reply to | #384278 |
On Wed, 10 Apr 2024 19:47:11 -0700 Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > Michael S <already5chosen@yahoo.com> writes: > > > On Sun, 24 Mar 2024 10:24:45 -0700 > > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > > > >> Michael S <already5chosen@yahoo.com> writes: > >> > >>> On Wed, 20 Mar 2024 10:01:10 -0700 > >>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > >>> > >>>> Michael S <already5chosen@yahoo.com> 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.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-04-11 21:06 -0700 |
| Subject | Re: filling area by color atack safety - worst memory size |
| Message-ID | <86zftzz0kx.fsf@linuxsc.com> |
| In reply to | #384282 |
Michael S <already5chosen@yahoo.com> writes:
(I'm replying in pieces.)
> On Wed, 10 Apr 2024 19:47:11 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> 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?
Easier for me just to repost the corrected algorithm. The
type UC is an unsigned char, the types Index and Count are
size_t (or maybe unsigned long long), the type U32 is a
32-bit unsigned type.
Please excuse any minor glitches, I have done some hand
editing to take out various bits of diagnostic code.
extern Count
fifo_fill( UC *field, Index w, Index h, Point p0, UC old, UC new ){
Index const xm = w-1;
Index const ym = h-1;
Index j = 0;
Index k = 0;
Index n = 1u << 10;
Index m = n-1;
U32 *todo = malloc( n * sizeof *todo );
Index x = p0.x;
Index y = p0.y;
if( !todo || x >= w || y >= h || field[ x+y*w ] != old ) return 0;
todo[ k++ ] = x<<16 | y;
while( j != k ){
Index used = j < k ? k-j : k+n-j;
Index open = n - used;
if( open < used/16 ){
Index new_n = n*2;
Index new_m = new_n-1;
Index new_j = j < k ? j : j+n;
U32 *t = realloc( todo, new_n * sizeof *t );
if( ! t ) break;
if( j != new_j ) memcpy( t+new_j, t+j, (n-j) * sizeof *t );
todo = t, n = new_n, m = new_m, j = new_j, open = n-used;
}
assert( (k-j&m) == used && open+used == n );
Index const jx = used*3 < open ? k : j+open/3 &m; // here it is!
while( j != jx ){
if( (k-j&m) > mm ) mm = k-j&m;
U32 p = todo[j]; j = j+1 &m;
x = p >> 16, y = p & 0xFFFF;
if( x > 0 && field[ x-1 + y*w ] == old ){
todo[k] = x-1<<16 | y, k = k+1&m, field[ x-1 + y*w ] = new;
}
if( y > 0 && field[ x + (y-1)*w ] == old ){
todo[k] = x<<16 | y-1, k = k+1&m, field[ x + (y-1)*w ] = new;
}
if( x < xm && field[ x+1 + y*w ] == old ){
todo[k] = x+1<<16 | y, k = k+1&m, field[ x+1 + y*w ] = new;
}
if( y < ym && field[ x + (y+1)*w ] == old ){
todo[k] = x<<16 | y+1, k = k+1&m, field[ x + (y+1)*w ] = new;
}
}
}
return free( todo ), 0;
}
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-04-11 21:55 -0700 |
| Subject | Re: filling area by color atack safety - worst memory size |
| Message-ID | <86v84nyybp.fsf@linuxsc.com> |
| In reply to | #384282 |
Michael S <already5chosen@yahoo.com> writes: > On Wed, 10 Apr 2024 19:47:11 -0700 > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > >> Michael S <already5chosen@yahoo.com> writes: >>> 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. Thank you for the implied compliment. At this point I think the probability that I will figure it out anytime soon is pretty low.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-04-11 22:09 -0700 |
| Subject | Re: filling area by color atack safety - worst memory size |
| Message-ID | <86o7afyxnk.fsf@linuxsc.com> |
| In reply to | #384282 |
Michael S <already5chosen@yahoo.com> writes:
> On Wed, 10 Apr 2024 19:47:11 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> 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.
This comment makes me wonder if I should post my timing results.
Maybe I will (and including an appropriate disclaimer).
I do timings over these sizes:
25 x 19
19 x 25
200 x 200
1280 x 760
760 x 1280
1920 x 1080
1080 x 1920
3840 x 2160
2160 x 3840
4096 x 4096
38400 x 21600
21600 x 38400
32767 x 32767
32768 x 32768
with these patterns:
fractal
slalom
rotated slalom
horizontal snake and vertical snake
cross in cross
donut aka ellipse with hole
entire field starting from center
If you have other patterns to suggest that would be great,
I can try to incorporate them (especially if there is
code to generate the pattern).
Patterns are allowed to include a nominal start point,
otherwise I can make an arbitrary choice and assign one.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-04-12 11:13 +0300 |
| Subject | Re: filling area by color atack safety - worst memory size |
| Message-ID | <20240412111305.00004bf2@yahoo.com> |
| In reply to | #384298 |
On Thu, 11 Apr 2024 22:09:51 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Michael S <already5chosen@yahoo.com> writes:
>
> > On Wed, 10 Apr 2024 19:47:11 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >
> >> 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.
>
> This comment makes me wonder if I should post my timing results.
> Maybe I will (and including an appropriate disclaimer).
>
> I do timings over these sizes:
>
> 25 x 19
> 19 x 25
> 200 x 200
> 1280 x 760
> 760 x 1280
> 1920 x 1080
> 1080 x 1920
> 3840 x 2160
> 2160 x 3840
> 4096 x 4096
> 38400 x 21600
> 21600 x 38400
> 32767 x 32767
> 32768 x 32768
>
I didn't went that far up (ended at 4K) and I only test landscape sizes.
May be, I'd add portrait option to see anisotropic behaviors.
For bigger sizes, correctness is interesting, speed - not so much, since
they are unlikely to be edited in interactive manner.
> with these patterns:
>
> fractal
> slalom
> rotated slalom
> horizontal snake and vertical snake
> cross in cross
> donut aka ellipse with hole
> entire field starting from center
>
> If you have other patterns to suggest that would be great,
> I can try to incorporate them (especially if there is
> code to generate the pattern).
>
> Patterns are allowed to include a nominal start point,
> otherwise I can make an arbitrary choice and assign one.
My suit is about the same with following exceptions:
1. I didn't add donut yet
2. + 3 greeds with cell size 2, 3 and 4
3. + fractal tree
4. + entire field starting from corner
It seems, neither of us tests the cases in which linear dimensions of
the shape are much smaller than those of the field.
static void make_grid(
unsigned char *image,
int width, int height,
unsigned char background_c,
unsigned char pen_c, int cell_sz)
{
for (int y = 0; y < height; ++y) {
unsigned char* p = &image[y*width];
if (y % cell_sz == 0) {
memset(p, pen_c, width);
} else {
for (int x = 0; x < width; ++x)
p[x] = x % cell_sz ? background_c : pen_c;
}
}
}
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-04-13 08:30 -0700 |
| Subject | Re: filling area by color atack safety - worst memory size |
| Message-ID | <86y19hxouc.fsf@linuxsc.com> |
| In reply to | #384305 |
Michael S <already5chosen@yahoo.com> writes:
> On Thu, 11 Apr 2024 22:09:51 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
[...]
>> I do timings over these sizes:
>>
>> 25 x 19
>> 19 x 25
>> 200 x 200
>> 1280 x 760
>> 760 x 1280
>> 1920 x 1080
>> 1080 x 1920
>> 3840 x 2160
>> 2160 x 3840
>> 4096 x 4096
>> 38400 x 21600
>> 21600 x 38400
>> 32767 x 32767
>> 32768 x 32768
>
> I didn't went that far up (ended at 4K)
I test large sizes for three reasons. One, even if viewable
area is smaller, virtual displays might be much larger. Two,
to see how the algorithms scale. Three, larger areas have
relatively less influence from edge effects.
Also I have now added
275 x 25 25 x 275
400 x 300 300 x 400
640 x 480 480 x 640
1600 x 900 900 x 1600
16000 x 9000 9000 x 16000
> and I only test landscape sizes. May be, I'd add portrait option
> to see anisotropic behaviors.
I decided to do both, one, for symmetry (and there are still some
applications for portrait mode), and two, to see whether that has
an effect on behavior (indeed my latest algorithm is anisotropic,
so it is good to test the flipped sizes).
>> with these patterns:
>>
>> fractal
>> slalom
>> rotated slalom
>> horizontal snake and vertical snake
>> cross in cross
>> donut aka ellipse with hole
>> entire field starting from center
>>
>> If you have other patterns to suggest that would be great,
>> I can try to incorporate them (especially if there is
>> code to generate the pattern).
>>
>> Patterns are allowed to include a nominal start point,
>> otherwise I can make an arbitrary choice and assign one.
>
> My suit is about the same with following exceptions:
> 1. I didn't add donut yet
> 2. + 3 greeds with cell size 2, 3 and 4
> 3. + fractal tree
By "fractal" I meant fractal tree. Sorry if that was confusing.
> 4. + entire field starting from corner
I used to do that but took it out as redundant. I've added
it back now. :)
> It seems, neither of us tests the cases in which linear dimensions
> of the shape are much smaller than those of the field.
Shouldn't make a difference (for any of the algorithms shown) as
long as there is at least a 1 pixel border around the pattern.
Maybe I will add that variation (ick, a lot of work). By the
way the donut pattern already has a 1 pixel border, ie, does
not touch any edge.
> static void make_grid(
> unsigned char *image,
> int width, int height,
> unsigned char background_c,
> unsigned char pen_c, int cell_sz)
> {
> for (int y = 0; y < height; ++y) {
> unsigned char* p = &image[y*width];
> if (y % cell_sz == 0) {
> memset(p, pen_c, width);
> } else {
> for (int x = 0; x < width; ++x)
> p[x] = x % cell_sz ? background_c : pen_c;
> }
> }
> }
Ahh, this is what you meant by greed. A nice set of patterns.
I wrote a variation where the "line width" as well as the
"hole width" is variable, and added a bunch of those to my
tests (so a full timing suite now runs for several hours).
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-04-11 22:38 -0700 |
| Subject | Re: filling area by color atack safety - worst memory size |
| Message-ID | <86jzl3ywb0.fsf@linuxsc.com> |
| In reply to | #384282 |
Michael S <already5chosen@yahoo.com> writes: > On Wed, 10 Apr 2024 19:47:11 -0700 > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >> 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? In my copy of volume 3 of TAOCP, the chapter on sorting takes up 388 pages. On the other hand, only 108 pages of that deals with what we normally think of as sorting algorithms today, and even that part is longer than it needs to be because of Knuth's exhaustive (and exhausting) writing style. Don Knuth would never write a book in the style of The C Programming Language.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-04-11 22:43 -0700 |
| Subject | Re: filling area by color atack safety - worst memory size |
| Message-ID | <86frvryw41.fsf@linuxsc.com> |
| In reply to | #384282 |
Michael S <already5chosen@yahoo.com> writes: > On Wed, 10 Apr 2024 19:47:11 -0700 > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > >> 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 ? The better algorithms I have done are long and also make liberal use of goto's. Maybe it isn't impossible to break one or more of these algorithms into smaller pieces, but C doesn't make it easy.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-04-12 11:59 -0700 |
| Subject | Re: filling area by color atack safety - worst memory size |
| Message-ID | <86bk6ez9te.fsf@linuxsc.com> |
| In reply to | #384282 |
Michael S <already5chosen@yahoo.com> writes: > On Wed, 10 Apr 2024 19:47:11 -0700 > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > >> 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'm curious to know how your 2x2 algorithm compares to my second (longer) stack-based algorithm when run on the Zen3. On my test hardware they are roughly comparable, depending on size and pattern. My curiosity includes the fatter patterns as well as the long skinny ones.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-04-13 20:26 +0300 |
| Subject | Re: filling area by color atack safety - worst memory size |
| Message-ID | <20240413202639.00006182@yahoo.com> |
| In reply to | #384315 |
On Fri, 12 Apr 2024 11:59:25 -0700 Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > Michael S <already5chosen@yahoo.com> writes: > > > On Wed, 10 Apr 2024 19:47:11 -0700 > > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > > > >> 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'm curious to know how your 2x2 algorithm compares to my > second (longer) stack-based algorithm when run on the Zen3. > On my test hardware they are roughly comparable, depending > on size and pattern. My curiosity includes the fatter > patterns as well as the long skinny ones. This particular server turned off right now. Hopefully, next Monday I would be able to test on it. It would help if in the mean time you point me to specific post with code.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-04-13 10:54 -0700 |
| Subject | Re: filling area by color atack safety - worst memory size |
| Message-ID | <86ttk5xi55.fsf@linuxsc.com> |
| In reply to | #384325 |
Michael S <already5chosen@yahoo.com> writes: > On Fri, 12 Apr 2024 11:59:25 -0700 > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > >> I'm curious to know how your 2x2 algorithm compares to my >> second (longer) stack-based algorithm when run on the Zen3. >> On my test hardware they are roughly comparable, depending >> on size and pattern. My curiosity includes the fatter >> patterns as well as the long skinny ones. > > This particular server turned off right now. > Hopefully, next Monday I would be able to test on it. > It would help if in the mean time you point me to specific post > with code. Does this help? Message-ID: <8634ru3ofo.fsf@linuxsc.com>
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-04-13 23:11 +0300 |
| Subject | Re: filling area by color atack safety - worst memory size |
| Message-ID | <20240413231159.000015e4@yahoo.com> |
| In reply to | #384328 |
On Sat, 13 Apr 2024 10:54:46 -0700 Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > Michael S <already5chosen@yahoo.com> writes: > > > On Fri, 12 Apr 2024 11:59:25 -0700 > > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > > > >> I'm curious to know how your 2x2 algorithm compares to my > >> second (longer) stack-based algorithm when run on the Zen3. > >> On my test hardware they are roughly comparable, depending > >> on size and pattern. My curiosity includes the fatter > >> patterns as well as the long skinny ones. > > > > This particular server turned off right now. > > Hopefully, next Monday I would be able to test on it. > > It would help if in the mean time you point me to specific post > > with code. > > Does this help? Message-ID: <8634ru3ofo.fsf@linuxsc.com> Yes, it is.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-04-17 10:47 -0700 |
| Subject | Re: filling area by color atack safety - worst memory size |
| Message-ID | <86plunyj82.fsf@linuxsc.com> |
| In reply to | #384315 |
Michael S <already5chosen@yahoo.com> writes: [...] > Finally found the time for speed measurements. [...] I got these. Thank you. The format used didn't make it easy to do any automated processing. I was able to get around that, although it would have been nicer if that had been easier. The results you got are radically different than my own, to the point where I wonder if there is something else going on. Considering that, since I now have no way of doing any useful measuring, it seems there is little point in any further development or investigation on my part. It's been fun, even if ultimately inconclusive.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-04-17 22:41 +0300 |
| Subject | Re: filling area by color atack safety - worst memory size |
| Message-ID | <20240417224126.0000727a@yahoo.com> |
| In reply to | #384359 |
On Wed, 17 Apr 2024 10:47:25 -0700 Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > Michael S <already5chosen@yahoo.com> writes: > > [...] > > > Finally found the time for speed measurements. [...] > > I got these. Thank you. > > The format used didn't make it easy to do any automated > processing. I was able to get around that, although it > would have been nicer if that had been easier. > > The results you got are radically different than my own, > to the point where I wonder if there is something else > going on. > What are your absolute result? Are they much faster, much slower or similar to mine? Also it would help if you find out characteristics of your test hardware. > Considering that, since I now have no way of doing any > useful measuring, it seems there is little point in any > further development or investigation on my part. It's > been fun, even if ultimately inconclusive. I am still interested in combination of speed that does not suck with O(N) worst-case memory footprint. I already have couple of variants of the former, but so far they are all unreasonably slow - ~5 times slower than the best.
[toc] | [prev] | [next] | [standalone]
Page 8 of 9 — ← Prev page 1 2 3 4 5 6 7 [8] 9 Next page →
Back to top | Article view | comp.lang.c
csiph-web