NetNews Usenet Archive 1992 #16/NN_1992_16.iso/spool/comp/lang/cplus/11656

Internet Message Format | 1992-07-28 | 4.6 KB

Xref: sparky comp.lang.c++:11656 comp.lang.eiffel:997
Path: sparky!uunet!mcsun!corton!irisa!irisa.fr!jezequel
From: [e-mail] (Jean-Marc Jezequel)
Newsgroups: comp.lang.c++,comp.lang.eiffel
Subject: Re: Multi-operator expressions
Message-ID: <[e-mail]>
Date: 28 Jul 92 13:14:55 GMT
References: <[e-mail]>
Sender: [e-mail]
Organization: Irisa, Rennes(FR)
Lines: 108

In article <[e-mail]>, [e-mail] (Dan Frankowski) writes:
|> This posting is long.  :-(  I ask, "How do we optimize expressions
|> involving more than one operator, such as A * B + C, x = x + y,
|> and list = one + two + three + four?"
As I think this discussion is not specific to C++, I cross-posted it to comp.lang.eiffel

|> Motivation
|> ----------
|>
|> In many cases there are important optimizations for expressions that
|> involve more than one operator.  For example:
|>
|>   A + B * C (where A, B, and C are matrices) on a Cray should be a
|>   Cray Assembly Language (CAL) routine to pipeline the results of
|>   multiplication to the adder while more multiplication is done.
|>
|> This is a serious optimization, resulting in noticeable improvement in
|> performance.  It is inhibited by the fact that in this expression,
|> operator* doesn't know about operator+ nor vice-versa.  But to
|> implement it properly, _something_ must know that both addition and
|> multiplication are taking place.
|>
|> Two present-day solutions:
|>
|> - Specify the expression as addMult(A,B,C).
|>
|> - Overload + and * to build a parse tree, and then make = optimize
|>   the parse tree and perform all of the necessary calculations.
|>   (See Jim Adcock's 1992 June 15 posting to comp.lang.c++)
|>
|> The first solution is completely counter to the style of C++.  The
|> second has runtime overhead for evaluating a parse tree, which is the
|> bread and butter of a compiler.
This is my feeling.

|> It also does not account for function
|> calls with A + B * C as a parameter, or any other places where an
|> expression may be used.
|>
|> Wouldn't it be nice to have a simple notation to allow the programmer
|> to specify functions to be put in the place of expressions that
|> involve more than one operator?  The programmer could then tell the
|> compiler, "Make A + B * C into AddMult(A,B,C)" much as we now say
|> "Make A + B into operator+(const Matrix&, const Matrix&)" (which can
|> be an inlined call to Add(A,B)).
|>
|> Proposal
|> --------
|>
|> For the matrix example above, we could use
|>
|> Matrix operator+*(const Matrix&, const Matrix&, const Matrix&);
|>
|> The compiler would transform A + B * C into operator+*(A,B,C).  In
|> other words, use operator<op1><op2>(<arguments>) to specify a two
|> operator expression.  This is easily extended to any fixed number of
|> operators.
|>

This sounds interesting, but I still think this kind of optimisation should be pure
compiler job.
Indeed, you seem to consider than your Matrix class is not to be subclassed
(because otherwise this would'nt be possible at compile time, as the actual methods under
names + and * would depend on actual (dynamic) type of your Matrices).
But if you (the compiler) know statically what version of + and * will be invoked in the
expression A + B * C, then a "normal" concatenation of compiler optimisations would give
the wanted result. Here is an outline of this string (using pseudo-code):

D:=A+B*C
--The parser gives:
D:=A.plus(B.mult(C)) which leads to E:=B.mult(C);D:=A.plus(E);

--Dynamic types of A, B and C are known at compile time, so are actual versions of plus and
mult. Then a reasonably good OO compiler could do the inline expansion (see ISE Eiffel 2.3
for example):
for i:1..n
  for j:1..n
    for k:1..n
    e(i,j)+=b(i,k)*c(k,j)
for i:1..n
  for j:1..n
    d(i,j):=a(i,j)+e(i,j)

--Then use standard loop merging (I think GCC 2.something can do it)
for i:1..n
  for j:1..n {
    for k:1..n
    e(i,j)+=b(i,k)*c(k,j)
    d(i,j):=a(i,j)+e(i,j)
  }

--Dependance analysis (getting rid of e(i,j)):
for i:1..n
  for j:1..n {
    for k:1..n
    d(i,j)+=b(i,k)*c(k,j)
    d(i,j)+=a(i,j)
  }

--And then no problem to pipe-line, or even execute as data parallel on a MIMD machine.
So I guess this is today compiler technology, and the only problem should be to melt
these different optimisations in the same compiler (or did I get anything wrong?)
To test it, it would be interesting to try the ISE compiler (Eiffel->C) followed by GCC.

--
+----------------------------------------------------------------------------+
| Jean-Marc Jezequel, IRISA/CNRS, 35042 RENNES (FRANCE) // [e-mail] |
+----------------------------------------------------------------------------+