Know your implementation

How well do you know your language implementation? Below you'll see four different implementations of the same function.

Can you predict which version is fastest?

Too easy? Well, then try not only to pick the fastest, but also to rank them according to speed.

You are welcome to leave a comment, if you try the snippets.

The task is simple: we want to append two linked lists. That is, we'll reimplement the builtin function append, although we'll restrict our-selves to two arguments. The four versions are of course not allowed to use the builtin append.

First version: Building the list in reverse

(define (append1 xs ys)
  (append-rev (reverse xs) ys))

(define (append-rev rev-xs ys)
  (cond
    [(null? rev-xs) ys]
    [else           (append-rev (cdr rev-xs) 
                                (cons (car rev-xs) ys))]))

Second version: Naïve recursion

A naïve, non-tail-recursive solution.

(define (append2 xs ys)
  (cond
    [(null? xs) ys]
    [else (let ([result (append2 (cdr xs) ys)])
            (cons (car xs) result))]))

Third version: Continuation passing style

(define (append3 xs ys)
  (define (append3-k xs ys k)
    (cond
      [(null? xs) (k ys)]
      [else (append3-k (cdr xs) ys
                       (lambda (tail) (k (cons (car xs) tail))))]))
  (append3-k xs ys (lambda (x) x)))

Using side-effects

Let's avoid any unnecessary consing.

(define (for-each-reverse! f xs)
(cond
  [(null? xs) 'done]
  [else (for-each-reverse! f (cdr xs))
        (f (car xs))]))

(define (append4 xs ys)
(let ([result ys])
  (for-each-reverse!
    (lambda (x)
      (set! result (cons x result)))
      xs)
  result))

Benchmarking

And now for the bencmarking. Before each timing, I invoke the garbage collector. In this way garbage produced by test one, doesn't affect the timings of test two.

(define (test n)
 (let ([xs (vector->list (make-vector n))])
   (collect-garbage)
   (time (begin (append1 xs xs) 'done))
   (collect-garbage)
   (time (begin (append2 xs xs) 'done))
   (collect-garbage)
   (time (begin (append3 xs xs) 'done))
   (collect-garbage)
   (time (begin (append4 xs xs) 'done))))

(test 100)
(test 1000)
(test 10000)
(test 100000)
(test 1000000)
(test 2000000)