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

From: AndrevanTonder <andre>
Date: Mon Oct 2 15:16:05 2006

On Mon, 2 Oct 2006, Abdulaziz Ghuloum wrote:

> On Oct 1, 2006, at 5:08 PM, AndrevanTonder wrote:
>>
>> Requirement of cycle detection in list procedures
>> may be too onerous, potential performance problem.
>> procedures rather significantly.
>
> 1. The claim of "adverse global effects on performance"
> needs to be supported.

Okay, here is an (admittedly small) set of benchmarks, done on a LENGTH
procedure with and without cycle detection, run on Intel. The definition of
these procedures are at the end.

                no cycle detection with cycle detection % factor
                ------------------ -------------------- --------
Larceny (compiled): 110 140 127%
Petite (interpr): 125 390 312%
MzScheme (compiled): 141 172 122%

The best of these cases exhibits a slowdown of about 20%. This may be below
the threshold for some users, above it for others. Many compiler writers
find it worthwhile to implement all kinds of optimizations that have less than
20% significance.

(define (length-regular list)
   (define (length-acc list acc)
     (if (null? list)
         acc
         (length-acc (cdr list) (+ 1 acc))))
   (length-acc list 0))

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

(define (create n)
   (if (= n 0)
       '()
       (cons #t (create (- n 1)))))

(define million (create 1000000))

(time
  (length-regular million))

(time
  (length-circ million))

Cheers
Andre
Received on Mon Oct 02 2006 - 15:13:13 UTC