home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / lang / scheme / 2784 < prev    next >
Encoding:
Internet Message Format  |  1992-12-17  |  2.7 KB
  1. Path: sparky!uunet!mitech!gjc
  2. From: gjc@mitech.com (George J. Carrette)
  3. Newsgroups: comp.lang.scheme
  4. Subject: Summary. Interpreters are faster than I thought
  5. Message-ID: <4094@mitech.com>
  6. Date: 17 Dec 92 12:21:03 GMT
  7. Organization: Mitech Corporation, Concord MA
  8. Lines: 93
  9.  
  10. A good deal of private email has come in on the speed of
  11. interpreters issue. Most with benchmarks of interpreters
  12. that are faster than SIOD. In fact I was most impressed by
  13. some results with SCM that had (standard-fib 20) running a
  14. good 3.8 times faster, and SCM is still an s-expression
  15. interpreter although it has been extended with some tricks
  16. that remind me a bit of the pdp-10 maclisp coded scheme
  17. interpreter that was used at MIT around 1980 for the
  18. last 6.031 classes ever, and I think the first 6.001 classes.
  19.  
  20. In summary. Some scheme interpreters are pretty close to being only 3
  21. times slower than compiled code. Therefore interpreters are indeed
  22. as fast or faster than compiled code on machines from a couple years
  23. ago.
  24.  
  25. -----------------------------
  26.  
  27. FIB has always been a favorite benchmark of many people, probably
  28. because it is easy to count operations but not entirely trivial.
  29.  
  30. However, it tends to bring up the issue of numeric optimizations,
  31. which can be hairy and distracting.
  32.  
  33. So here is another version of fib that uses binary arithmetic
  34. implemented as lists of symbols. It runs around 50 times slower
  35. than using built-in arithmetic. 
  36.  
  37. ;-*-mode:lisp-*-
  38. ; a fib benchmark that uses binary arithmetic.
  39. ; 16-DEC-92 George Carrette. GJC@MITECH.COM
  40. ; Wanted a benchmark that avoided built-in numbers
  41. ; and that did more work.
  42. ;
  43. ; Benchmark: (b->number (b-fib '(A A B A B))) => 6765
  44. ;
  45. ; Note: (b->number '(A A B A B)) => 20
  46. ;
  47. ; (C) Copyright 1992 George Carrette. As described in SLIB.C
  48.  
  49. (define (b-fib x)
  50.   (if (b< x '(A B))
  51.       x
  52.       (b+ (b-fib (b- x '(B)))
  53.           (b-fib (b- x '(A B))))))
  54.  
  55. (define (b->number x)
  56.   (if (null? x)
  57.       0
  58.     (+ (if (eq? (car x) 'B) 1 0)
  59.        (* 2 (b->number (cdr x))))))
  60.  
  61. (define (b+ x y)
  62.   (if (null? x)
  63.       y
  64.     (if (null? y)
  65.     x
  66.       (if (eq? (car x) 'A)
  67.       (cons (car y) (b+ (cdr x) (cdr y)))
  68.     (if (eq? (car y) 'A)
  69.         (cons 'B (b+ (cdr x) (cdr y)))
  70.       (cons 'A (b+ (b+ '(B) (cdr x)) (cdr y))))))))
  71.  
  72. (define (b- x y)
  73.   (if (null? y)
  74.       x
  75.     (if (null? x)
  76.     (error "negative number")
  77.       (if (eq? (car y) 'A)
  78.       (bA-cons (car x) (b- (cdr x) (cdr y)))
  79.     (if (eq? (car x) 'B)
  80.         (bA-cons (if (eq? (car y) 'B) 'A 'B) (b- (cdr x) (cdr y)))
  81.       (cons 'B (b- (b- (cdr x) '(B)) (cdr y))))))))
  82.  
  83. (define (bA-cons x l)
  84.   (if (and (null? l) (eq? x 'A))
  85.       '()
  86.     (cons x l)))
  87.  
  88. (define (b< x y)
  89.   (if (null? x)
  90.       (not (null? y))
  91.     (or (b< (cdr x) (cdr y))
  92.     (if (equal? (cdr x) (cdr y))
  93.         (if (eq? (car x) 'A)
  94.         (eq? (car y) 'B))))))
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.