[racket] Kudos: match and performance

I've just been playing about with writing a quick sort, using partition
(to replace one implemented by two "filter"s).

(define (quick-sort l gt?)
   (if
     (null? l) null
     (call-with-values
      (lambda () (partition (curry gt? (car l)) (cdr l)))
      (lambda (lt-part gt-part)
        (append
         (quick-sort lt-part gt?)
         (cons (car l)
               (quick-sort gt-part gt?)))))))

I thought, looking at the shape of it, that I could change my "if" with
a "match", just to give it a different looking syntax.

(define (quick-sort/match l gt?)
   (match l
     ['() null]
     [(cons hd tl)
     (call-with-values
      (lambda () (partition (curry gt? hd) tl))
      (lambda (lt-part gt-part)
        (append
         (quick-sort/match lt-part gt?)
         (cons hd (quick-sort/match gt-part gt?)))))]))

I wanted to see how much performance that extra syntactic sugar _cost_
me, so I put the effort into timing the functions.

(let ((big-list (build-list 1000000 (lambda (i) (random 100000000)))))
   (time (quick-sort big-list >))
   (time (quick-sort/match big-list >))
   (void))

Er... that can't be right! The second one (with the match) is coming
out 2% faster!

I've just done another run...
    cpu time: 10047 real time: 10046 gc time: 4987
    cpu time: 8158 real time: 8175 gc time: 3259
... 20% faster (although that might be some artifact of the timing).

Looking at the expansion of the match, it matches the pair? (or not),
and then, knowing it's a pair uses unsafe-car or unsafe-cdr.  The
expansion also has a large number of nested (let-values ...), but I
guess the JIT is making short work of those.

I wouldn't be as confident using an unsafe-... in my code as the match
is (since it gets its confidence from being mechanically correct). In
fact, looking at the original code; I'm making an assumption that l is
a list (a pair or null); which is something else that the match will
help pick up, although I'd probably want an _ clause at the end.

This is truly a surprise to me -- not an engineered situation. Which is
a bit annoying, since now I have to rethink how I implement solutions in
racket, since the language now seems to be capable of behaving as if
it's smarter than I am [although the same could probably be said of BF].

Anyway, enough rambling -- I just wished to heap praise on those of
you whose work has combined to make this so.

Yours, much impressed,

Tim

--
| Tim Brown <tim.brown at timb.net> |