[racket] case form implemented with a hash

10% is pretty good for this kind of thing. FWIW.

Robby

2011/9/29 Jos Koot <jos.koot at telefonica.net>:
> I tried the binary search. Speed up in my case about 10%. Not very
> spectacular.
> The macro is a dragon.
> Jos
>
> -----Original Message-----
> From: Matthew Flatt [mailto:mflatt at cs.utah.edu]
> Sent: jueves, 29 de septiembre de 2011 15:08
> To: Jos Koot
> Cc: 'Racket-users'
> Subject: RE: [racket] case form implemented with a hash
>
> I don't see Clinger's technique as useful only for a small number of
> clauses. Although I'm not sure that 86 clauses is enough to tell the
> difference, just to double-check: did you try a binary search instead
> of a hash table?
>
> That is, instead of
>
>   (if (= x 0)
>       e0
>       (if (= x 1)
>           e1
>           (if (= x 2)
>               e2
>               e3)))
>
> using
>
>  (if (x . < . 2)
>      (if (x . < . 1)
>          e0
>          e1)
>      (if (x . < . 3)
>          e2
>          e3))
>
> ?
>
> At Thu, 29 Sep 2011 12:25:16 +0200, "Jos Koot" wrote:
>> Thanks Matthew.
>> I read the paper.
>> In my case I have a case form which dispatches on a character, 86
>> different
>> ones. Therefore I can dispatch by means of a vector. However, almost every
>> character has its own clause and therefore dispatching on the index of the
>> character would give no speed up. I already tried a hash-table and a
>> vector
>> (making sure it is computed once only) The values in the table/vector are
>> procedures that run the body of a clause. The vector is used as follows:
>>
>> (define (parse-fmt-instr parser-state) ; Parses one single instruction.
>>  (skip-white-fmt-and-commas parser-state)
>>  (let ((char (pop-fmt-char parser-state #f)))
>>   (and char
>>    (if (char=? char #\λ) call-proc-instr
>>     (let ((i (char->integer char)))
>>      (if (< i 128)
>>       ((vector-ref parser-table i) parser-state char)
>>       (fmt-error parser-state)))))))
>>
>> However, as you predicted, I found no speed up. With a hash table in some
>> cases even a slow down.
>> The gain in speed of dispatching seems to be destroyed by the extra
>> procedure call.
>> I think Clinger's paper is particularly useful for case forms wih many
>> keys
>> but few clauses.
>> Thanks for your help.
>> Jos
>>
>> -----Original Message-----
>> From: Matthew Flatt [mailto:mflatt at cs.utah.edu]
>> Sent: miércoles, 28 de septiembre de 2011 22:59
>> To: Jos Koot
>> Cc: 'Racket-users'
>> Subject: RE: [racket] case form implemented with a hash
>>
>> I had in mind the comment on page 64, bottom right, but I see that it's
>> a smaller comment than in my memory.
>>
>> Overall, I think it will work better to use a hash table to go from a
>> value to an index, and then use a binary search on the index as in
>> Clinger's paper. Indirect dispatch via thunks in a hash table will most
>> likely be slower.
>>
>> At Wed, 28 Sep 2011 22:55:08 +0200, "Jos Koot" wrote:
>> > Hi Hatthew,
>> > I am still trying to implement 'case' by means of a hash.
>> > Can you give me a more specific pointer. I followed your pointer but did
>> not
>> > see anything relevant to my question.
>> > Jos
>> >
>> > -----Original Message-----
>> > From: Matthew Flatt [mailto:mflatt at cs.utah.edu]
>> > Sent: miércoles, 28 de septiembre de 2011 22:20
>> > To: Jos Koot
>> > Cc: 'Racket-users'
>> > Subject: Re: [racket] case form implemented with a hash
>> >
>> > At Wed, 28 Sep 2011 22:08:44 +0200, "Jos Koot" wrote:
>> > > By inspection with the macro stepper I found that case forms are
>> expanded
>> > to
>> > > nested if-forms. For case forms with many clauses, this may be
>> > inefficient.
>> > > I have tried to prepare a hash-case form using a hash table in order
>> > > to
>> > > select the desired clause more efficiently. So far my attempts failed.
>> > > I
>> > am
>> > > still trying. However, has anybody else on this list thought of using
>> > > a
>> > hash
>> > > for case forms with many clauses? Does it exist? If not, would anyone
>> > > be
>> > > interested in a hash-case form that has the same shape as a case-form,
>> but
>> > > uses a hash-table to select the appropriate clause? The hash table
>> should
>> > be
>> > > a map onto thunks and macro hash-case simply would have to retrieve
>> > > the
>> > > thunk and call it.
>> >
>> > See "Rapid Case Dispatch in Scheme", Clinger, Scheme'06.
>> >
>> > If you implement a revised `case' that consistently works better, then
>> > I'd be happy to use it as a replacement for the current `case'.
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/users
>