🚀 go-pugleaf

In article <SLEHAR.92Aug7111245@kendall.bu.edu> slehar@kendall.bu.edu (Steve Lehar) writes:
>
>I    have given much  thought to    an agonizing  trade-off in   image
>processing   loops in   c,  and have   not  come   up with a   totally
>satisfactory solution-   I wonder  whether    anyone  has  any    good
>suggestions.
>
>    yskip = 0;
>    for(y=0;y<ysize;y++){
>      for(x=0;x<xsize;x++){
>	*(data+yskip+x) = ...
>      }
>      yskip += xsize;
>    }
>
>Now this solution works o.k, and  that  is basically  what I am using.
>But the code looks very messy- maybe not  so bad in  this example, but
>when you start adding extra inner loops like for an image convolution,

The above code is close to what I am doing - if I process pixels sequentially,
I keep a pointer to the current pixel, and increment it as I go along:

cur = data;

for (y = 0; y < ysize; y++) {
  for (x = 0; x < xsize; x++, cur++) {
    cur = whatever;
  }
}

You can also do this if you wander around the image - to go to next or 
previous pixel, just increment or decrement cur, to go to the pixel below
or above, just add or subtract the width of the bitmap. Of course, when
you travel around like this, make sure you don't step out of bounds.

Michal

Original source code is omitted here.

One solution to the messy problem is to make some functions to do
the offset calculation. For example, we can PutPixel and
GetPixel() here. They should look like:

BYTE GetPixel(BYTE *ImageBuf, long RowOffset, long Col)
{
	return ImageBuf[RowOffset+Col];
}


BYTE PutPixel(BYTE *ImageBuf, long RowOffset, long Col, BYTE Value)
{
	ImageBuf[RowOffset+Col] = Value;
}

Use this two function to whereever you need to access the pixel and the
code will look nicer. The efficiency will not be too much worse than
the one you have.

Good luck.

Yecheng

In article <SLEHAR.92Aug7111245@kendall.bu.edu> slehar@kendall.bu.edu (Steve Lehar) writes:
>
>I    have given much  thought to    an agonizing  trade-off in   image
>processing   loops in   c,  and have   not  come   up with a   totally
>satisfactory solution-   I wonder  whether    anyone  has  any    good
>suggestions.

	How about this:

  /**** in main program ****/
  unsigned char **data;
	.
	.
	.
  data = (unsigned char **)calloc(xsize,sizeof(unsigned char **));
  data[0] = (unsigned char *)calloc(xsize*ysize,sizeof(unsigned char *));
  for (i=1;i<xsize;i++){
     data[i] = data[i-1] + ysize;
  }
	.
	.
	.
  subroutine(data,xsize,ysize)
  int xsize,ysize;
  unsigned char **data;
  {
    int x,y;

    for(y=0;y<ysize;y++){
      for(x=0;x<xsize;x++){
	data[x][y] = ...
      }
    }
  }

	BTW, I just typed this in.  It did not come from working
code.



-- 
	mark shattuck (mds@phy.duke.edu)

In article <SLEHAR.92Aug7111245@kendall.bu.edu> writes:
>
>I    have given much  thought to    an agonizing  trade-off in   image
>processing   loops in   c,  and have   not  come   up with a   totally
>satisfactory solution-   I wonder  whether    anyone  has  any    good
>suggestions.

[examples deleted]

>This works o.k,  but  the problem now is  that   you are performing  a
>multiplication  in  the innermost  loop  of the  program,  which slows
>things down quite a bit.  You  can fix this  by using offsets that are
>incremented  inside    the     loop- with    addition     instead   of
>multiplication...

A good optimizing compiler will correct this problem.  *If* you
have a good optimizer, the best solution is usually to write the loops
in the most straightforward manner possible.  The multiplications
can usually be written into a nice macro and the source code stays
pretty clean.  In general, let the compiler/optimizer do its work
and then see where it doesn't do well enough.

If you must microoptimize (which I must do on one of the machines I'm
working on), then try incrementing pointers.

For example, your code becomes

   unsigned char *p = data;
   for(y=0;y<ysize;y++){
      for(x=0;x<xsize;x++,p++){
         *p = ...
      }
   }

Efficient execution and pretty clean source.

Your convolution code becomes (something like)

        unsigned char *im1, *im2, *f;
        im1 = img1->data + ...;
        /**** for each pixel ****/
        for(y=hafy;y<ysize-hafy;y++){
          for(x=hafx;x<xsize-hafx;x++,im2++){
            *im2 = 0.0;
            /**** for each filter element ****/
            im1 = img1->data+ ...;
            f = filt->data + ...;
            for(yy=0;yy<fysize;yy++){
              for(xx=0;xx<fxsize;xx++,im1++,f++){
                *im2 += *im1 * *f;
              }
          }
        }

I'll leave you to figure out the correct pointer initializations
for the indexing variables that you are using, but you should get
the basic idea.  Notice the reinitialization inside the outermost
loop (the destination image) to accomodate the separate loops over 
the source image and the filter (technically, kernel).

I hope this helps.

-- 
Bryan Morse                University of North Carolina at Chapel Hill
morse@cs.unc.edu           Department of Computer Science

In article <SLEHAR.92Aug7111245@kendall.bu.edu> slehar@kendall.bu.edu (Steve Lehar) writes:

 > I    have given much  thought to    an agonizing  trade-off in   image
 > processing   loops in   c,  and have   not  come   up with a   totally
 > satisfactory solution-   I wonder  whether    anyone  has  any    good
 > suggestions.
 > 
 > [...]
 > 
 > now it is much more elegant to pass the  image size in with the image,
 > to make   the  routine more  general.  
 > 
 >   subroutine(data,xsize,ysize)
 >   int xsize,ysize;
 >   unsigned char data[ysize][xsize];  <=== PROBLEM!
 >   {
 >     int x,y;
 > 
 >     for(y=0;y<YSIZE;y++){
 > 	 for(x=0;x<XSIZE;x++){
 > 	   data[y][x] = ...
 > 	 }
 >     }
 >   }
 > 
 > The problem is that c will not allow the array data[][] to be declared
 > without   specifying  at compile-time at  LEAST  the  dimension of the
 > xsize.

In C, the best solution is to use an array of pointers. For example,

   unsigned char **ucialloc(int w, int h)
   {
   	unsigned char *base = malloc(w*h*sizeof (unsigned char));
   	unsigned char **ptr = malloc(w*sizeof (unsigned char *));
   	int i;
   	for(i=0;i<w;i++) ptr[i]=base+i*h;
   	return ptr;
   }

   void ucifree(unsigned char **ptr)
   {
   	free(ptr[0]);
   	free(ptr);
   }

The resulting object can be passed around and used like a
multidimensional array:

   void invert(unsigned char **image,int w,int h) {
	for(x=0;x<w;x++) for(y=0;y<h;y++) {
		image[x][y] = -image[x][y];
	}
   }

   void use_it(int w,int h) {
	unsigned char **foo = ucialloc(w,h);
	...
	invert(foo,w,h);
	...
   }

This works well in practice. Memory access is faster than integer
multiplication on many machines (even taking into account cache
effects), so that this tends to be faster than index computations as
well. The only disadvantage is that the compiler generally can't
optimize loops in which the indices have been reversed.  Also, you pay
a little bit of storage overhead for the extra vector, but this is
very moderate.

The other solution is to use C++, which lets you define your own array
types.

I have a library of image processing and vision functions in C, based
on the above representation, as well as the beginnings of a library of
C++ functions. I hope that I'll be able to release the C library in a
few weeks (stay tuned).

					Thomas.

From article <SLEHAR.92Aug7111245@kendall.bu.edu>, by slehar@kendall.bu.edu (Steve Lehar):
> 
> God forbid you should have to make any changes  to this  code!  I have
> tried to think of some kind of macro that would simplify things a bit,
> but I can't come up with anything  that is less  complicated than what
> you see here.  Does anyone have an elegant solution to this problem?
> 

This is what I use when I have to access the contents of an image on a 
pixel-to-pixel basis:

function (DATATYPE *data, int xsize, int ysize)
{
  int x, y;
#define PIX(a,b) ((a)+(b)*xsize)

  for (y = 0; y < ysize; y++)
    for (x = 0; x < xsize; x++)
      data[PIX(x,y)] = ...

}

this to me looks a little better than having the arithmetics explicitly 
plugged into the square brackets.  You could even use this macro:

function (DATATYPE *data, int xsize, int ysize)
{
  int x, y;
#define DATA(a,b) data[((a)+(b)*xsize)]

  for (y = 0; y < ysize; y++)
    for (x = 0; x < xsize; x++)
      DATA(x,y) = ...

}


A far as making the loop tight and fast, if you are only accessing your data
in a sequential way, the best thing to do is increment the pointer as in:


function (DATATYPE *data, int xsize, int ysize)
{
  int x, y;
  DATATYPE *dp;

  dp = data;
  for (y = 0; y < ysize; y++)
    for (x = 0; x < xsize; x++, dp++)
      *dp = ...

}

Inner loops can be written in a similar fashion.  As far as I know, this
will be as fast as you can get.

Hope this helps

Be certain that the architecture you are using will be fast with multiple
loops.  Also, on the Sun Sparcstations you will probably find that loops
which begin at the last pixel of an image and increment to 0 will perform
significantly faster than otherwise.

Just a thought,
Michael

In article <1992Aug11.151146.11849@vuse.vanderbilt.edu>, jarreau@vuse.vanderbilt.edu (Michael P. Jarreau) writes:
|>         Also, on the Sun Sparcstations you will probably find that loops
|> which begin at the last pixel of an image and increment to 0 will perform
|> significantly faster than otherwise.
   ^^^^^^^^^^^^^

Is this in fact true? Whats is the reason for it?

Thanks,

-- Siamak

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Siamak Khoubyari		   	| Internet:    khoub-s@cs.buffalo.edu
Department of Computer Science	/ CEDAR	| BITNET:      khoub-s@sunybcs.BITNET
State University of New York at Buffalo | UUCP: !uunet!cs.buffalo.edu!khoub-s
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

slehar@kendall.bu.edu (Steve Lehar) writes:

>This works o.k,  but  the problem now is  that   you are performing  a
>multiplication  in  the innermost  loop  of the  program,  which slows
>things down quite a bit.

I hope you are aware that that when you create an array, say, int
array[200][200], then when you reference array[i][j], there is an
implicit multiplication performed by the compiler to find this address.
There is no performance loss or gain by doing the multiplication
explicitly when you malloc your own array.

The solution given previously, using an array of pointers, is probably
the best speed-up.

-- 
#ifdef TRUE         | Fuzzy Fox                  fuzzy@netcom.com
#define  TRUE   0   | a.k.a. David DeSimone      an207@cleveland.freenet.edu
#define  FALSE  1   |
#endif              |         How's my posting?  Call 1-800-ALT-FLAME

In article <1992Aug10.221247.8016@cfa.harvard.edu> alberto@cfa.harvard.edu (Alberto Accomazzi) writes:

> A far as making the loop tight and fast, if you are only accessing your data
> in a sequential way, the best thing to do is increment the pointer as in:
> 
> function (DATATYPE *data, int xsize, int ysize)
> {
>   int x, y;
>   DATATYPE *dp;
> 
>   dp = data;
>   for (y = 0; y < ysize; y++)
>     for (x = 0; x < xsize; x++, dp++)
>       *dp = ...
> }
> 
> Inner loops can be written in a similar fashion.  As far as I know, this
> will be as fast as you can get.

Actually, you can get just a smidgin faster on most machines:

  dp = data;
  for (y = 0; y < ysize; y++)
    for (x = 0; x < xsize; x++)
      *dp++ = ...
}

but this is probably even less readable than the other examples
posted.


--
 Dr Adrian F. Clark                                   JANET: alien@uk.ac.essex
 INTERNET: alien%uk.ac.essex@nsfnet-relay.ac.uk          FAX: (+44) 206-872900
 BITNET: alien%uk.ac.essex@ac.uk              PHONE: (+44) 206-872432 (direct)
 Dept ESE, University of Essex, Wivenhoe Park, Colchester, Essex, C04 3SQ, UK.

alien@essex.ac.uk ("Adrian F Clark") writes:


>In article <1992Aug10.221247.8016@cfa.harvard.edu> alberto@cfa.harvard.edu (Alberto Accomazzi) writes:

>Actually, you can get just a smidgin faster on most machines:
>  dp = data;
>  for (y = 0; y < ysize; y++)
>    for (x = 0; x < xsize; x++)
>      *dp++ = ...
>}

>but this is probably even less readable than the other examples
>posted.

You really don't need a separate x counter varaiable. Use the
pointer itself for the inner loop:

  dp = data;
  for (y = 0; y < ysize; y++)
   {
     rowend = (y+1)*xsize*sizeof(int); /* or whatever size your data is */
     for ( ; (int)dp < rowend; )       /* note the obscure empty statements */
       *dp++ = ...
   }

This saves one increment instruction. It makes a difference.
Yes, I have written a program like this. No, I wouldn't like to
try to read somebody else's program written like this.

And now for the *really* compact stuff...

For greater obscurity, you could use the pointer for the outer loop, too,
and move some initialization inside the for(;;) construct, and remove the
silly type casts that weenie compilers try to make you put in there:

  for(dp=data; dp<xsize*ysize*sizeof(int);)
    {
      for(rowend = dp+xsize*sizeof(int); dp<rowend; )
        *dp++ = ...
    }

Or if you don't care which row you are on, you could just write:

  for(dp=data; dp<xsize*ysize*sizeof(int); *dp++= ...)

Or if you like to... Hey! Let go of me! I'm writing an article here!
No, I don't need a vacation. And I won't let that man in the white robe
get anywhere near me with that needl

The basic question is how to program for images with variable sizes. The 
solution presented by the author here (malloc a linear array of xsize*ysize) is
imo the best. Those numerical recipies in C readers who propose the famous 
array of pointers solution are thinking rather 2d. What if you go to 3d: an 
image of pointers? Which is of course implemented as an array of pointers to 
pointers. Good luck!
As for the author who proposed the function call in the innerloop: you must 
drink lots of coffee at work :)

The loop I most often use is:

pixel *p = beginofdata;
int i;  /* make sure this is 32 bits! */

for (i=xsize*ysize; --i>=0;) *p++ = ...;

This is the fastest on 68000Us! And also on sparcstations. Try it. (thanx to 
Gert van Antwerpen)
Make sure the optimizer is on. Else write register pixel *p and register int i;

What if you want to do something with *p++?

Of course you will only in the most exceptional of cases want to write a loop 
like in the original posting. Most filters can be written as a sequence of 2 
1-dimensional filters. One in x and one in y (which also scales nicely to 3d).
Such as maximum, minimum, uniform, gaussian filters.
But if you have to you should keep the innerloop simple. So the 
straightforward implementation:

for ysize
   for xsize
      for yfiltersize
          for xfiltersize


is hopeless. The innerloop is only a few iterations. And the work to be done 
there not really simple.

The following is a lot better:

for yfiltersize
    for xfiltersize
        for ysize
            for xsize


In that case the innerloop is the largest and simplest. Also handy if you have
a vector processing machine. Of course you need a little imaganation to 
construct the innermost part of the loop, with may include a temporary image or
two to hold intermediate results. Whereas in the most often used construct you
only need one or two ints. But memory is cheap, and my time is not. On 68000Us
and the like the speedup can be a factor of 3! On sparcUs however the speedup 
is negligable, because the cache is not well used. So the following is best:

for ysize
   for yfiltersize
      for xfiltersize
          for xsize


Ben Verwer. Below see a real program (coauthored by Henri Vrooman).



/* The rolling ball filter smooths an image by rolling a ball over the surface
of the image, (imagine grey-value as height) and tracing the contour of the 
ball as it goes */

static int ball[63*63]; /* rolling ball shape, maximum diameter 63 */

qball(inp,out,xsize,ysize,fsize)
short *inp,*out;
int xsize, ysize, fsize;
        {

        register int *q1, *q2;
        register int x,xend,v;

        int *input, *output;
        int i,j,y,b;
        int hf,len;

        char *malloc();
        double dtmp, sqrt();

        input = (int *)malloc(xsize*ysize*sizeof(int));
        output = (int *)malloc(xsize*ysize*sizeof(int));

        hf = fsize/2;

        len = xsize*ysize;
        for (j=0; j<len; j++) output[j] = input[j] = (int)inp[j];

        b = 0;
        for (j=-hf; j<=hf; j++) {
                for (i=-hf; i<=hf; i++) {

                        dtmp = .25*fsize*fsize-i*i-j*j;
                        if (dtmp < 0.0) ball[b++] = -1000; 
                        else ball[b++] = (int) sqrt(dtmp);
                }
        }

        xend = xsize-hf;

        for (y=hf; y<ysize-hf; y++) {

                b = 0;
                for (j=-hf; j<=hf; j++) {
                        for (i=-hf; i<=hf; i++) {

                                v = ball[b++];

                                q1 = input+y*xsize+hf;
                                q2 = output+y*xsize+hf+j*xsize+i;

                                for (x=0; x<xend; x++, q1++, q2++){
                                        if (*q2 < *q1+v) *q2 = *q1+v;
                                }
                        }
                }
        }


        len = xsize*ysize;
        for (j=0; j<len; j++) out[j] = output[j];

        free(output);
        free(input);

        return(0);
}

In <ben.714157437@galaxy> ben@ph.tn.tudelft.nl (Ben Verwer) writes:

>The basic question is how to program for images with variable sizes. The 
>solution presented by the author here (malloc a linear array of xsize*ysize) is
>imo the best. Those numerical recipies in C readers who propose the famous 
>array of pointers solution are thinking rather 2d. What if you go to 3d: an 
>image of pointers? Which is of course implemented as an array of pointers to 
>pointers. Good luck!

Yes, an 3d image can be implemented as an 2-d array (not image) of pointers.
And a n-d image as an (n-1)-d array of pointers. No problem! Note that the
overhead involved in space typically is sizeof( any * ), for each row.
And since row sizes typically are >> sizeof(any *), there is no big
problem.

A problem with using a linear array is present when multiplication is
slower as pointer indirection (for instance, on a sparc, or a 68000).
Accessing image pixel (x,y) will involve accessing image[y*xsize+x];
otherwise *(imageptr[y]+x) is used.
Off course you can use a pointer array, and allocate your image memory
continuous -- this will give you best of to worlds! (at the cost of
setting up your pointer array, which typically is of order columnsize,
instead of order columnsize * rowsize for the full operation. So the
overhead is rather small.)

>The loop I most often use is:

>pixel *p = beginofdata;
>int i;  /* make sure this is 32 bits! */

>for (i=xsize*ysize; --i>=0;) *p++ = ...;

>This is the fastest on 68000Us! And also on sparcstations. Try it. (thanx to 
>Gert van Antwerpen)

It is not on sparcstations (and i doubt it on 68k). Faster is:

pixel *p_end = beginofdata+sizeofdata+1;

for(p=beginofdata;p<p_end;) *p++ = ...;
(At least with /bin/cc and Sun C 1.4. gcc 2.2.1 didn't care...)

>Make sure the optimizer is on. Else write register pixel *p and register int i;
Very true! Use highest optimizer option (-O4 on sun compilers, -O2 on gcc).
Check best compiler for best performance! (differences easily can be about
25% !)

>Ben Verwer. Below see a real program (coauthored by Henri Vrooman).

Don't read that program. Above principles are not correct applied!
(i.e. lot of looping with pointer[index] instead of *pointer++ ! )
Also statements which are in the loop can be easily placed outside!


Please correct if i am wrong. This kind of discussions are of help to
everybody!

Klamer

--
Klamer Schutte			Tel: +31-53-892778	Fax: +31-53-340045
Faculty of electrical engineering -- University of Twente, The Netherlands
preferred: klamer@mi.el.utwente.nl     SMTP: klamer@utelmi01.el.utwente.nl

ben@ph.tn.tudelft.nl (Ben Verwer) writes:

[...]
>As for the author who proposed the function call in the innerloop: you must 
>drink lots of coffee at work :)
[...]

Ahem. It was me, and if I may say so, I resent your cheap blow.
I drink a lot of coffee at work, but not for the reason you imply.
If you call sizeof() a function call, you can't really be a very
experienced programmer. sizeof() evaluates at compile time to a
constant. And I was really only making a joke. Remember?
Did my last posting get lost before you saw it? I _have_ tried my
examples too, you know.

I recently wrote a convolution routine with only pointer indirection
and addition for addressing and no sissy extra loop increment variables.
Incomprehensible but fast. It _does_ make a difference.
No hard feelings - just getting things straight.

    /Stefan Gustavson (stefang@isy.liu.se)

stefang@isy.liu.se (Stefan Gustavson) writes:

>ben@ph.tn.tudelft.nl (Ben Verwer) writes:

>[...]
>>As for the author who proposed the function call in the innerloop: you must 
>>drink lots of coffee at work :)
>[...]

>Ahem. It was me, and if I may say so, I resent your cheap blow.
>I drink a lot of coffee at work, but not for the reason you imply.
>If you call sizeof() a function call, you can't really be a very
>experienced programmer. sizeof() evaluates at compile time to a
>constant. And I was really only making a joke. Remember?
>Did my last posting get lost before you saw it? I _have_ tried my
>examples too, you know.

Sorry, I'll be more specific, though I don't know why you thought I
was speaking of you.

I was speaking about the posting in which wyc@bucrsb.bu.edu (Yecheng Wu) wrote:

>One solution to the messy problem is to make some functions to do
>the offset calculation. For example, we can PutPixel and
>GetPixel() here. They should look like:

>BYTE GetPixel(BYTE *ImageBuf, long RowOffset, long Col)
>{
>       return ImageBuf[RowOffset+Col];
>}


Ben

klamer@mi.el.utwente.nl (Klamer Schutte) writes:

>In <ben.714157437@galaxy> ben@ph.tn.tudelft.nl (Ben Verwer) writes:

>A problem with using a linear array is present when multiplication is
>slower as pointer indirection (for instance, on a sparc, or a 68000).
>Accessing image pixel (x,y) will involve accessing image[y*xsize+x];
>otherwise *(imageptr[y]+x) is used.

This is false. Or misleading. You do not need to muliply to get
to a point. Once you have set a pointer to it, increments will do.
Only when you do random acces to the image you are right.

>>The loop I most often use is:

>>pixel *p = beginofdata;
>>int i;  /* make sure this is 32 bits! */

>>for (i=xsize*ysize; --i>=0;) *p++ = ...;

>>This is the fastest on 68000Us! And also on sparcstations. Try it. (thanx to 
>>Gert van Antwerpen)

>It is not on sparcstations (and i doubt it on 68k). Faster is:

>pixel *p_end = beginofdata+sizeofdata+1;

I think you have a +1 too much.

>for(p=beginofdata;p<p_end;) *p++ = ...;
>(At least with /bin/cc and Sun C 1.4. gcc 2.2.1 didn't care...)

I don't get a difference between the following two:
for (p=start; p<end;) *p++ = 1;  /* end = start + leng */
for (i=leng; --i>=0;) *p++ = 1;
And it reads a lot better.

>Don't read that program. Above principles are not correct applied!
>(i.e. lot of looping with pointer[index] instead of *pointer++ ! )
>Also statements which are in the loop can be easily placed outside!

Through, but only the innerloop is important. 
And as you see, the principles are applied there.
(Although I agree the x=0; x<xend; x++ should be x=xend; --x>=0;
but It was written for a compiler on a vector machine which only
recognized the x=0; x<end; x++ type, sorry about that)
The little loop to fill the filter and the final copying of the result
take about .1 % of the total filter time.
Why don't you spend a few hours to see if you can get it back to
.05%. I'am sure lots of people will be interested. :)

>Klamer

Ben 

In article <stefang.714225838@isy> stefang@isy.liu.se (Stefan Gustavson) writes:
>
>I recently wrote a convolution routine with only pointer indirection
>and addition for addressing and no sissy extra loop increment variables.
>Incomprehensible but fast. It _does_ make a difference.
>No hard feelings - just getting things straight.


Please post this code.  It would be very useful.


Ward Page
NCCOSC RDT&E
San Diego, CA
page@cod.nosc.mil

-- 
Ward Page
Naval Ocean Systems Center
San Diego, CA
page@cod.nosc.mil

In <ben.714268436@galaxy> ben@ph.tn.tudelft.nl (Ben Verwer) writes:
]klamer@mi.el.utwente.nl (Klamer Schutte) writes:
]>In <ben.714157437@galaxy> ben@ph.tn.tudelft.nl (Ben Verwer) writes:

]>A problem with using a linear array is present when multiplication is
]>slower as pointer indirection (for instance, on a sparc, or a 68000).
]>Accessing image pixel (x,y) will involve accessing image[y*xsize+x];
]>otherwise *(imageptr[y]+x) is used.

]This is false. Or misleading. You do not need to muliply to get
]to a point. Once you have set a pointer to it, increments will do.
]Only when you do random acces to the image you are right.

I meant the case when you do random access. I do that sometimes, you know.

]>>The loop I most often use is:

]>>pixel *p = beginofdata;
]>>int i;  /* make sure this is 32 bits! */

]>>for (i=xsize*ysize; --i>=0;) *p++ = ...;

]>>This is the fastest on 68000Us! And also on sparcstations. Try it. (thanx to 
]>>Gert van Antwerpen)

]>It is not on sparcstations (and i doubt it on 68k). Faster is:

]>pixel *p_end = beginofdata+sizeofdata+1;

]I think you have a +1 too much.

You're right! Sorry for the error!

]>for(p=beginofdata;p<p_end;) *p++ = ...;
]>(At least with /bin/cc and Sun C 1.4. gcc 2.2.1 didn't care...)

]I don't get a difference between the following two:
]for (p=start; p<end;) *p++ = 1;  /* end = start + leng */
]for (i=leng; --i>=0;) *p++ = 1;
]And it reads a lot better.

Sure, it reads a lot better. But here are my timings:
(cc == Sun C 1.4, gcc == Gnu C 2.2.1)
----- inserted text follows
0 klamer@mi7 11:11 79> cc -O4 test3.c -o test3
0 klamer@mi7 11:11 80> cc -O4 test4.c -o test4
0 klamer@mi7 11:11 81> gcc -O2 test3.c -o test3g
0 klamer@mi7 11:11 82> gcc -O2 test4.c -o test4g
0 klamer@mi7 11:11 83> diff -c test3.c test4.c
*** test3.c     Fri Aug 21 10:51:07 1992
--- test4.c     Fri Aug 21 11:12:23 1992
***************
*** 7,12 ****
--- 7,13 ----
        char    *image = malloc( 60000 );
        register char   *p, *q;
        register int    i;
+       register char   *pend;
        int     cnt;

        cnt = (argc > 1) ? atoi(argv[argc-1]) : 1;
***************
*** 14,20 ****
        while(cnt--)
        {
                p = q = image;
!               for(i=60000; --i>=0;)
                        *p++ = 1;
        }
  }
--- 15,22 ----
        while(cnt--)
        {
                p = q = image;
!               pend = image+60000;
!               for(;p<pend;)
                        *p++ = 1;
        }
  }
1 klamer@mi7 11:12 84> time test3 100
2.150u 0.070s 0:02.25 98.6% 0+106k 2+0io 2pf+0w
0 klamer@mi7 11:12 85> time test4 100
1.410u 0.030s 0:01.46 98.6% 0+107k 2+0io 2pf+0w
0 klamer@mi7 11:12 86> time test3g 100
1.580u 0.030s 0:01.64 98.1% 0+111k 2+0io 2pf+0w
2 klamer@mi7 11:13 87> time test4g 100
1.540u 0.090s 0:01.63 100.0% 0+110k 2+0io 2pf+0w
2 klamer@mi7 11:13 88>
----- end of inserted text

As can be seen, the test4 program is faster when compiled with cc.
Using gcc did both programs run just as fast.
cc beats gcc on test4 because cc does some loop unrolling (4 times).

Doing this by hand gave times in the range of 1.3 seconds.

]>Don't read that program. Above principles are not correct applied!
]>(i.e. lot of looping with pointer[index] instead of *pointer++ ! )
]>Also statements which are in the loop can be easily placed outside!

]Through, but only the innerloop is important. 
]And as you see, the principles are applied there.
](Although I agree the x=0; x<xend; x++ should be x=xend; --x>=0;
]but It was written for a compiler on a vector machine which only
]recognized the x=0; x<end; x++ type, sorry about that)
]The little loop to fill the filter and the final copying of the result
]take about .1 % of the total filter time.
]Why don't you spend a few hours to see if you can get it back to
].05%. I'am sure lots of people will be interested. :)

The point i tried to make overhere is that when one demonstrates
a certain feature, demonstrate only that feature! Don't bother
people with inefficient i/o routines or initialisations. Only
give the program segment relevant to the problem!

Off course, you only should optimise parts of your program which take
considerable time. Every one should know and use the 99% - 1% rule!

]Ben 

Klamer
--
Klamer Schutte			Tel: +31-53-892778	Fax: +31-53-340045
Faculty of electrical engineering -- University of Twente, The Netherlands
preferred: klamer@mi.el.utwente.nl     SMTP: klamer@utelmi01.el.utwente.nl

In article <ben.714157437@galaxy>, ben@ph.tn.tudelft.nl (Ben Verwer)
writes:
>The basic question is how to program for images with variable sizes. The 
>solution presented by the author here (malloc a linear array of
>xsize*ysize) is
>imo the best. Those numerical recipies in C readers who propose the famous
>>array of pointers solution are thinking rather 2d. What if you go to 3d:
>an 
>image of pointers? Which is of course implemented as an array of pointers
>to 
>pointers. Good luck!
>As for the author who proposed the function call in the innerloop: you
>must 
>drink lots of coffee at work :)
>
Why not do what I do and have the best of both worlds? Allocate one long
array of nx*ny doubles, then an array of nx double*s, each of which points
to the appropriate section of the previous array. Operations that naturally
run across the entire array can be coded like that, and operations that
make use of the 2Dness of the array can be coded like that. You also have
something you can pass to Fortran. Of course I wrap it up in a C++ class to
hide the ugly details of creating and destroying the objects each time I
use them.

Maynard Handley

In article <1992Aug22.051723.28817@msc.cornell.edu> maynard@tamar.msc.cornell.edu (Maynard J. Handley) writes:

   Why not do what I do and have the best of both worlds? Allocate one long
   array of nx*ny doubles, then an array of nx double*s, each of which points
   to the appropriate section of the previous array. Operations that naturally
   run across the entire array can be coded like that, and operations that
   make use of the 2Dness of the array can be coded like that. You also have
   something you can pass to Fortran.

I posted C code for this in this very group about a week ago...

   Of course I wrap it up in a C++ class to
   hide the ugly details of creating and destroying the objects each time I
   use them.

C++ code for implementing template arrays in this way is available
from "maya.idiap.ch:pub/tmb/array.shar".

					Thomas.