 |
Newsgroups: comp.lang.scheme
From: luc...@math.purdue.edu (Brad Lucier)
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 So far, so good. Gambit is faster, but not by much. > different operations cost (among other things). Notes are at the bottom. > Formula CPU times (ms) > (expt 3 1000000) ; a 930 4700 > (* 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 Nothing too strange here, but there is a factor of < 3 in Gambit and > > (sqrt c) ; 14080 57240 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 No surprises. > (fib 100001) ; b 4450 7790 > (gcd a b) ; 27580 88780 gcd is based on a lot of quotients, but here the gcd times for > (gcd a b) ; a=3^100000, b=2^100000 23380 56230 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 These two are interesting. Here we have an exponential running in the > (expt2 3 1000000) ; note 3 6510 6290 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 A factor of 10 between a Scheme bignum implementation (Gambit) and a > (expt 10 10000000); a 42770 486200 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 http://groups.google.com/groups?q=expt+group:comp.lang.scheme+author:... I took the opportunity at that time to add this to Gambit. This > (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 These two, where mzscheme is about 40 times slower than Gambit, tell > (expt 3/5 10000) ; b 10 370 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 > (* 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)) and instead uses the naive (* p/q r/s) => (make-rational (quotient (* p r) (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)) and no gcd is necessary. Again, this is very useful in computing > (factorial 10000) ; note 5 1630 1210 I'm not tremendously happy with Gambit's performance here; before > (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 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 Here's another small point related to this computation---I looked at > (pi-brent-salamin) ; beta^k=2^33219 902040 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 available separately. (Perhaps it is, nobody answered when I asked how to do exact integer square root in mzscheme.) So I would characterize mzscheme's bignum and ratnum implementation as This, to me, indicates a design problem that cannot be fixed just by Brad You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
| |||||||||||||