10% is pretty good for this kind of thing. FWIW. Robby
2011/9/29 Jos Koot <[email protected]>: > 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:[email protected]] > 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:[email protected]] >> 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:[email protected]] >> > 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 > _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
