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

Text File | 1992-07-27 | 5.8 KB | 156 lines

Newsgroups: comp.lang.c++
Path: sparky!uunet!timbuk.cray.com!hemlock.cray.com!dsf
From: [e-mail] (Dan Frankowski)
Subject: Multi-operator expressions
Message-ID: <[e-mail]>
Summary: How to do function calls for multi-operator expressions?
Lines: 145
Organization: Cray Research, Inc.
Date: 27 Jul 92 15:41:35 CDT

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?"

There is a statement of the problem, for which I yearn to see a clean
solution.  There is also the beginnings of a proposal for a language
extension to allow user-specified compile-time expression
optimization.  I'm not proposing a language extension!  It's just for
discussion, folks.

DISCLAIMER: This ain't official Cray business.

Dan Frankowski            [e-mail]     [phone]

**********************************************************************

Title: Optimizing expressions involving many operators
Alternate title: Function calls for expressions involving many operators

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.  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 does not conflict with -=, +=, .., OP= because a OP b is not an
lvalue, so a OP b = c isn't legal.  For example, operator+= is
unambiguously a += b; it cannot be a + b = c.  (See below for many
problems, however.)

Other examples
--------------

Most classes should optimize x = x + y in user code to x += y
automatically, because then the "addition" may be done in place-- that
is, without allocating additional storage.  The same holds for x = x / y,
x = x * y, x = x - y, x = x & y, and so on.  This is a considerable
optimization, and one which the user of the class may not (and ideally
should not need to) know about.

Two concrete examples similar to this:

- In the string routines of libg++,

    cat(x, y, z) for z = x + y
    cat(z, y, x, x) for x = z + y + x
    y.prepend(x) for y = x + y

- A "+" overloaded to mean concatenation, when encountering

    list = one + two + three + four + five + six

  does not need to generate five temporaries and delete them.

This seems a continuation of the ideas of C++: it has allowed
programmers to specify operators, traditionally the domain of the
compiler; why not optimizations on those operators?  I prefer to view
these optimizations as function calls for multi-operator expressions.
Does anyone have other examples where it would be very useful to
replace a multi-operator expression with a single function call?

Problems
--------

- This ruins parsing completely, does it not?  Currently, when a + token
  is passed from the lexical analyzer to the parser, we are sure that it
  is a binary operator.  For the ternary operator ?:, when we encounter
  a ? token, we are sure it is part of a ternary operator.  Now, with
  operator+*() defined, when we encounter a + token, we are not sure how
  many operators and operands are left on the input stream for a match.
  Has the grammar for C++ now become ambiguous as well?  Help!

- This doesn't solve the linked list example above.  How could
  we specify a variable number of operands?

- Is operator++() then for a + b + c or a++?  The syntax for
  operator()++ is already complicated by distinguishing prefix and
  postfix.

- This does not allow us to restrict the operands of an expression,
  so that only x = x + y would translate to operator=+() (which could
  be inlined to call operator+=() ), and not x = y + z.

- Is a + b = c legal in any extended versions of C or C++?  Then the
  proposal would break programs that use such expressions.

Questions
---------

Are there other examples?
Is this worth the trouble?
Isn't there a better syntax?
What is a notation to specify restrictions on the operands?

References
----------
<[e-mail]>
  "operator+ operator* for N objects, ?"
<[e-mail]>
  "Re: operator+ operator* for N objects, ?"
--
Dan Frankowski            [e-mail]     [phone]