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

[AndrevanTonder]

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