Michael S wrote:
> On Mon, 18 Mar 2024 03:00:32 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> bart <bc@freeuk.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?
>>>
>>> You have evidence to suggest that the opposite is true?
>>
>> The claim is that recursion always makes programs harder to reason
>> about and prove correct. It's easy to find examples that show
>> recursion does not always makes programs harder to reason about and
>> prove correct.
>>
>>> I personally find recursion hard work and errors much harder to
>>> debug.
>>
>> Most likely that's because you haven't had the relevant background
>> in learning how to program in a functional style. That matches my
>> own experience: it was only after learning how to write programs in
>> a functional style that I really started to appreciate the benefits
>> of using recursion, and to understand how to write and reason about
>> recursive programs.
>>
>>> It is also becomes much more important to show that will not cause
>>> stack overflow.
>>
>> In most cases it's enough to show that the stack depth never exceeds
>> log N for an input of size N. I use recursion quite routinely
>> without there being any significant danger of stack overflow. It's
>> a matter of learning which patterns are safe and which patterns are
>> potentially dangerous, and avoiding the dangerous patterns (unless
>> certain guarantees can be made to make them safe again).
>
> The problem in this case is that max. depth of recursion is O(N) where N
> is total number of pixels to change color. So far I didn't find an
> obvious way to cut the worst case by more than small factor without
> turning recursive algorithm into something that is unrecognizably
> different from original and require proof of correction of its own.
> Classic 'divide and conquer smaller part first" strategy does not
> appear applicable here, or at least not obviously.
>
in reality it is less i guess..
well that would be like if i would like to recolor
vertical line of say length 2 milion pixels
- i would go always one pixel right 2 milion times

if this is 100x 100 square and i put the initioation
in middle it would go 50x right then at depth 50
it would go one up than i guess 100 times left

then just about this line up until up edge of picture
- then it probably revert back (with a lot
of false is) to first line and then go down

- so it seems (though i was not checkingh it
tu much in my head) that the depth in that case
would be about half

- but this is becouse its much unfortunate,
'normally' i think the recursion depth
should be more like to edge of an area

(i will answer more later as i hate usenet by newsreader
so unconveniant to read and answer its pain)

the problem has a couple of aspects imo
- interesting is in fact the great simplicity
of this recursion method esp in that case - which gives to think

On 19/03/2024 15:05, fir wrote:
> Michael S wrote:
>> On Mon, 18 Mar 2024 03:00:32 -0700
>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>
>>> bart <bc@freeuk.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?
>>>>
>>>> You have evidence to suggest that the opposite is true?
>>>
>>> The claim is that recursion always makes programs harder to reason
>>> about and prove correct.  It's easy to find examples that show
>>> recursion does not always makes programs harder to reason about and
>>> prove correct.
>>>
>>>> I personally find recursion hard work and errors much harder to
>>>> debug.
>>>
>>> Most likely that's because you haven't had the relevant background
>>> in learning how to program in a functional style.  That matches my
>>> own experience:  it was only after learning how to write programs in
>>> a functional style that I really started to appreciate the benefits
>>> of using recursion, and to understand how to write and reason about
>>> recursive programs.
>>>
>>>> It is also becomes much more important to show that will not cause
>>>> stack overflow.
>>>
>>> In most cases it's enough to show that the stack depth never exceeds
>>> log N for an input of size N.  I use recursion quite routinely
>>> without there being any significant danger of stack overflow.  It's
>>> a matter of learning which patterns are safe and which patterns are
>>> potentially dangerous, and avoiding the dangerous patterns (unless
>>> certain guarantees can be made to make them safe again).
>>
>> The problem in this case is that max. depth of recursion is O(N) where N
>> is total number of pixels to change color. So far I didn't find an
>> obvious way to cut the worst case by more than small factor without
>> turning recursive algorithm into something that is unrecognizably
>> different from original and require proof of correction of its own.
>> Classic 'divide and conquer smaller part first" strategy does not
>> appear applicable here, or at least not obviously.
>>
> in reality it is less i guess..
> well that would be like if i would like to recolor
> vertical line of say length 2 milion pixels
> - i would go always one pixel right 2 milion times
>
> if this is 100x 100 square and i put the initioation
> in middle it would go 50x right then at depth 50
> it would go one up than i guess 100 times left
>
> then just about this line up until up edge of picture
> - then it probably revert back (with a lot
> of false is) to first line and then go down

That's what I thought until I tried it.

If I start with an 18x18 image of all zeros, then fill starting from the
centre with a 'colour' that is an incrementing value, then the final
image displayed as a table of integers looks like this:

171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154
136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
135 134 133 132 131 130 129 128 127 126 125 124 123 122 121 120 119 118
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82
64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46
28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10
172 173 174 175 176 177 178 179 180 1 2 3 4 5 6 7 8 9
209 210 211 212 213 214 215 216 181 182 183 184 185 186 187 188 189 190
208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191
217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234
252 251 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235
253 254 255 325 257 258 259 260 261 262 263 264 265 266 267 268 269 270
288 287 286 285 284 283 282 281 280 279 278 277 276 275 274 273 272 271
289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306
324 323 322 321 320 319 318 317 316 315 314 313 312 311 310 309 308 307

By following the sequence starting from 1, you can see the fill-pattern.

It's not clear how it gets from 171 at top left to 172 half-way down the
left edge.

On Tue, 19 Mar 2024 11:57:53 +0000
Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:

> On 19/03/2024 11:18, Michael S wrote:
> > 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.
> >>
> >>
> >> typedef unsigned char Color;
> >> typedef unsigned int UI;
> >> typedef struct { UI x, y; } Point;
> >> typedef unsigned int Index;
> >>
> >> static _Bool change_it( UI w, UI h, Color [w][h], Point, Color,
> >> Color );
> >>
> >> void
> >> fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old,
> >> Color new ){ static const Point deltas[4] = { {1,0}, {0,1},
> >> {-1,0}, {0,-1}, }; UI k = 0;
> >> UI n = 17;
> >> Point *todo = malloc( n * sizeof *todo );
> >>
> >> if( todo && change_it( w, h, pixels, p0, old, new ) )
> >> todo[k++] = p0;
> >>
> >> while( k > 0 ){
> >> Index j = n-k;
> >> memmove( todo + j, todo, k * sizeof *todo );
> >> k = 0;
> >>
> >> while( j < n ){
> >> Point p = todo[ j++ ];
> >> for( Index i = 0; i < 4; i++ ){
> >> Point q = { p.x + deltas[i].x, p.y + deltas[i].y
> >> }; if( ! change_it( w, h, pixels, q, old, new ) )
> >> continue; todo[ k++ ] = q;
> >> }
> >>
> >> if( j-k < 3 ){
> >> Index new_n = n+n/4;
> >> Index new_j = new_n - (n-j);
> >> Point *t = realloc( todo, new_n * sizeof *t );
> >> if( !t ){ k = 0; break; }
> >> memmove( t + new_j, t + j, (n-j) * sizeof *t );
> >> todo = t, n = new_n, j = new_j;
> >> }
> >> }
> >> }
> >>
> >> free( todo );
> >> }
> >>
> >> _Bool
> >> change_it( UI w, UI h, Color pixels[w][h], Point p, Color old,
> >> Color new ){ if( p.x >= w || p.y >= h || pixels[p.x][p.y] !=
> >> old ) return 0; return pixels[p.x][p.y] = new, 1;
> >> }
> >
> > This variant is significantly slower than Malcolm's.
> > 2x slower for solid rectangle, 6x slower for snake shape.
> > Is it the same algorithm?
> >
>
> No. Mine takes horizontal scan lines and extends them, then places
> the pixels above and below in a queue to be considered as seeds for
> the next scan line. (It's not mine, but I don't know who invented it.
> It wasn't me.)
>
> Tim, now what does it do? Essentially it's the recursive fill
> algorithm but with the data only on the stack instead of the call and
> the data. And todo is actually a queue rather than a stack.
>
> Now why would it be slower? Probaby because you usually only hit a
> pixel three times with mine - once below, once above, and once for
> the scan line itself, whilst you consider it 5 times for Tim's - once
> for each neighbour and once for itself. Then horizontally adjacent
> pixels are more likely to be in the same cache line than vertically
> adjacent pixels, so processing images in scan lines tends to be a bit
> faster.
>

I did a little more investigation gradually modifying Tim's code for
improved performance without changing the basic principle of the
algorithm. Yes, micro-optimization. Yes, I said earlier that doing so
in c.l.c it is bad sportsmanship. So what? I never claimed to be an
ideal sportsman.
The point is that after optimizations it's actually faster than the
best implementations of original recursive algorithm, including
implementation that uses explicit stack and is quite economical in its
memory consumption. Tim's algorithm is 8 times less economical (8 bytes
per saved node vs 1 byte in explicit stack) and nevertheless almost
twice faster for both shapes that I was testing.
So far, this algorithm is fastest among all "local" algorithms that I
tried. By "local" I mean algorithms that don't try to recolor more than
one pixel at time.
"Non-local" algorithms i.e. yours and my recursive algorithm that
recolors St. George cross, are somewhat faster, but I suspect that
it's because all shapes that I use for testing have either long
columns or long rows or both.
The nice thing about Tim's method is that we can expect that
performance depends on number of recolored pixels and almost nothing
else.
The second nice thing is that it is easy to understand. Not as easy as
original recursive method, but easier than the rest of them.

If you or somebody else is interested, here is [micro]optimized variant:

#include <stdlib.h>
#include <stddef.h>
#include <string.h>

typedef unsigned char Color;
typedef int UI;
typedef struct { UI x, y; } Point;

static inline
Point* circularIncr(Point* p, Point* beg, Point* end) {
return p + 1 == end ? beg : p + 1;
}

static inline
Point mk_point(int x, int y) {
Point pt={x,y};
return pt;
}

int floodfill_r(
Color *pixels,
int w, int h,
int pt0_x, int pt0_y,
Color old, Color new)
{ if (pt0_x < 0 || pt0_x >= w || pt0_y < 0 || pt0_y >= h)
return 0;

if (pixels[pt0_y*w+pt0_x] != old)
return 0;

pixels[pt0_y*w+pt0_x] = new;

const ptrdiff_t INITIAL_TODO_SIZE = 125;
Point *todo = malloc( (INITIAL_TODO_SIZE+3) * sizeof *todo );
// +3 is extra size to assist wrap-around of wr
if (!todo)
return -1;
Point* todo_end = &todo[INITIAL_TODO_SIZE];

todo[0] = mk_point(pt0_x, pt0_y);
Point* wr = &todo[1];
Point* rd = todo;
ptrdiff_t free_space = INITIAL_TODO_SIZE - 1;
do {
Point pt = *rd;
rd = circularIncr(rd, todo, todo_end);
Point* prev_wr = wr;
if (pt.x > 0 && pixels[pt.y*w+pt.x-1] == old) {
pixels[pt.y*w+pt.x-1] = new;
*wr++ = mk_point(pt.x-1, pt.y);
}
if (pt.y > 0 && pixels[pt.y*w+pt.x-w] == old) {
pixels[pt.y*w+pt.x-w] = new;
*wr++ = mk_point(pt.x, pt.y-1);
}
if (pt.x+1 < w && pixels[pt.y*w+pt.x+1] == old) {
pixels[pt.y*w+pt.x+1] = new;
*wr++ = mk_point(pt.x+1, pt.y);
}
if (pt.y+1 < h && pixels[pt.y*w+pt.x+w] == old) {
pixels[pt.y*w+pt.x+w] = new;
*wr++ = mk_point(pt.x, pt.y+1);
}

free_space += 1 - (wr - prev_wr);
if (wr >= todo_end) {
memcpy(todo, todo_end, (wr - todo_end)*sizeof(*wr));
wr += todo - todo_end;
}

if (free_space < 4) {
ptrdiff_t rdi = rd-todo;
ptrdiff_t wri = wr-todo;
ptrdiff_t sz = todo_end - todo;
ptrdiff_t incr = sz/4;
Point* new_todo = realloc(todo, (sz+incr+3) * sizeof *todo );
// +3 is extra size to assist wrap-around of wr
if(!new_todo) {
free(todo);
return -1;
}
free_space += incr;
rd = &new_todo[rdi];
wr = &new_todo[wri];
todo = new_todo;
todo_end = &todo[sz+incr];
if (rd >= wr) {
memmove(&rd[incr], rd, (sz-rdi) * sizeof *todo );
rd = &rd[incr];
}
}
} while (rd != wr);

free( todo );
return 1;
}

On 19/03/2024 17:16, bart wrote:
> On 19/03/2024 15:05, fir wrote:

>> if this is 100x 100 square and i put the initioation
>> in middle it would go 50x right then at depth 50
>> it would go one up than i guess 100 times left
>>
>> then just about this line up until up edge of picture
>> - then it probably revert back (with a lot
>> of false is) to first line and then go down
>
> That's what I thought until I tried it.
>
> If I start with an 18x18 image of all zeros, then fill starting from the
> centre with a 'colour' that is an incrementing value, then the final
> image displayed as a table of integers looks like this:
>
>
> 171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154
> 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
> 135 134 133 132 131 130 129 128 127 126 125 124 123 122 121 120 119 118
> 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
>  99  98  97  96  95  94  93  92  91  90  89  88  87  86  85  84  83  82
>  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81
>  63  62  61  60  59  58  57  56  55  54  53  52  51  50  49  48  47  46
>  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45
>  27  26  25  24  23  22  21  20  19  18  17  16  15  14  13  12  11  10
> 172 173 174 175 176 177 178 179 180   1   2   3   4   5   6   7   8   9
> 209 210 211 212 213 214 215 216 181 182 183 184 185 186 187 188 189 190
> 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191
> 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234
> 252 251 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235
> 253 254 255 325 257 258 259 260 261 262 263 264 265 266 267 268 269 270
> 288 287 286 285 284 283 282 281 280 279 278 277 276 275 274 273 272 271
> 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306
> 324 323 322 321 320 319 318 317 316 315 314 313 312 311 310 309 308 307

> It's not clear how it gets from 171 at top left to 172 half-way down the
> left edge.

Actually, a more revealing picture is produced when storing the
calldepth in each cell rather than sequence number (these images are now
16-bits/cell rather than 8):

171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154
136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
135 134 133 132 131 130 129 128 127 126 125 124 123 122 121 120 119 118
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82
64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46
28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10
28 29 30 31 32 33 34 35 36 1 2 3 4 5 6 7 8 9
65 66 67 68 69 70 71 72 37 38 39 40 41 42 43 44 45 46
64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47
65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82
100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83
101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
136 135 134 133 132 131 130 129 128 127 126 125 124 123 122 121 120 119
137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154
172 171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155

At least now I know how it gets from the top left to the 172 in the top
image: it must do a cascade of Returns until it gets back to call-depthe
27 in this second chart, then it does the cell immediately below.

bart wrote:
> On 19/03/2024 15:05, fir wrote:
>> Michael S wrote:
>>> On Mon, 18 Mar 2024 03:00:32 -0700
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>>
>>>> bart <bc@freeuk.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?
>>>>>
>>>>> You have evidence to suggest that the opposite is true?
>>>>
>>>> The claim is that recursion always makes programs harder to reason
>>>> about and prove correct. It's easy to find examples that show
>>>> recursion does not always makes programs harder to reason about and
>>>> prove correct.
>>>>
>>>>> I personally find recursion hard work and errors much harder to
>>>>> debug.
>>>>
>>>> Most likely that's because you haven't had the relevant background
>>>> in learning how to program in a functional style. That matches my
>>>> own experience: it was only after learning how to write programs in
>>>> a functional style that I really started to appreciate the benefits
>>>> of using recursion, and to understand how to write and reason about
>>>> recursive programs.
>>>>
>>>>> It is also becomes much more important to show that will not cause
>>>>> stack overflow.
>>>>
>>>> In most cases it's enough to show that the stack depth never exceeds
>>>> log N for an input of size N. I use recursion quite routinely
>>>> without there being any significant danger of stack overflow. It's
>>>> a matter of learning which patterns are safe and which patterns are
>>>> potentially dangerous, and avoiding the dangerous patterns (unless
>>>> certain guarantees can be made to make them safe again).
>>>
>>> The problem in this case is that max. depth of recursion is O(N) where N
>>> is total number of pixels to change color. So far I didn't find an
>>> obvious way to cut the worst case by more than small factor without
>>> turning recursive algorithm into something that is unrecognizably
>>> different from original and require proof of correction of its own.
>>> Classic 'divide and conquer smaller part first" strategy does not
>>> appear applicable here, or at least not obviously.
>>>
>> in reality it is less i guess..
>> well that would be like if i would like to recolor
>> vertical line of say length 2 milion pixels
>> - i would go always one pixel right 2 milion times
>>
>> if this is 100x 100 square and i put the initioation
>> in middle it would go 50x right then at depth 50
>> it would go one up than i guess 100 times left
>>
>> then just about this line up until up edge of picture
>> - then it probably revert back (with a lot
>> of false is) to first line and then go down
>
> That's what I thought until I tried it.
>
> If I start with an 18x18 image of all zeros, then fill starting from the
> centre with a 'colour' that is an incrementing value, then the final
> image displayed as a table of integers looks like this:
>
>
> 171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154
> 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
> 135 134 133 132 131 130 129 128 127 126 125 124 123 122 121 120 119 118
> 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
> 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82
> 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
> 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46
> 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
> 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10
> 172 173 174 175 176 177 178 179 180 1 2 3 4 5 6 7 8 9
> 209 210 211 212 213 214 215 216 181 182 183 184 185 186 187 188 189 190
> 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191
> 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234
> 252 251 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235
> 253 254 255 325 257 258 259 260 261 262 263 264 265 266 267 268 269 270
> 288 287 286 285 284 283 282 281 280 279 278 277 276 275 274 273 272 271
> 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306
> 324 323 322 321 320 319 318 317 316 315 314 313 312 311 310 309 308 307
>
> By following the sequence starting from 1, you can see the fill-pattern.
>
> It's not clear how it gets from 171 at top left to 172 half-way down the
> left edge.
>
>
well its exactly what i said and is clear imo, whats not clear - simply
it was developing "try right, try left, try up, try down" untill
clasjhes with up edge then gets beck to level one depth and continues
but now until meets down edge - but fine you tested it

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

David Brown wrote:
> rks, 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

this code of my was a most fast implementation when i was needed to test
something in 3 minutes as the efect looks good
(i wrote an editor for low resolution drawing when i select the
given color piece then if selected by pressing control or shift
and moving mouse i recolorise this component in fluid way -

- it ios good becouse you may see which colors fits to other colors and
some editors liek paint dont allow that this to compose some image with
fitting colors you got much much harder amount of work)

btw this is seen its written as adhoc solution becouse from
optimistation point of view apssing old_color and new_color
wchich are always teh same (like passing them in whole branch
potential milion times) is nonsense - but this "branch"
(as i wouldnt call it function, its ratcher brabjc - need
that data.. and if not passing it as args i would need to make
standalone variables

Michael S 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;
> }
>
>
im not quite sure what you do here.. pass the structure? in fact
the thing you name context you may not pass at all just make is
standalone static variables becouse they/it is the same for whole
"branch" (given recursive branch of recolorisation)

On Wed, 20 Mar 2024 00:03:04 +0100
fir <fir@grunge.pl> wrote:
> im not quite sure what you do here.. pass the structure? in fact
> the thing you name context you may not pass at all just make is
> standalone static variables becouse they/it is the same for whole
> "branch" (given recursive branch of recolorisation)
>
> something like
>
> int old_color = 0xff0000;
> int new_color = 0x00ff00;
>
> void RecolorizePixelAndAdjacentPixels(int x, int y)
> {
> //...
> }
>
>

Not thred-safe.

Michael S wrote:
> On Wed, 20 Mar 2024 00:03:04 +0100
> fir <fir@grunge.pl> wrote:
>> im not quite sure what you do here.. pass the structure? in fact
>> the thing you name context you may not pass at all just make is
>> standalone static variables becouse they/it is the same for whole
>> "branch" (given recursive branch of recolorisation)
>>
>> something like
>>
>> int old_color = 0xff0000;
>> int new_color = 0x00ff00;
>>
>> void RecolorizePixelAndAdjacentPixels(int x, int y)
>> {
>> //...
>> }
>>
>>
>
> Not thred-safe.
>
some thread safe as previous, and i just say that thiose new_color and
old_color in arguments i add for convenience - as those all was
functional test if the operation of recolorisation visibly works and how
in my lowres (bigpixel) graphics editor - its no need to pass it
down the stack..also the test if old_color = new color then return
is strictly probably not needed to populate

i also made unnecesary GetPixelSafe - i use two metods liek SetPixelSafe
just checks if x,y is in array at all ans SetPixelUnsafe
simply frame[y*frame_width+x] = color

so if you were interested in speed comparsions you wouldnt need to pass
structure at all and that will be faster

i agree generally with bot mclean and brown in this discusion
1) its not optimal so its kinda wrong
2) it is simple so its kinda usable and for some uses its handy so
not all accusations of this being wring are justified

Michael S wrote:
> On Sat, 16 Mar 2024 11:33:20 +0000
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> 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.
>
> Except I don't understand why it works it all.
> Can't fill area have sub-areas that only connected through diagonal?
>
>

this is right remark..i simply not thought on it..but thiose are kinda
details i just my modify the function if i would notice i need the
diagonally conected

note how the topic was born : i was writing the editor, the simple
editor is a work of 1-2 days of code - in here the "recolorisation
of selected (by mouse click) area" is a 30 minutes try then i go further

i asked the topic here as i felt i got no time to rethink if it will
blow my progranm or not but that 30 minurtes task was for 30 minutes
not for a multi hour discusion

hovever i often like to post that some piece of coding to turn into
multi-hpour discusiion to get a bigger ground on some things then coding
become more solid

Peter 'Shaggy' Haywood wrote:
> Groovy hepcat Lew Pitcher was jivin' in comp.lang.c on Mon, 18 Mar 2024
> 01:27 am. It's a cool scene! Dig it.
>
>>> On 16/03/2024 04:11, fir wrote:
>
> [Snip.]
>
>>>> 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;
>>>> }
>
> [Snippity doo dah.]
>
>> Take fir's example code above; a simple single call to
>> RecolorizePixelAndAdjacentOnes() will effectively recolour the
>> origin cell multiple times, because of how the recursion is handled.
>
> No, I don't think so. You seem to have missed the fact that it checks
> the colour of the "current" pixel, and only continues (setting new
> colour & recursing) if it is the old colour.
> Of course, I'm infering (guessing) the functionality, at least
> partially (Unsafe? Safe?), of GetPixelUnsafe() and SetPixelSafe() based
> on their names.
>
> [Snip Lew's examples.]
>

Safe and Unsafe means that Safe checks if the x,y is in the array of
pixels, when Unsafe just writes without checking - i draw in array of
unsigned 32 bit ARGB or GBRA (never remeber) pixels - then i blit that
'bitmap' on window client size as it can be done in winapi

here are exact code

inline void SetPixelUnsafe(int x, int y, unsigned color)
{ extern int frame_size_x ;
extern int frame_size_y ;
extern unsigned int* frame_bitmap ;

frame_bitmap[y*frame_size_x+x]=color;
}

inline void SetPixelSafe(int x, int y, unsigned color)
{ // if(frame==0) ERROR_EXIT("frame is zero in setpixelsafe ");
if(x<0) return;
if(x>frame_size_x-1) return;
if(y<0) return;
if(y>frame_size_y-1) return;

frame_bitmap[y*frame_size_x+x]=color;
}

there was soem mistake in that function before as if i check already i
should be using Unsafe versions of setpixel and getpixel but i tested
this for work not for optimisation so i didnt care

fir wrote:
>
> this code of my was a most fast implementation when i was needed to test
> something in 3 minutes as the efect looks good

i mean probabaly 30 minutes

bart 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 -
>
> On my machine, it's OK up to a 400x400 image (starting with all one
> colour and filling from the centre with another colour).
>
> At 500x500, I get stack overflow. The 400x400 the maximum recursion
> depth is 80,000 calls.
>

i was slightly thinking a bit of this recursion more generally and
i observed that those very long depth chains are kinda problem of this
recursion becouse maybe it is more fitted to be run parrallel

if yu would just 'fork' that one call on 4 parallel calls you dont get
that problem - as it then works like 'horisontal' (shallow, like in
shallow searh) not 'vertical' (in-depth, deep search)

and if someone would rewrite in on non recursion way then it would be
natural to rewrite it to work horisontal -w hich is better

if someone would fork it in really parallel then the program of
sybchronistation of ram accesses appears

this observation hovewer may be seen as a strength of resursion -
as it naturally shows it works good with micro-paralelisation
(crowd of execution channels)

Malcolm McLean 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;
> }
>
if someone would write simpler version i would write

recolorize_pixel_chain(int x, int y)
{ if(map[y][x]==color_to_replace)
{
map[y][x]=replacement_color);

recolorize_pixel_chain(x+1, y);
recolorize_pixel_chain(x-1, y);
recolorize_pixel_chain(x, y+1);
recolorize_pixel_chain(x, y-1);
}
}

but from practical coding the one with longer names is more practical
imo - but this one above is more 'presenting'

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On 19/03/2024 05:54, Tim Rentsch wrote:
>
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>
>>> On 18/03/2024 09:30, Tim Rentsch wrote:
>>>
>>>> Michael S <already5chosen@yahoo.com> writes:
>>
>> [...]
>>
>>>>> Except I don't understand why it works it all.
>>>>> Can't fill area have sub-areas that only connected through
>>>>> diagonal?
>>>>
>>>> It is customary in raster graphics to count pixels as adjacent
>>>> only if they share an edge, not if they just share a corner.
>>>> Usually that gives better results; the exceptions tend to need
>>>> special handling anyway and not just connecting through
>>>> diagonals.
>>>
>>> Though with a binary image, if the foreground is 4-connected, the
>>> background must therefore be 8-connected.
>>
>> It might be but it doesn't have to be.
>>
>> Also different terminology should be used, since 4-connected
>> (also N-connected, for other integer N) has a specific meaning in
>> graph theory, and one very different than what is meant above.
>
> That is the terminology in binary image processing. The pixels are
> 4-connected or 8-connected depending on whether a shared corner is
> considered to make the group of pixels two objects or one object.

A poor choice of terminology. Side adjacent or corner and side
adjacent would be better.

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.
>>
>>
>> typedef unsigned char Color;
>> typedef unsigned int UI;
>> typedef struct { UI x, y; } Point;
>> typedef unsigned int Index;
>>
>> static _Bool change_it( UI w, UI h, Color [w][h], Point, Color,
>> Color );
>>
>> void
>> fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old, Color
>> new ){ static const Point deltas[4] = { {1,0}, {0,1}, {-1,0},
>> {0,-1}, }; UI k = 0;
>> UI n = 17;
>> Point *todo = malloc( n * sizeof *todo );
>>
>> if( todo && change_it( w, h, pixels, p0, old, new ) )
>> todo[k++] = p0;
>>
>> while( k > 0 ){
>> Index j = n-k;
>> memmove( todo + j, todo, k * sizeof *todo );
>> k = 0;
>>
>> while( j < n ){
>> Point p = todo[ j++ ];
>> for( Index i = 0; i < 4; i++ ){
>> Point q = { p.x + deltas[i].x, p.y + deltas[i].y };
>> if( ! change_it( w, h, pixels, q, old, new ) )
>> continue; todo[ k++ ] = q;
>> }
>>
>> if( j-k < 3 ){
>> Index new_n = n+n/4;
>> Index new_j = new_n - (n-j);
>> Point *t = realloc( todo, new_n * sizeof *t );
>> if( !t ){ k = 0; break; }
>> memmove( t + new_j, t + j, (n-j) * sizeof *t );
>> todo = t, n = new_n, j = new_j;
>> }
>> }
>> }
>>
>> free( todo );
>> }
>>
>> _Bool
>> change_it( UI w, UI h, Color pixels[w][h], Point p, Color old, Color
>> new ){ if( p.x >= w || p.y >= h || pixels[p.x][p.y] != old )
>> return 0; return pixels[p.x][p.y] = new, 1;
>> }
>
> 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 any case
the code was written for clarity of presentation, with
no attention paid to low-level performance.

> Is it the same algorithm?

Sorry, the same algorithm as what? The same as Malcolm's?
Definitely not. The same as my other posting that does
not do dynamic reallocation? Yes in the sense that if the
allocated array is large enough to begin with then no
reallocations are needed.

> 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. 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. Anyway the
interface is poorly designed to start with, there are bigger
problems than just whether a variably modified type is used.
(I chose the interface I did to approximate the interface
used in Malcolm's code.)

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.

Michael S <already5chosen@yahoo.com> writes:

> On Tue, 19 Mar 2024 11:57:53 +0000
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
>
>> No. Mine takes horizontal scan lines and extends them, then places
>> the pixels above and below in a queue to be considered as seeds for
>> the next scan line. (It's not mine, but I don't know who invented it.
>> It wasn't me.)
>>
>> Tim, now what does it do? Essentially it's the recursive fill
>> algorithm but with the data only on the stack instead of the call and
>> the data. And todo is actually a queue rather than a stack.
>>
>> Now why would it be slower? Probaby because you usually only hit a
>> pixel three times with mine - once below, once above, and once for
>> the scan line itself, while you consider it 5 times for Tim's - once
>> for each neighbour and once for itself. Then horizontally adjacent
>> pixels are more likely to be in the same cache line than vertically
>> adjacent pixels, so processing images in scan lines tends to be a bit
>> faster.
>
> Below is a variant of recursive algorithm that is approximately as
> fast as your code (1.25x faster for filling solid rectangle, 1.43x
> slower for filling snake shape).
> The code is a bit long, but I hope that the logic is still obvious and
> there is no need to prove correctness. [...]

To me it looks like this recursive algorithm doesn't find all
pixels that need coloring in some situations.

On 3/19/2024 9:40 PM, Tim Rentsch wrote:
> Michael S <already5chosen@yahoo.com> writes:
[...]

We should take a shape, and use it as a unit test. Perhaps a fractal:

https://i.ibb.co/Xpq2trH/ct-p1.png

On 3/19/2024 9:43 PM, Chris M. Thomasson wrote:
> On 3/19/2024 9:40 PM, Tim Rentsch wrote:
>> Michael S <already5chosen@yahoo.com> writes:
> [...]
>
> We should take a shape, and use it as a unit test. Perhaps a fractal:
>
> https://i.ibb.co/Xpq2trH/ct-p1.png
>
fun with shaders:

Think of scaling back an escaping point wrt escape time fractals, for a
couple of iterations:

https://i.ibb.co/Xpq2trH/ct-p1.png

https://i.ibb.co/cLxjV5W/image.png

I have a shader for it, mutating and existing one by Inigo Quilez -
iq/2013 , hyper smart! on and on... :^)

https://www.shadertoy.com/view/XtscDl

Flood fill it... ;^)

Michael S wrote:
> On Tue, 19 Mar 2024 11:57:53 +0000
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
>
>> On 19/03/2024 11:18, Michael S wrote:
>>> 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.
>>>>
>>>>
>>>> typedef unsigned char Color;
>>>> typedef unsigned int UI;
>>>> typedef struct { UI x, y; } Point;
>>>> typedef unsigned int Index;
>>>>
>>>> static _Bool change_it( UI w, UI h, Color [w][h], Point, Color,
>>>> Color );
>>>>
>>>> void
>>>> fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old,
>>>> Color new ){ static const Point deltas[4] = { {1,0}, {0,1},
>>>> {-1,0}, {0,-1}, }; UI k = 0;
>>>> UI n = 17;
>>>> Point *todo = malloc( n * sizeof *todo );
>>>>
>>>> if( todo && change_it( w, h, pixels, p0, old, new ) )
>>>> todo[k++] = p0;
>>>>
>>>> while( k > 0 ){
>>>> Index j = n-k;
>>>> memmove( todo + j, todo, k * sizeof *todo );
>>>> k = 0;
>>>>
>>>> while( j < n ){
>>>> Point p = todo[ j++ ];
>>>> for( Index i = 0; i < 4; i++ ){
>>>> Point q = { p.x + deltas[i].x, p.y + deltas[i].y
>>>> }; if( ! change_it( w, h, pixels, q, old, new ) )
>>>> continue; todo[ k++ ] = q;
>>>> }
>>>>
>>>> if( j-k < 3 ){
>>>> Index new_n = n+n/4;
>>>> Index new_j = new_n - (n-j);
>>>> Point *t = realloc( todo, new_n * sizeof *t );
>>>> if( !t ){ k = 0; break; }
>>>> memmove( t + new_j, t + j, (n-j) * sizeof *t );
>>>> todo = t, n = new_n, j = new_j;
>>>> }
>>>> }
>>>> }
>>>>
>>>> free( todo );
>>>> }
>>>>
>>>> _Bool
>>>> change_it( UI w, UI h, Color pixels[w][h], Point p, Color old,
>>>> Color new ){ if( p.x >= w || p.y >= h || pixels[p.x][p.y] !=
>>>> old ) return 0; return pixels[p.x][p.y] = new, 1;
>>>> }
>>>
>>> This variant is significantly slower than Malcolm's.
>>> 2x slower for solid rectangle, 6x slower for snake shape.
>>> Is it the same algorithm?
>>>
>>
>> No. Mine takes horizontal scan lines and extends them, then places
>> the pixels above and below in a queue to be considered as seeds for
>> the next scan line. (It's not mine, but I don't know who invented it.
>> It wasn't me.)
>>
>> Tim, now what does it do? Essentially it's the recursive fill
>> algorithm but with the data only on the stack instead of the call and
>> the data. And todo is actually a queue rather than a stack.
>>
>> Now why would it be slower? Probaby because you usually only hit a
>> pixel three times with mine - once below, once above, and once for
>> the scan line itself, whilst you consider it 5 times for Tim's - once
>> for each neighbour and once for itself. Then horizontally adjacent
>> pixels are more likely to be in the same cache line than vertically
>> adjacent pixels, so processing images in scan lines tends to be a bit
>> faster.
>>
>
> I did a little more investigation gradually modifying Tim's code for
> improved performance without changing the basic principle of the
> algorithm. Yes, micro-optimization. Yes, I said earlier that doing so
> in c.l.c it is bad sportsmanship. So what? I never claimed to be an
> ideal sportsman.
> The point is that after optimizations it's actually faster than the
> best implementations of original recursive algorithm, including
> implementation that uses explicit stack and is quite economical in its
> memory consumption. Tim's algorithm is 8 times less economical (8 bytes
> per saved node vs 1 byte in explicit stack) and nevertheless almost
> twice faster for both shapes that I was testing.
> So far, this algorithm is fastest among all "local" algorithms that I
> tried. By "local" I mean algorithms that don't try to recolor more than
> one pixel at time.
> "Non-local" algorithms i.e. yours and my recursive algorithm that
> recolors St. George cross, are somewhat faster, but I suspect that
> it's because all shapes that I use for testing have either long
> columns or long rows or both.
> The nice thing about Tim's method is that we can expect that
> performance depends on number of recolored pixels and almost nothing
> else.
> The second nice thing is that it is easy to understand. Not as easy as
> original recursive method, but easier than the rest of them.
>
> If you or somebody else is interested, here is [micro]optimized variant:
>
>
> #include <stdlib.h>
> #include <stddef.h>
> #include <string.h>
>
>
> typedef unsigned char Color;
> typedef int UI;
> typedef struct { UI x, y; } Point;
>
> static inline
> Point* circularIncr(Point* p, Point* beg, Point* end) {
> return p + 1 == end ? beg : p + 1;
> }
>
> static inline
> Point mk_point(int x, int y) {
> Point pt={x,y};
> return pt;
> }
>
> int floodfill_r(
> Color *pixels,
> int w, int h,
> int pt0_x, int pt0_y,
> Color old, Color new)
> {
> if (pt0_x < 0 || pt0_x >= w || pt0_y < 0 || pt0_y >= h)
> return 0;
>
> if (pixels[pt0_y*w+pt0_x] != old)
> return 0;
>
> pixels[pt0_y*w+pt0_x] = new;
>
> const ptrdiff_t INITIAL_TODO_SIZE = 125;
> Point *todo = malloc( (INITIAL_TODO_SIZE+3) * sizeof *todo );
> // +3 is extra size to assist wrap-around of wr
> if (!todo)
> return -1;
> Point* todo_end = &todo[INITIAL_TODO_SIZE];
>
> todo[0] = mk_point(pt0_x, pt0_y);
> Point* wr = &todo[1];
> Point* rd = todo;
> ptrdiff_t free_space = INITIAL_TODO_SIZE - 1;
> do {
> Point pt = *rd;
> rd = circularIncr(rd, todo, todo_end);
> Point* prev_wr = wr;
> if (pt.x > 0 && pixels[pt.y*w+pt.x-1] == old) {
> pixels[pt.y*w+pt.x-1] = new;
> *wr++ = mk_point(pt.x-1, pt.y);
> }
> if (pt.y > 0 && pixels[pt.y*w+pt.x-w] == old) {
> pixels[pt.y*w+pt.x-w] = new;
> *wr++ = mk_point(pt.x, pt.y-1);
> }
> if (pt.x+1 < w && pixels[pt.y*w+pt.x+1] == old) {
> pixels[pt.y*w+pt.x+1] = new;
> *wr++ = mk_point(pt.x+1, pt.y);
> }
> if (pt.y+1 < h && pixels[pt.y*w+pt.x+w] == old) {
> pixels[pt.y*w+pt.x+w] = new;
> *wr++ = mk_point(pt.x, pt.y+1);
> }
>
> free_space += 1 - (wr - prev_wr);
> if (wr >= todo_end) {
> memcpy(todo, todo_end, (wr - todo_end)*sizeof(*wr));
> wr += todo - todo_end;
> }
>
> if (free_space < 4) {
> ptrdiff_t rdi = rd-todo;
> ptrdiff_t wri = wr-todo;
> ptrdiff_t sz = todo_end - todo;
> ptrdiff_t incr = sz/4;
> Point* new_todo = realloc(todo, (sz+incr+3) * sizeof *todo );
> // +3 is extra size to assist wrap-around of wr
> if(!new_todo) {
> free(todo);
> return -1;
> }
> free_space += incr;
> rd = &new_todo[rdi];
> wr = &new_todo[wri];
> todo = new_todo;
> todo_end = &todo[sz+incr];
> if (rd >= wr) {
> memmove(&rd[incr], rd, (sz-rdi) * sizeof *todo );
> rd = &rd[incr];
> }
> }
> } while (rd != wr);
>
> free( todo );
> return 1;
> }
>
>
>

On 19/03/2024 18:16, bart wrote:
> On 19/03/2024 15:05, fir wrote:

>> if this is 100x 100 square and i put the initioation
>> in middle it would go 50x right then at depth 50
>> it would go one up than i guess 100 times left
>>
>> then just about this line up until up edge of picture
>> - then it probably revert back (with a lot
>> of false is) to first line and then go down
>
> That's what I thought until I tried it.
>
> If I start with an 18x18 image of all zeros, then fill starting from the
> centre with a 'colour' that is an incrementing value, then the final
> image displayed as a table of integers looks like this:
>
>
> 171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154
> 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
> 135 134 133 132 131 130 129 128 127 126 125 124 123 122 121 120 119 118
> 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
>  99  98  97  96  95  94  93  92  91  90  89  88  87  86  85  84  83  82
>  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78  79  80  81
>  63  62  61  60  59  58  57  56  55  54  53  52  51  50  49  48  47  46
>  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45
>  27  26  25  24  23  22  21  20  19  18  17  16  15  14  13  12  11  10
> 172 173 174 175 176 177 178 179 180   1   2   3   4   5   6   7   8   9
> 209 210 211 212 213 214 215 216 181 182 183 184 185 186 187 188 189 190
> 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191
> 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234
> 252 251 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235
> 253 254 255 325 257 258 259 260 261 262 263 264 265 266 267 268 269 270
> 288 287 286 285 284 283 282 281 280 279 278 277 276 275 274 273 272 271
> 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306
> 324 323 322 321 320 319 318 317 316 315 314 313 312 311 310 309 308 307
>
> By following the sequence starting from 1, you can see the fill-pattern.
>
> It's not clear how it gets from 171 at top left to 172 half-way down the
> left edge.
>

After the sequence hits the end at 171, it backtracks down the numbers.
27 is the first it reaches where there is a zero square neighbour, so it
goes down from there - and the next number in the sequence is 172. Then
it is free to move to the right again (then down after moving right is
blocked at 180).

I think your posts here gives a very nice and clear way to view the
working of the algorithm. Thanks for doing that.

fir wrote:
>
> inline void RecolorizePixelAndSpawnNewPixelArea(int x, int y)
> {

as i use word area in doble mining here it should be renamed like

inline void RecolorizePixelAndSpawnNewPixelImmediateVicinity(int x, int y)

(generally i use almost such log function names in my codes but not
write comments at all
than as everything is then self commenting imo..with variable names i
use shorter, but sometimes it seem that some can also be a bit longel
like here list_of_pixels_bot etc)

On Wed, 20 Mar 2024 01:13:10 +0100
fir <fir@grunge.pl> wrote:
>
> i asked the topic here as i felt i got no time to rethink if it will
> blow my progranm or not but that 30 minurtes task was for 30 minutes
> not for a multi hour discusion
>

So you got the answer rather quickly and the answer is:
"Yes, in the worst case it can consume a lot of stack. Don't use this
simple and elegant algorithm unless you have full control both on size
of the images and on size of the stack and on size of the stack frame
generates by compiler for each recursive call."

fir wrote:
>
> RecolorizePixelAndSpawnNewPixelArea(x,y);
>
> while(list_of_pixels_bot<list_of_pixels_top)
> {
>
> RecolorizePixelAndSpawnNewPixelArea(list_of_pixels[list_of_pixels_bot].x,list_of_pixels[list_of_pixels_bot].y);
>
> list_of_pixels_bot++;
> }
>
> }
>
>
>
maybe this is an example os case when do {} while() would work better
than while,

do {
RecolorizePixelAndSpawnNewPixelImmediateVicinity(list_of_pixels[list_of_pixels_bot].x,list_of_pixels[list_of_pixels_bot].y);

} while(list_of_pixels_bot<list_of_pixels_top)

but that would be need to check as such loops are confusing

if so i think it is somewhat general sheme

do {something();} while(bot<top)

of rewriting recursion probably