[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: straw-man [was Re: arithmetic issues]



 | From: William D Clinger <will@xxxxxxxxxxx>
 | Date: Wed, 18 Jan 2006 00:53:56 -0500
 | 
 | Aubrey Jaffer wrote:
 | > "Branch Prediction and Interpreter Speed"
 | > <http://swiss.csail.mit.edu/~jaffer/CNS/interpreter-branch>
 | 
 | The first two paragraphs of that article's conclusion read as follows:
 | > For an interpreter, using branch prediction to prevent speculative
 | > fetches can make generic arithmetic operations as fast as
 | > typed-restricted ones.
 | >
 | > As a result, the SRFI-77 type-specific duplicate arithmetic
 | > functions have motivation only for Scheme compilers. Type
 | > information for compiling is commonly supplied thorugh type
 | > declarations. It is incumbent upon SRFI-77 to justify its
 | > approach versus type declarations, which it doesn't mention.
 | 
 | That first paragraph is moderately interesting, but is not
 | particularly relevant to SRFI-77.  It appears to me that
 | the second paragraph implicitly rests on three questionable
 | assumptions:
 | 
 | 1.  Speedups that are achievable only by compilers are not
 | particularly important.
 | 
 | Assumption 1 does not require a response.

There is a constituency within the Scheme community which doesn't use
compilers.  Doing violence to the language solely in support of
compilers has no upside for this constituency.

 | 2.  Speed is the primary rationale for the type-specific
 | operations described in SRFI-77.

 | Assumption 2 is, in my view, false.  In my view, the primary
 | rationale for the type-specific operations is to improve the
 | portability and predictability of Scheme code.  The fixnum
 | and flonum operations do that by providing a portable base
 | for a portable implementation of the full numeric tower.
 | This will allow Scheme programmers to use generic arithmetic
 | without worrying about implementations that don't provide the
 | full tower, and the fixnum-specific operations will allow
 | those who are already using fixnum-specific operations or
 | implementations to do so more portably.  The primary rationale
 | for the other type-specific operations is to address some of
 | the portability and predictability issues that were raised
 | in the paper by Egner et al.

The words "efficient", "efficiency", and "faster" appear 16 times in
srfi-77.  Its abstract states:

  Moreover, the R5RS generic arithmetic is difficult to implement as
  efficiently as purely fixnum or purely flonum arithmetic.

"Interpreter-branch" disproves this asserertion as far as interpreters
with immediate fixnums and boxed numbers are concerned.

The section "Recommendations":

  To improve the effectiveness of flow analysis and to improve the
  efficiency of arithmetic, I recommend that the R6RS:

      * add fixnum-specific operations, e.g. fx+

      * add flonum-specific operations, e.g. fl+

      * change the definition of real numbers so that a complex number
	is real if and only if its imaginary part is an exact zero

      * change the interpretation of literals accordingly, e.g. so
	`(imag-part 2.0)' is an exact zero

SRFI-77 talks about efficiency as though it is obvious which practices
will run fast and which won't.  For CPUs performing speculative
execution, such claims are not merely unsubstantiated; they are
probably wrong.  Attention to branch prediction may well eliminate the
speed penalty for arithmetic type dispatch compiling some programs.

 | 3.  The common way of doing things is the best way to do
 | them in Scheme.

Although the words "efficient", "efficiency", and "faster" appear 16
times in SRFI-77, the word "declaration" does not appear.  It is
unreasonable to propose sweeping changes without mention of and
comparison to the relevant precedents.

 | As for assumption 3, type declarations cannot address the
 | portability and predictability issues unless implementations
 | are required to interpret those declarations in a consistent
 | way.

You seem to be making an assumption that complete arithmetic
reproducibility across implementations is desirable to all Scheme
users.  Unpredictability in a program indicates poor numerical
conditioning.  Such programs will behave badly for some inputs or
minor changes.  Having reproducibility across implementations does not
make them less brittle; it only masks the problem until the program is
used or changed by others.  Implementations behaving differently has
been useful in exposing order-of-evaluation dependencies and numerical
conditioning bugs in JACAL, a symbolic mathematics system.

 | Given the expectations created by Common Lisp, many Scheme
 | programmers would make the mistake of thinking that type
 | declarations are for performance, and that interpreters are free to
 | ignore them.  Some implementors might make the same mistakes,
 | especially when you consider that requiring implementations to pay
 | attention to type declarations is likely to make interpreters
 | slower, not faster.
 | 
 | By the way, when speed is a goal, the Common Lisp experience
 | suggests that type declarations are often less effective than
 | type-specific operations, mainly because programmers would
 | rather write and read (fx+ (foo x) (baz y)) than
 | (the fixnum (+ (the fixnum (foo x)) (the fixnum (baz y)))).

What about (* (the fixnum (foo x)) (the flonum (baz y)))?