[racket-dev] racket/match is broken

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.

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

On Thu, Oct 6, 2011 at 5:56 PM, Robby Findler
<robby at eecs.northwestern.edu> wrote:
> Do we have performance measurements that show the importance of such
> reorderings?
>
> Robby
>
> On Thursday, October 6, 2011, Neil Toronto <neil.toronto at gmail.com> wrote:
>> On 10/06/2011 01:20 PM, Eli Barzilay wrote:
>>>
>>> Just now, Neil Toronto wrote:
>>>>
>>>> On 10/06/2011 12:28 PM, Prabhakar Ragde wrote:
>>>>>
>>>>> On 10/6/11 2:12 PM, Eli Barzilay wrote:
>>>>>
>>>>>> Sam is talking about building the ASTs *while* matching, which is
>>>>>> what Jay was trying to do with uses of `app'. I think that a
>>>>>> teaching context is in particular one where such a thing doesn't
>>>>>> fit -- it obscures the distinction between the side the sexpr
>>>>>> goes into, and the side where an AST comes out.
>>>>>
>>>>> Okay, I see the distinction, and I apologize for not having fully
>>>>> understood Jay's example. I agree that this obscurity is
>>>>> hazardous. I think, though, that I have always assumed
>>>>> left-to-right matching, though I may never have constructed
>>>>> anything that would break if it didn't happen. --PR
>>>>
>>>> I think most people expect branching constructs like 'match' to make
>>>> in-order (left-to-right/depth-first), short-cutting decisions.
>>>> Additionally, the cases themselves do this. So I think the fact that
>>>> the patterns don't is very surprising.
>>>
>>> IIRC, the cases are also reordered to optimize tests -- and that's an
>>> even more important optimization:
>>>
>>>   ->  (define (list?? x) (printf "list-checking ~s\n" x) (list? x))
>>>   ->  (define (one?? x) (printf "one-checking ~s\n" x) (eq? 1 x))
>>>   ->  (match '(1 (2) 3)
>>>        [(list (? one??) 2 3) 1]
>>>        [(list _ (? list??) _) 2]
>>>        [(list (? one??) 20 30) 3])
>>>   list-checking (2)
>>>   2
>>>
>>> and after Jay broke it, you get
>>>
>>>   one-checking 1
>>>   list-checking (2)
>>>   2
>>>
>>> IMO it is perfectly fine to require that stuff used in `match'
>>> patterns is side-effect-free, and therefore cachable and reorderable.
>>
>> Well I'll be darned.
>>
>> I suppose this shows just how deeply I hold assumptions about order and
>> shortcutting.
>>
>> Neil T
>>
>> _________________________________________________
>>  For list-related administrative tasks:
>>  http://lists.racket-lang.org/listinfo/dev
>>
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/dev
>



-- 
sam th
samth at ccs.neu.edu