[racket-dev] racket/match is broken

On Thu, Oct 6, 2011 at 6:32 PM, Robby Findler
<robby at eecs.northwestern.edu> wrote:
> On Thursday, October 6, 2011, Sam Tobin-Hochstadt <samth at ccs.neu.edu> wrote:
>> In Le Fessant and Maranget, ICFP 2001, they have measurements that
>> show a 30% speedup of whole (toy) programs, with a similar but smaller
>> suite of optimizations.
>
> Does match reproduce that speedup?

It's difficult to know how to precisely tell.  Their measurements are
in OCaml which has a different object representation, they compile to
a switch statement on type tags that isn't currently expressible in
Racket, and their benchmarks are no longer available from the URL in
their paper.

However, I would expect to get bigger speedups in Racket in some
cases, because structure field access is slower in Racket than in
OCaml.

Currently, none of the Racket benchmarks exercise `match' heavily.  I
will look into writing some.

Also, what are we comparing against?  A version of `match' that makes
ordering guarantees?  Or that avoids coalescing structure accesses as
well (this is programmer-visible with mutable data and threads)?  What
about the functions referenced by static structure info -- should
those be assumed to be pure?

>> Given the extensibility of `match', the performance difference can be
>> made arbitrarily large.  For example, Eli's example doesn't call the
>> `one??' function, which could take arbitrarily long (imagine a
>> database query).
>
> Match's reordering of the predicates can also slow it down arbitrarily with
> reasoning like that (imaging a predicate that is very fast at saying "no" on
> one element if a list and very slow to say "no" to a different element and
> that predicate is used twice in the same list pattern).
>
> I don't see how that helps us understand the value of reordering the
> patterns.

Consider the following match expression:

(match e
  [(vector (list (? number?) ...) 0) #t]
  [_ #f])

In the usual case, you'd expect that checking the second element of
the vector first would be faster, by arbitrarily much (depending on
the length of the list).  That's the only point I was trying to make
-- I shouldn't have even referenced extensibility.  Of course, in the
presence of chaperones, that can be a pessimization by arbitrarily
much again, but that's not the case to optimize for.
-- 
sam th
samth at ccs.neu.edu