efficient vector/matrix operations in Ada

efficient vector/matrix operations in Ada

[Russ]

Several years ago I developed a C++ class for vector/matrix operations.
I decided to do the same in Ada as an excercize. A key lesson I learned
about C++ is that vector/matrix operations can be done much more
efficiently using the arithmetic "assignment" operators such as "+="
instead of "+". I am interested in how this is handled in Ada.

Suppose A and B are matrices. The expression

    A = A + B; // inefficient

is much less efficient than

    A += B; // efficient

The former requires the dynamic construction of a temporary matrix to
hold the sum (A + B), which must then be passed by value and copied into
A. This can take three or four times as long as the addition "in place"
using "+=". That is simply unacceptable for numerically intensive
applications such as Monte Carlo simulations.

Since Ada has no arithmetic assignment operators, are vector/matrix
operations in Ada simply inefficient, or do Ada programmers resort to
tacky, ambiguous expressions like

    PlusEquals(A,B);

-- 
Russ P.
http://RussP.org

Re: efficient vector/matrix operations in Ada

[Dale Stanbrough]

Russ wrote:

> Since Ada has no arithmetic assignment operators, are vector/matrix
> operations in Ada simply inefficient, or do Ada programmers resort to
> tacky, ambiguous expressions like
> 
>     PlusEquals(A,B);


Tacky it may be, but it doesn't have to be ambiguous, if you use
named parameter association...

 
   Add (To => A, Item => B);


Note that using '+' in C++ can be just as efficient as += by using
templates.

Dale

Re: efficient vector/matrix operations in Ada

[tmoran]

>tacky, ambiguous expressions like
>   PlusEquals(A,B);
but is
    Inc(A, B);
so bad or non-obvious?  Fortran programmers, no slouch at fast matrix
operations, seem to have figured out a satisfactory approach.  If you
are really pressed for speed, you are going to be calling an optimized
library anyway.

>    A = A + B; // inefficient
>
>is much less efficient than
>
>    A += B; // efficient
>
>The former requires the dynamic construction of a temporary matrix to
>hold the sum (A + B), which must then be passed by value and copied into
>A.
  Is A = A+B, an O(n**2) operation, going to be limiting the speed of
your matrix arithmetic, which probably involves some O(n**3) operations
if it does anything substantial?
  Just because one way of doing it is slow doesn't mean there isn't a
fast way.  For instance why does a temporary need to be dynamic?
Register oriented CPUs don't dynamically create a new register
every time they need one.  One could easily imagine a machine with
vector instructions that can do A+B->C very fast, but has no special
instruction for A+B->A.  In the case of a temporary matrix, of
course, "dynamic construction" could mean something as simple as
"move the stack pointer".  Or your aithmetic operations could create
expressions, moving just pointers and op-codes, and the assignment
operator could analyze the expression and decide the fastest way
to actually calculate the result.  Think outside of the box. ;)

Re: efficient vector/matrix operations in Ada

[Russ P.]

tmoran@acm.org wrote:
> 
> >tacky, ambiguous expressions like
> >   PlusEquals(A,B);
> but is
>     Inc(A, B);
> so bad or non-obvious?  Fortran programmers, no slouch at fast matrix
> operations, seem to have figured out a satisfactory approach.  If you
> are really pressed for speed, you are going to be calling an optimized
> library anyway.

I'm not looking for high-level optimization, I'm just looking for
something that is reasonably efficient.

> 
> >    A = A + B; // inefficient
> >
> >is much less efficient than
> >
> >    A += B; // efficient
> >
> >The former requires the dynamic construction of a temporary matrix to
> >hold the sum (A + B), which must then be passed by value and copied into
> >A.
>   Is A = A+B, an O(n**2) operation, going to be limiting the speed of
> your matrix arithmetic, which probably involves some O(n**3) operations
> if it does anything substantial?
>   Just because one way of doing it is slow doesn't mean there isn't a
> fast way.  For instance why does a temporary need to be dynamic?
> Register oriented CPUs don't dynamically create a new register
> every time they need one.  One could easily imagine a machine with
> vector instructions that can do A+B->C very fast, but has no special
> instruction for A+B->A.  In the case of a temporary matrix, of
> course, "dynamic construction" could mean something as simple as
> "move the stack pointer".  Or your aithmetic operations could create
> expressions, moving just pointers and op-codes, and the assignment
> operator could analyze the expression and decide the fastest way
> to actually calculate the result.  Think outside of the box. ;)

No, you really need the dynamically instantiated temporary matrix, I
believe. I've been through this little lesson years ago. Don't forget
that you also need to be able to handle expressions such as "A = B + C +
D;". You can play complicated games with static arrays of "work"
matrices, but you are asking for trouble and the resulting code is
likely to not be re-entrant.

-- 
Russ P.
http://RussP.org

Re: efficient vector/matrix operations in Ada

[B.Gaffney]

"Russ P." <18k11tm001@sneakemail.com> wrote in message news:<3B6F5ABC.3C40E189@sneakemail.com>...
> No, you really need the dynamically instantiated temporary matrix, I
> believe. I've been through this little lesson years ago. Don't forget
> that you also need to be able to handle expressions such as "A = B + C +
> D;". You can play complicated games with static arrays of "work"
> matrices, but you are asking for trouble and the resulting code is
> likely to not be re-entrant.

Um, OK, but how would you handle this case using your "+="
implementation?  That was your original point wasn't it?

                       --Bg

Re: efficient vector/matrix operations in Ada

[Dmitry Kazakov]

On 10 Aug 2001 09:54:33 -0700, B_Gaffney@My-Deja.com (B.Gaffney)
wrote:

>"Russ P." <18k11tm001@sneakemail.com> wrote in message news:<3B6F5ABC.3C40E189@sneakemail.com>...
>> No, you really need the dynamically instantiated temporary matrix, I
>> believe. I've been through this little lesson years ago. Don't forget
>> that you also need to be able to handle expressions such as "A = B + C +
>> D;". You can play complicated games with static arrays of "work"
>> matrices, but you are asking for trouble and the resulting code is
>> likely to not be re-entrant.
>
>Um, OK, but how would you handle this case using your "+="
>implementation?  That was your original point wasn't it?

One could allow to define "accelerators" for binary and unary
operations. For instance:

   function "+" (A, B : Matrix) return Matrix;
   procedure InPlaceSum (A : in out Matrix, B : Matrix);
   pragma Accelerator (InPlaceSum, "+");

The compiler should replace calls to "+" with calls to InPlaceSum if
the left argument is temporal. So B+C+D has to be compiled into:

InPlaceSum ("+"(B,C),D)

[or silently ignore the pragma (:-))]

As for +=, it would be nice to extend the set of operators in Ada.
However it should be done in a consistent manner, i.e. for each
operator @ there should a @:= counterpart. Like "<=:=" for "<=". A bit
cumsy, isn't it? And what to do with "and" or "abs"? (:-))

Regards,
Dmitry Kazakov

Re: efficient vector/matrix operations in Ada

[Russ]

B_Gaffney@My-Deja.com (B.Gaffney) wrote in message news:<9f6e2b77.0108100854.66b084b4@posting.google.com>...
> "Russ P." <18k11tm001@sneakemail.com> wrote in message news:<3B6F5ABC.3C40E189@sneakemail.com>...
> > No, you really need the dynamically instantiated temporary matrix, I
> > believe. I've been through this little lesson years ago. Don't forget
> > that you also need to be able to handle expressions such as "A = B + C +
> > D;". You can play complicated games with static arrays of "work"
> > matrices, but you are asking for trouble and the resulting code is
> > likely to not be re-entrant.
> 
> Um, OK, but how would you handle this case using your "+="
> implementation?  That was your original point wasn't it?
> 
>                        --Bg

Here's how you write "A = B + C + D;" efficiently:

    A  = B;
    A += C;
    A += D;

This requires no temporary matrices or passing by value. The original
form (A=B+C+D) is fine for rapid prototyping, but the efficient form
is preferable for production code. As far as I am concerned, Ada
really needs arithmetic assignment operators. Sure, you can use
procedures, but they're intent and effect is not as obvious to the
reader.

Russ

Re: efficient vector/matrix operations in Ada

[Larry Hazel]

Russ wrote:
> 
> Here's how you write "A = B + C + D;" efficiently:
> 
>     A  = B;
>     A += C;
>     A += D;
> 
> This requires no temporary matrices or passing by value. The original
> form (A=B+C+D) is fine for rapid prototyping, but the efficient form
> is preferable for production code. As far as I am concerned, Ada
> really needs arithmetic assignment operators. Sure, you can use
> procedures, but they're intent and effect is not as obvious to the
> reader.
> 
Seems to me if a compiler can't generate the most efficient code for 

A = B + C + D

  or

A := B + C + D

in any language, you need a different compiler.

Larry

Re: efficient vector/matrix operations in Ada

[Ted Dennison]

In article <3B783732.A3A1EB82@mindspring.com>, Larry Hazel says...
>
>Seems to me if a compiler can't generate the most efficient code for 
>
>A = B + C + D
>
>  or
>
>A := B + C + D
>
>in any language, you need a different compiler.

Perhaps, but then what do you do when the language allows you to redfine "+" to
do something complicated? You'd have to turn that optimization off (at least
when using a redefined "+").

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
          home email - mailto:dennison@telepath.com

Re: efficient vector/matrix operations in Ada

[Russ]

Larry Hazel <lhazel@mindspring.com> wrote in message news:<3B783732.A3A1EB82@mindspring.com>...
> Russ wrote:
> > 
> > Here's how you write "A = B + C + D;" efficiently:
> > 
> >     A  = B;
> >     A += C;
> >     A += D;
> > 
> > This requires no temporary matrices or passing by value. The original
> > form (A=B+C+D) is fine for rapid prototyping, but the efficient form
> > is preferable for production code. As far as I am concerned, Ada
> > really needs arithmetic assignment operators. Sure, you can use
> > procedures, but they're intent and effect is not as obvious to the
> > reader.
> > 
> Seems to me if a compiler can't generate the most efficient code for 
> 
> A = B + C + D
> 
>   or
> 
> A := B + C + D
> 
> in any language, you need a different compiler.
> 
> Larry

I'm no compiler expert, but I seriously doubt that you are correct
here. Come to think of it, I'll just say that you are flat out
wrong--and I'll eat crow if you are right. The difference (in C++)
between

    A = B + C + D;
and
    A = B; A += C; A += D;

is more fundamental than a compiler can account for. Don't forget that
"+" and "+=" are user-defined operators to start with. The former says
to add B, C, and D, place the result in a temporary matrix, and copy
that matrix by value back into A. The latter says to copy B into A,
Add C directly to the result, then add D directly to that result. The
latter needs no temporary matrices, whereas the former requires a
temporary for each "+" operator. A special preprocessor could possibly
convert the former to the latter, but I don't see how a compiler could
possibly do it.

This is all old hat in the C++ community. Ada is a great language, but
it missed the boat here. If you don't believe it, you probably don't
understand efficient vector/matrix operations.

By the way, if you think the arithmetic operators should be called
"+:=", "-:=", etc., I give up.

Russ

Re: efficient vector/matrix operations in Ada

[David Starner]

> By the way, if you think the arithmetic operators should be called
> "+:=", "-:=", etc., I give up.
>
> Russ

Why? Ada wouldn't be the first to do so - Icon has a full set of +:=, ||:=,
etc. operators.

Re: efficient vector/matrix operations in Ada

[Alexander Boucke]

> > Here's how you write "A = B + C + D;" efficiently:
> >
> >     A  = B;
> >     A += C;
> >     A += D;
> >
> > This requires no temporary matrices or passing by value. The original
> > form (A=B+C+D) is fine for rapid prototyping, but the efficient form
> > is preferable for production code. As far as I am concerned, Ada
> > really needs arithmetic assignment operators. Sure, you can use
> > procedures, but they're intent and effect is not as obvious to the
> > reader.


There is a way to do the same (regarding efficiency) in Ada 95 using the A:=
B + C + D form. For my work I've written a Matrix-Vector package, that
encapsulates the Arrays using access-types. The only temporary objects you
get now are access-types. There would have been a problem with the RAM
slowly filling up, so I used controlled types to do reference-counting.
Together with a temporary vector holding all results from sums, this leads
to equivalent efficiency as using the += operators. You have to deal with
the overhead due to the garbage collection using controlled types, but that
is negligible when using large vectors/matrices as in typical finite element
programs.

How this could look (simplified):

package vectors is

...

  type Vector is new Ada.Finalization.Controlled with private;

  function "+" (left,right : vector) return vector;

...

private

  type value_array is array (<>) of real;
  type handled_vector (first,last : integer) is
     record
        value : value_array(first, last);
        count : natural; -- for reference counting
     end record;

  type handled_vector_access is access handled_vector;

  type vector is new ada.finalization.controlled with
     record
        the_vector : handled_vector_access;
     end record;

end vectors;


Regards,

Alexander Boucke

Re: efficient vector/matrix operations in Ada

[Lutz Donnerhacke]

* Russ wrote:
>Larry Hazel <lhazel@mindspring.com> wrote in message news:<3B783732.A3A1EB82@mindspring.com>...
>> Seems to me if a compiler can't generate the most efficient code for
>> A = B + C + D
>>   or
>> A := B + C + D
>> in any language, you need a different compiler.
>
>I'm no compiler expert, but I seriously doubt that you are correct here.
>Come to think of it, I'll just say that you are flat out wrong--and I'll
>eat crow if you are right. The difference (in C++) between
>
>    A = B + C + D;
>and
>    A = B; A += C; A += D;
>
>is more fundamental than a compiler can account for. Don't forget that
>"+" and "+=" are user-defined operators to start with. The former says
>to add B, C, and D, place the result in a temporary matrix, and copy
>that matrix by value back into A.

Even the dragon book contains a chapter about data flow analysis, which is
invented to remove unnecessary temporary copies and does a wonderful job on
this subject.

Re: efficient vector/matrix operations in Ada

[Jacob Sparre Andersen]

Russ:

I haven't looked at the code generated by "my" compiler, so
I will just come with some general remarks...

> Larry Hazel <lhazel@mindspring.com> wrote in message news:<3B783732.A3A1EB82@mindspring.com>...
[...]
> > Seems to me if a compiler can't generate the most efficient code for
> >
> > A = B + C + D
> >
> >   or
> >
> > A := B + C + D
> >
> > in any language, you need a different compiler.

It doesn't always make a large difference, but I would
definitely prefer a compiler which could do the
optimisation.

> I'm no compiler expert, but I seriously doubt that you are correct
> here. Come to think of it, I'll just say that you are flat out
> wrong--and I'll eat crow if you are right.

I think it is time to go hunting now...

> The difference (in C++)
> between
> 
>     A = B + C + D;
> and
>     A = B; A += C; A += D;
> 
> is more fundamental than a compiler can account for. Don't forget that
> "+" and "+=" are user-defined operators to start with. The former says
> to add B, C, and D, place the result in a temporary matrix, and copy
> that matrix by value back into A. The latter says to copy B into A,
> Add C directly to the result, then add D directly to that result. The
> latter needs no temporary matrices, whereas the former requires a
> temporary for each "+" operator. A special preprocessor could possibly
> convert the former to the latter, but I don't see how a compiler could
> possibly do it.

It shouldn't be too hard for a compiler to figure out if a
user-defined operator, "+", can do the calculation "A := A +
B" without having to allocate an intermediate buffer (at
least all the cases, where the operation is simply a loop
over all elements in the composite type).

If you know that, then it is pretty simple to generate the
two versions of the assignment and compare their execution
times.

> This is all old hat in the C++ community. Ada is a great language, but
> it missed the boat here.

Sorry?

What's the difference between:

   A += B;

and

   Add (Target => A,
        Addend => B);

(except for a few extra characters)?

> By the way, if you think the arithmetic operators should be called
> "+:=", "-:=", etc., I give up.

When you come to the point, where this kind of optimisations
are necessary, it really doesn't matter if the operators are
called "+:=", ":+", "+=" or are written as a procedure call.

Jacob
-- 
http://hugin.ldraw.org/Jacob/edb/digitale_nyheder
Om redakt�rens opgave p� internetnyhedstjenester.

Re: efficient vector/matrix operations in Ada

[Ted Dennison]

In article <bebbba07.0108131145.8e90df5@posting.google.com>, Russ says...
(talking about matrices with redefined math ops)
>Here's how you write "A = B + C + D;" efficiently:
>
>    A  = B;
>    A += C;
>    A += D;
>
>really needs arithmetic assignment operators. Sure, you can use
>procedures, but they're intent and effect is not as obvious to the
>reader.

Perhaps to a reader who is *already* familiar with the idiom above that is true.
I'm not, and it took me a couple of takes to see what you were doing here (and a
bit of thought to figure out why). For someone starting from ground zero, I
think the point is quite arguable.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
          home email - mailto:dennison@telepath.com

Re: efficient vector/matrix operations in Ada

[Russ]

Ted Dennison<dennison@telepath.com> wrote in message news:<aGXd7.88$2u.23428@www.newsranger.com>...
> In article <bebbba07.0108131145.8e90df5@posting.google.com>, Russ says...
> (talking about matrices with redefined math ops)
> >Here's how you write "A = B + C + D;" efficiently:
> >
> >    A  = B;
> >    A += C;
> >    A += D;
> >
> >really needs arithmetic assignment operators. Sure, you can use
> >procedures, but they're intent and effect is not as obvious to the
> >reader.
> 
> Perhaps to a reader who is *already* familiar with the idiom above that is true.
> I'm not, and it took me a couple of takes to see what you were doing here (and a
> bit of thought to figure out why). For someone starting from ground zero, I
> think the point is quite arguable.

If you know even a tiny bit of C++, the "+=" notation is very obvious.
And it's use here in my example of matrix addition is perfectly
consistent with its use for normal scalar addition. No, you don't
absolutely need those operators, but neither do you need to be able
define your own "+", "-", etc. in Ada either. So why does Ada have
some nice-looking operators but not have the operators one really
needs for efficient code? I guess the goofy syntax isn't the only
problem with Ada, eh?

Russ

efficient vector/matrix operations in Fortran, was Re: ... in Ada

[tmoran]

>but not have the operators one really needs for efficient code?
  The existence of Fortran, which has long been used successfully
for highly efficient vector/matrix code, demonstrates that += is
not required.
  One possible reason is that significant matrix/vector programs
don't normally spend a lot of their time doing a += b type O(n**2)
operations, but rather spend their time doing O(n**3) operations.
+= would be of minor benefit in that case.
---------------------------------
"Premature optimization is the root of all evil"  Knuth (?)

Re: efficient vector/matrix operations in Ada

[Ted Dennison]

In article <bebbba07.0108132056.7bcc7c95@posting.google.com>, Russ says...
>
>Ted Dennison<dennison@telepath.com> wrote in message news:<aGXd7.88$2u.23428@www.newsranger.com>...
>> >    A  = B;
>> >    A += C;
>> >    A += D;
>> Perhaps to a reader who is *already* familiar with the idiom above that is 
>> true. I'm not, and it took me a couple of takes to see what you were doing 
>> here (and a bit of thought to figure out why). For someone starting from 
>> ground zero, I think the point is quite arguable.
>
>If you know even a tiny bit of C++, the "+=" notation is very obvious.

For one thing, the issue isn't that *one* of them is tough to decipher. The
issue is that the cumulative effect of all *three* of them is tough to deciper.

For another, you are again assuming someone comfortable with C++. If C++ is
going to remain your touchstone for readability, then there's no point at all in
having this discussion. Ada, or any other language with a different syntax, is
set up to loose from the get-go.

I hope you can see where I'm comming from here. If you want to know, "what's the
most readable way to do this efficiently in Ada", we can work with that. If you
want to know, "how can I make this look exactly like C++, because anything that
doesn't look that way is inferior", there's really nothing constructive anyone
here can do for you.

As for trying to be constructive, I think what I'd want to see in this situation
would be "Sum" routine with the following profile (uncompiled, and forgive me if
my posting s/w kills the formatting):
---------
type Matrices is array (Natural range <>) of Matrix;

procedure Sum
(Target :    out Matrix;
Source : in     Matrices
);
---------

That way the operation is carried out in one statement for clarity, and it can
have as many addends as you need, and can be implemented as efficiently as you
need. A call would loook something like:
----
Sum (Target => A, Source => (B, C, D));
----

That certianly looks clearer to me than your n lines of code (where n=# of
addends), all of which have to be read and mentally pieced together to figure
out what's going on.

If your compiler can't do this efficently (some might make copies of B, C, and D
on the stack), then a good subsitute would be to just have several overloaded
"Sum" routines containting as many addends as you might need.


---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
          home email - mailto:dennison@telepath.com

Re: efficient vector/matrix operations in Fortran, was Re: ... in Ada

[Gautier Write-only-address]

>   The existence of Fortran, which has long been used successfully
>for highly efficient vector/matrix code, demonstrates that += is
>not required.
>   One possible reason is that significant matrix/vector programs
>don't normally spend a lot of their time doing a += b type O(n**2)
>operations, but rather spend their time doing O(n**3) operations.
>+= would be of minor benefit in that case.

The real reason is the "+" operator is defined in the language
for vectors or matrices, not a programmable function like in Ada.
Or, say, it has a pragma Import(intrinsic,...) like for functions
in Standard or Interfaces.
So the Fortran compiler optimizes with full latitude.
With a <<function "+"(a,b:vector) return vector>>, and no
trick to tell the compiler that it is intrisic,
you have a local variable in your function, perform the addition,
and return the variable. Maybe a pragma Inline and a strong
optimization can do the job on some compilers. It would be
interesting to see if at least one is able to suppress the
local variable in an inlined call. If not, there is no chance
that a user-defined "+" is as efficient as a user-defined "+=".

________________________________________________________
Gautier  --  http://www.mysunrise.ch/users/gdm/gsoft.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: efficient vector/matrix operations in Fortran, was Re: ... in Ada

[Lutz Donnerhacke]

* Gautier Write-only-address wrote:
>and return the variable. Maybe a pragma Inline and a strong
>optimization can do the job on some compilers. It would be
>interesting to see if at least one is able to suppress the
>local variable in an inlined call. If not, there is no chance
>that a user-defined "+" is as efficient as a user-defined "+=".

GNAT does a pretty bad job on this subject. Using the "+=" Procedure is
works considerably better. Please play around with compiler flags.

OTOH it is possible to enhance the Kernel Interface vastly if you are
switching to direct syscalls (using System.Machine_Code). Inlining does a
pretty good job on this subject:

\f
with Kernel.Calls;
use Kernel.Calls;

procedure test_kernel is
   res : long := sys_kill (0, 0);
begin
   null;
end test_kernel;
\f
_ada_test_kernel:
	movb $37,%al
	xorl %ebx,%ebx
	movl %ebx,%ecx
	int $0x80
	ret
\f
with Ada.Text_IO;

procedure t is
   type Vector is array (Positive range <>) of Integer;

   function "+" (a, b : Vector) return Vector is
      c : Vector(a'Range);
   begin
      for i in a'Range loop
         c(i) := a(i) + b(i);
      end loop;
      return c;
   end "+";

   procedure Add_To (a : in out Vector; b : in Vector) is
   begin
      for i in a'Range loop
         a(i) := a(i) + b(i);
      end loop;
   end Add_To;
   pragma Inline("+", Add_To);
   
   procedure Print (a : in Vector) is
      package IIO is new Ada.Text_IO.Integer_IO (Integer);
      use IIO, Ada.Text_IO;
   begin   
      for i in a'Range loop
         Put (i);
         Put (a (i));
      end loop;
      New_Line;
   end Print;
   
   a : Vector(1..3) := (others => 3);
   b : Vector(1..3) := (1, 2, 3);
   c : Vector(1..3) := (4, 5, 6);
   d : Vector(1..3);
begin
   d := a + b + c;
   Print(d);
   d := a; Add_To (d, b); Add_To (d, c);
   Print(d);
end t;