[r6rs-discuss] [Formal] Requirement to detect circular lists - benchmarks

From: dyb_at_cs.indiana.edu <dyb>
Date: Mon Oct 2 16:19:31 2006

In Chez Scheme, with full optimization enabled (as one would do for
built-in primitives), the difference is totally in the noise, with the
circ version beating the regular version as often as not.

You might be testing the compiler's ability to inline procedures like
length-1 into length-0. You might try the following instead, derived
by running Chez Scheme's expand/optimize on your length-circ:

(define length-circ
  (lambda (clist)
    (define length-0
      (lambda (clist tortoise acc)
        (if (null? clist)
            acc
            (let ([acc (+ 1 acc)] [clist (cdr clist)])
              (if (eq? clist tortoise)
                  (error 'length-circ "Circular list" clist))
              (if (null? clist)
                  acc
                  (length-0 (cdr clist) (cdr tortoise) (+ 1 acc)))))))
    (length-0 clist clist 0)))

> (define million (create 1000000))

You might also use the following to test multiple calls with lists shorter
than 1000000. I suspect that million-length lists are not the norm.

  (define (test m n)
    (write m) (display " iterations list of length ") (write n) (newline)
    (let ([ls (create n)])
      (define (test-one p)
        (time (let f ([m m])
                (unless (= m 0)
                  (p ls)
                  (f (- m 1))))))
      (test-one length-regular)
      (test-one length-circ)))

  (test 10 1000000)
  (test 100 100000)
  (test 1000 10000)
  (test 10000 1000)
  (test 100000 100)
  (test 1000000 10)
  (test 10000000 1)

Again, in each case the difference is in the noise with Chez Scheme.

Kent
Received on Mon Oct 02 2006 - 16:19:13 UTC