Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sdd.hp.com!hplabs!otter.hpl.hp.com!otter!sfk
From: sfk@otter.hpl.hp.com (Steve Knight)
Newsgroups: comp.lang.scheme
Subject: Re: Re: Order of evaluation (was Re: evaluating () should be an error
Message-ID: <6260003@otter.hpl.hp.com>
Date: 2 Apr 91 10:33:02 GMT
References: <1991Mar26.224805.23381@cs.ubc.ca>
Organization: Hewlett-Packard Laboratories, Bristol, UK.
Lines: 56

Daniel's example of code generation for
    (baz (foo 1) 2 3 (+ 4 (bar 5)))
assumes a very strong interpretation for "insists we evaluate from left to
right".  As a consequence, even integers are evaluated from left to right.

If we take the more relaxed and, it seems to me, more typical view that the
compiler preserves apparent order of evaluation, then we only have one
constraint to worry about -- namely "(foo 1)" is evaluated before "(bar 5)".
We could even dispose of this constraint given that either foo or bar were
known to be side-effect free (or, more generally, side-effect independent).

Under the worst assumption, that foo and bar might interfere with one another,
we get
      load r0,1
      call foo   ;; Assume args are passed in lowest numbered regs.
      load r2,r0 ;; SAVE
      load r0,5
      call bar
      load r1,4
      call +
      load r4,r0 ;; Assume result is returned in r0.
      load r0,r2 ;; RESTORE
      load r1,2
      load r2,3
      call baz
This causes two extra register-to-register instructions.  The overall balance
here is 
	4 calls
	4 load immediates
	4 load registers
Assuming that all instructions take one clock cycle (which is ultra-
pessimistic) this adds on a 20% slowdown.  More typically, this would be
a 10% slowdown, not counting the fact that the cost of this sequence is likely
to be swamped by the costs of full-arithmetic "+" and the contents of "foo"
and "bar".

Examples like this are helpful in that they help to gauge the likely penalty of
a fixed order of evaluation.  Of course, we don't have statistics for the 
likelihood of being able to prove that "foo" and "bar" are independent, which
eliminates the overhead entirely.  

From looking at simple examples of this kind, I've come to the ROUGH estimate
that in development mode there might be an additional 10% slowdown and code 
growth due to fixed order of evaluation (and other omitted optimisations of 
the same type.)  In delivery mode, I reckon that the overall cost will be on 
the order of 1%.  This rough-and-ready estimate assumes some simple 
inter-module information is created and used and modern compiler techniques, 
too.

Because I've encountered problems due to free-order of evaluation of arguments
in industrial programs and have found them unacceptable, and because I find
the efficiency arguments unconvincing, I believe that the argument order 
should be fixed.  An acceptable, though less attractive, alternative would be
a lint-like tool for detecting likely violations.

Steve