Can I eliminate these temporary objects?
David Hoadley
complex numbers, called DCMatrix, and an operator* function:
int main()
{
DCMatrix A(2,3, complex(0.0,0.0));
DCMatrix B(3,4,complex(1.0,0.0));
DCMatrix C(2,4);
// fill A and B with stuff
C = A * B;
return (0);
};
If I trace its execution, I see:
constructor --A(2,3)
constructor --B(3,4)
constructor --C(2,4)
operator*
constructor --Result(2,4) (from declaration within operator*)
copy constructor --anon(2,4) (values copied from Result to new anon)
destructor --Result
operator= (copies values from anon to C)
destructor --anon
destructor --C
destructor --B
destructor --A
Result is a temporary matrix which I would rather not have, but I
could not see how to write operator* without it. anon is another
temporary matrix, which I didn't declare.
Is is possible to implement this without these two temporary matrices?
If not, which I fear, can I at least avoid the creation of one of them
(presumably anon)?
Thanks for any help,
David.
--
-----------------------------------------------------------------------------
David Hoadley Internet: s84...@minyos.xx.rmit.edu.au
Electrical Engineering, RMIT
Melbourne, Australia Ph: +61 3 660-4847, Fax: +61 3 660-2007
David J Keenan
Compilers have the option of optimizing away the creation of unnamed
temporaries where they see fit. Without seeing your operator* member
function, it's hard to tell whether your code allows optimization or
not. Furthermore, it's hard to tell whether it's even possible for you
to write your code to allow this type of optimization. Also, some
compilers are better than others at performing such optimizations.
Most compilers do not have any trouble optimizing away the creation of
a temporary (and the subsequent copy to the return object) in the
following simple example:
Complex Complex::operator+(const Complex &c) const
{
return Complex(real + c.real, img + c.img);
}
If you can write your code in such a way (returning an unnamed temporary
by value), there is a good chance your compiler can optimize away the
temporary and the call to the copy constructor.
--
David J. Keenan
Michigan State University
keen...@cps.msu.edu
David Vandevoorde
Yes, but it's not so easy to make a general robust code that achieves
this.
>If not, which I fear, can I at least avoid the creation of one of them
>(presumably anon)?
>
>Thanks for any help,
>David.
I would suggest you take a look at two packages.
The first one is "NewMat" ("newmat08" is the latest release, I believe)
by Robert Davies (rob...@kauri.vuw.ac.nz). You may get it by ftp from
plaza.aarnet.edu.au in /usenet/comp.sources.misc/volume47/newmat08.
It uses a dynamic expression analysis technique to handle this problem.
For large objects where operations are not only "elementwise" (e.g.,
matrix addition is an elementwise operation, whereas matrix multiplication
is not) this might well be the best way to go.
The second package is my own valarray<Troy> (get it by anonymous ftp from
ftp.cs.rpi.edu in pub/vandevod/Valarray). It is _not_ a matrix library,
but an implementation of a numerical array modeled after the specs for a
similar array included in the current working paper of the ISO committee.
It makes heavy use of class and function templates to avoid the generation
of temporary arrays altogether (but the supported operations are "element-
wise" which makes things a whole lot simpler). It comes with some technical
discussion that reviews other alternatives.
>-----------------------------------------------------------------------------
>David Hoadley Internet: s84...@minyos.xx.rmit.edu.au
>Electrical Engineering, RMIT
>Melbourne, Australia Ph: +61 3 660-4847, Fax: +61 3 660-2007
Daveed
Alex & Natasha Maclinovsky
>Is is possible to implement this without these two temporary matrices?
>If not, which I fear, can I at least avoid the creation of one of them
>(presumably anon)?
dirt cheap by using envelope/letter metaphor, and probably even void
if combined with right inlines and smart compiler.
Hope it helps,
Alex.
--
Alex and/or Natasha Maclinovsky
65a Highsted Road, Bishopdale, E-mail: s...@krym.equinox.gen.nz
Christchurch, New Zealand, Earth Fax: (64)(3)358-0320 (Dept.)
Phone: (64)(3)359-3185 (h) (64)(3)358-3399 ext 88-40 (b)
Anil Vijendran
1. Have operator* return a reference.
2. Add a wrapper class around DCMatrix, whose copy constructor and
operator = implement aliased representation using reference counting.
This should work like a charm.
--
Anil
___________________________________________________________________________
Anil K Vijendran USL Box 43007, Lafayette, LA 70504-3007
a...@cacs.usl.edu (318) 232-5502 [H]
Nick Mein
: Consider the following code. I have created a matrix class for
What about:
DCMatrix A(2,3, complex(0.0,0.0));
DCMatrix B(3,4,complex(1.0,0.0));
DCMatrix C; //Default constructor - do nothing
// fill A and B with stuff
C = A;
C *= B;
Not as clear as your code, but no tempories required.
--
Nick Mein
MSc Student
Dept of Computer Science
University of Otago
Dunedin
New Zealand.
David Vandevoorde
Nick Mein <nm...@bifrost.otago.ac.nz> wrote:
>David Hoadley (s84...@minyos.xx.rmit.EDU.AU) wrote:
>: Consider the following code. I have created a matrix class for
>: complex numbers, called DCMatrix, and an operator* function:
>
>: int main()
>: {
>: DCMatrix A(2,3, complex(0.0,0.0));
>: DCMatrix B(3,4,complex(1.0,0.0));
>: DCMatrix C(2,4);
>: // fill A and B with stuff
>: C = A * B;
>: return (0);
>: };
>
>
>: Result is a temporary matrix which I would rather not have, but I
>: could not see how to write operator* without it. anon is another
>: temporary matrix, which I didn't declare.
>
>: Is is possible to implement this without these two temporary matrices?
>: If not, which I fear, can I at least avoid the creation of one of them
>: (presumably anon)?
>
>What about:
>
> DCMatrix A(2,3, complex(0.0,0.0));
> DCMatrix B(3,4,complex(1.0,0.0));
> DCMatrix C; //Default constructor - do nothing
>// fill A and B with stuff
> C = A;
> C *= B;
>
>Not as clear as your code, but no tempories required.
Yes and no. If the meaning of '*' is an "inner product" (as opposed
to elemenwise multiplication) you'll need at least a row or column
worth of temporary storage. There is also a performance penalty in
that the copy of A into C is extraneous.
>
>--
>Nick Mein
>MSc Student
>Dept of Computer Science
>University of Otago
>Dunedin
>New Zealand.
Daveed
Robert Davies
>From: vand...@pleiades.cs.rpi.edu (David Vandevoorde)
>Subject: Re: Can I eliminate these temporary objects?
>Date: 17 Mar 1995 19:36:53 GMT
>In article <3kaqnn$g...@aggedor.rmit.EDU.AU>,
>David Hoadley <s84...@minyos.xx.rmit.EDU.AU> wrote:
>>Consider the following code. I have created a matrix class for
>>complex numbers, called DCMatrix, and an operator* function:
>>Is is possible to implement this without these two temporary matrices?
>I would suggest you take a look at two packages.
>The first one is "NewMat" ("newmat08" is the latest release, I believe)
If you are dealing with only a small number of matrix classes - like no
more than 2 then you can probably do a simpler scheme than
newmat uses. You have two versions of each matrix class; the
usual one and a transient one. Any operation produces the
transient version. Any operation (including =) involving a transient
one can recycle its memory (and must delete it otherwise). This
means all the decisions as to what to do with memory can be done
at compile time. But you need to write a lot of versions of your
various operations. You don't need templates although possibly
templates would help in the hands of a clever person. If I ever
get round to writing a small matrix class, this is the method I
would favour.
A slightly less efficient mechanism is to have a flag attached
to each matrix to say whether it is transient. This reduces the
coding complexity at the expense of an extra operation. This
is one of the tricks used by newmat.
Of course another way of reducing the use of temporaries
is the use of delayed copy. I don't think it is as effective
as the methods I have described, but it is much simpler
and may be sufficent.
Look at the string class in Hansen's C++ answer book to
see how it is done.
Robert
Paul Billings
>
> In article <3kaqnn$g...@aggedor.rmit.EDU.AU>, s84...@minyos.xx.rmit.EDU.AU (David Hoadley) writes:
> |> Consider the following code. I have created a matrix class for
> |> complex numbers, called DCMatrix, and an operator* function:
> |>
> |> int main()
> |> {
> |> DCMatrix A(2,3, complex(0.0,0.0));
> |> DCMatrix B(3,4,complex(1.0,0.0));
> |> DCMatrix C(2,4);
> |> // fill A and B with stuff
> |> C = A * B;
> |> return (0);
> |> };
> |> Is is possible to implement this without these two temporary matrices?
> |> If not, which I fear, can I at least avoid the creation of one of them
> |> (presumably anon)?
The temporaries will probably have to be created, but you don't have
to allocate memory and copy the data each time. For large matrices, this
will affect performance drastically. Check out the concept of a reference
counter. Basically the memory is allocated once. Your matrix will have
a pointer to this data and the number of "references" or "accesses" to the
data. To copy the data, just set the pointer in the second matrix to
the data. In the destructor, just decrease the reference count. If it
goes to 0, delete the memory. Problems arise when you wish to write
to the matrix since writing to matrix A will modify matrix B. In this case,
you must make a copy of the data for matrix A. This technique is called
"copy on write". Most structures that must allocate memory can benefit
from the reference concept. The more advanced C++ books will detail
the concept further and may define a reference class for general purpose
use. I don't know any titles off the top of my head, sorry.
Paul
Jan Reimers
>
>1. Have operator* return a reference.
A reference to WHAT? You can't return a refernce to a matrix created on
the stack because you don't know when it will go out of scope and be
deleted. You can't return a reference to a dynamicaly constructed
object, because then it will never be deleted. At least there is no
garauntee that it will be deleted by the user of operator*.
>2. Add a wrapper class around DCMatrix, whose copy constructor and
>operator = implement aliased representation using reference counting.
>This should work like a charm.
Yes this is much better. How would one access the matrix elements through
the wrapper class WITHOUT a lot of overhead?
>--
>Anil
>
>___________________________________________________________________________
>Anil K Vijendran USL Box 43007, Lafayette, LA 70504-3007
>a...@cacs.usl.edu (318) 232-5502 [H]
--
+--------------------------------------+-------------------------------------+
| Jan N. Reimers, Research Scientist | Sorry, Don't have time to write the |
| Moli Energy (1990) Ltd. B.C. Canada | usual clever stuff in this spot. |
| ja...@molienergy.bc.ca | |
David Vandevoorde
Jan Reimers <ja...@molienergy.bc.ca> wrote:
>In article <AKV.95Ma...@srl03.cacs.usl.edu> a...@cacs.usl.edu writes:
>>
>>1. Have operator* return a reference.
>
>A reference to WHAT? You can't return a refernce to a matrix created on
>the stack because you don't know when it will go out of scope and be
>deleted. You can't return a reference to a dynamicaly constructed
>object, because then it will never be deleted. At least there is no
>garauntee that it will be deleted by the user of operator*.
Indeed.
>
>
>>2. Add a wrapper class around DCMatrix, whose copy constructor and
>>operator = implement aliased representation using reference counting.
>>This should work like a charm.
>
>Yes this is much better. How would one access the matrix elements through
But not good enough :(
>the wrapper class WITHOUT a lot of overhead?
By "wrapping" at compile-time using templates.
Daveed
P.S.: see ftp://ftp.cs.rpi.edu/pub/vandevod/Valarray for details ;^P