Re: filling area by color atack safety

From	Michael S <already5chosen@yahoo.com>
Newsgroups	comp.lang.c
Subject	Re: filling area by color atack safety
Date	2024-03-24 20:27 +0300
Organization	A noiseless patient Spider
Message-ID	<20240324202758.00001b75@yahoo.com> (permalink)
References	(2 earlier) <865xxiok09.fsf@linuxsc.com> <20240319131842.00002138@yahoo.com> <utbuk3$qed7$1@dont-email.me> <20240319191859.00004bc8@yahoo.com> <86bk79m10l.fsf@linuxsc.com>

Show all headers | View raw

On Wed, 20 Mar 2024 07:27:38 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Michael S <already5chosen@yahoo.com> writes:
> 
> > On Tue, 19 Mar 2024 11:57:53 +0000
> > Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
> >  
> 
> > The nice thing about Tim's method is that we can expect that
> > performance depends on number of recolored pixels and almost
> > nothing else.  
> 
> One aspect that I consider a significant plus is my code never
> does poorly.  Certainly it isn't the fastest in all cases, but
> it's never abysmally slow.
> 

To be fair, none of presented algorithms is abysmally slow.
When compared by number of visited points, they all appear to be within
factor of 2 or 2.5 of each other.
Some of them for some patterns could be 10-15 times slower than
others, but it does not happen for all patterns and when it happens
it's because of problematic implementation rather because of
differences in algorithms.
Even original naive recursive algorithm is not too slow when
implemented in optimized asm - 2.2x slower than the fastest for solid
square shape and closer than that for other shapes.

The big difference between algorithms is not a speed, but amount of
auxiliary memory used in the worst case. Your algorithm appears to be
the best in that department, Malcolm's algorithm it's also quite good
and all others (plain recursion, stacks, my deferred stack, all my
cross variants, lines-oriented recursion of : Peter 'Shaggy'
Haywood) are a lot worse.

But even by that metric, the difference between different
implementations of the same algorithm is often much bigger than
difference between algorithms.

For example, solid 200x200 image with starting point in the corner
recolored by code presented in first Malcolm's post (not his own
algorithm, but recursive algorithm that he presented as a reference
point) on x86-64/gcc consumes 5,094,784 bytes of stack. After small
modification (all non-changing parameters aggregated in structure
and passed by reference) the footprint falls to 2,547,328 B.
Coding the same algorithm (well, almost the same) in asm reduces it to
32,0000 B. Coding it with explicit stack cuts it to 40,000 B. Now I
didn't actually coded it, but I know how to compress explicit stack
down to 2 bits per level of recursion. If implemented, it would be
10,000B, i.e. comparable with much more economical algorithm of Malcolm
and 512x smaller than original implementation of [well, almost] the
same algorithm!

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

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

csiph-web