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

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

This page is part of the web mail archives of SRFI 77 from before July 7th, 2015. The new archives for SRFI 77 contain all messages, not just those from before July 7th, 2015.

 | 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)))?