Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!hplabs!hp-pcd!hplsla!jima
From: jima@hplsla.HP.COM (Jim Adcock)
Newsgroups: comp.lang.c++
Subject: Re: Generating temporaries
Message-ID: <6590094@hplsla.HP.COM>
Date: 12 Apr 89 22:51:25 GMT
References: <8904042239.AA07890@yahi.stanford.edu>
Organization: HP Lake Stevens, WA
Lines: 77

Hm, tiemann and bs seem to be saying they know
a good, fast, easy way to handle the 
"binary operator for matrices" class of 
problem.  If so, I'd sure like to know what
the simple solution is, 'cuz I can't figure it out!

I assume that matrices consist of a moderate and
fixed size chunk of store representing 
standard properties of the matrix: number
of rows and columns, zero or non-zero,
symmetric or non-symmetric, etc, plus a 
pointer to a chunk of heap to hold the
n by m numbers that make up that matrix.

So that both the fixed part and the variable
part of the matrix are bigger than one
would like to copy.  And one doesn't
want to introduce temporaries unnecessarily
since that also requires initialization and
a call to the heap manager to allocate
space for the variable-sized part of the
matrix.

Certainly small, and/or fixed sized objects
are not too hard to handle.  For example,
implementing a class of 3x3 matrices would
seem to be pretty straight-forward.

Has anybody found a simple, fast, easy way
to handle these large, variable sized
objects with binary operators?

----

While far from simple, or easy, I have been
playing around with a Matrix approach that
avoids generating unnecessary copies or
temporaries, and generates fast, compact
code.

The general approach is to have the binary
operators, instead of returning a "Matrix",
return a linked structure that represents
the operations that need to be performed,
along with the addresses of the Matrices
on which to perform the operations.  The
operations are not actually performed until
their result is assigned to a matrix, at
which point in time the operation can be
performed "in place."  Since the intermediate
structure that is formed is made of small, fixed
size objects, the intermediate class can
be entirely "inlined", resulting in surprisingly
good efficiencies when followed by a good,
optimizing backend C compiler.

For example:

a = b + c + d;

where a, b, c, and d are matrices, results
in 11 machine code instructions that set
up a linked structure saying what needs to
get added to what, and where to put the 
results, followed by one call to a routine
that copies b into a (resizing if necessary),
and then adds c to a, then adds d to a.

It seems if you mix adds and multiplies in
an expression you are forced to generate
a temporary [on heap space] which then
must be reclaimed at destruction time.

If anybody has actually figured out a
cleaner way to handle these difficult
large, variable sized object classes, 
please tell us.