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

From: AndrevanTonder <andre>
Date: Mon Oct 2 21:13:53 2006

On Mon, 2 Oct 2006, AndrevanTonder wrote:

> Amazingly, the r6rs cycle-checking version is consistently faster by
> about 10%. I would imagine the reason for this is that the loop is unrolled
> with respect to the r5rs version.

Correction: I really should have compared the r6rs version with a similarly
unrolled version of the r5rs version (below). Upon doing this, I find that the
r5rs and r6rs times are indistinguishable in Stalin. This agrees with Kent
Dybvig's experience in Chez.

So my formal comment based on performance was unfounded.

(not to deny that there may still be other issues, as Shiro Kawai's map example
illustrated).

Andre

;; unrolled r5rs length:

(define length-regular
    (lambda (clist)
      (define length-0
        (lambda (clist acc)
          (if (null? clist)
              acc
              (let ((acc (+ 1 acc)) (clist (cdr clist)))
                (if (null? clist)
                    acc
                    (length-0 (cdr clist) (+ 1 acc)))))))
      (length-0 clist 0)))

;; unrolled r6rs length:

(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 "Circular list"))
                (if (null? clist)
                    acc
                    (length-0 (cdr clist) (cdr tortoise) (+ 1 acc)))))))
      (length-0 clist clist 0)))
Received on Mon Oct 02 2006 - 21:11:12 UTC