[racket] case form implemented with a hash

No I did not try the binary search. It is worthwhile to try it. I'll do. It
should be possible to do so by a macro that first sorts the clauses and then
builds the binary if tree without having to wrap the bodies in procedures.
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'.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20110929/37b6f4f8/attachment.html>