<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> <HTML> <HEAD> <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=gb2312"> <META NAME="Generator" CONTENT="MS Exchange Server version 6.5.7036.0"> <TITLE>RE: [racket] case form implemented with a hash</TITLE> </HEAD> <BODY>  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 (       ((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 [<A HREF="mailto:mflatt@cs.utah.edu">mailto:mflatt@cs.utah.edu</A>] 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 [<A HREF="mailto:mflatt@cs.utah.edu">mailto:mflatt@cs.utah.edu</A>] > 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'. </BODY> </HTML>