[racket-dev] racket/match is broken

On Thu, Oct 6, 2011 at 6:03 PM, Sam Tobin-Hochstadt <samth at ccs.neu.edu> wrote:
> 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?

I think it makes sense to ask 'what is the effect of turning off and
on the reordering optimizations?' (ala Jay's edit) ask that is
apparently at least somewhat surprising. It seems like it would make
for a much more compelling argument for why it is that way if there
are at least some numbers to back it up.

(Like you could explain this in the docs better in that case.)

>>> 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.

Agreed, completely.

Robby