Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!leah!bingvaxu!sunybcs!oswego!rocky.oswego.edu!dl From: dl@rocky.oswego.edu (Doug Lea) Newsgroups: comp.lang.c++ Subject: Re: Generating temporaries Message-ID: <1179@oswego.Oswego.EDU> Date: 5 Apr 89 15:13:14 GMT References: <7.UUL1.2#261@persoft.UUCP> Sender: news@oswego.Oswego.EDU Reply-To: dl@rocky.oswego.edu.UUCP (Doug Lea) Organization: SUNY, Collego at Oswego Lines: 177 Managing temporaries in expression-oriented C++ classes is hard. None of the kinds of solutions I know of works in a way that everyone thinks is entirely satisfactory. I believe the reason for this lies in the fact that C++ does not (and perhaps can not (and perhaps should not!)) support the kinds of programmer-specified expression analyses required in order to translate `functional' construction-oriented code dealing with arbitrary programmer-defined classes into the object-oriented programming model that C++ otherwise emphasizes. Let me illustrate with a mostly `generic' example. (Pretending that `M' stands for `Matrix' would not hurt here though!) class M { desc_type desc; data_type* data; public: M() { quickly_get_into_a_legal_default_state(); } M(M& y) { copy_desc_and_data(y); } void operator = (M& y) { kill_data(); copy_desc_and_data(y); } void add(M& a, M& b); // add a and b into *this (i.e., *this=a+b) void mul(M& a, M& b) // similarly multiply a by b into *this M operator + (M& b) { M res; res.add(*this, b); return res; } M operator * (M& b) { M res; res.mul(*this, b); return res; } }; void print(M&); // just to have a fn that uses M's Now consider the user code, void f() { M a, b, c, d, e; // ... // do some things with a, b, c, d, e // ... a = b + c * d + e; print(a); print(d); } This is compiled into something equivalent to void f2() { // ... M t1; t1.mul(c, d); M t2; t2.add(b, t1); M t3; t3.add(t2, e); a = t3; // ... } (It is not exactly equivalent to f(), since t1, t2, and t3, have lifetimes to the end of f2(), but only to the end of the expression in f().) However, anyone who wanted to write a substantially faster version of this could do it via void f3() { // ... a.mul(c, d); c.add(b, a); a.add(c, e); // ... } which takes advantage of (1) The fact that `a' can be used to hold partial calculations during the course of evaluation, since it is not otherwise used in the expression (2) The fact that `c' can be reused as a temporary, since it is not used subsequently in f(); (3) The fact that the final copy into `a' can be avoided by using it as the destination of the final operation. In other examples, additional, similar analyses could have been performed in order to further simplify things, by e.g., reusing common subexpressions, taking advantage of the commutativity of addition, and so on. Now, if f() were dealing with simple builtin int's rather than objects of type M, a good optimizing compiler generating 3-address assembly code (like for a Vax) would have discovered all of this on its own, and would have translated f() into the assembler analog of f3(). However, there is no way to tell C++ about such optimizations, because, among many other things, M::operator +(M&) is not obligated to behave `plus-like' at all. Here are some things you can do about all this: First is to encourage programmers to program in the idiom that is best supported by the language. i.e., in an object-oriented, procedural style. A good-enough caricature of object-oriented programming is one in which relatively few objects are `born', they undergo series of mutations during their lifetimes, then they die. This notion is less than fully compatible with the caricature of expression oriented programming in which values are created and passed around, without ever being mutated, in order to construct new values. Programming in this fashion has all the disadvantages and advantages of programming in assembly language versus programming in, say, `pure' Lisp or ML: It is less aesthetically pleasing to most people, places more responsibility for temporary management, evaluation order, etc., on the programmer, and encourages trickery (or at least non-obvious, difficult-to-verify coding techniques), but on the other hand, allows much fuller specification and control, and generates code that can be almost arbitrarily more time and space efficient. In a sense, designing one of these `arithmetic-type' classes in a way that supports this style is like designing your own 1-, 2-, and 3-address special-purpose assembly language. One can even go a bit further by supporting a mechanism for programmers to specifically indicate that variables can be `scrapped' and reused as temporaries inside procedures (So, for example, `M r; r.add(a, scrap(b));' could then be performed by allowing r to `steal' b's data if necessary during the calculation), along with a few similar kinds of constructs. On the other hand, there is no reason for a class designer *not* to provide operator syntax as `syntactic sugar' on top of the procedural base: It allows programmers to write code in a form more closely related to their conceptual framework, but at the same time providing a mechanism (via the procedural versions) to fine-tune such code if they so desire (`Make it right, *then* make it fast', as they say). It is hard to ask for too much more, except to try to penalize all programmers as little as possible for the mere act of constructing new objects via functions, by fine-tuning C++ itself to more gracefully and efficiently handle such constructions. Things like taking advantage of X(X&) constructor idempotency via elision, supporting named returned values, and allowing programmers to declare functions as `const' to indicate that they are free of side-effects all help here (and are all implemented as `experimental extensions' in g++-1.34.2). It is also possible to use variations of shadow `temp' classes and/or reference counting techniques -- each can eliminate some degree of redundant copying and promote space reuse in the course of computing expressions. While I have used several such strategies, my current feeling is that since these techniques cannot be implemented so as to guarantee anything close to optimal expression evaluation, and thus lull users into the false impression that they need not worry about such things, since their use makes otherwise transparent class designs utterly baffling, and since they have occasionally surprising side-effects to the unwary, they are rarely worth doing. (Oh, one thing that does not work at all is to have something like M::operator+(M&) return a reference to a single static `temp' variable. This would fail for `a = (b + c) * (d + e);' which requires 2 temporaries.) Finally, one could really solve the whole problem by establishing a zillion #pragma's in C++ that could tell a C++ compiler everything it might ever need to know about `M' and its constituent operations so that it could perform expression analysis on its own. This looks very difficult, but is perhaps worth contemplating in a slightly more tractable guise: Those people who do not wish to break from expression-oriented programming styles in C++ might want to try writing special preprocessors for these kinds of classes, that translate expression code into procedural/oo code, in order to scope out the kinds of issues involved. As Stephen Pope indicated, many of these ideas can someday be seen in the libg++ Matrix package, that will be ready RSN. (Thanks to Stephen, as well as others for helping me get some of these things straight!) -Doug Doug Lea, Computer Science Dept., SUNY Oswego, Oswego, NY, 13126 (315)341-2367 email: dl@rocky.oswego.edu or dl%rocky.oswego.edu@nisc.nyser.net UUCP :...cornell!devvax!oswego!dl or ...rutgers!sunybcs!oswego!dl