Re: Realtime cost of call by value

[taltman]

Hi Przemek,

Please find my comments interspersed below:

On Nov 5, 2003 at 1:18pm, Przemek Klosowski wrote:

przeme >There has been a discussion recently about efficient passing of arrays,
przeme >and the discussion quickly moved past the issue at hand ('how to avoid
przeme >needless copying') into syntactical flavors of passing by reference.
przeme >
przeme >My initial reaction to this discussion was that since we have 'by
przeme >value' and 'by reference' parameters in the usual high level languages
przeme >(C/C++, etc) and it looks like it may help Octave, it's worth
przeme >implementing. However, after discussing it some more w/Paul Kienzle, I
przeme >became convinced that it's the wrong way to go about it. The parameter
przeme >passing is a fairly low level issue (c.f. the discussion of scoping in
przeme >Lisp that was pretty esoteric). I think that Very High Level Languages
przeme >(VHLLs) like Octave should attempt to solve problems on the highest
przeme >possible levels of abstraction. In this particular case, the issue is
przeme >the live range of variables, and how it affects data moves; so the

Doing a "live range of variables" type of analysis is something that
one can do as a compiler optimization step, but would be a severe
handicap on an interpreter. 

przeme >solution should be based on analysis of variable's lifetime.
przeme >
przeme >Paul's example (b=3*a; a=[]) was perhaps unfortunate because nobody
przeme >writes code like that; this, to me, obscured his real point, namely
przeme >that the a=[] is really a 'compiler pragma',i.e. a message to Octave
przeme >interpreter that data move optimizations on 'a' are allowed
przeme >(specifically, that we can multiply in place every element of 'a' by
przeme >3, and rename 'a' to 'b'). This is more powerful than the 'ref' approach
przeme >because it benefits the existing code w/o the need to explicitly change
przeme >procedure definitions (not to mention all the changes to the interpreter
przeme >to keep track of references in presence of possibly aliased pointers)

The problem with this kind of analysis is that it doesn't work too
well in interpreted environments, where further mutation and binding
of variables can occur "in the future", i.e., in further statements to
the interpreter. Even in enclosed scripts, calls to "source()" and
"eval()" can make things extremely complicated, especially if they're
passed string variables instead of string literals.

This really works best when you have a static block of code ( no
interpreter, no "source()" or "eval()" ), and you want to optimize
it. In this case, you have complete knowledge and confidence in the
roles the variable plays over the course of its "life".

I don't see how these "interpreter pragmas" would be more powerful;
could you give an example? I guess I'm not following exactly what
you're trying to say. For example, what's the difference between:

b = 3*a;
a = [];

and

b = 3*a;
clear a;

---

The beauty of just adding an additional bit of syntax to the function
definition statement is:

* There's a direct correspondence between this type of reference, and
  the underlying language ( C++ ). Therefore, we can snarf that
  functionality with the minimal amount of redesign.

* It won't break code. Existing code that doesn't use it will simply
  be left alone. Those scripts which can enjoy improved performance by
  utilizing references instead of "copy down" ( and, if the resulting
  mutation of the copied-down variable is needed further, "copy up"
  ), can elect to add a syntactic marker, such as "&".

* Abstraction. Once functions make use of this, functions that call
  them don't need to do anything special, like
  "referencing/dereferencing" prior to a function call. This provides
  a nice layer of abstraction.

* Avoiding "pointers to everything". This would break down even more
  the idea of Octave as a "VHLL".

przeme >
przeme >If one believes that, then one may discuss design and implementation
przeme >issues, like how should the interpreter determine the live range:
przeme > 
przeme > - fully automatically in the global context: I think it's impossible
przeme >   in general if we consider multi-module programs and 'eval'

Sorry, but I'm getting lost in the terminology: what's "multi-module"?
AFAIK, Octave has one global environment / "namespace" aside from
every function's non-nested lexical/static scope. 

przeme >
przeme > - automatically, within current module: perhaps possible, under
przeme >   some restrictions, like no 'eval' use within current module
przeme >
przeme > - automatically, within one or more statements: most generally useful
przeme >   but possibly hard to implement: modification in-place, triggered by
przeme >   overwriting of the variable within few statements
przeme >   
przeme > - using triggering constructs: either comment-like pragmas like
przeme >   OpenMP or C preprocessor constructs, or idioms like a=f(a) or
przeme >   [a,result]=sin(a), or s=sin(discard(a)) or Paul's 'f(a);a=[]':
przeme >   simplest to implement but probably requiring most changes in 
przeme >   the existing .m files

       I think that this is in the end pointing to an Octave
       "sublanguage", where interpreter pragmas & static code allow
       for optimizations. I personally think that in the end this
       would be more work to implement, will bog down the interpreter,
       and that it forces the user to change more code to enjoy the
       speed-ups.

przeme >
przeme >                p

       Just my $0.02,

       ~Tomer



-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------