🚀 go-pugleaf

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