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 2 of 9 — ← Prev page 1 [2] 3 4 5 6 7 8 9 Next page →
| From | fir <fir@grunge.pl> |
|---|---|
| Date | 2024-03-19 23:23 +0100 |
| Message-ID | <utd392$2e30d$1@i2pn2.org> |
| In reply to | #383662 |
Malcolm McLean wrote: > On 16/03/2024 18:21, Scott Lurndal wrote: >> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: >>> On 16/03/2024 13:55, Ben Bacarisse wrote: >>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: >>>> >>>>> Recursion make programs harder to reason about and prove correct. >>>> >>>> Are you prepared to offer any evidence to support this astonishing >>>> statement or can we just assume it's another Malcolmism? >>>> >>> >>> Example given. A recursive algorithm which is hard to reason about and >> >> Perhaps hard for _you_ to reason about. That doesn't >> generalize to every other programmer that might read that >> code. >> >> > From experience this one blows the stack, but not always. Sometimes > it's OK to use. > > Since you can reason about it so easily, you can tell the others when > you're OK and when you are not, in a handy intuitive way so that someone > thinking of implementing it will know. > from "effective c" or maybe i call it "optimal" point of view recursion as it is implementeded in c is wrong (it is sub-optimel) so i agree with that statement - hovever a big dose of world today programs in a non optimal way (for example whole that python ond other programing ways is non optimal)..and thus te recursion may be found one way ..and i must say whan i way younger i was much more hardfixed to optimal coding..today i almost no code at all and lost a interest (i mean "being interested") in many things ..i also consider that non optimal cases more interesting - and generallt this recursion would be standable - especialy if for example windows has this "guard page" some exception based mechanism that would allow to resize stack up its default two megabytes (which is a bit small size as for today) instead of crashing application im not sure hovever if its done and if its posoble as i understand there is exception when tryibgf to read write immediatelly after stack reserve but not quite if someone just moves up stack pointer (like when allocating stack space for array) but those machanisms could be handy
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-17 15:32 +0200 |
| Message-ID | <20240317153203.00006be1@yahoo.com> |
| In reply to | #383657 |
On Sat, 16 Mar 2024 18:21:38 GMT scott@slp53.sl.home (Scott Lurndal) wrote: > Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: > >On 16/03/2024 13:55, Ben Bacarisse wrote: > >> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: > >> > >>> Recursion make programs harder to reason about and prove correct. > >>> > >> > >> Are you prepared to offer any evidence to support this astonishing > >> statement or can we just assume it's another Malcolmism? > >> > > > >Example given. A recursive algorithm which is hard to reason about > >and > > Perhaps hard for _you_ to reason about. That doesn't > generalize to every other programmer that might read that > code. > > As a matter of fact, David Brown was not able to reason about depth of recursion in fir's code. And you answered David's post without spotting his mistake. Now, I don't know if you didn't spot his mistake because you didn't read this part of his message or because for you too it was hard to reason about depth of recursion.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2024-03-17 11:25 +0000 |
| Message-ID | <87frwpje2b.fsf@bsb.me.uk> |
| In reply to | #383652 |
Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: > On 16/03/2024 13:55, Ben Bacarisse wrote: >> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: >> >>> Recursion make programs harder to reason about and prove correct. >> Are you prepared to offer any evidence to support this astonishing >> statement or can we just assume it's another Malcolmism? > > Example given. A recursive algorithm which is hard to reason about and > prove correct, because we don't really know whether under perfectly > reasonable assumptions it will or will not blow the stack. Had you offered a proof that your code neither "blows the stack" nor runs out of any other resource we'd have a starting point for comparison, but you have not done that. Mind you, had you done that, we would have something that might eventually become only one piece of evidence for what is an astonishingly general remark. Broadly applicable remarks require either broadly applicable evidence or a wealth of distinct cases. Your "rule" suggests that all reasoning is impeded by the presence of recursion and I don't think you can support that claim. This is characteristic of many of your remarks -- they are general "rules" that often remain rules even when there is evidence to the contrary. I'll make another point in the hope of clarifying the matter. An algorithm or code is usually proved correct (or not!) under the assumption that it has adequate resources -- usually time and storage. Further reasoning may then be done to determine the resource requirements since this is so often dependent on context. This separation is helpful as you don't usually want to tie "correctness" to some specific installation. The code might run on a system with a dynamically allocated stack, for example, that has very similar limitations to "heap" memory. To put is more generally, we often want to prove properties of code that are independent of physical constraints. Your remark includes this kind reasoning. Did you intend it to? -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2024-03-17 12:37 +0000 |
| Message-ID | <ut6o5l$3h3cb$3@dont-email.me> |
| In reply to | #383679 |
On 17/03/2024 11:25, Ben Bacarisse wrote: > Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: > >> On 16/03/2024 13:55, Ben Bacarisse wrote: >>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: >>> >>>> Recursion make programs harder to reason about and prove correct. >>> Are you prepared to offer any evidence to support this astonishing >>> statement or can we just assume it's another Malcolmism? >> >> Example given. A recursive algorithm which is hard to reason about and >> prove correct, because we don't really know whether under perfectly >> reasonable assumptions it will or will not blow the stack. > > Had you offered a proof that your code neither "blows the stack" nor > runs out of any other resource we'd have a starting point for > comparison, but you have not done that. > > Mind you, had you done that, we would have something that might > eventually become only one piece of evidence for what is an > astonishingly general remark. Broadly applicable remarks require either > broadly applicable evidence or a wealth of distinct cases. > > Your "rule" suggests that all reasoning is impeded by the presence of > recursion and I don't think you can support that claim. This is > characteristic of many of your remarks -- they are general "rules" that > often remain rules even when there is evidence to the contrary. > > I'll make another point in the hope of clarifying the matter. An > algorithm or code is usually proved correct (or not!) under the > assumption that it has adequate resources -- usually time and storage. > Further reasoning may then be done to determine the resource > requirements since this is so often dependent on context. This > separation is helpful as you don't usually want to tie "correctness" to > some specific installation. The code might run on a system with a > dynamically allocated stack, for example, that has very similar > limitations to "heap" memory. > > To put is more generally, we often want to prove properties of code that > are independent of physical constraints. Your remark includes this kind > reasoning. Did you intend it to? > The convetional wisdom is the opposite, But here, conventional wisdom fails. Because heaps are unlimited whilst stacks are not. -- Check out Basic Algorithms and my other books: https://www.lulu.com/spotlight/bgy1mm
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <433-929-6894@kylheku.com> |
|---|---|
| Date | 2024-03-17 17:11 +0000 |
| Message-ID | <20240317095014.365@kylheku.com> |
| In reply to | #383684 |
On 2024-03-17, Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote: > The convetional wisdom is the opposite, But here, conventional wisdom > fails. Because heaps are unlimited whilst stacks are not. The strawman, absolutist conventional wisdom that "recursion is always easier to analyze than iteration" is wrong in the first place. Any program graph based on nothing but IF and GOTO primitives can be mechanically transliterated into a (tail) recursive structure that has the same shape, and is no easier to understand. Your point is not very well made, though. Even though recursion may run into a resource limit, its structure can still help analyze the logic of the algorithm apart from that resource issue. The resource issue can be separately analyzed and provisions made for the algorithm to handle the required inputs, and reject others. Most algorithms (especially ones working with all inputs in memory) are constrained by resources. The iterative version of that image processing algorithm might handle larger images than the recursive one, but there are yet image sizes it won't handle. The idea of calling algorithm implementations "incorrect" if they have any limitations on their input sizes and such isn't particularly informative or useful. Obviously it is incorrect if something has limitations, and is used in such a way that they are exceeded. E.g. the C <int> + <int> operation when a result is implied that is beyond INT_MIN or INT_MAX. Oops, + is not "correct"; don't use it! Now, there is a bit of value in algorithms that will successfully operate on any object that was successfully fit into memory. Do these really exist though? Pretty much any algorithm implementation requires some space to do its work, even if that space is small and fixed. It's possible that the input fit into memory, yet that small and fixed amount of space is not available. -- TXR Programming Language: http://nongnu.org/txr Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal Mastodon: @Kazinator@mstdn.ca
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2024-03-23 00:21 +0000 |
| Message-ID | <8734shiys3.fsf@bsb.me.uk> |
| In reply to | #383684 |
Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: > On 17/03/2024 11:25, Ben Bacarisse wrote: >> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: >> >>> On 16/03/2024 13:55, Ben Bacarisse wrote: >>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: >>>> >>>>> Recursion make programs harder to reason about and prove correct. >>>> Are you prepared to offer any evidence to support this astonishing >>>> statement or can we just assume it's another Malcolmism? >>> >>> Example given. A recursive algorithm which is hard to reason about and >>> prove correct, because we don't really know whether under perfectly >>> reasonable assumptions it will or will not blow the stack. >> Had you offered a proof that your code neither "blows the stack" nor >> runs out of any other resource we'd have a starting point for >> comparison, but you have not done that. >> Mind you, had you done that, we would have something that might >> eventually become only one piece of evidence for what is an >> astonishingly general remark. Broadly applicable remarks require either >> broadly applicable evidence or a wealth of distinct cases. >> Your "rule" suggests that all reasoning is impeded by the presence of >> recursion and I don't think you can support that claim. This is >> characteristic of many of your remarks -- they are general "rules" that >> often remain rules even when there is evidence to the contrary. >> I'll make another point in the hope of clarifying the matter. An >> algorithm or code is usually proved correct (or not!) under the >> assumption that it has adequate resources -- usually time and storage. >> Further reasoning may then be done to determine the resource >> requirements since this is so often dependent on context. This >> separation is helpful as you don't usually want to tie "correctness" to >> some specific installation. The code might run on a system with a >> dynamically allocated stack, for example, that has very similar >> limitations to "heap" memory. >> To put is more generally, we often want to prove properties of code that >> are independent of physical constraints. Your remark includes this kind >> reasoning. Did you intend it to? >> > The convetional wisdom is the opposite, But here, conventional wisdom > fails. Because heaps are unlimited whilst stacks are not. I put off answering for enough time that I now don't care anymore. I think that's a win for everyone. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | scott@slp53.sl.home (Scott Lurndal) |
|---|---|
| Date | 2024-03-23 14:43 +0000 |
| Message-ID | <FUBLN.90799$Wbff.11445@fx37.iad> |
| In reply to | #383684 |
>Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: > >> The convetional wisdom is the opposite, But here, conventional wisdom >> fails. Because heaps are unlimited whilst stacks are not. That's not actually true. The size of both are bounded, yes. It's certainly possible (in POSIX, anyway) for the stack bounds to be unlimited (given sufficient real memory and/or backing store) and the heap size to be bounded. See 'setrlimit'.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-23 11:48 -0700 |
| Message-ID | <86sf0gkcnj.fsf@linuxsc.com> |
| In reply to | #383921 |
scott@slp53.sl.home (Scott Lurndal) writes: >> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: >> >>> The convetional wisdom is the opposite, But here, conventional wisdom >>> fails. Because heaps are unlimited while stacks are not. > > That's not actually true. The size of both are bounded, yes. > > It's certainly possible (in POSIX, anyway) for the stack bounds > to be unlimited (given sufficient real memory and/or backing > store) and the heap size to be bounded. See 'setrlimit'. The sizes of both heaps and stacks are bounded, because pointers have a fixed number of bits. Certainly these sizes can be very very large, but they are not unbounded.
[toc] | [prev] | [next] | [standalone]
| From | scott@slp53.sl.home (Scott Lurndal) |
|---|---|
| Date | 2024-03-24 20:48 +0000 |
| Message-ID | <Uk0MN.450379$yEgf.443209@fx09.iad> |
| In reply to | #383935 |
Tim Rentsch <tr.17687@z991.linuxsc.com> writes: >scott@slp53.sl.home (Scott Lurndal) writes: > >>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: >>> >>>> The convetional wisdom is the opposite, But here, conventional wisdom >>>> fails. Because heaps are unlimited while stacks are not. >> >> That's not actually true. The size of both are bounded, yes. >> >> It's certainly possible (in POSIX, anyway) for the stack bounds >> to be unlimited (given sufficient real memory and/or backing >> store) and the heap size to be bounded. See 'setrlimit'. > >The sizes of both heaps and stacks are bounded, because >pointers have a fixed number of bits. Certainly these >sizes can be very very large, but they are not unbounded. I was referring to the term of art used in POSIX, where unlimited simply means that the operating system doesn't limit them (and as I pointed out, physical limits, including address space size (which is often only 48 bits, regardless of the 64-bit pointer space)) will dominate. $ ulimit -a address space limit (Kibytes) (-M) unlimited core file size (blocks) (-c) 0 cpu time (seconds) (-t) unlimited data size (Kibytes) (-d) unlimited file size (blocks) (-f) unlimited locks (-x) unlimited
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-28 22:51 -0700 |
| Message-ID | <86bk6xk2li.fsf@linuxsc.com> |
| In reply to | #383972 |
scott@slp53.sl.home (Scott Lurndal) writes: > Tim Rentsch <tr.17687@z991.linuxsc.com> writes: > >> scott@slp53.sl.home (Scott Lurndal) writes: >> >>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: >>>> >>>>> The convetional wisdom is the opposite, But here, conventional wisdom >>>>> fails. Because heaps are unlimited while stacks are not. >>> >>> That's not actually true. The size of both are bounded, yes. >>> >>> It's certainly possible (in POSIX, anyway) for the stack bounds >>> to be unlimited (given sufficient real memory and/or backing >>> store) and the heap size to be bounded. See 'setrlimit'. >> >> The sizes of both heaps and stacks are bounded, because >> pointers have a fixed number of bits. Certainly these >> sizes can be very very large, but they are not unbounded. > > I was referring to the term of art used in POSIX, where > unlimited simply means that the operating system doesn't > limit them [.. elaboration ..] The earlier sentence was confusing, as the sentence construction suggested "unlimited" was a general term rather than one with a specific meaning in POSIX. In any case thank you for the education.
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2024-03-16 15:40 +0100 |
| Message-ID | <ut4b09$2uhpm$1@dont-email.me> |
| In reply to | #383648 |
On 16/03/2024 12:33, Malcolm McLean wrote:
> On 16/03/2024 04:11, fir wrote:
>> i was writing simple editor (something like paint but more custom for
>> my eventual needs) for big pixel (low resolution) drawing
>>
>> it showed in a minute i need a click for changing given drawed area of
>> of one color into another color (becouse if no someone would need to
>> do it by hand pixel by pixel and the need to change color of given
>> element is very common)
>>
>> there is very simple method of doing it - i men i click in given color
>> pixel then replace it by my color and call the same function on
>> adjacent 4 pixels (only need check if it is in screen at all and if
>> the color to change is that initial color
>>
>> int RecolorizePixelAndAdjacentOnes(int x, int y, unsigned old_color,
>> unsigned new_color)
>> {
>> if(old_color == new_color) return 0;
>>
>> if(XYIsInScreen( x, y))
>> if(GetPixelUnsafe(x,y)==old_color)
>> {
>> SetPixelSafe(x,y,new_color);
>> RecolorizePixelAndAdjacentOnes(x+1, y, old_color, new_color);
>> RecolorizePixelAndAdjacentOnes(x-1, y, old_color, new_color);
>> RecolorizePixelAndAdjacentOnes(x, y-1, old_color, new_color);
>> RecolorizePixelAndAdjacentOnes(x, y+1, old_color, new_color);
>> return 1;
>> }
>>
>> return 0;
>> }
>>
>> it work but im not quite sure how to estimate the safety of this -
>> incidentally as i said i use this editor to low res graphics like
>> 200x200 pixels or less, and it is only a toll of private use,
>> yet i got no time to work on it more than 1-2-3 days i guess but still
>>
>> is there maybe simple way to improve it?
> >
> This is a cheap and cheerful fllod fill. And it's easy to get right and
> shouldn't afall over. But but makes an awful not of unnecessary calls,
> and on a small system and large image might even blow the stack.
It is not going to lead to stack overflow on any reasonable system. If
the image size is 200 x 200, as the OP said, it will never reach a depth
of more than 400 calls (the maximum path length before back-tracking is
inevitable). Even for big images, I can't see it being a problem. I
remember using the same method on a 16K ZX Spectrum as a teenager.
>
> Recursion make programs harder to reason about and prove correct.
As a general statement, that is simply wrong. It is no coincidence that
most provably correct software development is done using functional
programming languages, which are based entirely on recursion. Recursion
maps well to inductive proofs, and avoids variables, and is thus often
much easier to work with for proving code correct.
>
> So a real flood fill doesn't work like that. You use a queue and put the
> pixels to be filled into that, and trace lines.
>
That might be a bit more efficient, but not significantly so (at least,
not in your implementation below). You are using a queue instead of the
stack, but it will grow in exactly the same manner.
> And here's some code I wrote a while ago. Use that as a pattern. But not
> sure how well it works. Haven't used it for a long time.
>
> https://github.com/MalcolmMcLean/binaryimagelibrary/blob/master/drawbinary.c
>
Your implementation is a mess, /vastly/ more difficult to prove correct
than the OP's original one, and unlikely to be very much faster (it will
certainly scale in the same way in both time and memory usage).
There are a variety of different flood-fill algorithms, with different
advantages and disadvantages. Speeds will often depend as much on the
way the get/set pixel code works, especially if the flood-fill is on
live displayed data rather than in a buffer off-screen. But typically
you need to get a /lot/ more advanced (i.e., not your algorithm) to
improve on the OP's version by an order of magnitude, so if speed is not
essential but understanding that it is correct is important, then it
makes more sense to stick to the original recursive version.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2024-03-16 15:09 +0000 |
| Message-ID | <ut4cnc$2ut2t$1@dont-email.me> |
| In reply to | #383650 |
On 16/03/2024 14:40, David Brown wrote: > On 16/03/2024 12:33, Malcolm McLean wrote: > >> And here's some code I wrote a while ago. Use that as a pattern. But >> not sure how well it works. Haven't used it for a long time. >> >> https://github.com/MalcolmMcLean/binaryimagelibrary/blob/master/drawbinary.c >> > > Your implementation is a mess, /vastly/ more difficult to prove correct > than the OP's original one, and unlikely to be very much faster (it will > certainly scale in the same way in both time and memory usage). > Now is this David Brown being David Borwn, ot its it actaully ture? It's not designed to be eay to prove correct, that's true. And the maintain it's mess is that we are managing the queue manually for speed. But the naive recursive algorithm is O(N) (N = pixels to flood), and inherently we can't beat that without special hardware. The recursive one tends to be slow because calls are expensive. And mine makes calls to malloc() and realloc to manage the queue. And of course whilst we might blow the stack, we are much less likely to run out of heap. And it's been tweaked abit in hacky way to make it faster on real images. And whilst it's still going to work, is it out of date? And I need to run some tests, don't I? > > There are a variety of different flood-fill algorithms, with different > advantages and disadvantages. Speeds will often depend as much on the > way the get/set pixel code works, especially if the flood-fill is on > live displayed data rather than in a buffer off-screen. But typically > you need to get a /lot/ more advanced (i.e., not your algorithm) to > improve on the OP's version by an order of magnitude, so if speed is not > essential but understanding that it is correct is important, then it > makes more sense to stick to the original recursive version. > What are these / lot / more advanced algorithms? Maybe they exist. But don't people deserve some sort of link? -- Check out Basic Algorithms and my other books: https://www.lulu.com/spotlight/bgy1mm
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2024-03-17 14:56 +0000 |
| Message-ID | <ut70b4$3itvb$1@dont-email.me> |
| In reply to | #383653 |
On 16/03/2024 15:09, Malcolm McLean wrote:
> On 16/03/2024 14:40, David Brown wrote:
>> On 16/03/2024 12:33, Malcolm McLean wrote:
>>
>>> And here's some code I wrote a while ago. Use that as a pattern. But
>>> not sure how well it works. Haven't used it for a long time.
>>>
>>> https://github.com/MalcolmMcLean/binaryimagelibrary/blob/master/drawbinary.c
>>>
>>
>> Your implementation is a mess, /vastly/ more difficult to prove
>> correct than the OP's original one, and unlikely to be very much
>> faster (it will certainly scale in the same way in both time and
>> memory usage).
>>
> Now is this David Brown being David Borwn, ot its it actaully ture?
> And I need to run some tests, don't I?
>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
int floodfill_r(unsigned char *grey, int width, int height, int x, int y,
unsigned char target, unsigned char dest)
{
if (x < 0 || x >= width || y < 0 || y >= height)
return 0;
if (grey[y*width+x] != target)
return 0;
grey[y*width+x] = dest;
floodfill_r(grey, width, height, x - 1, y, target, dest);
floodfill_r(grey, width, height, x + 1, y, target, dest);
floodfill_r(grey, width, height, x, y - 1, target, dest);
floodfill_r(grey, width, height, x, y + 1, target, dest);
return 0;
}
/**
Floodfill4 - floodfill, 4 connectivity.
@param[in,out] grey - the image (formally it's greyscale but it could be
binary or indexed)
@param width - image width
@param height - image height
@param x - seed point x
@param y - seed point y
@param target - the colour to flood
@param dest - the colur to replace it by.
@returns Number of pixels flooded.
*/
int floodfill4(unsigned char *grey, int width, int height, int x, int y,
unsigned char target, unsigned char dest)
{
int *qx = 0;
int *qy = 0;
int qN = 0;
int qpos = 0;
int qcapacity = 0;
int wx, wy;
int ex, ey;
int tx, ty;
int ix;
int *temp;
int answer = 0;
if(grey[y * width + x] != target)
return 0;
qx = malloc(width * sizeof(int));
qy = malloc(width * sizeof(int));
if(qx == 0 || qy == 0)
goto error_exit;
qcapacity = width;
qx[qpos] = x;
qy[qpos] = y;
qN = 1;
while(qN != 0)
{
tx = qx[qpos];
ty = qy[qpos];
qpos++;
qN--;
if(qpos == 256)
{
memmove(qx, qx + 256, qN*sizeof(int));
memmove(qy, qy + 256, qN*sizeof(int));
qpos = 0;
}
if(grey[ty*width+tx] != target)
continue;
wx = tx;
wy = ty;
while(wx >= 0 && grey[wy*width+wx] == target)
wx--;
wx++;
ex = tx;
ey = ty;
while(ex < width && grey[ey*width+ex] == target)
ex++;
ex--;
for(ix=wx;ix<=ex;ix++)
{
grey[ty*width+ix] = dest;
answer++;
}
if(ty > 0)
for(ix=wx;ix<=ex;ix++)
{
if(grey[(ty-1)*width+ix] == target)
{
if(qpos + qN == qcapacity)
{
temp = realloc(qx, (qcapacity + width) * sizeof(int));
if(temp == 0)
goto error_exit;
qx = temp;
temp = realloc(qy, (qcapacity + width) * sizeof(int));
if(temp == 0)
goto error_exit;
qy = temp;
qcapacity += width;
}
qx[qpos+qN] = ix;
qy[qpos+qN] = ty-1;
qN++;
}
}
if(ty < height -1)
for(ix=wx;ix<=ex;ix++)
{
if(grey[(ty+1)*width+ix] == target)
{
if(qpos + qN == qcapacity)
{
temp = realloc(qx, (qcapacity + width) * sizeof(int));
if(temp == 0)
goto error_exit;
qx = temp;
temp = realloc(qy, (qcapacity + width) * sizeof(int));
if(temp == 0)
goto error_exit;
qy = temp;
qcapacity += width;
}
qx[qpos+qN] = ix;
qy[qpos+qN] = ty+1;
qN++;
}
}
}
free(qx);
free(qy);
return answer;
error_exit:
free(qx);
free(qy);
return -1;
}
int main(void)
{
unsigned char *image;
clock_t tick, tock;
int i;
image = malloc(100 * 100);
tick = clock();
for (i = 0 ; i < 10000; i++)
{
memset(image, 0, 100 * 100);
floodfill_r(image, 100, 100, 50, 50, 0, 1);
}
tock = clock();
printf("floodfill_r %g\n", ((double)(tock - tick))/CLOCKS_PER_SEC);
tick = clock();
for (i = 0 ; i < 10000; i++)
{
memset(image, 0, 100 * 100);
floodfill4(image, 100, 100, 50, 50, 0, 1);
}
tock = clock();
printf("floodfill4 %g\n", ((double)(tock - tick))/CLOCKS_PER_SEC);
return 0;
}
Let's give it a whirl
malcolm@Malcolms-iMac cscratch % gcc -O3 testfloodfill.c
malcolm@Malcolms-iMac cscratch % ./a.out
floodfill_r 1.69274
floodfill4 0.336705
--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-17 17:42 +0200 |
| Message-ID | <20240317174218.0000471e@yahoo.com> |
| In reply to | #383695 |
On Sun, 17 Mar 2024 14:56:34 +0000 Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote: > On 16/03/2024 15:09, Malcolm McLean wrote: > > On 16/03/2024 14:40, David Brown wrote: > >> On 16/03/2024 12:33, Malcolm McLean wrote: > >> > >>> And here's some code I wrote a while ago. Use that as a pattern. > >>> But not sure how well it works. Haven't used it for a long time. > >>> > >>> https://github.com/MalcolmMcLean/binaryimagelibrary/blob/master/drawbinary.c > >>> > >> > >> Your implementation is a mess, /vastly/ more difficult to prove > >> correct than the OP's original one, and unlikely to be very much > >> faster (it will certainly scale in the same way in both time and > >> memory usage). > >> > > Now is this David Brown being David Borwn, ot its it actaully ture? > > > > > And I need to run some tests, don't I? > > > > Let's give it a whirl > <snip> > malcolm@Malcolms-iMac cscratch % gcc -O3 testfloodfill.c > malcolm@Malcolms-iMac cscratch % ./a.out > floodfill_r 1.69274 > floodfill4 0.336705 > > Now try the case in which original recursion is particularly deep. Something like that: *.***.** *.*.*.*. *.*.*.*. *.*.*.*. *.*.*.*. *.*.*.*. *.*.*.*. ***.***.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-17 18:25 +0200 |
| Message-ID | <20240317182520.00002390@yahoo.com> |
| In reply to | #383695 |
On Sun, 17 Mar 2024 14:56:34 +0000
Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
> On 16/03/2024 15:09, Malcolm McLean wrote:
> > On 16/03/2024 14:40, David Brown wrote:
> >> On 16/03/2024 12:33, Malcolm McLean wrote:
> >>
> >>> And here's some code I wrote a while ago. Use that as a pattern.
> >>> But not sure how well it works. Haven't used it for a long time.
> >>>
> >>> https://github.com/MalcolmMcLean/binaryimagelibrary/blob/master/drawbinary.c
> >>>
> >>
> >> Your implementation is a mess, /vastly/ more difficult to prove
> >> correct than the OP's original one, and unlikely to be very much
> >> faster (it will certainly scale in the same way in both time and
> >> memory usage).
> >>
> > Now is this David Brown being David Borwn, ot its it actaully ture?
> >
>
> > And I need to run some tests, don't I?
> >
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> #include <time.h>
>
> int floodfill_r(unsigned char *grey, int width, int height, int x,
> int y, unsigned char target, unsigned char dest)
> {
> if (x < 0 || x >= width || y < 0 || y >= height)
> return 0;
> if (grey[y*width+x] != target)
> return 0;
> grey[y*width+x] = dest;
> floodfill_r(grey, width, height, x - 1, y, target, dest);
> floodfill_r(grey, width, height, x + 1, y, target, dest);
> floodfill_r(grey, width, height, x, y - 1, target, dest);
> floodfill_r(grey, width, height, x, y + 1, target, dest);
>
> return 0;
> }
>
> /**
> Floodfill4 - floodfill, 4 connectivity.
>
> @param[in,out] grey - the image (formally it's greyscale but it
> could be binary or indexed)
> @param width - image width
> @param height - image height
> @param x - seed point x
> @param y - seed point y
> @param target - the colour to flood
> @param dest - the colur to replace it by.
> @returns Number of pixels flooded.
> */
> int floodfill4(unsigned char *grey, int width, int height, int x, int
> y, unsigned char target, unsigned char dest)
> {
> int *qx = 0;
> int *qy = 0;
> int qN = 0;
> int qpos = 0;
> int qcapacity = 0;
> int wx, wy;
> int ex, ey;
> int tx, ty;
> int ix;
> int *temp;
> int answer = 0;
>
> if(grey[y * width + x] != target)
> return 0;
> qx = malloc(width * sizeof(int));
> qy = malloc(width * sizeof(int));
> if(qx == 0 || qy == 0)
> goto error_exit;
> qcapacity = width;
> qx[qpos] = x;
> qy[qpos] = y;
> qN = 1;
>
> while(qN != 0)
> {
> tx = qx[qpos];
> ty = qy[qpos];
> qpos++;
> qN--;
>
> if(qpos == 256)
> {
> memmove(qx, qx + 256, qN*sizeof(int));
> memmove(qy, qy + 256, qN*sizeof(int));
> qpos = 0;
> }
> if(grey[ty*width+tx] != target)
> continue;
> wx = tx;
> wy = ty;
> while(wx >= 0 && grey[wy*width+wx] == target)
> wx--;
> wx++;
> ex = tx;
> ey = ty;
> while(ex < width && grey[ey*width+ex] == target)
> ex++;
> ex--;
>
>
> for(ix=wx;ix<=ex;ix++)
> {
> grey[ty*width+ix] = dest;
> answer++;
> }
>
> if(ty > 0)
> for(ix=wx;ix<=ex;ix++)
> {
> if(grey[(ty-1)*width+ix] == target)
> {
> if(qpos + qN == qcapacity)
> {
> temp = realloc(qx, (qcapacity + width) * sizeof(int));
> if(temp == 0)
> goto error_exit;
> qx = temp;
> temp = realloc(qy, (qcapacity + width) * sizeof(int));
> if(temp == 0)
> goto error_exit;
> qy = temp;
> qcapacity += width;
> }
> qx[qpos+qN] = ix;
> qy[qpos+qN] = ty-1;
> qN++;
> }
> }
> if(ty < height -1)
> for(ix=wx;ix<=ex;ix++)
> {
> if(grey[(ty+1)*width+ix] == target)
> {
> if(qpos + qN == qcapacity)
> {
> temp = realloc(qx, (qcapacity + width) * sizeof(int));
> if(temp == 0)
> goto error_exit;
> qx = temp;
> temp = realloc(qy, (qcapacity + width) * sizeof(int));
> if(temp == 0)
> goto error_exit;
> qy = temp;
> qcapacity += width;
> }
> qx[qpos+qN] = ix;
> qy[qpos+qN] = ty+1;
> qN++;
> }
> }
> }
>
> free(qx);
> free(qy);
>
> return answer;
> error_exit:
> free(qx);
> free(qy);
> return -1;
> }
>
> int main(void)
> {
> unsigned char *image;
> clock_t tick, tock;
> int i;
>
> image = malloc(100 * 100);
> tick = clock();
> for (i = 0 ; i < 10000; i++)
> {
> memset(image, 0, 100 * 100);
> floodfill_r(image, 100, 100, 50, 50, 0, 1);
> }
> tock = clock();
> printf("floodfill_r %g\n", ((double)(tock -
> tick))/CLOCKS_PER_SEC);
>
> tick = clock();
> for (i = 0 ; i < 10000; i++)
> {
> memset(image, 0, 100 * 100);
> floodfill4(image, 100, 100, 50, 50, 0, 1);
> }
> tock = clock();
> printf("floodfill4 %g\n", ((double)(tock - tick))/CLOCKS_PER_SEC);
>
> return 0;
> }
>
>
> Let's give it a whirl
>
> malcolm@Malcolms-iMac cscratch % gcc -O3 testfloodfill.c
> malcolm@Malcolms-iMac cscratch % ./a.out
> floodfill_r 1.69274
> floodfill4 0.336705
>
>
I find your performance measurement non-decisive for two reasons:
(1) because your test case is too trivial and probably uncharacteristic
and
(2) because recursive variant could be trivially rewritten in a way
that reduces # of stack memory accesses by factor of 2 or 3.
Like that:
struct recursive_context_t {
unsigned char *grey;
int width, height;
unsigned char target, dest;
};
static void floodfill_r_core(const struct recursive_context_t* context,
int x, int y) {
if (x < 0 || x >= context->width || y < 0 || y >= context->height)
return;
if (context->grey[y*context->width+x] == context->target) {
context->grey[y*context->width+x] = context->dest;
floodfill_r_core(context, x - 1, y);
floodfill_r_core(context, x + 1, y);
floodfill_r_core(context, x, y - 1);
floodfill_r_core(context, x, y + 1);
}
}
int floodfill_r(
unsigned char *grey,
int width, int height,
int x, int y,
unsigned char target, unsigned char dest)
{
if (x < 0 || x >= width || y < 0 || y >= height)
return 0;
if (grey[y*width+x] != target)
return 0;
struct recursive_context_t context = {
.grey = grey,
.width = width,
.height = height,
.target = target,
.dest = dest,
};
floodfill_r_core(&context, x, y);
return 1;
}
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-17 19:39 +0200 |
| Message-ID | <20240317193908.00002634@yahoo.com> |
| In reply to | #383698 |
On Sun, 17 Mar 2024 18:25:20 +0200
Michael S <already5chosen@yahoo.com> wrote:
> On Sun, 17 Mar 2024 14:56:34 +0000
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
>
> > On 16/03/2024 15:09, Malcolm McLean wrote:
> > > On 16/03/2024 14:40, David Brown wrote:
> > >> On 16/03/2024 12:33, Malcolm McLean wrote:
> > >>
> > >>> And here's some code I wrote a while ago. Use that as a pattern.
> > >>> But not sure how well it works. Haven't used it for a long time.
> > >>>
> > >>> https://github.com/MalcolmMcLean/binaryimagelibrary/blob/master/drawbinary.c
> > >>>
> > >>
> > >> Your implementation is a mess, /vastly/ more difficult to prove
> > >> correct than the OP's original one, and unlikely to be very much
> > >> faster (it will certainly scale in the same way in both time and
> > >> memory usage).
> > >>
> > > Now is this David Brown being David Borwn, ot its it actaully
> > > ture?
> >
> > > And I need to run some tests, don't I?
> > >
> > #include <stdio.h>
> > #include <stdlib.h>
> > #include <string.h>
> > #include <time.h>
> >
> > int floodfill_r(unsigned char *grey, int width, int height, int x,
> > int y, unsigned char target, unsigned char dest)
> > {
> > if (x < 0 || x >= width || y < 0 || y >= height)
> > return 0;
> > if (grey[y*width+x] != target)
> > return 0;
> > grey[y*width+x] = dest;
> > floodfill_r(grey, width, height, x - 1, y, target, dest);
> > floodfill_r(grey, width, height, x + 1, y, target, dest);
> > floodfill_r(grey, width, height, x, y - 1, target, dest);
> > floodfill_r(grey, width, height, x, y + 1, target, dest);
> >
> > return 0;
> > }
> >
> > /**
> > Floodfill4 - floodfill, 4 connectivity.
> >
> > @param[in,out] grey - the image (formally it's greyscale but it
> > could be binary or indexed)
> > @param width - image width
> > @param height - image height
> > @param x - seed point x
> > @param y - seed point y
> > @param target - the colour to flood
> > @param dest - the colur to replace it by.
> > @returns Number of pixels flooded.
> > */
> > int floodfill4(unsigned char *grey, int width, int height, int x,
> > int y, unsigned char target, unsigned char dest)
> > {
> > int *qx = 0;
> > int *qy = 0;
> > int qN = 0;
> > int qpos = 0;
> > int qcapacity = 0;
> > int wx, wy;
> > int ex, ey;
> > int tx, ty;
> > int ix;
> > int *temp;
> > int answer = 0;
> >
> > if(grey[y * width + x] != target)
> > return 0;
> > qx = malloc(width * sizeof(int));
> > qy = malloc(width * sizeof(int));
> > if(qx == 0 || qy == 0)
> > goto error_exit;
> > qcapacity = width;
> > qx[qpos] = x;
> > qy[qpos] = y;
> > qN = 1;
> >
> > while(qN != 0)
> > {
> > tx = qx[qpos];
> > ty = qy[qpos];
> > qpos++;
> > qN--;
> >
> > if(qpos == 256)
> > {
> > memmove(qx, qx + 256, qN*sizeof(int));
> > memmove(qy, qy + 256, qN*sizeof(int));
> > qpos = 0;
> > }
> > if(grey[ty*width+tx] != target)
> > continue;
> > wx = tx;
> > wy = ty;
> > while(wx >= 0 && grey[wy*width+wx] == target)
> > wx--;
> > wx++;
> > ex = tx;
> > ey = ty;
> > while(ex < width && grey[ey*width+ex] == target)
> > ex++;
> > ex--;
> >
> >
> > for(ix=wx;ix<=ex;ix++)
> > {
> > grey[ty*width+ix] = dest;
> > answer++;
> > }
> >
> > if(ty > 0)
> > for(ix=wx;ix<=ex;ix++)
> > {
> > if(grey[(ty-1)*width+ix] == target)
> > {
> > if(qpos + qN == qcapacity)
> > {
> > temp = realloc(qx, (qcapacity + width) * sizeof(int));
> > if(temp == 0)
> > goto error_exit;
> > qx = temp;
> > temp = realloc(qy, (qcapacity + width) * sizeof(int));
> > if(temp == 0)
> > goto error_exit;
> > qy = temp;
> > qcapacity += width;
> > }
> > qx[qpos+qN] = ix;
> > qy[qpos+qN] = ty-1;
> > qN++;
> > }
> > }
> > if(ty < height -1)
> > for(ix=wx;ix<=ex;ix++)
> > {
> > if(grey[(ty+1)*width+ix] == target)
> > {
> > if(qpos + qN == qcapacity)
> > {
> > temp = realloc(qx, (qcapacity + width) * sizeof(int));
> > if(temp == 0)
> > goto error_exit;
> > qx = temp;
> > temp = realloc(qy, (qcapacity + width) * sizeof(int));
> > if(temp == 0)
> > goto error_exit;
> > qy = temp;
> > qcapacity += width;
> > }
> > qx[qpos+qN] = ix;
> > qy[qpos+qN] = ty+1;
> > qN++;
> > }
> > }
> > }
> >
> > free(qx);
> > free(qy);
> >
> > return answer;
> > error_exit:
> > free(qx);
> > free(qy);
> > return -1;
> > }
> >
> > int main(void)
> > {
> > unsigned char *image;
> > clock_t tick, tock;
> > int i;
> >
> > image = malloc(100 * 100);
> > tick = clock();
> > for (i = 0 ; i < 10000; i++)
> > {
> > memset(image, 0, 100 * 100);
> > floodfill_r(image, 100, 100, 50, 50, 0, 1);
> > }
> > tock = clock();
> > printf("floodfill_r %g\n", ((double)(tock -
> > tick))/CLOCKS_PER_SEC);
> >
> > tick = clock();
> > for (i = 0 ; i < 10000; i++)
> > {
> > memset(image, 0, 100 * 100);
> > floodfill4(image, 100, 100, 50, 50, 0, 1);
> > }
> > tock = clock();
> > printf("floodfill4 %g\n", ((double)(tock -
> > tick))/CLOCKS_PER_SEC);
> >
> > return 0;
> > }
> >
> >
> > Let's give it a whirl
> >
> > malcolm@Malcolms-iMac cscratch % gcc -O3 testfloodfill.c
> > malcolm@Malcolms-iMac cscratch % ./a.out
> > floodfill_r 1.69274
> > floodfill4 0.336705
> >
> >
>
> I find your performance measurement non-decisive for two reasons:
> (1) because your test case is too trivial and probably
> uncharacteristic and
> (2) because recursive variant could be trivially rewritten in a way
> that reduces # of stack memory accesses by factor of 2 or 3.
> Like that:
>
> struct recursive_context_t {
> unsigned char *grey;
> int width, height;
> unsigned char target, dest;
> };
>
> static void floodfill_r_core(const struct recursive_context_t*
> context, int x, int y) {
> if (x < 0 || x >= context->width || y < 0 || y >= context->height)
> return;
> if (context->grey[y*context->width+x] == context->target) {
> context->grey[y*context->width+x] = context->dest;
> floodfill_r_core(context, x - 1, y);
> floodfill_r_core(context, x + 1, y);
> floodfill_r_core(context, x, y - 1);
> floodfill_r_core(context, x, y + 1);
> }
> }
>
> int floodfill_r(
> unsigned char *grey,
> int width, int height,
> int x, int y,
> unsigned char target, unsigned char dest)
> {
> if (x < 0 || x >= width || y < 0 || y >= height)
> return 0;
> if (grey[y*width+x] != target)
> return 0;
> struct recursive_context_t context = {
> .grey = grey,
> .width = width,
> .height = height,
> .target = target,
> .dest = dest,
> };
> floodfill_r_core(&context, x, y);
> return 1;
> }
>
>
I did my own measurements with snake-like image from my first
response to Malcolm. For this shape, recursive version (after my
improvement) is almost exactly 10 times slower than Malcolm's iterative
code. And suspect to stack overflow although a little less so than
original.
Even if in Big Oh sense they are the same, it does look like Malcolm's
variant is decisively faster in practice.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-18 11:36 -0700 |
| Message-ID | <86le6fo09e.fsf@linuxsc.com> |
| In reply to | #383704 |
Michael S <already5chosen@yahoo.com> writes: > On Sun, 17 Mar 2024 18:25:20 +0200 > Michael S <already5chosen@yahoo.com> wrote: > >> On Sun, 17 Mar 2024 14:56:34 +0000 >> Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote: >>> [a floodfill routine posted by Malcolm] >> [...] >> >> [a recursive area fill written by Michael S] > > I did my own measurements with snake-like image from my first > response to Malcolm. For this shape, recursive version (after my > improvement) is almost exactly 10 times slower than Malcolm's > iterative code. And suspect to stack overflow although a little > less so than original. It's hard to write a recursive area fill routine if one wants to guarantee worst case behavior in all cases. This problem is not a good fit to using recursion without there being some kind of constraints on what the inputs will be. > Even if in Big Oh sense they are the same, it does look like > Malcolm's variant is decisively faster in practice. I've done some tests with Malcolm's code. Some observations: It uses more memory than it needs to. It's anisotropic, which is to say it behaves differently with respect to changes in width than it does to changes in height. It doesn't scale well. In particular worst case performance scaling is worse than O(N) (as determined experimentally, not theoretically). The code is much longer than is needed just to do an area fill. A small fraction of that is simply layout style, but mostly it's that the code is more complicated than it needs to be.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2024-03-18 18:51 +0000 |
| Message-ID | <uta2g5$amps$1@dont-email.me> |
| In reply to | #383723 |
On 18/03/2024 18:36, Tim Rentsch wrote: > > > It doesn't scale well. In particular worst case performance > scaling is worse than O(N) (as determined experimentally, not > theoretically). > Is that because the queue is being memmoved instead of using a circular buffer when it gets towards the end? -- Check out Basic Algorithms and my other books: https://www.lulu.com/spotlight/bgy1mm
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-18 23:10 -0700 |
| Message-ID | <86wmpyn44y.fsf@linuxsc.com> |
| In reply to | #383725 |
Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: > On 18/03/2024 18:36, Tim Rentsch wrote: >> >> >> It doesn't scale well. In particular worst case performance >> scaling is worse than O(N) (as determined experimentally, not >> theoretically). > > Is that because the queue is being memmoved instead of using a > circular buffer when it gets towards the end? I'm sure I don't know, and I'm astonished that you would ask. It's your code after all. IMO it should simply be thrown out and re-written; it pains me just to look at it, let alone to try to understand or fix it.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2024-03-19 12:06 +0000 |
| Message-ID | <utbv3l$qed7$2@dont-email.me> |
| In reply to | #383734 |
On 19/03/2024 06:10, Tim Rentsch wrote: > Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes: > >> On 18/03/2024 18:36, Tim Rentsch wrote: >>> >>> >>> It doesn't scale well. In particular worst case performance >>> scaling is worse than O(N) (as determined experimentally, not >>> theoretically). >> >> Is that because the queue is being memmoved instead of using a >> circular buffer when it gets towards the end? > > I'm sure I don't know, and I'm astonished that you would ask. > It's your code after all. IMO it should simply be thrown out and > re-written; it pains me just to look at it, let alone to try to > understand or fix it. Yes, but I wrote it years ago. I can't remember why the value of 256 pixels was put in. But I do remember why the queue isn't very efficient - for the small images I expected to be processed, I judged that the added complexity of maintaining a circular queue wouldn't be worth it, given that I wanted the routine to be leaf. However if you can somehow trigger catastrophic big O behaviour, it won't be a surprise. -- Check out Basic Algorithms and my other books: https://www.lulu.com/spotlight/bgy1mm
[toc] | [prev] | [next] | [standalone]
Page 2 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