[plt-scheme] Timings

I am in the process of implementing various data structures.
One is ordinary sets represented by sorted lists.

Here is the straight implementation of union:

    (define (union2 s1 s2)
      (cond
        [(null? s1) s2]
        [(null? s2) s1]
        [else  (let ([x (car s1)]
                     [y (car s2)])
                 (cond
                   [(< x y) (cons x (union2 s2 (cdr s1)))]
                   [(> x y) (cons y (union2 s1 (cdr s2)))]
                   [else    (cons x (union2 (cdr s1) (cdr s2)))]))]))

Then I noticed that in the cases (< x y) and (> x y) we know
that one of the lists is non-empty, thus it is unncessary to
test for this in the recursive call. This leads to this version:

    (define (union s1 s2)
      ; union1 : set set -> set
      ;  s1 is non-empty
      (define (union1 s1 s2)
        (cond
          [(null? s2) s1]
          [else  (let ([x (car s1)]
                       [y (car s2)])
                   (cond
                     [(< x y) (cons x (union1 s2 (cdr s1)))]
                     [(> x y) (cons y (union1 s1 (cdr s2)))]
                     [else    (cons x (union (cdr s1) (cdr s2)))]))]))
      (if (null? s1)
          s2
          (union1 s1 s2)))

To get some timings I use:

  (define (interval m n)
    (if (> m n)
        '()
        (cons m (interval (add1 m) n))))

> (let ([s1 (interval 1 100000)]
        [s2 (interval 50000 150000)])
    (collect-garbage)
    (time (union2 s1 s2))
    (collect-garbage)
    (time (union s1 s2))
    (void))
cpu time: 3475 real time: 3575 gc time: 0
cpu time: 4176 real time: 4196 gc time: 0

Then I tried:

> (let ([s1 (interval 1 100000)]
        [s2 (interval 50000 150000)])
    (collect-garbage)
    (time (union s1 s2))
    (collect-garbage)
    (time (union2 s1 s2))
    (void))
cpu time: 3125 real time: 3125 gc time: 0
cpu time: 4246 real time: 4267 gc time: 0

... and now I'm confused.

Which union is faster?

--
Jens Axel Søgaard