The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Message from discussion Whither now, Oh Scheme.

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Nov 10 2003, 1:33 pm
Newsgroups: comp.lang.scheme
Date: 10 Nov 2003 10:33:12 -0800
Local: Mon, Nov 10 2003 1:33 pm
Subject: Re: Whither now, Oh Scheme.
I'll be more explicit here about what these computations tell me about
mzscheme's implementation of bignums and rationals and mzscheme's
integration of gmp into its runtime library.  I haven't looked much at
mzscheme's code; perhaps my comments will help mzscheme and other
implementors with their runtime implementations.

b...@cs.purdue.edu (Bradley J Lucier) wrote in message <news:bnuhtk\$9er@arthur.cs.purdue.edu>...

> Like I said, this is code from some notes to tell math students how much
> different operations cost (among other things).  Notes are at the bottom.

> Formula                                               CPU times (ms)
>                                             beta Gambit-C      mzscheme 205

> (expt 3 1000000)  ; a                             930              4700
> (expt 3 1000001)  ; b                            1610              4970

So far, so good.  Gambit is faster, but not by much.

> (* a a)           ; c                            1170              3150

Here things start to look strange.  mzscheme's multiplication is
faster than its exponential, but in Gambit-C it's slower.  We'll get
back to this later.

> (* a b)           ;                              1640              4660

Similar effect, but smaller.

> (quotient c a)    ;                              6960             10780
> (sqrt c)          ;                             14080             57240

Nothing too strange here, but there is a factor of < 3 in Gambit and >
5 in mzscheme comparing (sqrt c) to (quotient c a), so it seems that
mzscheme's sqrt implementation could be improved.

> (fib 100000)      ; a, note 1                    4280              7560
> (fib 100001)      ; b                            4450              7790

No surprises.

> (gcd a b)         ;                             27580             88780
> (gcd a b)         ; a=3^100000, b=2^100000      23380             56230

gcd is based on a lot of quotients, but here the gcd times for
Gambit-C are < 4 times (quotient c a), and in mzscheme they can be > 8
times (quotient c a), so it seems again that mzscheme's gcd code is
not tremendously good.

> (expt1 3 1000000) ; note 2                        920              1770
> (expt2 3 1000000) ; note 3                       6510              6290

These two are interesting.  Here we have an exponential running in the
interpreter (expt1) that's almost three times as fast as mzscheme's
compiled runtime version of expt.  This shouldn't happen; mzscheme's
integer exponential should at the least be replaced by expt1.

> (* a a)           ; a=3^1000000                  1180              2950
> (expt 10 10000000); a                           42770            486200

A factor of 10 between a Scheme bignum implementation (Gambit) and a
compiled C bignum implementation (mzscheme) should not be acceptable.
I can't tell why this arises, except perhaps that mzscheme's basic
expt routine is not based on expt1.

> (expt 2 10000000) ; b                             990             70300

Here we have a factor of 70 difference in speed.  This tells me that
mzscheme does not special case either multiplication by a number with
many low-order zero bits or exponential of such a number.  This is not
really acceptable in a runtime that goes to great lengths to use fast
algorithms for other operations.

I was surprised by this a few months ago with the Gambit-C bignum
implementation and talked in this post about how a naive
multiplication algorithm can compute this in O(N) time while a "fast"
FFT-based algorithm takes O(N log N) time for the same thing:

I took the opportunity at that time to add this to Gambit.  This
implementors certainly didn't follow up on it.

> (quotient a b)    ;                               140           3169230

Here there is a time difference of over 2000; dividing by a number
with many low-order bits zero should also be fast using a grade school
algorithm.  And this is useful for fixed-point arithmetic computations
to high precision.

> (expt 2/3 10000)  ; a                               0               130
> (expt 3/5 10000)  ; b                              10               370

These two, where mzscheme is about 40 times slower than Gambit, tell
me that the mzscheme runtime probably doesn't use the fact that

(expt p/q n) = (make-rational (expt p n) (expt q n))

where you don't have to do a gcd to get things in lowest form.  My
notes talk about computing with power series, where this is important.

> (* a b)           ;                               280               390

Doesn't tell you much, but coupled with the previous two means that
mzscheme's runtime probably does not use the formula

(* p/q r/s) => (make-rational (* (quotient p (gcd p s))
(quotient r (gcd r q)))
(* (quotient q (gcd r q))
(quotient s (gcd p s))))

(* p/q r/s) => (make-rational (quotient (* p r) (gcd (* p r) (* q s)))
(quotient (* q s) (gcd (* p r) (* q
s))))

> (fib 1000)        ; note 4                         10              2790

This time difference of about 300 tells me that mzscheme does not use
that

(+ n p/q) = (make-rational (+ p (* n q))
q)

and no gcd is necessary.  Again, this is very useful in computing
power series using binary splitting.

> (factorial 10000) ; note 5                       1630              1210
> (partial-factorial 0 10000) ; note 6              170               160
> (binary-splitting-compute-e 1000) ; note 7        980               400
> (naive-compute-e 1000) ; note 8                142970             51520
> (binary-splitting-compute-pi 1000) ; note 9      2070              1130

I'm not tremendously happy with Gambit's performance here; before
looking at the runtime, however, I'd like to compile both to see if
the interpreter speed is masking the time of the runtime.  But I don't
really want to bother figuring out how to compile code in mzscheme.

> (pi-brent-salamin) ; n. 10, beta^k=10^1000000 1345230
> (pi-brent-salamin) ; beta^k=2^33219            902040

Here's another small point related to this computation---I looked at
the mzscheme runtime to see if exact integer square root was available
as a separate routine.  It is, as a C routine, but there doesn't seem
to be an associated scheme routine.  This is an important operation,
is invoked in (sqrt n) if n is a perfect square, and if you're going
to have a fast implementation of it, which mzscheme has, it should be
how to do exact integer square root in mzscheme.)

So I would characterize mzscheme's bignum and ratnum implementation as
one where they go to great lengths to do some things quickly, probably
within a constant of best possible, by using gmp, and at the same time
do not implement simple algorithms that in certain special cases that
come up quite often in practice can speed performance by a factor of
100s to 1000s.  If I found one such problem it would be one thing,
something that was overlooked; instead, with so many such problems, it
seems that little was done beyond "bolting gmp onto this side of"
mzscheme.

This, to me, indicates a design problem that cannot be fixed just by
going back and adding the few hundred lines of code to implement the
changes I suggested above.  Design is not about fixing bugs and