[racket] case form implemented with a hash

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'.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20110929/f8aa2f9d/attachment.html>