home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / lang / scheme / 2821 < prev    next >
Encoding:
Text File  |  1992-12-23  |  4.1 KB  |  127 lines
  1. Newsgroups: comp.lang.scheme
  2. Path: sparky!uunet!think.com!mintaka.lcs.mit.edu!zurich.ai.mit.edu!jaffer
  3. From: jaffer@zurich.ai.mit.edu (Aubrey Jaffer)
  4. Subject: Re: Are interpreters now as fast as compiled code used to be?
  5. In-Reply-To: jbeekman@prodigy.bc.ca's message of 17 Dec 92 19:10:58 GMT
  6. Message-ID: <JAFFER.92Dec23012204@camelot.ai.mit.edu>
  7. Sender: news@mintaka.lcs.mit.edu
  8. Organization: M.I.T. Artificial Intelligence Lab.
  9. References: <4051@mitech.com> <4065@mitech.com> <4066@mitech.com> <4067@mitech.com>
  10.     <1992Dec17.191058.28471@prodigy.bc.ca>
  11. Date: Wed, 23 Dec 1992 06:22:04 GMT
  12. Lines: 113
  13.  
  14. Although SCM now runs faster than this, I think this message is
  15. relevant to the discussion.
  16.  
  17. From: jaffer@zurich.ai.mit.edu (Aubrey Jaffer)
  18. Newsgroups: comp.lang.scheme
  19. Subject: Benchmarking Scheme
  20. Date: 1 May 91 20:38:05 GMT
  21. Distribution: comp.lang.scheme
  22. Organization: M.I.T. Artificial Intelligence Lab.
  23.  
  24. At the end of this message is benchmark code in C and in Scheme.  My
  25. original hope was that computing the ratios of execution time for the
  26. 2 programs would allow me to roughly measure speed of an
  27. implementation independent of the hardware.  There are problems with
  28. this approach.
  29.  
  30. The benchmark programs take an argument and compute that many digits
  31. of pi.  The programs take time proportional to the square of the
  32. number of digits.  This allows one to compensate for widely differing
  33. times of computation.
  34.  
  35. When I measure the times on my 10Mhz 68000 I get:
  36. (pi 100)       takes 33.9 secs (scm2d)
  37. time pi 200    takes 7.1 secs
  38. 33.9/(7.1/4) ==> 19 times slower than C
  39.  
  40. But on kleph.ai.mit.edu (which I think has a 68020) I get:
  41. (pi 100)       takes 6.6 secs (scm2d)
  42. time pi 800    takes 7.6 secs
  43. 6.6/(7.6/64) ==> 56 times slower that C ??!
  44.  
  45. What is going on here?  J. Finger suggests that kleph has an
  46. instruction cache.  That would mean that the C inner loop stays in the
  47. cache while the scm interpreter doesn't.
  48.  
  49. So what are the prospects for machine independent performance
  50. measures?  An algorithm with a more complicated inner loop would keep
  51. the C program out of cache.  But such algorithms tend either to be
  52. artifically lengthened or lack the nice scaling properties of the pi
  53. programs.  Part of the appeal to me of the pi program is that it does
  54. an actual difficult computation with the best code I can devise.
  55. Previously I used an intentionally less that optimal fibonacci.
  56.  
  57. An argument can also be made that the cached figures are more
  58. realistic for everyday programming problems.  This has an interesting
  59. consequence in that the penalty for using interpreters on newer
  60. machines is more severe than on old ones.
  61.  
  62. /*  'Spigot' algorithm origionally due to Stanly Rabinowitz */
  63. /*
  64. main(c,v)
  65. int c;char **v;{
  66.   int n=200,j,m,b=2,k,t,r=1e5;
  67.   long q;
  68.   short *a;
  69.   if(c==2)n=atoi(v[1])/5+1;
  70.   k=m=3.322*n*5;
  71.   a=calloc(1+m,2);
  72.   while(k)a[--k]=2;
  73.   for(a[m]=4;j<n;b=q%r){
  74.     q=0;
  75.     for(k=m;k;){
  76.       q+=a[k]*r;
  77.       t=(2*k+1);
  78.       a[k]=q%t;
  79.       q=q/t;
  80.       q*=k--;}
  81.     printf("%05d%s",b+q/r,++j%10?"  ":"\n");}
  82.   puts("");}
  83. */
  84.  
  85.                        main
  86.  (c,v)int c;char**v;{int n=200,j,m,
  87. b=2,k,t,r=1e5;long q;short*a;if(c==2
  88.  )n=atoi(v[1])/5+1;k=m=3.322*n*5;a=
  89.        calloc(       1+m,2)
  90.        ;while        (k)a[
  91.        --k]=2        ;for(a
  92.        [m]=4;        j<n;b=
  93.        q%r){q        =0;for
  94.        (k=m;k        ;){q+=
  95.        a[k]*r        ;t=(2*
  96.        k+1);         a[k]=q
  97.        %t;q=         q/t;q*
  98.        =k--;}        printf(
  99.       "%05d%s"       ,b+q/r,
  100.       ++j%10?        " ":"\n"
  101.       );}puts         ("");}
  102.   
  103. ===========================================================
  104.  
  105. (define r 100000)
  106. (define (pi n)
  107.   (let* ((n (+ (quotient n 5) 1))
  108.      (m (quotient (* n 5 3322) 1000))
  109.      (a (make-vector (+ 1 m) 2)))
  110.     (vector-set! a m 4)
  111.     (do ((j 1 (+ 1 j))
  112.      (q 0 0)
  113.      (b 2 (remainder q r)))
  114.     ((> j n))
  115.       (do ((k m (- k 1)))
  116.       ((zero? k))
  117.     (set! q (+ q (* (vector-ref a k) r)))
  118.     (let ((t (+ 1 (* 2 k))))
  119.       (vector-set! a k (remainder q t))
  120.       (set! q (* k (quotient q t)))))
  121.       (let ((s (number->string (+ b (quotient q r)))))
  122.     (do ((l (string-length s) (+ 1 l)))
  123.         ((>= l 5) (display s))
  124.       (display #\0)))
  125.       (display (if (zero? (modulo j 10)) #\newline #\ )))
  126.     (newline)))
  127.