Recursion make programs harder to reason about and prove correct.
Malcolm McLean <[email protected]> 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?
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.
Recursion make programs harder to reason about and prove 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.
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
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 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
On 16/03/2024 13:55, Ben Bacarisse wrote:
Malcolm McLean <[email protected]> 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
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.
On 16/03/2024 13:55, Ben Bacarisse wrote:
Malcolm McLean <[email protected]> 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?
David Brown <[email protected]> writes:
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
Malcolm can't even spell 'integer' correctly in that code blob :-).
Certainly the intent of Fir's algorithm is easily discerned from
his code. I can't say that about Malcolms.
On 16/03/2024 13:55, Ben Bacarisse wrote:
Malcolm McLean <[email protected]> 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.
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.
On 17/03/2024 10:31, Ben Bacarisse wrote:
[email protected] (Scott Lurndal) writes:Tbe main intent was to help fir. That algorithm does tend to blow the
David Brown <[email protected]> writes:
On 16/03/2024 12:33, Malcolm McLean wrote:Malcolm can't even spell 'integer' correctly in that code blob :-).
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 >>>
As someone with dyslexia I have never liked mocking remarks about
spelling errors. Using "even" suggests that a superficial issue hints
at deeper problems. This is rarely the case.
However, I /would/ urge Malcolm to correct the spelling if Bresenham
since the intent was clearly to credit the discoverer. Also,
misspellings don't play well with library databases.
Certainly the intent of Fir's algorithm is easily discerned from
his code. I can't say that about Malcolms.
I have some reservations about the code, but he posted a link so there
is no indication that he wants a review of it.
stack though of course it depends on the image. However worst case is a pattern which is pixel wide line, e.g. a spiral or a maze or a series of alterante light and dark bands with a lirtel gaps at each end. And you achieve that by filling half the pixels. So foe a 100x100 image your
worst case is 10,000 = 5,000 recursive calls, and the stack is blown.
On Sat, 16 Mar 2024 11:33:20 +0000
Malcolm McLean <[email protected]> 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?
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)
Malcolm McLean <[email protected]> writes:
On 16/03/2024 13:55, Ben Bacarisse wrote:
Malcolm McLean <[email protected]> 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.
On 17/03/2024 12:46, Michael S wrote:
On Sat, 16 Mar 2024 11:33:20 +0000
Malcolm McLean <[email protected]> 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?
Suppose you have an image which is a chessboard. You want to fill one
of the black squares so that it is red.
If you allow connectivity through the diagonals (so two notionally
square pixels that only meet at their corners would be connected),
then all the black squares would turn red, not just one.
On Sun, 17 Mar 2024 12:54:34 +0000
bart <[email protected]> wrote:
On 17/03/2024 12:46, Michael S wrote:
On Sat, 16 Mar 2024 11:33:20 +0000
Malcolm McLean <[email protected]> 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?
Suppose you have an image which is a chessboard. You want to fill one
of the black squares so that it is red.
If you allow connectivity through the diagonals (so two notionally
square pixels that only meet at their corners would be connected),
then all the black squares would turn red, not just one.
That's what I want.
Do fir wants something else?
On 17/03/2024 13:15, Michael S wrote:
On Sun, 17 Mar 2024 12:54:34 +0000
bart <[email protected]> wrote:
On 17/03/2024 12:46, Michael S wrote:
On Sat, 16 Mar 2024 11:33:20 +0000
Malcolm McLean <[email protected]> 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?
Suppose you have an image which is a chessboard. You want to fill
one of the black squares so that it is red.
If you allow connectivity through the diagonals (so two notionally
square pixels that only meet at their corners would be connected),
then all the black squares would turn red, not just one.
That's what I want.
Do fir wants something else?
His algorithm is the same as that presented in my textbook, where it
is called FloodFill4.
If I reread the notes I see now the significance of the '4', as it
talks about 4-connected and 8-connected versions.
Presumably you want the 8-connected version, which will have 4 extra
calls for the pixels at each corner.
His algorithm is the same as that presented in my textbook, where it is called FloodFill4.
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.
Recursion make programs harder to reason about and prove correct.
On Sat, 16 Mar 2024 11:33:20 +0000, 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.
Recursion make programs harder to reason about and prove correct.
I would have said that those unfamiliar with the concept of recursion
have a harder time reasoning about the effects of recursion, or proving
their recursive code correct.
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.
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:Now is this David Brown being David Borwn, ot its it actaully ture?
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).
And I need to run some tests, don't I?
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
On 16/03/2024 14:40, David Brown wrote:
On 16/03/2024 12:33, Malcolm McLean wrote:Now is this David Brown being David Borwn, ot its it actaully ture?
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).
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?
[email protected] (Scott Lurndal) writes:
David Brown <[email protected]> writes:
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
Malcolm can't even spell 'integer' correctly in that code blob :-).
As someone with dyslexia I have never liked mocking remarks about
spelling errors. Using "even" suggests that a superficial issue hints
at deeper problems. This is rarely the case.
However, I /would/ urge Malcolm to correct the spelling if Bresenham
since the intent was clearly to credit the discoverer. Also,
misspellings don't play well with library databases.
Certainly the intent of Fir's algorithm is easily discerned from
his code. I can't say that about Malcolms.
I have some reservations about the code, but he posted a link so there
is no indication that he wants a review of it.
On Sun, 17 Mar 2024 13:23:55 +0000
bart <[email protected]> wrote:
On 17/03/2024 13:15, Michael S wrote:
On Sun, 17 Mar 2024 12:54:34 +0000
bart <[email protected]> wrote:
On 17/03/2024 12:46, Michael S wrote:
On Sat, 16 Mar 2024 11:33:20 +0000
Malcolm McLean <[email protected]> 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?
Suppose you have an image which is a chessboard. You want to fill
one of the black squares so that it is red.
If you allow connectivity through the diagonals (so two notionally
square pixels that only meet at their corners would be connected),
then all the black squares would turn red, not just one.
That's what I want.
Do fir wants something else?
His algorithm is the same as that presented in my textbook, where it
is called FloodFill4.
If I reread the notes I see now the significance of the '4', as it
talks about 4-connected and 8-connected versions.
Presumably you want the 8-connected version, which will have 4 extra
calls for the pixels at each corner.
'4' variant does not appear useful for changing colors of drawn shapes,
like lines or circles. Nor would it work for changing color of text
except when font is unusually bold.
The convetional wisdom is the opposite, But here, conventional wisdom
fails. Because heaps are unlimited whilst stacks are not.
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:Now is this David Brown being David Borwn, ot its it actaully ture?
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).
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
On Sun, 17 Mar 2024 14:56:34 +0000
Malcolm McLean <[email protected]> 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:Now is this David Brown being David Borwn, ot its it actaully
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).
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;
}
On Sun, 17 Mar 2024 14:10:15 +0000
Ben Bacarisse <[email protected]> wrote:
bart <[email protected]> writes:
His algorithm is the same as that presented in my textbook, where it is
called FloodFill4.
s/my/his/?
What is mentioned in <ut4v4r$32mgb$[email protected]> : "I've just looked in my Computer Graphics Principles and Practice book" .
Spiros Bousbouras <[email protected]> writes:
On Sun, 17 Mar 2024 14:10:15 +0000
Ben Bacarisse <[email protected]> wrote:
bart <[email protected]> writes:
His algorithm is the same as that presented in my textbook, where it is >>>> called FloodFill4.
s/my/his/?
What is mentioned in <ut4v4r$32mgb$[email protected]> : "I've just looked in >> my Computer Graphics Principles and Practice book" .
That context seems to have got lost, and MM was quoting from his
textbook (or book at any rate). Thanks for pointing out the missing
context.
On 17/03/2024 16:45, David Brown wrote:
On 16/03/2024 16:09, Malcolm McLean wrote:Except it is not. You didn't give the right answer for the space requirements.
The OP's code is simple and obvious, as is its correctness (assuming
reasonable definitions of the pixel access and setting functions) and
its time and space requirements. Yours is not.
Your algorithm could be used in a proper implementation, with separateIt's better to have one function. Subroutines have a way of getting lost.>
functions to handle the different parts (such as the stack). The
algorithm itself is not bad, it's the implementation that is the main
problem.
I have no idea if your code is "out of date" or not. It seems to beIt was written a long time ago. But it is writeen in a conservative
written for images consisting of unsigned chars, so I a not sure it
was ever designed for real-world images.
subset of ANSI C, and so of course it still works, and should work for
along time to come. But the 256 integer queue tweak might be out of
date. And cache use is far more important now that it was on big
processors. So it might be a bit long in the tooth.
And it's part of the binary image library, and it's designed for marking
8- or 4- connected sections of those images by setting the 1 to a
different value. And then further processing. The binary images are
often derived from photographs by Otsu thresholding, which is in the
same library. But they aren't usually meant for human viewing by end users.
And are you going to be constructive or not? Suggest one which might be better? Even implement it?
I don't know if it is fair to call them a /lot/ more advanced, but
certainly a bit more advanced. And certainly better implementations
are possible.
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;
}
Except I don't understand why it works it all.
Can't fill area have sub-areas that only connected through diagonal?
On 16/03/2024 13:55, Ben Bacarisse wrote:
Malcolm McLean <[email protected]> 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?
I personally find recursion hard work and errors much harder to
debug.
It is also becomes much more important to show that will not cause
stack overflow.
bart <[email protected]> writes:
On 16/03/2024 13:55, Ben Bacarisse wrote:
Malcolm McLean <[email protected]> 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).
On 3/16/2024 1:29 PM, Chris M. Thomasson wrote:
On 3/16/2024 1:02 PM, Malcolm McLean wrote:
On 16/03/2024 18:21, Scott Lurndal wrote:
Malcolm McLean <[email protected]> writes:From experience this one blows the stack, but not always.
On 16/03/2024 13:55, Ben Bacarisse wrote:
Malcolm McLean <[email protected]> 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.
Sometimes it's OK to use.
Blowing the stack is not good at all. However, sometimes, I
consider a recursive algorithm easier to understand. So, I build it first... Get it working, _then_ think about an iterative
solution...
Gaining the iterative solution from a working recursive solution is
the fun part!
:^)
On 18/03/2024 06:58, David Brown wrote:
On 17/03/2024 19:28, Malcolm McLean wrote:I this case it s very short code and easy to see that it is right, so a
On 17/03/2024 16:45, David Brown wrote:
On 16/03/2024 16:09, Malcolm McLean wrote:Except it is not. You didn't give the right answer for the space
The OP's code is simple and obvious, as is its correctness (assuming
reasonable definitions of the pixel access and setting functions)
and its time and space requirements. Yours is not.
requirements.
Unfortunately, I am still fallible - /easier/ does not mean I'll get
it right :-( And I apologise for unhelpfully rushing that and getting
it wrong.
However, I stand by my claim that the recursive version is much easier
to analyse.
win for recursion.
Except that it is only right if the stack is bigger
than N/2 calls deep, where N is the number fo pixels in the image.
Now a
100x100 woked fine an my machine - I just checked the main stack, and
it's 8MB by default. BUt of cuuurse the bigger than machine, the bigger
the image th euser might want to load.
Exactly. If a routine ia leaf, you can cut and paste it and use it whereIt's better to have one function. Subroutines have a way of getting
lost.>
Seriously? "Subroutines get lost" ? So your answer is to put all
your ideas in a mixer and scrunch them up until any semblance of logic
and structure is lost, and the code works (if it does) by trial and
error? And then the whole mess is cut-and-paste duplicated - along
with any subtle bugs it might have - for 8-connected version. And
that's better, in your eyes, than re-using code?
you will. If you have to take subroutines, you've got to explore the
code to understand what you neeed to take, then you have to out them somewhere. So it's better to keep routines leaf is possible and fold a
few trivial operations into the code body, even if ideally they would be subroutines. And I understand these trade offs. >
I have been most interested in being able to be sure the algorithm isThat is an idea. But a bit extravanagant. I'd like to try to work out
correct, rather than considering its absolute (rather than "big O")
efficiency in different systems. It is certainly the case that cache
considerations are more relevant now than they used to be on many
systems. And for working on PC's, you would likely dispense with your
growing stack entirely and simply allocate a queue big enough for
every pixel in the image.
how much quue s actually used in typical as well as worst case.
I suggested separating the code into functions - that is /definitely/And of course the entire binary image library has a consistent style.
constructive. I suggested using sensible names for parameters and
variables (well, the suggestion was implied by my criticism).
And I am also suggesting now that you allocate a queue that is big
enough for every pixel in the image. Much of what you don't touch of
that space, will probably never be physically allocated by the OS,
depending on page sizes and free memory.
And I would also suggest you drop the requirement for coding in an
ancient tongue, and instead switch to reasonably modern C. Make
abstractions for the types and the access functions - it will make the
code far easier to follow, easier to show correct, and easier to
modify and reuse, without affecting efficiency at run-time.
And we don't want the user mee=ssing about with writing his own getpixel
/ setpixel functions, thouhg there would be a case for that for a
geneeral purpose flood fill.
On 18/03/2024 16:28, David Brown wrote:
On 18/03/2024 10:26, Malcolm McLean wrote:
It is completely normal for correctness proofs to make assumptions about
things like resources. An analysis of your code for correctness would
also generally assume that the heap would be big enough - if the heap
runs out, your code will not correctly flood-fill the image. Analysis
of efficiency in time and space is a separate issue - related, but
separate. Things like maximum recursion depth (and heap size) are very
implementation-specific, and thus need to be considered separately from
the algorithm itself.
It's trivial to engineer a system with a large stack and very small
heap. But unlikley anyone would actually do so on a system on which
floodfill would run.
And while this code is in C, the same algorithm could be implemented inI'll try it out. Since you're dyslexic.
other languages. A language that uses a VM might be fine with a much
higher recursion depth - or it might be much lower. A language for
which recursion is a major tool (such as a functional programming
language) might automatically convert some recursive code to a
queue-based non-recursive solution. (I'd be impressed to see one do
that for this algorithm, however.)
Now a 100x100 woked fine an my machine - I just checked the main
stack, and it's 8MB by default. BUt of cuuurse the bigger than
machine, the bigger the image th euser might want to load.
You still haven't considered using a spell-checker, even though you use
a news client with one built in? Perhaps you need a better keyboard?
Normal readers can read English
text with just the initial and terminal letters right and the rest
jumbled, at similar speed to normal text.
Pixels usually represent objects. Take a glance around your. How many
objects of a similar colour are spider's webs, lace curtains, long
wires, and so on. And how many are pieces of paper, coffee cups.
computer mice, and so on? And of course it mustn't fall over on the
unusual objects, but the main consideration is usually that it is fast
and efficient on the common ones.
Malcolm McLean <[email protected]> writes:
On 18/03/2024 16:28, David Brown wrote:
On 18/03/2024 10:26, Malcolm McLean wrote:
It is completely normal for correctness proofs to make assumptions about >>> things like resources. An analysis of your code for correctness would
also generally assume that the heap would be big enough - if the heap
runs out, your code will not correctly flood-fill the image. Analysis
of efficiency in time and space is a separate issue - related, but
separate. Things like maximum recursion depth (and heap size) are very >>> implementation-specific, and thus need to be considered separately from
the algorithm itself.
It's trivial to engineer a system with a large stack and very small
heap. But unlikley anyone would actually do so on a system on which
floodfill would run.
The first sentence is correct. Although with modern systems, 'small'
is relative (my 12 year old workstation has 16GB RAM) and defaults
to an 8MB stack, which can easily be increased on a per process or
per user basis.
The second is your opinion. What evidence do you have that
your opinion is fact?
On Sun, 17 Mar 2024 18:25:20 +0200
Michael S <[email protected]> wrote:
On Sun, 17 Mar 2024 14:56:34 +0000
Malcolm McLean <[email protected]> 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.
Even if in Big Oh sense they are the same, it does look like
Malcolm's variant is decisively faster in practice.
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?
On Mon, 18 Mar 2024 03:00:32 -0700
Tim Rentsch <[email protected]> wrote:
bart <[email protected]> writes:
On 16/03/2024 13:55, Ben Bacarisse wrote:
Malcolm McLean <[email protected]> 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.
On 18/03/2024 09:30, Tim Rentsch wrote:[...]
Michael S <[email protected]> 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.
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?
On 18/03/2024 16:28, David Brown wrote:
On 18/03/2024 10:26, Malcolm McLean wrote:
It is completely normal for correctness proofs to make assumptions
about things like resources. An analysis of your code for correctness
would also generally assume that the heap would be big enough - if the
heap runs out, your code will not correctly flood-fill the image.
Analysis of efficiency in time and space is a separate issue -
related, but separate. Things like maximum recursion depth (and heap
size) are very implementation-specific, and thus need to be considered
separately from the algorithm itself.
It's trivial to engineer a system with a large stack and very small
heap. But unlikley anyone would actually do so on a system on which
floodfill would run.
And while this code is in C, the same algorithm could be implementedI'll try it out. Since you're dyslexic. Normal readers can read English
in other languages. A language that uses a VM might be fine with a
much higher recursion depth - or it might be much lower. A language
for which recursion is a major tool (such as a functional programming
language) might automatically convert some recursive code to a
queue-based non-recursive solution. (I'd be impressed to see one do
that for this algorithm, however.)
Now a 100x100 woked fine an my machine - I just checked the main
stack, and it's 8MB by default. BUt of cuuurse the bigger than
machine, the bigger the image th euser might want to load.
You still haven't considered using a spell-checker, even though you
use a news client with one built in? Perhaps you need a better keyboard? >>
text with just the initial and terminal letters right and the rest
jumbled, at similar speed to normal text.
Pixels usually represent objects. Take a glance around your. How many
The worst case is either going to be the stripy path example given by
Michael S., or a completely blank image - it depends on how the
east-west stripes affect the queue depth. It should not be hard to
try these. So that would be either approximately half the total pixel
count, or the total pixel count. And I can't think how you could
specify a "typical" image and "typical" flood fill request - without
specifying this in some way, you need to collect lots of statistics of
real-world use, or it's mere guesswork.
objects of a similar colour are spider's webs, lace curtains, long
wires, and so on. And how many are pieces of paper, coffee cups.
computer mice, and so on? And of course it mustn't fall over on the
unusual objects, but the main consideration is usually that it is fast
and efficient on the common ones.
But not always of course, Sometimes results must in in under 0.1
seconds, and so 0.09 is as good as 0.01, but 0.11 on a rare spider's web
is catastrophic.
That would be the "royal we", I presume? I know /I/ would have no use
for a flood-fill routine that did not support colour styles I use.
This routine is part of the binary image processing library, so of
course it is written to be easy to use with binary images, or binary
images which have been processed and are no longer strictly binary
images. But if people want to take it and use it as pattern for a
general flood fill, then of course I'm perfectly happy that they have
found the code to be of use.
Malcolm McLean <[email protected]> writes:
On 18/03/2024 16:28, David Brown wrote:
You still haven't considered using a spell-checker, even though you useI'll try it out. Since you're dyslexic.
a news client with one built in? Perhaps you need a better keyboard?
I believe you're conflating David with someone else
who made that claim.
Malcolm McLean <[email protected]> writes:
On 18/03/2024 16:28, David Brown wrote:[...]
You still haven't considered using a spell-checker, even though youI'll try it out. Since you're dyslexic. Normal readers can read
use a news client with one built in? Perhaps you need a better
keyboard?
English text with just the initial and terminal letters right and the
rest jumbled, at similar speed to normal text.
I will not speculate about why you seem to be unaware that calling
someone dyslexic is insulting, both to the person you're addressing and
to people with dyslexia.
You need to stop making disparaging personal comments.
Tim Rentsch <[email protected]> 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;
}
I expect most people here can figure out the words Malcolm meant to type
when he fails to press the right keys. But we should not have to do so.
On 16/03/2024 04:11, fir wrote:
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;
}
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. 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.
On Mon, 18 Mar 2024 03:00:32 -0700
Tim Rentsch <[email protected]> wrote:
bart <[email protected]> writes:
On 16/03/2024 13:55, Ben Bacarisse wrote:
Malcolm McLean <[email protected]> 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.
Michael S wrote:
On Mon, 18 Mar 2024 03:00:32 -0700in reality it is less i guess..
Tim Rentsch <[email protected]> wrote:
bart <[email protected]> writes:
On 16/03/2024 13:55, Ben Bacarisse wrote:
Malcolm McLean <[email protected]> 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.
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
On 19/03/2024 11:18, Michael S wrote:
On Mon, 18 Mar 2024 22:42:14 -0700
Tim Rentsch <[email protected]> wrote:
Tim Rentsch <[email protected]> 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.
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.
On 19/03/2024 15:05, fir wrote:
Michael S wrote:
On Mon, 18 Mar 2024 03:00:32 -0700in reality it is less i guess..
Tim Rentsch <[email protected]> wrote:
bart <[email protected]> writes:
On 16/03/2024 13:55, Ben Bacarisse wrote:
Malcolm McLean <[email protected]> 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.
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 16/03/2024 18:21, Scott Lurndal wrote:
Malcolm McLean <[email protected]> writes:From experience this one blows the stack, but not always. Sometimes
On 16/03/2024 13:55, Ben Bacarisse wrote:
Malcolm McLean <[email protected]> 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.
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.
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
On Sun, 17 Mar 2024 14:56:34 +0000
Malcolm McLean <[email protected]> wrote:
On 16/03/2024 15:09, Malcolm McLean wrote:
On 16/03/2024 14:40, David Brown wrote:#include <stdio.h>
On 16/03/2024 12:33, Malcolm McLean wrote:Now is this David Brown being David Borwn, ot its it actaully ture?
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).
And I need to run some tests, don't I?
#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;
}
On Wed, 20 Mar 2024 00:03:04 +0100
fir <[email protected]> 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.
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)
{
//...
}
On Sat, 16 Mar 2024 11:33:20 +0000
Malcolm McLean <[email protected]> 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?
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.
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.]
this code of my was a most fast implementation when i was needed to test something in 3 minutes as the efect looks good
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:Now is this David Brown being David Borwn, ot its it actaully ture?
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).
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;
}
On 19/03/2024 05:54, Tim Rentsch wrote:
Malcolm McLean <[email protected]> writes:
On 18/03/2024 09:30, Tim Rentsch wrote:
Michael S <[email protected]> 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.
On Tue, 19 Mar 2024 11:57:53 +0000
Malcolm McLean <[email protected]> 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. [...]
On Mon, 18 Mar 2024 22:42:14 -0700
Tim Rentsch <[email protected]> wrote:
Tim Rentsch <[email protected]> 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?
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++.
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
inline void RecolorizePixelAndSpawnNewPixelArea(int x, int y)
{
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.
On Tue, 19 Mar 2024 11:57:53 +0000
Malcolm McLean <[email protected]> wrote:
On 19/03/2024 11:18, Michael S wrote:
On Mon, 18 Mar 2024 22:42:14 -0700
Tim Rentsch <[email protected]> wrote:
Tim Rentsch <[email protected]> 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;
}
Michael S <[email protected]> writes:
On Tue, 19 Mar 2024 11:57:53 +0000
Malcolm McLean <[email protected]> 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.
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++;
}
}
Michael S wrote:
On Wed, 20 Mar 2024 00:03:04 +0100
fir <[email protected]> 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,
Michael S <[email protected]> writes:
On Mon, 18 Mar 2024 22:42:14 -0700
Tim Rentsch <[email protected]> wrote:
Tim Rentsch <[email protected]> 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.
On Tue, 19 Mar 2024 21:40:22 -0700...
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
...Tim Rentsch <[email protected]> writes:
static _Bool change_it( UI w, UI h, Color [w][h], Point, Color,
Color );
Besides, I don't think that use of VLA in library code is a good
idea. VLA is optional in latest C standards. And incompatible with
C++.
The code uses a variably modified type, not a variable length
array.
I am not sufficiently versed in C Standard terminology to see a
difference.
Aren't they both introduced in C99 and made optional in later
standards?
On Wed, 20 Mar 2024 00:30:56 +0100
fir <[email protected]> wrote:
Michael S wrote:
On Wed, 20 Mar 2024 00:03:04 +0100some thread safe as previous,
fir <[email protected]> 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.
The same as your previous.
But I was modifying Malcolm's recursive variant rather than yours.
Malcolm's was thread-safe.
On Tue, 19 Mar 2024 21:43:33 -0700[...]
Tim Rentsch <[email protected]> wrote:
To me it looks like this recursive algorithm doesn't find all
pixels that need coloring in some situations.
Yesterday night I had few doubts myself, but after further thinking
came to conclusion that it it works in all situations.
Michael S wrote:
On Wed, 20 Mar 2024 00:30:56 +0100
fir <[email protected]> wrote:
Michael S wrote:
On Wed, 20 Mar 2024 00:03:04 +0100some thread safe as previous,
fir <[email protected]> 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.
The same as your previous.
But I was modifying Malcolm's recursive variant rather than yours. Malcolm's was thread-safe.
sure, i dont always read into peoples code.. i just wanted to say it
seems you pass this context structure or pointer to it
down the stack
each call - it is not necessary
On Wed, 20 Mar 2024 01:13:10 +0100
fir <[email protected]> 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."
On Wed, 20 Mar 2024 13:44:04 +0100
fir <[email protected]> wrote:
Michael S wrote:
On Wed, 20 Mar 2024 00:30:56 +0100sure, i dont always read into peoples code.. i just wanted to say it
fir <[email protected]> wrote:
Michael S wrote:
On Wed, 20 Mar 2024 00:03:04 +0100some thread safe as previous,
fir <[email protected]> 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.
The same as your previous.
But I was modifying Malcolm's recursive variant rather than yours.
Malcolm's was thread-safe.
seems you pass this context structure or pointer to it
Yes, pointer. That's the whole point of my modification of
Malcolm's code - to copy one pointer instead of 5 variables that
are never changed.
down the stack
each call - it is not necessary
Not necessary if you don't want it thread-safe. Necessary otherwise.
On Tue, 19 Mar 2024 11:57:53 +0000
Malcolm McLean <[email protected]> wrote:
On 19/03/2024 11:18, Michael S wrote:
On Mon, 18 Mar 2024 22:42:14 -0700
Tim Rentsch <[email protected]> wrote:
Tim Rentsch <[email protected]> writes:
Here is the refinement that uses a resizing rather than
fixed-size buffer.
I did a little more investigation gradually modifying Tim's code
for improved performance without changing the basic principle of
the algorithm. [...]
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, [...].
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: [...]
Michael S <[email protected]> writes:
On Tue, 19 Mar 2024 21:40:22 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
...
Tim Rentsch <[email protected]> writes:
...
static _Bool change_it( UI w, UI h, Color [w][h], Point, Color,
Color );
Besides, I don't think that use of VLA in library code is a
good idea. VLA is optional in latest C standards. And
incompatible with C++.
The code uses a variably modified type, not a variable length
array.
I am not sufficiently versed in C Standard terminology to see a
difference.
A VLA is a declared object -- an array with a size that is not a
compile-time constant. A variably modified type is just a type,
not an object. Obviously one can use such a type to declare a
VLA, but when it is the type of a function parameter, there need
be no declared object with that type. Usually the associated
function argument will have been dynamically allocated.
Aren't they both introduced in C99 and made optional in later
standards?
I think so but that's a shame since VMTs are very helpful for
writing array code. They avoid the need to keep calculating the
index with multiplications.
Making both optional was a classic case of throwing the baby out
with the bath water. Few of the objections raised about VLAs
apply to VMTs.
On Tue, 19 Mar 2024 21:40:22 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
On Mon, 18 Mar 2024 22:42:14 -0700
Tim Rentsch <[email protected]> wrote:
Tim Rentsch <[email protected]> writes:
[...]
Here is the refinement that uses a resizing rather than
fixed-size buffer.
[code]
This variant is significantly slower than Malcolm's.
2x slower for solid rectangle, 6x slower for snake shape.
Slower with some shapes, faster in others.
In my small test suit I found no cases where this specific code is
measurably faster than code of Malcolm.
I did find one case in which they are approximately equal. I call
it "slalom shape" and it's more or less designed to be the worst
case for algorithms that are trying to speed themselves by take
advantage of straight lines.
The slalom shape is generated by following code:
[code]
In any case
the code was written for clarity of presentation, with
no attention paid to low-level performance.
Yes, your code is easy to understand. Could have been easier
still if persistent indices had more meaningful names.
In other post I showed optimized variant of your algorithm: -
4-neighbors loop unrolled. Majority of the speed up come not from
unrolling itself, but from specialization of in-rectangle check
enabled by unroll.
- Todo queue implemented as circular buffer.
- Initial size of queue increased.
This optimized variant is more competitive with 'line-grabby'
algorithms in filling solid shapes and faster than them in
'slalom' case.
Generally, I like your algorithm.
It was surprising for me that queue can work better than stack, my
intuition suggested otherwise, but facts are facts.
Besides, I don't think that use of VLA in library code is a good
idea. VLA is optional in latest C standards. And incompatible
with C++.
The code uses a variably modified type, not a variable length
array.
I am not sufficiently versed in C Standard terminology to see a
difference.
Aren't they both introduced in C99 and made optional in later
standards?
Again, the choice is for clarity of presentation. If
someone wants to get rid of the variably modified types, it's
very easy to do, literally a five minute task.
Yes, that's what it took for me.
But I knew that variably modified types exist, even if I didn't know
that they are called such.
OTOH, many (majority?) of C programmers never heard about them.
Anyway the interface is poorly designed to start with, [...]
That's true. [...]
If someone wants to use the functionality from C++, it's
easy enough to write a C wrapper function to do that.
IMO C++ has diverged sufficiently from C so that there
is little to be gained by trying to make code interoperable
between the two languages.
From the practical perspective, the biggest obstacle is that your
code can't be compiled with popular Microsoft compilers.
I did a little more investigation gradually modifying Tim's code
for improved performance without changing the basic principle of
the algorithm. [...]
Michael S <[email protected]> writes:
[...]
I did a little more investigation gradually modifying Tim's code
for improved performance without changing the basic principle of
the algorithm. [...]
Here is a rendition of my latest and fastest refinement.
On Wed, 20 Mar 2024 10:26:58 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
[...]
I did a little more investigation gradually modifying Tim's code
for improved performance without changing the basic principle of
the algorithm. [...]
Here is a rendition of my latest and fastest refinement.
WOW, you really opened up your bag of tricks!
Power-of-two sized circular buffers is something that I tend to
use on smaller systems, like DSPs or MCUs rather than on "big"
computers. But, of course, on "big" computers it also helps.
Packing {x,y} into 32-bit word is a bit dirty. I'd guess that we
can justify it by claiming that original code although has similar
limitation of width*height <= INT_MAX.
Removal of FIFO empty and almost-full tests in the inner loop helps
solid shapes, but appears to slow down "drawn" shapes. Since solid
shapes are the slowest to fill, it is probably a good trade-off.
Overall, it is faster than my implementation of your algorithm.
Esp. so for solid shapes. Esp. of esp. so on Intel Skylake CPUs
where speed up is up to 1.75x.
More complicated 'St. George Cross' algorithms are still faster
for solid shapes and for shapes dominated by long horizontal or
long vertical lines. But they are ... well ... more complicated.
And [on Skylake] their worst case ('slalom' shape) is somewhat
slower in absolute sense than the worst case of your code (a solid
bar).
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
Groovy hepcat fir was jivin' in comp.lang.c on Wed, 20 Mar 2024 11:48
am. It's a cool scene! Dig it.
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
I wasn't going to post this here, since it's really an algorithm
issue, rather than a C issue. But the thread seems to have gone on for
some time with you seeming to be unable to solve this. So I'll give
you this as a clue.
The (or, at least, a) solution is only partially recursive. What I
have used is a line-based algorithm, each line being filled
iteratively (in a simple loop) from left to right. Recursion from
line to line completes the algorithm. Thus, the recursion level is
greatly reduced. And you should find that this approach fills an area
of any shape. Note, however, that for some pathological cases (very
large and complex shapes), this can still create a fairly large level
of recursion. Maybe a more complex approach can deal with this. What I present here is just a very simple one which, in most cases, should
have a level of recursion well within reason.
I use a two part approach. The first part (called floodfill in the
code below) just sets up for the second part. The second part (called r_floodfill here, for recursive floodfill) does the actual work, but
is only called by floodfill(). It goes something like this (although
this is incomplete, untested and not code I've actually used, just an example):
static void r_floodfill(unsigned y, unsigned x, pixel_t new_clr,
pixel_t old_clr)
{
unsigned start, end;
/* Find start and end of line within floodfill area. */
start = end = x;
while(old_clr == get_pixel(y, start - 1))
--start;
while(old_clr == get_pixel(y, end + 1))
++end;
/* Fill line with new colour. */
for(x = start; x <= end; x++)
set_pixel(y, x, new_clr);
/* Run along again, checking pixel colours above and below,
and recursing if appropriate. */
for(x = start; x <= end; x++)
{
if(old_clr == get_pixel(y - 1, x))
r_floodfill(y - 1, x, new_clr, old_clr);
if(old_clr == get_pixel(y + 1, x))
r_floodfill(y + 1, x, new_clr, old_clr);
}
}
void floodfill(unsigned y, unsigned x, pixel_t new_clr)
{
pixel_t old_clr = get_pixel(y, x);
/* Only proceed if colours differ. */
if(new_clr != old_clr)
r_floodfill(y, x, new_clr, old_clr);
}
To use this, simply call floodfill() passing the coordinates of the starting point for the fill (y and x) and the fill colour (new_clr).
On Fri, 22 Mar 2024 13:04:39 +1100
Peter 'Shaggy' Haywood <[email protected]> wrote:
To use this, simply call floodfill() passing the coordinates of
the starting point for the fill (y and x) and the fill colour
(new_clr).
It looks like anisotropic variant of my St. George Cross algorithm.
Or like recursive variant of Malcolm's algorithm.
Being anisotropic, it has higher amount of glass jaws. In particular,
it would be very slow for not uncommon 'jail window' patterns.
* *** *** *** ***
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
*** *** *** *** *
Also, implementation is still recursive and the worst-case recursion
depth is still O(N), where N is total number of recolored pixels, so
unlike many other solutions presented here, you didn't solve fir's
original problem.
And in presented form it's not thread-safe. Which is not a problem for
fir, but nonn-desirable for the rest of us.
Conclusion: sorry, you aren't going to get a cookie for your effort.
On 17/03/2024 11:25, Ben Bacarisse wrote:
Malcolm McLean <[email protected]> writes:The convetional wisdom is the opposite, But here, conventional wisdom
On 16/03/2024 13:55, Ben Bacarisse wrote:Had you offered a proof that your code neither "blows the stack" nor
Malcolm McLean <[email protected]> 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.
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?
fails. Because heaps are unlimited whilst stacks are not.
Groovy hepcat fir was jivin' in comp.lang.c on Wed, 20 Mar 2024 11:48
am. It's a cool scene! Dig it.
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
I wasn't going to post this here, since it's really an algorithm
issue, rather than a C issue. But the thread seems to have gone on for
some time with you seeming to be unable to solve this. So I'll give you
this as a clue.
The (or, at least, a) solution is only partially recursive. What I
have used is a line-based algorithm, each line being filled iteratively
(in a simple loop) from left to right. Recursion from line to line
completes the algorithm. Thus, the recursion level is greatly reduced.
And you should find that this approach fills an area of any shape.
Note, however, that for some pathological cases (very large and
complex shapes), this can still create a fairly large level of
recursion. Maybe a more complex approach can deal with this. What I
present here is just a very simple one which, in most cases, should
have a level of recursion well within reason.
I use a two part approach. The first part (called floodfill in the
code below) just sets up for the second part. The second part (called r_floodfill here, for recursive floodfill) does the actual work, but is
only called by floodfill(). It goes something like this (although this
is incomplete, untested and not code I've actually used, just an
example):
static void r_floodfill(unsigned y, unsigned x, pixel_t new_clr, pixel_t old_clr)
{
unsigned start, end;
/* Find start and end of line within floodfill area. */
start = end = x;
while(old_clr == get_pixel(y, start - 1))
--start;
while(old_clr == get_pixel(y, end + 1))
++end;
/* Fill line with new colour. */
for(x = start; x <= end; x++)
set_pixel(y, x, new_clr);
/* Run along again, checking pixel colours above and below,
and recursing if appropriate. */
for(x = start; x <= end; x++)
{
if(old_clr == get_pixel(y - 1, x))
r_floodfill(y - 1, x, new_clr, old_clr);
if(old_clr == get_pixel(y + 1, x))
r_floodfill(y + 1, x, new_clr, old_clr);
}
}
void floodfill(unsigned y, unsigned x, pixel_t new_clr)
{
pixel_t old_clr = get_pixel(y, x);
/* Only proceed if colours differ. */
if(new_clr != old_clr)
r_floodfill(y, x, new_clr, old_clr);
}
To use this, simply call floodfill() passing the coordinates of the starting point for the fill (y and x) and the fill colour (new_clr).
Malcolm McLean <[email protected]> writes:
The convetional wisdom is the opposite, But here, conventional wisdom
fails. Because heaps are unlimited whilst stacks are not.
Malcolm McLean <[email protected]> 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'.
Michael S <[email protected]> writes:
On Tue, 19 Mar 2024 21:40:22 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
On Mon, 18 Mar 2024 22:42:14 -0700
Tim Rentsch <[email protected]> wrote:
Tim Rentsch <[email protected]> writes:
[...]
Here is the refinement that uses a resizing rather than
fixed-size buffer.
[code]
This variant is significantly slower than Malcolm's.
2x slower for solid rectangle, 6x slower for snake shape.
Slower with some shapes, faster in others.
In my small test suit I found no cases where this specific code is measurably faster than code of Malcolm.
My test cases include pixel fields of 32k by 32k, with for
example filling the entire field starting at the center point.
Kind of a stress test but it turned up some interesting results.
I did find one case in which they are approximately equal. I call
it "slalom shape" and it's more or less designed to be the worst
case for algorithms that are trying to speed themselves by take
advantage of straight lines.
The slalom shape is generated by following code:
[code]
Thanks, I may try that.
In any case
the code was written for clarity of presentation, with
no attention paid to low-level performance.
Yes, your code is easy to understand. Could have been easier
still if persistent indices had more meaningful names.
I have a different view on that question. However I take your
point.
In other post I showed optimized variant of your algorithm: -
4-neighbors loop unrolled. Majority of the speed up come not from unrolling itself, but from specialization of in-rectangle check
enabled by unroll.
- Todo queue implemented as circular buffer.
- Initial size of queue increased.
This optimized variant is more competitive with 'line-grabby'
algorithms in filling solid shapes and faster than them in
'slalom' case.
Yes, unrolling is an obvious improvement. I deliberately chose a
simple (and non-optimized) method to make it easier to see how it
works. Simple optimizations are left as an exercise for the
reader. :)
Generally, I like your algorithm.
It was surprising for me that queue can work better than stack, my intuition suggested otherwise, but facts are facts.
Using a stack is like a depth-first search, and a queue is like a breadth-first search. For a pixel field of size N x N, doing a
depth-first search can lead to memory usage of order N**2,
whereas a breadth-first search has a "frontier" at most O(N).
Another way to think of it is that breadth-first gets rid of
visited nodes as fast as it can, but depth-first keeps them
around for a long time when everything is reachable from anywhere
(as will be the case in large simple reasons).
Michael S <[email protected]> writes:
On Tue, 19 Mar 2024 11:57:53 +0000
Malcolm McLean <[email protected]> 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.
On Wed, 20 Mar 2024 10:01:10 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
Generally, I like your algorithm.
It was surprising for me that queue can work better than stack, my
intuition suggested otherwise, but facts are facts.
Using a stack is like a depth-first search, and a queue is like a
breadth-first search. For a pixel field of size N x N, doing a
depth-first search can lead to memory usage of order N**2,
whereas a breadth-first search has a "frontier" at most O(N).
Another way to think of it is that breadth-first gets rid of
visited nodes as fast as it can, but depth-first keeps them
around for a long time when everything is reachable from anywhere
(as will be the case in large simple reasons).
For my test cases the FIFO depth of your algorithm never exceeds min(width,height)*2+2. I wonder if existence of this or similar
limit can be proven theoretically.
On Wed, 20 Mar 2024 07:27:38 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
On Tue, 19 Mar 2024 11:57:53 +0000
Malcolm McLean <[email protected]> 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.
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, [...]
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
[...]
[email protected] (Scott Lurndal) writes:
Malcolm McLean <[email protected]> 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.
Michael S <[email protected]> writes:
On Wed, 20 Mar 2024 10:01:10 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
[...]
Generally, I like your algorithm.
It was surprising for me that queue can work better than stack, my
intuition suggested otherwise, but facts are facts.
Using a stack is like a depth-first search, and a queue is like a
breadth-first search. For a pixel field of size N x N, doing a
depth-first search can lead to memory usage of order N**2,
whereas a breadth-first search has a "frontier" at most O(N).
Another way to think of it is that breadth-first gets rid of
visited nodes as fast as it can, but depth-first keeps them
around for a long time when everything is reachable from anywhere
(as will be the case in large simple reasons).
For my test cases the FIFO depth of your algorithm never exceeds min(width,height)*2+2. I wonder if existence of this or similar
limit can be proven theoretically.
I believe it is possible to prove the strict FIFO algorithm is
O(N) for an N x N pixel field, but I haven't tried to do so in
any rigorous way, nor do I know what the constant is. It does
seem to be larger than 2.
As for finding a worst case, try this (expressed in pseudo code):
let pc = { width/2, height/2 }
// assume pixel field 'field' starts out as all zeroes
color 8 "legs" with the value '1' as follows:
leg from { 1, pc.y-1 } to { pc.x -1, pc.y-1 }
leg from { 1, pc.y+1 } to { pc.x -1, pc.y+1 }
leg from { px.x + 1, pc.y-1 } to { width-2, pc.y-1 }
leg from { px.x + 1, pc.y+1 } to { width-2, pc.y+1 }
leg from { px.x - 1, 1 } to { px.x -1, pc.y-1 }
leg from { px.x + 1, 1 } to { px.x +1, pc.y-1 }
leg from { px.x - 1, pc.y+1 } to { px.x -1, height/2 }
leg from { px.x + 1, pc.y+1 } to { px.x +1, height/2 }
So the pixel field should look like this (with longer legs for a
bigger pixel field), with '-' being 0 and '*' being 1:
+-----------------------+
| - - - - - - - - - - - |
| - - - - * - * - - - - |
| - - - - * - * - - - - |
| - - - - * - * - - - - |
| - * * * * - * * * * - |
| - - - - - - - - - - - |
| - * * * * - * * * * - |
| - - - - * - * - - - - |
| - - - - * - * - - - - |
| - - - - * - * - - - - |
| - - - - - - - - - - - |
+-----------------------+
Now start coloring at the center point with a new value
of 2.
Michael S <[email protected]> writes:
On Wed, 20 Mar 2024 07:27:38 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
On Tue, 19 Mar 2024 11:57:53 +0000
Malcolm McLean <[email protected]> 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.
Certainly "abysmally slow" is subjective, but working in a large
pixel field, filling the whole field starting at the center,
Malcolm's code runs slower than my unoptimized code by a factor of
10 (and a tad slower than that compared to my optimized code).
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.
In the case of Malcolm's code I think it's the algorithm, because
it doesn't scale linearly. Malcolm's code runs faster than mine
for small colorings, but slows down dramatically as the image
being colored gets bigger.
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, [...]
Yes, my unoptimized algorithm was designed to use as little
memory as possible. The optimized version traded space for
speed: it runs a little bit faster but incurs a non-trivial cost
in terms of space used. I think it's still not too bad, an upper
bound of a small multiple of N for an NxN pixel field.
But even by that metric, the difference between different
implementations of the same algorithm is often much bigger than
difference between algorithms.
If I am not mistaken the original naive recursive algorithm has a
space cost that is O( N**2 ) for an NxN pixel field. The big-O
difference swamps everything else, just like the big-O difference
in runtime does for that metric.
For example, solid 200x200 image with starting point in the corner
[...]
On small pixel fields almost any algorithm is probably not too
bad. These days any serious algorithm should scale well up
to at least 4K by 4K, and tested up to at least 16K x 16K.
Tricks that make some things faster for small images sometimes
fall on their face when confronted with a larger image. My code
isn't likely to win many races on small images, but on large
images I expect it will always be competitive even if it doesn't
finish in first place.
On Sun, 24 Mar 2024 13:26:16 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
On Wed, 20 Mar 2024 07:27:38 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
On Tue, 19 Mar 2024 11:57:53 +0000
Malcolm McLean <[email protected]> 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.
Certainly "abysmally slow" is subjective, but working in a large
pixel field, filling the whole field starting at the center,
Malcolm's code runs slower than my unoptimized code by a factor of
10 (and a tad slower than that compared to my optimized code).
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.
In the case of Malcolm's code I think it's the algorithm, because
it doesn't scale linearly. Malcolm's code runs faster than mine
for small colorings, but slows down dramatically as the image
being colored gets bigger.
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, [...]
Yes, my unoptimized algorithm was designed to use as little
memory as possible. The optimized version traded space for
speed: it runs a little bit faster but incurs a non-trivial cost
in terms of space used. I think it's still not too bad, an upper
bound of a small multiple of N for an NxN pixel field.
But even by that metric, the difference between different
implementations of the same algorithm is often much bigger than difference between algorithms.
If I am not mistaken the original naive recursive algorithm has a
space cost that is O( N**2 ) for an NxN pixel field. The big-O
difference swamps everything else, just like the big-O difference
in runtime does for that metric.
For example, solid 200x200 image with starting point in the corner
[...]
On small pixel fields almost any algorithm is probably not too
bad. These days any serious algorithm should scale well up
to at least 4K by 4K, and tested up to at least 16K x 16K.
Tricks that make some things faster for small images sometimes
fall on their face when confronted with a larger image. My code
isn't likely to win many races on small images, but on large
images I expect it will always be competitive even if it doesn't
finish in first place.
You are right. At 1920*1080 except for few special patterns, your
code is faster than Malcolm's by factor of 1.5x to 1.8. Same for 4K. Auxiliary memory arrays of Malcolm are still quite small at these
image sizes, but speed suffers.
I wonder if it is a problem of algorithm or of implementation. Since I
still didn't figure out his idea, I can't improve his implementation
in order check it.
One thing that I were not expecting at this bigger pictures, is good performance of simple recursive algorithm. Of course, not of original
form of it, but of variation with explicit stack.
For many shapes it has quite large memory footprint and despite that
it is not slow. Probably the stack has very good locality of
reference.
Here is the code:
<snip>
[..various fill algorithms and how they scale..]
One thing that I were not expecting at this bigger pictures, is good performance of simple recursive algorithm. Of course, not of original
form of it, but of variation with explicit stack.
For many shapes it has quite large memory footprint and despite that it
is not slow. Probably the stack has very good locality of reference.
[algorithm]
Tim Rentsch <[email protected]> writes:
[email protected] (Scott Lurndal) writes:
Malcolm McLean <[email protected]> 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 ..]
Michael S <[email protected]> writes:
[..various fill algorithms and how they scale..]
One thing that I were not expecting at this bigger pictures, is good performance of simple recursive algorithm. Of course, not of
original form of it, but of variation with explicit stack.
For many shapes it has quite large memory footprint and despite
that it is not slow. Probably the stack has very good locality of reference.
[algorithm]
You are indeed a very clever fellow. I'm impressed.
Intrigued by your idea, I wrote something along the same lines,
only shorter and (at least for me) a little easier to grok.
If someone is interested I can post it.
I see you have also done a revised algorithm based on the same
idea, but more elaborate (to save on runtime footprint?).
Still working on formulating a response to that one...
On Thu, 28 Mar 2024 23:04:36 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
[..various fill algorithms and how they scale..]
One thing that I were not expecting at this bigger pictures, is
good performance of simple recursive algorithm. Of course, not of
original form of it, but of variation with explicit stack. For
many shapes it has quite large memory footprint and despite that
it is not slow. Probably the stack has very good locality of
reference.
[algorithm]
You are indeed a very clever fellow. I'm impressed.
Yes, the use of switch is clever :(
It more resemble computed GO TO in old FORTRAN or indirect jumps
in asm than idiomatic C switch. But it is a legal* C.
Intrigued by your idea, I wrote something along the same lines,
only shorter and (at least for me) a little easier to grok.
If someone is interested I can post it.
If non-trivially different, why not?
I see you have also done a revised algorithm based on the same
idea, but more elaborate (to save on runtime footprint?).
Still working on formulating a response to that one...
The original purpose of enhancement was to amortize non-trivial
and probably not very fast call stack emulation logic over more
than one pixel. 2x2 just happens to be the biggest block that
still has very simple in-block recoloring logic. ~4x reduction in
the size of auxiliary memory is just a pleasant side effect.
Exactly the same 4x reduction in memory size could have been
achieved with single-pixel variant by using packed array for 2-bit
state (==trace back) stack elements. But it would be the same or
slower than original while the enhanced variant is robustly faster
than original.
After implementing the first enhancement I paid attention that at
4K size the timing (per pixel) for few of my test cases is
significantly worse than at smaller images. So, I added another
enhancement aiming to minimize cache trashing effects by never
looking back at immediate parent of current block. The info about
location of the parent nicely fitted into remaining 2 bits of
stack octet.
The most robust code that I found so far that performs well both
with small pictures and with large and huge, is a variation on the
same theme of explicit stack, may be, more properly called trace
back. It operates on 2x2 squares instead of individual pixels.
The worst case auxiliary memory footprint of this variant is rather
big, up to picture_size/4 bytes. The code is *not* simple, but
complexity appears to be necessary for robust performance with
various shapes and sizes.
[...]
I did program in FORTRAN briefly but don't remember ever using
computed GO TO. And yes, I found that missing semicolon and put it
back. Is there some reason you don't always use -pedantic? I
pretty much always do.
An alternate idea is to use a 64-bit integer for 32 "top of stack"
elements, or up to 32 I should say, and a stack with 64-bit values.
Just an idea, it may not turn out to be useful.
The few measurements I have done don't show a big difference in
performance between the two methods. But I admit I wasn't paying
close attention, and like I said only a few patterns of filling were exercised.
After implementing the first enhancement I paid attention that at
4K size the timing (per pixel) for few of my test cases is
significantly worse than at smaller images. So, I added another enhancement aiming to minimize cache trashing effects by never
looking back at immediate parent of current block. The info about
location of the parent nicely fitted into remaining 2 bits of
stack octet.
The idea of not going back to the originator (what you call the
parent) is something I developed independently before looking at
your latest code (and mostly I still haven't). Seems like a good
idea.
Two further comments.
One, the new code is a lot more complicated than the previous
code. I'm not sure the performance gain is worth the cost
in complexity. What kind of speed improvements do you see,
in terms of percent?
Two, and more important, the new algorithm still uses O(NxN) memory
for an N by N pixel field. We really would like to get that down to
O(N) memory (and of course run just as fast). Have you looked into
how that might be done?
On Thu, 28 Mar 2024 23:04:36 -0700
Tim Rentsch <[email protected]> wrote:
Intrigued by your idea, I wrote something along the same lines,
only shorter and (at least for me) a little easier to grok.
If someone is interested I can post it.
If non-trivially different, why not?
Michael S <[email protected]> writes:
[...]
The most robust code that I found so far that performs well both
with small pictures and with large and huge, is a variation on the
same theme of explicit stack, may be, more properly called trace
back. It operates on 2x2 squares instead of individual pixels.
The worst case auxiliary memory footprint of this variant is rather
big, up to picture_size/4 bytes. The code is *not* simple, but
complexity appears to be necessary for robust performance with
various shapes and sizes.
[...]
I took a cursory look just now, after reading your other later
posting. I think I have a general sense, especially in conjunction
with the explanatory comments.
I'm still hoping to find a method that is both fast and has
good memory use, which is to say O(N) for an NxN pixel field.
Something that would help is to have a library of test cases,
by which I mean patterns to be colored, so that a set of
methods could be tried, and timed, over all the patterns in
the library. Do you have something like that? So far all
my testing has been ad hoc.
Incidentally, it looks like your code assumes X varies more rapidly
than Y, so a "by row" order, whereas my code assumes Y varies more
rapidly than X, a "by column" order.
The difference doesn't matter
as long as the pixel field is square and the test cases either are
symmetric about the X == Y axis or duplicate a non-symmetric pattern
about the X == Y axis. I would like to be able to run comparisons
between different methods and get usable results without having
to jump around because of different orientations. I'm not sure
how to accommodate that.
On Fri, 29 Mar 2024 23:58:26 -0700
Tim Rentsch <[email protected]> wrote:
One, the new code is a lot more complicated than the previous
code. I'm not sure the performance gain is worth the cost
in complexity. What kind of speed improvements do you see,
in terms of percent?
On my 11 y.o. and not top-of-the-line even then home PC for 4K
image (3840 x 2160) with cross-in-cross shape that I took from one of
your previous post, it is 2.43 times faster.
I don't remember how it compares on more modern systems. Anyway, right
now I have no test systems more modern than 3 y.o. Zen3.
Michael S <[email protected]> writes:
On Wed, 20 Mar 2024 10:01:10 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
[...]
Generally, I like your algorithm.
It was surprising for me that queue can work better than stack, my
intuition suggested otherwise, but facts are facts.
Using a stack is like a depth-first search, and a queue is like a
breadth-first search. For a pixel field of size N x N, doing a
depth-first search can lead to memory usage of order N**2,
whereas a breadth-first search has a "frontier" at most O(N).
Another way to think of it is that breadth-first gets rid of
visited nodes as fast as it can, but depth-first keeps them
around for a long time when everything is reachable from anywhere
(as will be the case in large simple reasons).
For my test cases the FIFO depth of your algorithm never exceeds min(width,height)*2+2. I wonder if existence of this or similar
limit can be proven theoretically.
I believe it is possible to prove the strict FIFO algorithm is
O(N) for an N x N pixel field, but I haven't tried to do so in
any rigorous way, nor do I know what the constant is. It does
seem to be larger than 2.
On Sat, 30 Mar 2024 00:54:19 -0700[...]
Tim Rentsch <[email protected]> wrote:
Something that would help is to have a library of test cases,
by which I mean patterns to be colored, so that a set of
methods could be tried, and timed, over all the patterns in
the library. Do you have something like that? So far all
my testing has been ad hoc.
I am not 100% sure about the meaning of 'ad hoc', but I'd guess
that mine are ad hoc too. Below are shapes that I use apart from
solid rectangles. I run them at 5 sizes: 25x19, 200x200,
1280x720, 1920x1080, 3840x2160. That is certainly not enough for
correction tests, but feel that it is sufficient for speed tests.
[code]
On Fri, 29 Mar 2024 23:58:26 -0700
Tim Rentsch <[email protected]> wrote:
I did program in FORTRAN briefly but don't remember ever using
computed GO TO. And yes, I found that missing semicolon and put it
back. Is there some reason you don't always use -pedantic? I
pretty much always do.
Just a habit.
In "real" work, as opposed to hobby, I use gcc almost exclusively for
small embedded targets and quite often with 3-rd party libraries in
source form. In such environment rising warnings level above -Wall
would be counterproductive, because it would be hard to see relevant
warning behind walls of false alarms.
May be, for hobby, where I have full control on everything, switching
to -Wpedantic is not a bad idea.
The idea of not going back to the originator (what you call the
parent) is something I developed independently before looking at
your latest code (and mostly I still haven't). Seems like a good
idea.
I call it a principle of Lot's wife.
That is yet another reason to not grow blocks above 2x2.
For bigger blocks it does not apply.
On Sat, 30 Mar 2024 21:15:06 +0300
Michael S <[email protected]> wrote:
On Fri, 29 Mar 2024 23:58:26 -0700
Tim Rentsch <[email protected]> wrote:
One, the new code is a lot more complicated than the previous
code. I'm not sure the performance gain is worth the cost
in complexity. What kind of speed improvements do you see,
in terms of percent?
On my 11 y.o. and not top-of-the-line even then home PC for 4K
image (3840 x 2160) with cross-in-cross shape that I took from one of
your previous post, it is 2.43 times faster.
I don't remember how it compares on more modern systems. Anyway, right
now I have no test systems more modern than 3 y.o. Zen3.
I tested on newer hardware - Intel Coffee Lake (Xeon-E 2176G) and AMD
Zen3 (EPYC 7543P).
Here I no longer see significant drop in speed of the 1x1 variant at 4K
size, but I still see that more complicated variant provides nice speed
up. Up to 1.56x on Coffee Lake and up to 3x on Zen3.
On Sun, 24 Mar 2024 10:24:45 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
On Wed, 20 Mar 2024 10:01:10 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
[...]
Generally, I like your algorithm.
It was surprising for me that queue can work better than stack, my
intuition suggested otherwise, but facts are facts.
Using a stack is like a depth-first search, and a queue is like a
breadth-first search. For a pixel field of size N x N, doing a
depth-first search can lead to memory usage of order N**2,
whereas a breadth-first search has a "frontier" at most O(N).
Another way to think of it is that breadth-first gets rid of
visited nodes as fast as it can, but depth-first keeps them
around for a long time when everything is reachable from anywhere
(as will be the case in large simple reasons).
For my test cases the FIFO depth of your algorithm never exceeds
min(width,height)*2+2. I wonder if existence of this or similar
limit can be proven theoretically.
I believe it is possible to prove the strict FIFO algorithm is
O(N) for an N x N pixel field, but I haven't tried to do so in
any rigorous way, nor do I know what the constant is. It does
seem to be larger than 2.
It seems that in worst case the strict FIFO algorithm is the same as
the rest of them, i.e. O(NN) where NN is the number of re-colored
points. Below is an example of the shape for which I measured memory consumption for 3840x2160 image almost exactly 4x as much as for
1920x1080.
[code to generate fractal tree pattern]
Michael S <[email protected]> writes:
On Sun, 24 Mar 2024 10:24:45 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
On Wed, 20 Mar 2024 10:01:10 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
[...]
Generally, I like your algorithm.
It was surprising for me that queue can work better than stack,
my intuition suggested otherwise, but facts are facts.
Using a stack is like a depth-first search, and a queue is like a
breadth-first search. For a pixel field of size N x N, doing a
depth-first search can lead to memory usage of order N**2,
whereas a breadth-first search has a "frontier" at most O(N).
Another way to think of it is that breadth-first gets rid of
visited nodes as fast as it can, but depth-first keeps them
around for a long time when everything is reachable from anywhere
(as will be the case in large simple reasons).
For my test cases the FIFO depth of your algorithm never exceeds
min(width,height)*2+2. I wonder if existence of this or similar
limit can be proven theoretically.
I believe it is possible to prove the strict FIFO algorithm is
O(N) for an N x N pixel field, but I haven't tried to do so in
any rigorous way, nor do I know what the constant is. It does
seem to be larger than 2.
Before I do anything else I should correct a bug in my earlier
FIFO algorithm. The initialization of the variable jx should
read
Index const jx = used*3 < open ? k : j+open/3 &m;
rather than what it used to. (The type may have changed but that
is incidental; what matters is the value of the initializing
expression.) I don't know what I was thinking when I wrote the
previous version, it's just completely wrong.
It seems that in worst case the strict FIFO algorithm is the same as
the rest of them, i.e. O(NN) where NN is the number of re-colored
points. Below is an example of the shape for which I measured
memory consumption for 3840x2160 image almost exactly 4x as much as
for 1920x1080.
I agree, the empirical evidence here and in my own tests is quite
compelling.
That said, the constant factor for the FIFO algorithm is lower
than the stack-based algorithms, even taking into account the
difference in sizes for queue and stack elements. Moreover cases
where FIFO algorithms are O( NxN ) are unusual and sparse,
whereas the stack-based algorithms tend to use a lot of memory
in lots of common and routine cases. On the average FIFO
algorithms typically use a lot less memory (or so I conjecture).
[code to generate fractal tree pattern]
Thank you for this. I incorporated it into my set of test
patterns more or less as soon as it was posted.
Now that I have taken some time to play around with different
algorithms and have been more systematic in doing speed
comparisons between different algorithms, on different patterns,
and with a good range of sizes, I have some general thoughts
to offer.
Stack-based methods tend to do well on long skinny patterns and
tend to do not as well on fatter patterns such as circles or
squares. The fractal pattern is ideal for a stack-based method.
Conversely, patterns that are mostly solid shapes don't fare as
well under stack-based methods, at least not the ones that have
been posted in this thread, and also they tend to use more memory
in those cases.
I've been playing around with a more elaborate, mostly FIFO
method, in hopes of getting something that offers the best
of both worlds. The results so far are encouraging, but a
fair amount of tuning has been necessary (and perhaps more
still is), and comparisons have been done on just the one
test server I have available. So I don't know how well it
would hold up on other hardware, including especially more
recent hardware. Under these circumstances I feel it is
premature to post actual code, especially since the code
is still in flux.
This topic has been more interesting that I was expecting, and
also more challenging.
I have a strong rule against writing
functions more than about 60 lines long. For the problem of
writing an acceptably quick flood-fill algorithm, I think it would
at the very least be a lot of work to write code to do that while
still observing a limit on function length of even 100 lines, let
alone 60.
On Wed, 10 Apr 2024 19:47:11 -0700
Tim Rentsch <[email protected]> wrote:
Before I do anything else I should correct a bug in my earlier
FIFO algorithm. The initialization of the variable jx should
read
Index const jx = used*3 < open ? k : j+open/3 &m;
I lost track, sorry. I can not find your code that contains line
similar to this.
Can you point to specific post?
On Wed, 10 Apr 2024 19:47:11 -0700
Tim Rentsch <[email protected]> wrote:
Stack-based methods tend to do well on long skinny patterns and
tend to do not as well on fatter patterns such as circles or
squares. The fractal pattern is ideal for a stack-based method.
Conversely, patterns that are mostly solid shapes don't fare as
well under stack-based methods, at least not the ones that have
been posted in this thread, and also they tend to use more memory
in those cases.
Indeed, with solid shapes it uses more memory. But at least in my
tests on my hardware with this sort of shapes it is easily faster
than anything else. The difference vs the best of the rest is
especially big at 4K images on AMD Zen3 based hardware, but even on
Intel Skylake which generally serves as equalizer between different algorithms, the speed advantage of 2x2 stack is significant.
On Wed, 10 Apr 2024 19:47:11 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
It seems that in worst case the strict FIFO algorithm is the same
as the rest of them, i.e. O(NN) where NN is the number of
re-colored points. Below is an example of the shape for which I
measured memory consumption for 3840x2160 image almost exactly 4x
as much as for 1920x1080.
I agree, the empirical evidence here and in my own tests is quite
compelling.
BTW, I am no longer agree with myself about "the rest of them".
By now, I know at least one method that is O(W*log(H)). It is even
quite fast for majority of my test shapes. Unfortunately, [in its
current form] it is abysmally slow (100x) for minority of tests.
[In it's current form] it has other disadvantages as well like
consuming non-trivial amount of memory when handling small spot in the
big image. But that can be improved. I am less sure that worst-case
speed can be improved enough to make it generally acceptable.
I think, I said enough for you to figure out a general principle of
this algorithm. I don't want to post code here before I try few improvements.
On Wed, 10 Apr 2024 19:47:11 -0700
Tim Rentsch <[email protected]> wrote:
This topic has been more interesting that I was expecting, and
also more challenging.
That's not the first time in my practice where problems with
simple formulation begots interesting challenges.
Didn't Donald Knuth wrote 300 or 400 pages about sorting and
still ended up quite far away from exhausting the topic?
On Wed, 10 Apr 2024 19:47:11 -0700
Tim Rentsch <[email protected]> wrote:
I have a strong rule against writing
functions more than about 60 lines long. For the problem of
writing an acceptably quick flood-fill algorithm, I think it would
at the very least be a lot of work to write code to do that while
still observing a limit on function length of even 100 lines, let
alone 60.
So why not break it down to smaller pieces ?
Michael S <[email protected]> writes:
On Wed, 10 Apr 2024 19:47:11 -0700
Tim Rentsch <[email protected]> wrote:
Stack-based methods tend to do well on long skinny patterns and
tend to do not as well on fatter patterns such as circles or
squares. The fractal pattern is ideal for a stack-based method.
Conversely, patterns that are mostly solid shapes don't fare as
well under stack-based methods, at least not the ones that have
been posted in this thread, and also they tend to use more memory
in those cases.
Indeed, with solid shapes it uses more memory. But at least in my
tests on my hardware with this sort of shapes it is easily faster
than anything else. The difference vs the best of the rest is
especially big at 4K images on AMD Zen3 based hardware, but even on
Intel Skylake which generally serves as equalizer between different algorithms, the speed advantage of 2x2 stack is significant.
This comment makes me wonder if I should post my timing results.
Maybe I will (and including an appropriate disclaimer).
I do timings over these sizes:
25 x 19
19 x 25
200 x 200
1280 x 760
760 x 1280
1920 x 1080
1080 x 1920
3840 x 2160
2160 x 3840
4096 x 4096
38400 x 21600
21600 x 38400
32767 x 32767
32768 x 32768
with these patterns:
fractal
slalom
rotated slalom
horizontal snake and vertical snake
cross in cross
donut aka ellipse with hole
entire field starting from center
If you have other patterns to suggest that would be great,
I can try to incorporate them (especially if there is
code to generate the pattern).
Patterns are allowed to include a nominal start point,
otherwise I can make an arbitrary choice and assign one.
On Wed, 10 Apr 2024 19:47:11 -0700
Tim Rentsch <[email protected]> wrote:
Stack-based methods tend to do well on long skinny patterns and
tend to do not as well on fatter patterns such as circles or
squares. The fractal pattern is ideal for a stack-based method.
Conversely, patterns that are mostly solid shapes don't fare as
well under stack-based methods, at least not the ones that have
been posted in this thread, and also they tend to use more memory
in those cases.
Indeed, with solid shapes it uses more memory. But at least in my
tests on my hardware with this sort of shapes it is easily faster
than anything else. The difference vs the best of the rest is
especially big at 4K images on AMD Zen3 based hardware, but even
on Intel Skylake which generally serves as equalizer between
different algorithms, the speed advantage of 2x2 stack is
significant.
On Thu, 11 Apr 2024 22:09:51 -0700[...]
Tim Rentsch <[email protected]> wrote:
I do timings over these sizes:
25 x 19
19 x 25
200 x 200
1280 x 760
760 x 1280
1920 x 1080
1080 x 1920
3840 x 2160
2160 x 3840
4096 x 4096
38400 x 21600
21600 x 38400
32767 x 32767
32768 x 32768
I didn't went that far up (ended at 4K)
and I only test landscape sizes. May be, I'd add portrait option
to see anisotropic behaviors.
with these patterns:
fractal
slalom
rotated slalom
horizontal snake and vertical snake
cross in cross
donut aka ellipse with hole
entire field starting from center
If you have other patterns to suggest that would be great,
I can try to incorporate them (especially if there is
code to generate the pattern).
Patterns are allowed to include a nominal start point,
otherwise I can make an arbitrary choice and assign one.
My suit is about the same with following exceptions:
1. I didn't add donut yet
2. + 3 greeds with cell size 2, 3 and 4
3. + fractal tree
4. + entire field starting from corner
It seems, neither of us tests the cases in which linear dimensions
of the shape are much smaller than those of the field.
static void make_grid(
unsigned char *image,
int width, int height,
unsigned char background_c,
unsigned char pen_c, int cell_sz)
{
for (int y = 0; y < height; ++y) {
unsigned char* p = &image[y*width];
if (y % cell_sz == 0) {
memset(p, pen_c, width);
} else {
for (int x = 0; x < width; ++x)
p[x] = x % cell_sz ? background_c : pen_c;
}
}
}
Michael S <[email protected]> writes:
On Wed, 10 Apr 2024 19:47:11 -0700
Tim Rentsch <[email protected]> wrote:
Stack-based methods tend to do well on long skinny patterns and
tend to do not as well on fatter patterns such as circles or
squares. The fractal pattern is ideal for a stack-based method.
Conversely, patterns that are mostly solid shapes don't fare as
well under stack-based methods, at least not the ones that have
been posted in this thread, and also they tend to use more memory
in those cases.
Indeed, with solid shapes it uses more memory. But at least in my
tests on my hardware with this sort of shapes it is easily faster
than anything else. The difference vs the best of the rest is
especially big at 4K images on AMD Zen3 based hardware, but even
on Intel Skylake which generally serves as equalizer between
different algorithms, the speed advantage of 2x2 stack is
significant.
I'm curious to know how your 2x2 algorithm compares to my
second (longer) stack-based algorithm when run on the Zen3.
On my test hardware they are roughly comparable, depending
on size and pattern. My curiosity includes the fatter
patterns as well as the long skinny ones.
On Fri, 12 Apr 2024 11:59:25 -0700
Tim Rentsch <[email protected]> wrote:
I'm curious to know how your 2x2 algorithm compares to my
second (longer) stack-based algorithm when run on the Zen3.
On my test hardware they are roughly comparable, depending
on size and pattern. My curiosity includes the fatter
patterns as well as the long skinny ones.
This particular server turned off right now.
Hopefully, next Monday I would be able to test on it.
It would help if in the mean time you point me to specific post
with code.
Michael S <[email protected]> writes:
On Fri, 12 Apr 2024 11:59:25 -0700
Tim Rentsch <[email protected]> wrote:
I'm curious to know how your 2x2 algorithm compares to my
second (longer) stack-based algorithm when run on the Zen3.
On my test hardware they are roughly comparable, depending
on size and pattern. My curiosity includes the fatter
patterns as well as the long skinny ones.
This particular server turned off right now.
Hopefully, next Monday I would be able to test on it.
It would help if in the mean time you point me to specific post
with code.
Does this help? Message-ID: <[email protected]>
Michael S <[email protected]> writes:
On Wed, 10 Apr 2024 19:47:11 -0700
Tim Rentsch <[email protected]> wrote:
Stack-based methods tend to do well on long skinny patterns and
tend to do not as well on fatter patterns such as circles or
squares. The fractal pattern is ideal for a stack-based method.
Conversely, patterns that are mostly solid shapes don't fare as
well under stack-based methods, at least not the ones that have
been posted in this thread, and also they tend to use more memory
in those cases.
Indeed, with solid shapes it uses more memory. But at least in my
tests on my hardware with this sort of shapes it is easily faster
than anything else. The difference vs the best of the rest is
especially big at 4K images on AMD Zen3 based hardware, but even
on Intel Skylake which generally serves as equalizer between
different algorithms, the speed advantage of 2x2 stack is
significant.
I'm curious to know how your 2x2 algorithm compares to my
second (longer) stack-based algorithm when run on the Zen3.
On my test hardware they are roughly comparable, depending
on size and pattern. My curiosity includes the fatter
patterns as well as the long skinny ones.
Finally found the time for speed measurements. [...]
Michael S <[email protected]> writes:
[...]
Finally found the time for speed measurements. [...]
I got these. Thank you.
The format used didn't make it easy to do any automated
processing. I was able to get around that, although it
would have been nicer if that had been easier.
The results you got are radically different than my own,
to the point where I wonder if there is something else
going on.
Considering that, since I now have no way of doing any
useful measuring, it seems there is little point in any
further development or investigation on my part. It's
been fun, even if ultimately inconclusive.
On Wed, 17 Apr 2024 10:47:25 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
[...]
Finally found the time for speed measurements. [...]
I got these. Thank you.
The format used didn't make it easy to do any automated
processing. I was able to get around that, although it
would have been nicer if that had been easier.
The results you got are radically different than my own,
to the point where I wonder if there is something else
going on.
What are your absolute result?
Are they much faster, much slower or similar to mine?
Also it would help if you find out characteristics of your
test hardware.
Considering that, since I now have no way of doing any
useful measuring, it seems there is little point in any
further development or investigation on my part. It's
been fun, even if ultimately inconclusive.
I am still interested in combination of speed that does
not suck with O(N) worst-case memory footprint.
I already have couple of variants of the former,
but so
far they are all unreasonably slow - ~5 times slower than
the best.
Michael S <[email protected]> writes:
On Wed, 17 Apr 2024 10:47:25 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
[...]
Finally found the time for speed measurements. [...]
I got these. Thank you.
The format used didn't make it easy to do any automated
processing. I was able to get around that, although it
would have been nicer if that had been easier.
The results you got are radically different than my own,
to the point where I wonder if there is something else
going on.
What are your absolute result?
Are they much faster, much slower or similar to mine?
Also it would help if you find out characteristics of your
test hardware.
I think trying to look at those wouldn't tell me anything
helpful. Too many unknowns. And still no way to test or
measure any changes to the various algorithms.
Considering that, since I now have no way of doing any
useful measuring, it seems there is little point in any
further development or investigation on my part. It's
been fun, even if ultimately inconclusive.
I am still interested in combination of speed that does
not suck with O(N) worst-case memory footprint.
I already have couple of variants of the former,
Did you mean you some algorithms whose worst case memory
behavior is strictly less than O( total number of pixels )?
I think it would be helpful to adopt a standard terminology
where the pixel field is of size M x N, otherwise I'm not
sure what O(N) refers to.
but so
far they are all unreasonably slow - ~5 times slower than
the best.
I'm no longer working on the problem but I'm interested to
hear what you come up with.
On Fri, 19 Apr 2024 14:59:20 -0700
Tim Rentsch <[email protected]> wrote:
Did you mean you some algorithms whose worst case memory
behavior is strictly less than O( total number of pixels )?
I think it would be helpful to adopt a standard terminology
where the pixel field is of size M x N, otherwise I'm not
sure what O(N) refers to.
No, I mean O(max(M,N)) plus possibly some logarithmic component that
loses significance when images grow bigger.
More so, if bounding rectangle of the shape is A x B then I'd like
memory requirements to be O(max(A,B)), but so far it does not appear
to be possible, or at least not possible without significant
complications and further slowdown. So, as an intermediate goal I am
willing to accept that allocation would be O(max(M,N)). but amount of
touched memory is O(max(A,B)).
but so
far they are all unreasonably slow - ~5 times slower than
the best.
I'm no longer working on the problem but I'm interested to
hear what you come up with.
old_color, s->new_color, src_todo, exp_todo, 1);if (!ret)
old_color, s->new_color, src_todo, exp_todo, 1);if (!ret)
On Sat, 20 Apr 2024 21:10:23 +0300
Michael S <[email protected]> wrote:
On Fri, 19 Apr 2024 14:59:20 -0700
Tim Rentsch <[email protected]> wrote:
Did you mean you some algorithms whose worst case memory
behavior is strictly less than O( total number of pixels )?
I think it would be helpful to adopt a standard terminology
where the pixel field is of size M x N, otherwise I'm not
sure what O(N) refers to.
No, I mean O(max(M,N)) plus possibly some logarithmic component that
loses significance when images grow bigger.
More so, if bounding rectangle of the shape is A x B then I'd like
memory requirements to be O(max(A,B)), but so far it does not appear
to be possible, or at least not possible without significant
complications and further slowdown. So, as an intermediate goal I am willing to accept that allocation would be O(max(M,N)). but amount
of touched memory is O(max(A,B)).
but so
far they are all unreasonably slow - ~5 times slower than
the best.
I'm no longer working on the problem but I'm interested to
hear what you come up with.
Here is what I had in mind.
I tried to optimize as little as I can in order to make it as simple
as I can. Unfortunately, I am not particularly good at it, so, code
still contains few unnecessary "tricks" that make understanding a
little harder.
The code uses VLA and recursion for the same purpose of making it less tricky.
If desired, the memory footprint could be easily reduced by factor of
8 through use of packed bit arrays instead arrays of _Bool.
Even in this relatively crude form for majority of shapes this code is blazingly fast.
Unfortunately, in the worst case (both 'slalom' shapes) an execution
time is O(max(A,B)**3) which makes it unfit as general-purpose
routine. At the moment I don't see a solution for this problem.
Overall, it's probably a dead end.
On Fri, 19 Apr 2024 14:59:20 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
On Wed, 17 Apr 2024 10:47:25 -0700
Tim Rentsch <[email protected]> wrote:
Michael S <[email protected]> writes:
[...]
Finally found the time for speed measurements. [...]
I got these. Thank you.
The format used didn't make it easy to do any automated
processing. I was able to get around that, although it
would have been nicer if that had been easier.
The results you got are radically different than my own,
to the point where I wonder if there is something else
going on.
What are your absolute result?
Are they much faster, much slower or similar to mine?
Also it would help if you find out characteristics of your
test hardware.
I think trying to look at those wouldn't tell me anything
helpful. Too many unknowns. And still no way to test or
measure any changes to the various algorithms.
Frankly, I don't understand.
If you have troubles with testing on shared hardware then you can
always test on the hardware that you own and has full control.
Even if it is a little old, the trends tend to be the same. At
least I clearly see the same trends on my almost 12 y.o. home PC
and on relatively modern EPYC3.
On Fri, 3 May 2024 18:33:05 +0300
Michael S <[email protected]> wrote:
On Thu, 25 Apr 2024 17:56:06 +0300
Michael S <[email protected]> wrote:
A solution (sort of) is in line with the famous quite of David
Wheeler
- to turn todo lists from bit maps into arrays of
abscesses-or-ordinates of contact points.
The cost is a memory footprint - 4x bigger than the previous
version, 32 times bigger than above-mentioned "packed" variant of
the previous version. But in BigO sense it's the same.
In my tests it reduced the worst case time from O(max(A,B)**3) to O(A*B*log(max(A,B)). Which is non-ideal, but probably acceptable,
because the bad cases should be very rare in practice.
The real trouble is different - I don't know if my "worst case" is
really the worst.
The code below is for presentation of algorithm in both clear and
compact manner, with emphasis on symmetry between x and y
directions. It is not optimal in any sense and can be made
no-trivially faster both by algorithm enhancements an by
specialization of critical loops.
Following code improves on ideas from the previous post.
Unlike the previous one, it is purely iterative, with no recursion.
The algorithm is simpler and access storage in more compact manner,
i.e. all accessed memory area starts from beginning and grows
according to need. Previous attempt did not have this property.
It's still longer and less simple than I would like.
On Thu, 25 Apr 2024 17:56:06 +0300
Michael S <[email protected]> wrote:
A solution (sort of) is in line with the famous quite of David Wheeler
- to turn todo lists from bit maps into arrays of
abscesses-or-ordinates of contact points.
The cost is a memory footprint - 4x bigger than the previous version,
32 times bigger than above-mentioned "packed" variant of the previous version. But in BigO sense it's the same.
In my tests it reduced the worst case time from O(max(A,B)**3) to O(A*B*log(max(A,B)). Which is non-ideal, but probably acceptable,
because the bad cases should be very rare in practice.
The real trouble is different - I don't know if my "worst case" is
really the worst.
The code below is for presentation of algorithm in both clear and
compact manner, with emphasis on symmetry between x and y directions.
It is not optimal in any sense and can be made no-trivially faster
both by algorithm enhancements an by specialization of critical loops.
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 715 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 152:20:44 |
| Calls: | 12,091 |
| Calls today: | 4 |
| Files: | 15,000 |
| Messages: | 6,517,636 |