pointer movement?

pointer movement?

[Andrzej Rybczynski]

I want to do some transformations of  large bitmap (dynamically 
allocated). With c/c++ I used to do this by moving pointer from 
pixel to pixel over all array. What is most important - it has to be 
extremely fast. How should I do this in Ada? Can I use package 
System.Storage_Elements for this purpose ?


Andrzej

Re: pointer movement?

[Gautier Write-only-address]

>From: "Andrzej Rybczynski" <arybczyn@lafot.com>

>I want to do some transformations of  large bitmap (dynamically
>allocated). With c/c++ I used to do this by moving pointer from
>pixel to pixel over all array. What is most important - it has to be
>extremely fast. How should I do this in Ada? Can I use package
>System.Storage_Elements for this purpose ?

Depending on the compiler, the code for moving an index in
an array like "bitmap: array(0..xmax*xmax-1) of pixel_type"
might deliver the same speed as moving the equivalent pointer
- this, when optimisation is on and checks are off...
______________________________________________________
Gautier  --  http://www.mysunrise.ch/users/gdm/e3d.htm

NB: Do not answer to sender address, visit the Web site!
    Ne r�pondez pas � l'exp�diteur, visitez le site ouaibe!



_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp

Re: pointer movement?

[Nick Roberts]

To my mind, it would be preferable if you did this at a higher level. E.g.:

   type Channel_Value is delta 1.0/256 range 0.0 .. 2.0;
   subtype Stored_Value is Channel_Value range 0.0 .. 1.0;
   --? for Stored_Value'Size use 8;
   type Channel_Selector is (Red, Green, Blue, Alpha);
   --? for Channel_Selector'Size use 4;
   subtype Colour_Channel is Channel_Selector range Red..Blue;
   type RGBA is array (Channel_Selector) of Stored_Value;
   --? pragma Pack(RGBA);
   --? for RGBA'Size use 4*Stored_Value'Size;
   type Screenful is array (0..639,0..359) of RGBA;
   --? pragma Pack(Screenful);
   --? for Screenful'Size use 640*360*RGBA'Size;
   S1, S2: Screenful;
   ...
   for x in Screenful'Range(1) loop
      for y in Screenful'Range(2) loop
         if S2(x,y)(Alpha) /= 0.0 then
            if S1(x,y)(Alpha) = 0.0 then
               S1(x,y) := S2(x,y);
            else
               for C in Colour_Channel loop
                  S1(x,y)(C) := (S1(x,y)(C)*S1(x,y)(Alpha) +
S2(x,y)(C)*S2(x,y)(Alpha))/(S1(x,y)(Alpha)+S2(x,y)(Alpha));
                  S1(x,y)(Alpha) := (S1(x,y)(Alpha)+S2(x,y)(Alpha))/2;
               end loop;
            end if;
         end if;
      end loop;
   end loop;

Note how representation clauses can be used (up to a point) to make Ada's
representations match those of the hardware.

Whether you get adequate speed is largely up to the optimisations provided
by the compiler (remember to turn on all the right switches). Of course, you
could help by removing loop invariants etc. (but the compiler ought to do
these for you, really). If this is not fast enough, you might consider going
to assembly (especially if that means you can take advantage of MMX or SIMD
or whatever).

Most modern graphics cards provide a variety of functions onboard. You can
sometimes get a major overall speed boost by offloading work to the graphics
co-processor (freeing up the main processor for other things). Sometimes, in
fact, it's much faster to have the main processor do it (because it's so
much faster than the graphics co-processor).

Hope this is helpful in some way.

--
Best wishes,
Nick Roberts



"Andrzej Rybczynski" <arybczyn@lafot.com> wrote in message
news:9t5ihf$dp$1@news.tpi.pl...
> I want to do some transformations of  large bitmap (dynamically
> allocated). With c/c++ I used to do this by moving pointer from
> pixel to pixel over all array. What is most important - it has to be
> extremely fast. How should I do this in Ada? Can I use package
> System.Storage_Elements for this purpose ?

Re: pointer movement?

[Robert Dewar]

"Andrzej Rybczynski" <arybczyn@lafot.com> wrote in message news:<9t5ihf$dp$1@news.tpi.pl>...
> I want to do some transformations of  large bitmap (dynamically 
> allocated). With c/c++ I used to do this by moving pointer from 
> pixel to pixel over all array. What is most important - it has to be 
> extremely fast. How should I do this in Ada? Can I use package 
> System.Storage_Elements for this purpose ?


It is a fallacy that having roaming pointers C style
will improve efficiency. In fact, this sloppy use of
pointers often makes it impossible for a C compiler
to do proper aliasing analysis. Declare an array,
reference it in the obvious manner, and for the most
typical code, normal optimizations should bring you
back to at least the C code efficiency, and if you use
a compiler with good aliasing analysis, perhaps better.

Re: pointer movement?

[DuckE]

I agree it is not a good idea to have roaming pointers.  And go a step
farther to preach my version of the rules of optimization (they're not
orginal but I can't remember the source):
  Rule #1.  Don't do it.
  Rule #2.  Don't do it yet.
  Rule #3.  Only optimize those parts of the program that need optimization.
With the side not that typically 10% of the program runs 90% of the time.

But...
  In my experience using GCC on an MVME162 (MC68040) under VxWorks, when I
had to optimize certain time critical parts of code (a very small fraction
of the overall code in the system), I found that sequencing through memory
by incrementing pointers was somewhat faster than incrementing an array
index and accessing the same memory by indexing the array.

IMHO it is not obvious that either method would perform better.  The only
way to determine performance is through testing or detailed analysis of the
generated code on the specific target architecture.

Generally you are better off to write the code in an obvious manner and
trust the compiler to be smarter than you are at generating optimal code
(compilers often are).  But when push comes to shove and you find that you
are close to but not quite achieving the required performance, in some cases
re-arranging the code will help.

SteveD

"Robert Dewar" <dewar@gnat.com> wrote in message
news:5ee5b646.0111171819.d56766d@posting.google.com...
[snip]
>
> It is a fallacy that having roaming pointers C style
> will improve efficiency. In fact, this sloppy use of
> pointers often makes it impossible for a C compiler
> to do proper aliasing analysis. Declare an array,
> reference it in the obvious manner, and for the most
> typical code, normal optimizations should bring you
> back to at least the C code efficiency, and if you use
> a compiler with good aliasing analysis, perhaps better.

Re: pointer movement?

[John R. Strohm]

I *KNOW* this is a stupid question, but (a) did you look at the generated
object code (b) keeping in mind the organization of the memory and the
caching and the response times?

A few years ago, I was doing image processing with a TI 320C80.  The way one
walked through the image (row-wise vs. column-wise) made a MAJOR difference
in the raw processing speed, because the RAM arrays could access successive
locations in a "row" a LOT faster than they could access successive
locations in a "column".  Some of the processing I was doing naturally
worked on a row at a time; some naturally worked on a column at a time.  We
compromised for consistent transfer times by processing small rectangular
patches at a time.

320C80 image processing code is some of the hardest I have ever done.  You
sweat blood for months over a loop with maybe twenty or thirty source
instructions in it, because that loop HAS to touch every pixel in the frame,
and the system HAS to run at video speed.  I thank my lucky stars I got my
start on a CDC 6600 all those years ago; the mindset from 6600 programming
came in handy.

DuckE <nospam_steved94@home.com> wrote in message
news:rvFJ7.41888$XJ4.23981255@news1.sttln1.wa.home.com...
> I agree it is not a good idea to have roaming pointers.  And go a step
> farther to preach my version of the rules of optimization (they're not
> orginal but I can't remember the source):
>   Rule #1.  Don't do it.
>   Rule #2.  Don't do it yet.
>   Rule #3.  Only optimize those parts of the program that need
optimization.
> With the side not that typically 10% of the program runs 90% of the time.
>
> But...
>   In my experience using GCC on an MVME162 (MC68040) under VxWorks, when I
> had to optimize certain time critical parts of code (a very small fraction
> of the overall code in the system), I found that sequencing through memory
> by incrementing pointers was somewhat faster than incrementing an array
> index and accessing the same memory by indexing the array.
>
> IMHO it is not obvious that either method would perform better.  The only
> way to determine performance is through testing or detailed analysis of
the
> generated code on the specific target architecture.
>
> Generally you are better off to write the code in an obvious manner and
> trust the compiler to be smarter than you are at generating optimal code
> (compilers often are).  But when push comes to shove and you find that you
> are close to but not quite achieving the required performance, in some
cases
> re-arranging the code will help.
>
> SteveD
>
> "Robert Dewar" <dewar@gnat.com> wrote in message
> news:5ee5b646.0111171819.d56766d@posting.google.com...
> [snip]
> >
> > It is a fallacy that having roaming pointers C style
> > will improve efficiency. In fact, this sloppy use of
> > pointers often makes it impossible for a C compiler
> > to do proper aliasing analysis. Declare an array,
> > reference it in the obvious manner, and for the most
> > typical code, normal optimizations should bring you
> > back to at least the C code efficiency, and if you use
> > a compiler with good aliasing analysis, perhaps better.
>
>

Re: pointer movement?

[DuckE]

"John R. Strohm" <strohm@airmail.net> wrote in message
news:0232EB9B71AA469C.63E4D85432274436.A56779B689231DC6@lp.airnews.net...
> I *KNOW* this is a stupid question, but (a) did you look at the generated
> object code (b) keeping in mind the organization of the memory and the
> caching and the response times?

No I did not look at the generated object code.  I found certain techniques
to improve speed by experimenting with the source code.  The MVME162 has an
available timer on board that permits me to time execution to the nearest
nanosecond.  I was able to make minor changes to the source code and observe
changes to execution speed very easily.

> A few years ago, I was doing image processing with a TI 320C80.  The way
one
> walked through the image (row-wise vs. column-wise) made a MAJOR
difference
> in the raw processing speed, because the RAM arrays could access
successive
> locations in a "row" a LOT faster than they could access successive
> locations in a "column".  Some of the processing I was doing naturally
> worked on a row at a time; some naturally worked on a column at a time.
We
> compromised for consistent transfer times by processing small rectangular
> patches at a time.

I was working with single dimension arrays.

> 320C80 image processing code is some of the hardest I have ever done.  You
> sweat blood for months over a loop with maybe twenty or thirty source
> instructions in it, because that loop HAS to touch every pixel in the
frame,
> and the system HAS to run at video speed.  I thank my lucky stars I got my
> start on a CDC 6600 all those years ago; the mindset from 6600 programming
> came in handy.

It's a pity that on occasion we still have to program at this level.

SteveD