Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #383647 > unrolled thread
| Started by | fir <fir@grunge.pl> |
|---|---|
| First post | 2024-03-16 05:11 +0100 |
| Last post | 2024-05-15 09:57 -0700 |
| Articles | 20 on this page of 167 — 16 participants |
Back to article view | Back to comp.lang.c
filling area by color atack safety fir <fir@grunge.pl> - 2024-03-16 05:11 +0100
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-16 11:33 +0000
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-16 13:55 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-16 14:41 +0000
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-17 10:42 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 03:00 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-18 14:23 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 14:13 -0700
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-19 16:05 +0100
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-19 17:16 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-19 17:33 +0000
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-19 23:07 +0100
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-20 09:29 +0100
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 03:04 -0700
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-16 14:45 +0000
Re: filling area by color atack safety scott@slp53.sl.home (Scott Lurndal) - 2024-03-16 18:21 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-16 20:02 +0000
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-16 13:29 -0700
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-17 13:19 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-18 14:40 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-19 23:23 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 15:32 +0200
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-17 11:25 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-17 12:37 +0000
Re: filling area by color atack safety Kaz Kylheku <433-929-6894@kylheku.com> - 2024-03-17 17:11 +0000
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-23 00:21 +0000
Re: filling area by color atack safety scott@slp53.sl.home (Scott Lurndal) - 2024-03-23 14:43 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-23 11:48 -0700
Re: filling area by color atack safety scott@slp53.sl.home (Scott Lurndal) - 2024-03-24 20:48 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-28 22:51 -0700
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-16 15:40 +0100
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-16 15:09 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-17 14:56 +0000
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 17:42 +0200
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 18:25 +0200
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 19:39 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 11:36 -0700
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-18 18:51 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 23:10 -0700
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-19 12:06 +0000
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 00:03 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 01:17 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 00:30 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 12:06 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 13:44 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 15:44 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 15:17 +0100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 02:15 +0100
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-17 17:45 +0100
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-17 18:28 +0000
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-18 07:58 +0100
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-18 09:26 +0000
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-18 17:28 +0100
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-18 17:25 +0000
Re: filling area by color atack safety scott@slp53.sl.home (Scott Lurndal) - 2024-03-18 17:42 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-18 18:50 +0000
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-19 11:41 +0100
Re: filling area by color atack safety Richard Harnden <richard.nospam@gmail.invalid> - 2024-03-19 12:19 +0000
Re: filling area by color atack safety Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-03-18 11:10 -0700
Keith-world (Was: filling area by color atack safety) gazelle@shell.xmission.com (Kenny McCormack) - 2024-03-18 22:42 +0000
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-19 12:31 +0100
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-18 16:18 -0700
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-19 11:32 +0100
Re: filling area by color atack safety scott@slp53.sl.home (Scott Lurndal) - 2024-03-16 18:25 +0000
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-17 10:31 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-17 12:28 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-17 12:49 +0000
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-17 17:59 +0100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-19 23:52 +0100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 01:36 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 14:46 +0200
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-17 12:54 +0000
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 15:15 +0200
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-17 13:23 +0000
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 15:37 +0200
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-17 18:05 +0100
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-17 14:10 +0000
Re: filling area by color atack safety Spiros Bousbouras <spibou@gmail.com> - 2024-03-17 16:58 +0000
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-17 22:14 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-17 22:21 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 02:30 -0700
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-18 11:08 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 22:54 -0700
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-19 11:41 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-19 21:19 -0700
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 01:13 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 10:41 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 15:20 +0100
Re: filling area by color atack safety Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2024-03-17 14:27 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-17 15:13 +0000
Re: filling area by color atack safety Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> - 2024-03-19 10:57 +1100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 01:26 +0100
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-16 19:13 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-16 20:23 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-16 20:29 +0000
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 01:48 +0100
Re: filling area by color atack safety Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> - 2024-03-22 13:04 +1100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-22 17:55 +0300
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-22 18:31 +0300
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-23 11:06 +0100
Re: filling area by color atack safety Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> - 2024-03-17 18:03 +1100
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 13:09 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 22:42 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-19 13:18 +0200
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-19 11:57 +0000
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-19 15:49 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-19 21:43 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 10:56 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-20 06:51 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-19 19:18 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 09:27 +0100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 09:39 +0100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 09:51 +0100
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-20 07:27 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-24 20:27 +0300
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-24 13:26 -0700
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-24 14:26 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-25 01:28 +0300
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-26 17:52 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-30 00:54 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-30 21:26 +0300
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-09 01:00 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-28 23:04 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-29 15:21 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-29 23:58 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-30 21:15 +0300
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-31 10:54 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-09 02:32 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-09 01:55 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-30 11:59 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-20 10:26 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-21 15:36 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-21 09:47 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-19 21:40 -0700
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-19 21:43 -0700
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-19 21:48 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 11:54 +0200
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-20 10:23 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-20 12:06 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-20 07:52 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-20 10:01 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-24 19:33 +0300
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-24 10:24 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-25 01:04 +0300
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-05 17:30 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-10 19:47 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-11 15:20 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 21:06 -0700
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 21:55 -0700
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 22:09 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-12 11:13 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-13 08:30 -0700
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 22:38 -0700
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 22:43 -0700
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-12 11:59 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-13 20:26 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-13 10:54 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-13 23:11 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-17 10:47 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-17 22:41 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-19 14:59 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-20 21:10 +0300
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-25 17:56 +0300
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-05-03 18:33 +0300
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-06-05 17:45 +0300
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-06-05 17:59 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-05-15 09:57 -0700
Page 7 of 9 — ← Prev page 1 2 3 4 5 6 [7] 8 9 Next page →
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-30 21:26 +0300 |
| Message-ID | <20240330212657.000066e1@yahoo.com> |
| In reply to | #384095 |
On Sat, 30 Mar 2024 00:54:19 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Michael S <already5chosen@yahoo.com> 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.
>
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.
static void make_standing_snake(
unsigned char *image,
int width, int height,
unsigned char background_c,
unsigned char pen_c)
{
for (int y = 0; y < height; ++y) {
unsigned char* p = &image[y*width];
if (y % 2 == 0) {
memset(p, pen_c, width);
} else {
memset(p, background_c, width);
if (y % 4 == 1)
p[width-1] = pen_c;
else
p[0] = pen_c;
}
}
}
static void make_prostrate_snake(
unsigned char *image,
int width, int height,
unsigned char background_c,
unsigned char pen_c)
{
memset(image, background_c, sizeof(*image)*width*height);
// vertical bars
for (int y = 0; y < height; ++y)
for (int x = 0; x < width; x += 2)
image[y*width+x] = pen_c;
// connect bars at top
for (int x = 3; x < width; x += 4)
image[x] = pen_c;
// connect bars at bottom
for (int x = 1; x < width; x += 4)
image[(height-1)*width+x] = pen_c;
}
static void make_slalom(
unsigned char *image,
int width, int height,
unsigned char background_c,
unsigned char pen_c)
{
const int n_col = width/3;
const int n_row = (height-3)/4;
// top row
// P B B P P P
for (int col = 0; col < n_col; ++col) {
unsigned char c = (col & 1)==0 ? background_c : pen_c;
image[col*3] = pen_c; image[col*3+1] = c; image[col*3+2] = c;
}
for (int x = n_col*3; x < width; ++x)
image[x] = image[n_col*3-1];
// main image: consists of 3x4 blocks filled by following pattern
// P B B
// P P B
// B P B
// P P B
for (int row = 0; row < n_row; ++row) {
for (int col = 0; col < n_col; ++col) {
unsigned char* p = &image[(row*4+1)*width+col*3];
p[0] = pen_c; p[1] = background_c; p[2] = background_c; p
+= width; p[0] = pen_c; p[1] = pen_c; p[2] =
background_c; p += width; p[0] = background_c; p[1] = pen_c;
p[2] = background_c; p += width; p[0] = pen_c; p[1] = pen_c;
p[2] = background_c; p += width; }
}
// near-bottom rows
// P B B
for (int y = n_row*4+1; y < height-1; ++y) {
for (int col = 0; col < n_col; ++col) {
unsigned char* p = &image[y*width+col*3];
p[0] = pen_c; p[1] = background_c; p[2] = background_c;
}
}
// bottom row - all P
// P P P P B B
unsigned char *b_row = &image[width*(height-1)];
for (int col = 0; col < n_col; ++col) {
unsigned char c = (col & 1)==1 ? background_c : pen_c;
b_row[col*3+0] = pen_c;
b_row[col*3+1] = c;
b_row[col*3+2] = c;
}
for (int x = n_col*3; x < width; ++x)
b_row[x] = b_row[n_col*3-1];
// rightmost columns
for (int x = n_col*3; x < width; ++x) {
for (int y = 1; y < height-1; ++y)
image[y*width+x] = background_c;
}
}
static void make_slalom90(
unsigned char *image,
int width, int height,
unsigned char background_c,
unsigned char pen_c)
{
const int n_col = (width-3)/4;
const int n_row = height/3;
// leftmost column
// P
// B
// B
// P
// P
// P
for (int row = 0; row < n_row; ++row) {
unsigned char c = (row & 1)==0 ? background_c : pen_c;
image[(row*3+0)*width] = pen_c;
image[(row*3+1)*width] = c;
image[(row*3+2)*width] = c;
}
for (int y = n_row*3; y < height; ++y)
image[y*width] = image[(n_row*3-1)*width];
// main image: consists of 4x3 blocks filled by following pattern
// P P B P
// B P P P
// B B B B
for (int row = 0; row < n_row; ++row) {
for (int col = 0; col < n_col; ++col) {
unsigned char* p = &image[(row*3*width)+(col*4+1)];
p[0] = pen_c; p[1] = pen_c; p[2] = background_c;
p[3] = pen_c; p += width; p[0] = background_c; p[1] = pen_c;
p[2] = pen_c; p[3] = pen_c; p += width; p[0] = background_c;
p[1] = background_c; p[2] = background_c; p[3] = background_c; }
}
// near-rightmost column
// P
// B
// B
for (int row = 0; row < n_row; ++row) {
for (int x = n_col*4+1; x < width-1; ++x) {
unsigned char* p = &image[row*width*3+x];
p[0*width] = pen_c;
p[1*width] = background_c;
p[2*width] = background_c;
}
}
// rightmost column
// P
// P
// P
// P
// B
// B
unsigned char *r_col = &image[width-1];
for (int row = 0; row < n_row; ++row) {
unsigned char c = (row & 1)==1 ? background_c : pen_c;
r_col[(row*3+0)*width] = pen_c;
r_col[(row*3+1)*width] = c;
r_col[(row*3+2)*width] = c;
}
for (int y = n_row*3; y < height; ++y)
r_col[y*width] = r_col[(n_row*3-1)*width];
// bottom rows
for (int y = n_row*3; y < height; ++y) {
for (int x = 1; x < width-1; ++x)
image[y*width+x] = background_c;
}
}
static void make_crosss_in_cross(
unsigned char* image,
int width,
int height,
int xc,
int yc,
unsigned char background_c,
unsigned char pen_c)
{
memset(image, pen_c, width*height);
if (xc > 1 && xc+1 < width-1 && yc > 1 && yc+1 < height-1) {
memset(&image[(yc-1)*width+1], background_c, xc-1);
memset(&image[(yc+1)*width+1], background_c, xc-1);
memset(&image[(yc-1)*width+xc+1], background_c, width-xc-2);
memset(&image[(yc+1)*width+xc+1], background_c, width-xc-2);
for (int y = 1; y < yc; ++y) {
image[y*width+xc-1] = background_c;
image[y*width+xc+1] = background_c;
}
for (int y = yc+1; y < height-1; ++y) {
image[y*width+xc-1] = background_c;
image[y*width+xc+1] = background_c;
}
}
}
> 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.
It is not so much about what I assume as about what is cheaper for
CPU hardware.
> 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.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-04-09 01:00 -0700 |
| Message-ID | <867ch72cf1.fsf@linuxsc.com> |
| In reply to | #384115 |
Michael S <already5chosen@yahoo.com> writes:
> On Sat, 30 Mar 2024 00:54:19 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> 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]
I got these, thank you.
Here is a pattern generating function I wrote for my own
testing. Disclaimer: slightly changed from my original
source, hopefully any errors inadvertently introduced can
be corrected easily. Also, it uses the value 0 for the
background and the value 1 for the pattern to be colored.
#include <math.h>
#include <stddef.h>
#include <string.h>
typedef unsigned char Pixel;
extern void
ellipse_with_hole( Pixel *field, unsigned w, unsigned h ){
size_t i, j;
double wc = w/2, hc = h/2;
double a = (w > h ? wc : hc) -1;
double b = (w > h ? hc : wc) -1;
double b3 = 1+6*b/8;
double radius = b/2.5;
double cx = w > h ? wc : b3+1;
double cy = w > h ? b3+1 : hc;
double focus = sqrt( a*a - b*b );
double f1x = w > h ? wc - focus : wc;
double f1y = w > h ? hc : hc - focus;
double f2x = w > h ? wc + focus : wc;
double f2y = w > h ? hc : hc + focus;
memset( field, 0, w*h );
for( i = 0; i < w; i++ ){
for( j = 0; j < h; j++ ){
double dx = i - cx, dy = j - cy;
double r2 = radius * radius;
if( dx * dx + dy*dy <= r2 ) continue;
double dx1 = i - f1x, dy1 = j - f1y;
double dx2 = i - f2x, dy2 = j - f2y;
double sum2 = a*2;
double d1 = sqrt( dx1*dx1 + dy1*dy1 );
double d2 = sqrt( dx2*dx2 + dy2*dy2 );
if( d1 + d2 > 2*a ) continue;
field[ i+j*w ] = 1;
}}
}
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-28 23:04 -0700 |
| Message-ID | <867chlk1zf.fsf@linuxsc.com> |
| In reply to | #383978 |
Michael S <already5chosen@yahoo.com> 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...
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-29 15:21 +0200 |
| Message-ID | <20240329162141.00006c81@yahoo.com> |
| In reply to | #384081 |
On Thu, 28 Mar 2024 23:04:36 -0700 Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > Michael S <already5chosen@yahoo.com> 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 versions I posted are not exactly legal C; they are illegal C non-rejected by gcc. But they can be trivially made into legal C by adding semicolon after one of the case labels.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-29 23:58 -0700 |
| Message-ID | <86y1a0i4tp.fsf@linuxsc.com> |
| In reply to | #384085 |
Michael S <already5chosen@yahoo.com> writes: > On Thu, 28 Mar 2024 23:04:36 -0700 > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > >> Michael S <already5chosen@yahoo.com> 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 :( In my view the cleverness is how "recursion" is accomplished by a means of a combination of using a stack to store a "return address" and restoring state by undoing a change rather than storing the old value. Using a switch() is just a detail (and to my way of thinking how the switch() is done here obscures the basic idea and makes the code harder to understand, but never mind that). > It more resemble computed GO TO in old FORTRAN or indirect jumps > in asm than idiomatic C switch. But it is a legal* C. 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. >> 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 hope to soon but am unable to right now (and maybe for a week or so due to circumstances beyond my control). For sure the code is different; whether it is non-trivially different I leave for others to judge. >> 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. 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?
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-30 21:15 +0300 |
| Message-ID | <20240330211506.00000b86@yahoo.com> |
| In reply to | #384094 |
On Fri, 29 Mar 2024 23:58:26 -0700 Tim Rentsch <tr.17687@z991.linuxsc.com> 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. > > 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. > That's just a detail of how to do pack/unpack with minimal overhead. It does not change the principle that 'packed' version would be less memory hungry but on modern PC with GBs of RAM it will not be faster than original. Memory footprint can directly affect speed when access patterns have poor locality or when the rate of access exceeds 10-20 GB/s. In our case locality of stack access is very good and the rate of stack access, even on ultra fast processor, is less than 1 GB/s. > 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. > 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. > 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? > 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. > 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? Using this particular principle of not saving (x,y) in auxiliary storage, I don't believe that it is possible to have a footprint smaller than O(W*H).
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-31 10:54 +0200 |
| Message-ID | <20240331115438.00003f3c@yahoo.com> |
| In reply to | #384114 |
On Sat, 30 Mar 2024 21:15:06 +0300 Michael S <already5chosen@yahoo.com> wrote: > On Fri, 29 Mar 2024 23:58:26 -0700 > Tim Rentsch <tr.17687@z991.linuxsc.com> 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.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-04-09 02:32 -0700 |
| Message-ID | <86y19m285s.fsf@linuxsc.com> |
| In reply to | #384129 |
Michael S <already5chosen@yahoo.com> writes: > On Sat, 30 Mar 2024 21:15:06 +0300 > Michael S <already5chosen@yahoo.com> wrote: > >> On Fri, 29 Mar 2024 23:58:26 -0700 >> Tim Rentsch <tr.17687@z991.linuxsc.com> 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 my test system the numbers are closer and also more evenly balanced: ratios range from about 0.70 to about 1.40, roughly evenly split with the 2x2 version somewhat better. There was one outlier at approximately 1.48. More precisely, the ratios have an average of 1.06 (which means the 1x1 version is about 6 percent slower on average), with a standard deviation of 0.21.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-04-09 01:55 -0700 |
| Message-ID | <8634ru3ofo.fsf@linuxsc.com> |
| In reply to | #384114 |
Michael S <already5chosen@yahoo.com> writes:
> On Fri, 29 Mar 2024 23:58:26 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> 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.
My experience with third party libraries is that sometimes they use
extensions, probably mostly gcc-isms. Not much to be done in that
case. Of course turning on -pedantic could be done selectively.
It might be worth an experiment of turning off -Wall while turning
on -pedantic to see how big or how little the problem is.
>> 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.
Here is an updated version of my "stacking" code. On my test
system (and I don't even know exactly what CPU it has, probably
about 5 years old) this code runs about 30% faster than your 2x2
version, averaged across all patterns and all sizes above the
smallest ones (25x19 and 19x25).
#include <assert.h>
#include <stdlib.h>
typedef unsigned char UC, Color;
typedef size_t Index, Count;
typedef struct { Index x, y; } Point;
extern Count
stack_plus( UC *field, Index w, Index h, Point p0, Color old, Color new ){
Index px = ( assert( p0.x < w ), p0.x );
Index py = ( assert( p0.y < h ), p0.y );
Index x0 = 0;
Index x = px;
Index xm = w-1;
UC *y0 = field;
UC *y = y0 + py*w;
UC *ym = y0 + h*w - w;
UC *s0 = malloc( 8 * sizeof *s0 );
UC *s = s0;
UC *sn = s0 ? s0+8 : s0;
Count r = 0;
if( s0 ) goto START_FOUR;
while( s != s0 ){
switch( *--s & 15 ){
case 0: goto UNDO_START_LEFT;
case 1: goto UNDO_START_RIGHT;
case 2: goto UNDO_START_UP;
case 3: goto UNDO_START_DOWN;
case 4: goto UNDO_LEFT_DOWN;
case 5: goto UNDO_LEFT_LEFT;
case 6: goto UNDO_LEFT_UP;
case 7: goto UNDO_UP_LEFT;
case 8: goto UNDO_UP_UP;
case 9: goto UNDO_UP_RIGHT;
case 10: goto UNDO_RIGHT_UP;
case 11: goto UNDO_RIGHT_RIGHT;
case 12: goto UNDO_RIGHT_DOWN;
case 13: goto UNDO_DOWN_RIGHT;
case 14: goto UNDO_DOWN_DOWN;
case 15: goto UNDO_DOWN_LEFT;
}
START_FOUR:
if( y[x] != old ) continue;
y[x] = new; r++;
if( x < xm && y[x+1] == old ){
x += 1, *s++ = 0; goto START_LEFT; UNDO_START_LEFT:
x -= 1;
}
if( x > x0 && y[x-1] == old ){
x -= 1, *s++ = 1; goto START_RIGHT; UNDO_START_RIGHT:
x += 1;
}
if( y < ym && x[y+w] == old ){
y += w, *s++ = 2; goto START_UP; UNDO_START_UP:
y -= w;
}
if( y > y0 && x[y-w] == old ){
y -= w, *s++ = 3; goto START_DOWN; UNDO_START_DOWN:
y += w;
}
continue;
START_LEFT:
y[x] = new; r++;
if( s == sn ){
Index s_offset = s - s0;
Index n = (sn-s0+1) *3 /2;
UC *new_s0 = realloc( s0, n * sizeof *new_s0 );
if( ! new_s0 ) break;
s0 = new_s0, s = s0 + s_offset, sn = s0 + n;
}
if( x < xm && y[x+1] == old ){
x += 1, *s++ = 5; goto START_LEFT; UNDO_LEFT_LEFT:
x -= 1;
}
if( y > y0 && x[y-w] == old ){
y -= w, *s++ = 4; goto START_DOWN; UNDO_LEFT_DOWN:
y += w;
}
if( y < ym && x[y+w] == old ){
y += w, *s++ = 6; goto START_UP; UNDO_LEFT_UP:
y -= w;
}
continue;
START_UP:
y[x] = new; r++;
if( s == sn ){
Index s_offset = s - s0;
Index n = (sn-s0+1) *3 /2;
UC *new_s0 = realloc( s0, n * sizeof *new_s0 );
if( ! new_s0 ) break;
s0 = new_s0, s = s0 + s_offset, sn = s0 + n;
}
if( x < xm && y[x+1] == old ){
x += 1, *s++ = 7; goto START_LEFT; UNDO_UP_LEFT:
x -= 1;
}
if( x > x0 && y[x-1] == old ){
x -= 1, *s++ = 9; goto START_RIGHT; UNDO_UP_RIGHT:
x += 1;
}
if( y < ym && x[y+w] == old ){
y += w, *s++ = 8; goto START_UP; UNDO_UP_UP:
y -= w;
}
continue;
START_RIGHT:
y[x] = new; r++;
if( s == sn ){
Index s_offset = s - s0;
Index n = (sn-s0+1) *3 /2;
UC *new_s0 = realloc( s0, n * sizeof *new_s0 );
if( ! new_s0 ) break;
s0 = new_s0, s = s0 + s_offset, sn = s0 + n;
}
if( x > x0 && y[x-1] == old ){
x -= 1, *s++ = 11; goto START_RIGHT; UNDO_RIGHT_RIGHT:
x += 1;
}
if( y < ym && x[y+w] == old ){
y += w, *s++ = 10; goto START_UP; UNDO_RIGHT_UP:
y -= w;
}
if( y > y0 && x[y-w] == old ){
y -= w, *s++ = 12; goto START_DOWN; UNDO_RIGHT_DOWN:
y += w;
}
continue;
START_DOWN:
y[x] = new; r++;
if( s == sn ){
Index s_offset = s - s0;
Index n = (sn-s0+1) *3 /2;
UC *new_s0 = realloc( s0, n * sizeof *new_s0 );
if( ! new_s0 ) break;
s0 = new_s0, s = s0 + s_offset, sn = s0 + n;
}
if( x > x0 && y[x-1] == old ){
x -= 1, *s++ = 13; goto START_RIGHT; UNDO_DOWN_RIGHT:
x += 1;
}
if( x < xm && y[x+1] == old ){
x += 1, *s++ = 15; goto START_LEFT; UNDO_DOWN_LEFT:
x -= 1;
}
if( y > y0 && x[y-w] == old ){
y -= w, *s++ = 14; goto START_DOWN; UNDO_DOWN_DOWN:
y += w;
}
continue;
}
return free( s0 ), r;
}
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-30 11:59 -0700 |
| Message-ID | <86cyrbim14.fsf@linuxsc.com> |
| In reply to | #384085 |
Michael S <already5chosen@yahoo.com> writes:
> On Thu, 28 Mar 2024 23:04:36 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> 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?
Here is the code:
void
stack_fill( UI w0, UI h0, UC pixels[], Point p0, UC old, UC new ){
U64 w = ( assert( w0 > 0 ), w0 );
U64 h = ( assert( h0 > 0 ), h0 );
U64 px = ( assert( p0.x < w ), p0.x );
U64 py = ( assert( p0.y < h ), p0.y );
UC *x0 = ( assert( pixels ), pixels );
UC *x = x0 + px*h;
UC *xm = x0 + h*w - h;
U64 y0 = 0;
U64 y = py;
U64 ym = h-1;
UC *s0 = malloc( sizeof *s0 );
UC *s = s0;
UC *sn = s0 ? s0+1 : s0;
if( s0 && x[y] == old ) do {
x[y] = new;
if( s == sn ){
U64 s_offset = s - s0;
U64 n = (sn-s0+1) *3 /2;
UC *new_s0 = realloc( s0, n * sizeof *new_s0 );
if( ! new_s0 ) break;
s0 = new_s0, s = s0 + s_offset, sn = s0 + n;
}
if( y < ym && x[y+1] == old ){
y += 1, *s++ = 2; continue; UNDO_UP:
y -= 1;
}
if( y > y0 && x[y-1] == old ){
y -= 1, *s++ = 3; continue; UNDO_DOWN:
y += 1;
}
if( x < xm && y[x+h] == old ){
x += h, *s++ = 0; continue; UNDO_LEFT:
x -= h;
}
if( x > x0 && y[x-h] == old ){
x -= h, *s++ = 1; continue; UNDO_RIGHT:
x += h;
}
if( s == s0 ) break;
switch( *--s & 3 ){
case 0: goto UNDO_LEFT;
case 1: goto UNDO_RIGHT;
case 2: goto UNDO_UP;
case 3: goto UNDO_DOWN;
}
} while( 1 );
free( s0 );
}
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-20 10:26 -0700 |
| Message-ID | <86v85glspp.fsf@linuxsc.com> |
| In reply to | #383747 |
Michael S <already5chosen@yahoo.com> 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.
#include <stdlib.h>
typedef unsigned char UC;
typedef unsigned UI;
typedef unsigned U32;
typedef unsigned long long U64;
typedef struct { UI x, y; } Point;
void
faster_fill( UI w0, UI h0, UC pixels[], Point p0, UC old, UC new ){
U64 const w = w0;
U64 const h = h0;
U64 const xm = w-1;
U64 const ym = h-1;
U64 j = 0;
U64 k = 0;
U64 n = 1u << 10;
U64 m = n-1;
U32 *todo = malloc( n * sizeof *todo );
U64 x = p0.x;
U64 y = p0.y;
if( !todo || x >= w || y >= h || pixels[ x*h+y ] != old ) return;
todo[ k++ ] = x<<16 | y;
while( j != k ){
U64 used = j < k ? k-j : k+n-j;
U64 open = n - used;
if( open < used / 16 ){
U64 new_n = n*2;
U64 new_m = new_n-1;
U64 new_j = j < k ? j : j+n;
U32 *t = realloc( todo, new_n * sizeof *t );
if( ! t ) break;
if( j != new_j ) memcpy( t+new_j, t+j, (n-j) * sizeof *t );
todo = t, n = new_n, m = new_m, j = new_j, open = n-used;
}
U64 const jx = used <= 3*open ? k : j+open/3 &m;
while( j != jx ){
UI p = todo[j]; j = j+1 &m;
x = p >> 16, y = p & 0xFFFF;
if( x > 0 && pixels[ x*h-h + y ] == old ){
todo[k] = x-1<<16 | y, k = k+1&m, pixels[ x*h-h +y ] = new;
}
if( y > 0 && pixels[ x*h + y-1 ] == old ){
todo[k] = x<<16 | y-1, k = k+1&m, pixels[ x*h +y-1 ] = new;
}
if( x < xm && pixels[ x*h+h + y ] == old ){
todo[k] = x+1<<16 | y, k = k+1&m, pixels[ x*h+h +y ] = new;
}
if( y < ym && pixels[ x*h + y+1 ] == old ){
todo[k] = x<<16 | y+1, k = k+1&m, pixels[ x*h +y+1 ] = new;
}
}
}
free( todo );
}
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-21 15:36 +0200 |
| Message-ID | <20240321153645.00002fdc@yahoo.com> |
| In reply to | #383805 |
On Wed, 20 Mar 2024 10:26:58 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Michael S <already5chosen@yahoo.com> 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).
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-21 09:47 -0700 |
| Message-ID | <86msqrlegc.fsf@linuxsc.com> |
| In reply to | #383832 |
Michael S <already5chosen@yahoo.com> writes:
> On Wed, 20 Mar 2024 10:26:58 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> 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!
That I did, that I did. :)
I can do this kind of stuff when I need to. Usually I don't need
to.
> 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.
Bitwise '&' is simply faster than '%'. Also, bitwise '&' works
on unsigned types in the event that there is wraparound, but '%'
probably doesn't.
> 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.
Yes, it is a bit dirty. In practice pixel fields almost never get
above 16 bits in each direction, and the code is easy enough to
change (by putting two 32-bit quantities into a 64-bit type) if
it becomes necessary to accommodate an enormous pixel field.
> 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.
Taking those tests out of the inner loop helps when there is big
frontier set, because the tests don't have to be done as often.
When the frontier set is small, as we would expect for long
skinny shapes, doing that doesn't help as much (and of course
other overhead may make it worse in such cases).
> 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 played around with a "non-local" (in your terminology) version
of my most recently posted code, and discovered some things.
First the non-local version is somewhat faster on some shapes,
but noticeably slower on others. The non-local version is more
sensitive to which starting point is chosen. In a way it looks
similar to what happens with compression algorithms - some cases
get better, others get decidedly worse. I didn't do a lot of
experiments in an effort to determine what the range or relative
proportions of the different behaviors are.
After thinking about it a bit, it seems to me that a local-only
method is "more queue-like" and a non-local method is "more
stack-like". Using a pure queue plods along very predictably,
never getting much better or much worse. Being more stack-like
sometimes gets a speedup, but sometimes stumbles into the pit of
despair, which in the worse case needs a lot of memory and does
more memory shuffling. So for a general algorithm I'd opt for a
local-only method. Later on it might be good to use a more
tailored algorithm for special cases, if we can identify which
cases are special in a way that isn't too expensive.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-19 21:40 -0700 |
| Message-ID | <86o7b9ms7d.fsf@linuxsc.com> |
| In reply to | #383737 |
Michael S <already5chosen@yahoo.com> writes:
> On Mon, 18 Mar 2024 22:42:14 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>> [...]
>>
>> Here is the refinement that uses a resizing rather than
>> fixed-size buffer.
>>
>>
>> typedef unsigned char Color;
>> typedef unsigned int UI;
>> typedef struct { UI x, y; } Point;
>> typedef unsigned int Index;
>>
>> static _Bool change_it( UI w, UI h, Color [w][h], Point, Color,
>> Color );
>>
>> void
>> fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old, Color
>> new ){ static const Point deltas[4] = { {1,0}, {0,1}, {-1,0},
>> {0,-1}, }; UI k = 0;
>> UI n = 17;
>> Point *todo = malloc( n * sizeof *todo );
>>
>> if( todo && change_it( w, h, pixels, p0, old, new ) )
>> todo[k++] = p0;
>>
>> while( k > 0 ){
>> Index j = n-k;
>> memmove( todo + j, todo, k * sizeof *todo );
>> k = 0;
>>
>> while( j < n ){
>> Point p = todo[ j++ ];
>> for( Index i = 0; i < 4; i++ ){
>> Point q = { p.x + deltas[i].x, p.y + deltas[i].y };
>> if( ! change_it( w, h, pixels, q, old, new ) )
>> continue; todo[ k++ ] = q;
>> }
>>
>> if( j-k < 3 ){
>> Index new_n = n+n/4;
>> Index new_j = new_n - (n-j);
>> Point *t = realloc( todo, new_n * sizeof *t );
>> if( !t ){ k = 0; break; }
>> memmove( t + new_j, t + j, (n-j) * sizeof *t );
>> todo = t, n = new_n, j = new_j;
>> }
>> }
>> }
>>
>> free( todo );
>> }
>>
>> _Bool
>> change_it( UI w, UI h, Color pixels[w][h], Point p, Color old, Color
>> new ){ if( p.x >= w || p.y >= h || pixels[p.x][p.y] != old )
>> return 0; return pixels[p.x][p.y] = new, 1;
>> }
>
> This variant is significantly slower than Malcolm's.
> 2x slower for solid rectangle, 6x slower for snake shape.
Slower with some shapes, faster in others. In any case
the code was written for clarity of presentation, with
no attention paid to low-level performance.
> Is it the same algorithm?
Sorry, the same algorithm as what? The same as Malcolm's?
Definitely not. The same as my other posting that does
not do dynamic reallocation? Yes in the sense that if the
allocated array is large enough to begin with then no
reallocations are needed.
> Besides, I don't think that use of VLA in library code is a good idea.
> VLA is optional in latest C standards. And incompatible with C++.
The code uses a variably modified type, not a variable length
array. Again, the choice is for clarity of presentation. If
someone wants to get rid of the variably modified types, it's
very easy to do, literally a five minute task. Anyway the
interface is poorly designed to start with, there are bigger
problems than just whether a variably modified type is used.
(I chose the interface I did to approximate the interface
used in Malcolm's code.)
If someone wants to use the functionality from C++, it's
easy enough to write a C wrapper function to do that.
IMO C++ has diverged sufficiently from C so that there
is little to be gained by trying to make code interoperable
between the two languages.
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2024-03-19 21:43 -0700 |
| Message-ID | <utdpie$1afd4$1@dont-email.me> |
| In reply to | #383763 |
On 3/19/2024 9:40 PM, Tim Rentsch wrote: > Michael S <already5chosen@yahoo.com> writes: [...] We should take a shape, and use it as a unit test. Perhaps a fractal: https://i.ibb.co/Xpq2trH/ct-p1.png
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2024-03-19 21:48 -0700 |
| Message-ID | <utdprn$1afd4$3@dont-email.me> |
| In reply to | #383765 |
On 3/19/2024 9:43 PM, Chris M. Thomasson wrote: > On 3/19/2024 9:40 PM, Tim Rentsch wrote: >> Michael S <already5chosen@yahoo.com> writes: > [...] > > We should take a shape, and use it as a unit test. Perhaps a fractal: > > https://i.ibb.co/Xpq2trH/ct-p1.png > fun with shaders: Think of scaling back an escaping point wrt escape time fractals, for a couple of iterations: https://i.ibb.co/Xpq2trH/ct-p1.png https://i.ibb.co/cLxjV5W/image.png I have a shader for it, mutating and existing one by Inigo Quilez - iq/2013 , hyper smart! on and on... :^) https://www.shadertoy.com/view/XtscDl Flood fill it... ;^)
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-20 11:54 +0200 |
| Message-ID | <20240320115416.00001ab5@yahoo.com> |
| In reply to | #383763 |
On Tue, 19 Mar 2024 21:40:22 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Michael S <already5chosen@yahoo.com> writes:
>
> > On Mon, 18 Mar 2024 22:42:14 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >
> >> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> >>
> >> [...]
> >>
> >> Here is the refinement that uses a resizing rather than
> >> fixed-size buffer.
> >>
> >>
> >> 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 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:
static
void make_slalom(
unsigned char *image,
int width, int height,
unsigned char background_c,
unsigned char pen_c)
{
const int n_col = width/3;
const int n_row = (height-3)/4;
// top row
// P B B P P P
for (int col = 0; col < n_col; ++col) {
unsigned char c = (col & 1)==0 ? background_c : pen_c;
image[col*3] = pen_c; image[col*3+1] = c; image[col*3+2] = c;
}
// main image: consists of 3x4 blocks filled by following pattern
// P B B
// P P B
// B P B
// P P B
for (int row = 0; row < n_row; ++row) {
for (int col = 0; col < n_col; ++col) {
unsigned char* p = &image[(row*4+1)*width+col*3];
p[0] = pen_c; p[1] = background_c; p[2] = background_c;
p += width;
p[0] = pen_c; p[1] = pen_c; p[2] = background_c;
p += width;
p[0] = background_c; p[1] = pen_c; p[2] = background_c;
p += width;
p[0] = pen_c; p[1] = pen_c; p[2] = background_c;
}
}
// near-bottom rows
// P B B
for (int y = n_row*4+1; y < height-1; ++y) {
for (int col = 0; col < n_col; ++col) {
unsigned char* p = &image[y*width+col*3];
p[0] = pen_c; p[1] = background_c; p[2] = background_c;
}
}
// bottom row - all P
memset(&image[(height-1)*width], pen_c, width);
// rightmost columns
for (int x = n_col*3; x < width; ++x) {
for (int y = 0; y < height-1; ++y)
image[y*width+x] = background_c;
}
}
> 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.
> > Is it the same algorithm?
>
> Sorry, the same algorithm as what? The same as Malcolm's?
Yes, that what I meant.
Still didn't find guts to try to understand what Malcolm's code is
doing.
> 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.
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, 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.)
>
That's true.
The biggest problem of Malcolm's interface is that logical width of the
image is the same as physical width (a.k.a. line pitch, in LAPACK
it is called the first dimension). These parameters should be separate.
> 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.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2024-03-20 10:23 +0000 |
| Message-ID | <87jzlxi4lq.fsf@bsb.me.uk> |
| In reply to | #383773 |
Michael S <already5chosen@yahoo.com> writes: > On Tue, 19 Mar 2024 21:40:22 -0700 > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >> Michael S <already5chosen@yahoo.com> writes: ... >> >> Tim Rentsch <tr.17687@z991.linuxsc.com> 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. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2024-03-20 12:06 +0000 |
| Message-ID | <utejgj$1fm67$1@dont-email.me> |
| In reply to | #383775 |
On 20/03/2024 10:23, Ben Bacarisse wrote: > Michael S <already5chosen@yahoo.com> writes: > >> On Tue, 19 Mar 2024 21:40:22 -0700 >> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>> Michael S <already5chosen@yahoo.com> writes: > ... >>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> 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. > VMT = variabley modified type. -- Check out Basic Algorithms and my other books: https://www.lulu.com/spotlight/bgy1mm
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-20 07:52 -0700 |
| Message-ID | <864jd1lzvn.fsf@linuxsc.com> |
| In reply to | #383775 |
Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> Michael S <already5chosen@yahoo.com> writes:
>
>> On Tue, 19 Mar 2024 21:40:22 -0700
>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>
>>> Michael S <already5chosen@yahoo.com> writes:
>
> ...
>
>>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> 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.
Also ordinary local variables can be declared to have a variably
modified type (the type not necessarily having been introduced
separately), often a benefit for code that is dealing with
multi-dimensional arrays.
>> 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.
C11 added a pre-defined preprocessor macro __STDC_NO_VLA__, which
implementations can define to be 1 "intended to indicate that the
implementation does not support variable length arrays or variably
modified types." It's amusing to note that an implementation can
support VLAs and VMTs but still define the macro if they are not
intended to be supported. ;)
> 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.
Agree 100%.
Someone who wants to take a stand on this issue might to consider
adding the following lines
#if __STDC_NO_VLA__
#error Substandard implementation detected
#endif
at various places around their source code.
[toc] | [prev] | [next] | [standalone]
Page 7 of 9 — ← Prev page 1 2 3 4 5 6 [7] 8 9 Next page →
Back to top | Article view | comp.lang.c
csiph-web