<!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>
<!-- Converted from text/rtf format -->

<P><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">I tried the binary search. Speed up in my case about 10%. Not very spectacular.</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">The macro is a dragon.</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">Jos </FONT></SPAN>
</P>

<P><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">-----Original Message-----</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">From: Matthew Flatt [</FONT></SPAN><A HREF="mailto:mflatt@cs.utah.edu"><SPAN LANG="es"><U><FONT COLOR="#0000FF" SIZE=2 FACE="Courier New">mailto:mflatt@cs.utah.edu</FONT></U></SPAN></A><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">] </FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">Sent: jueves, 29 de septiembre de 2011 15:08</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">To: Jos Koot</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">Cc: 'Racket-users'</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">Subject: RE: [racket] case form implemented with a hash</FONT></SPAN>
</P>

<P><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">I don't see Clinger's technique as useful only for a small number of</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">clauses. Although I'm not sure that 86 clauses is enough to tell the</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">difference, just to double-check: did you try a binary search instead</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">of a hash table?</FONT></SPAN>
</P>

<P><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">That is, instead of</FONT></SPAN>
</P>

<P><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&nbsp; (if (= x 0)</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; e0</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (if (= x 1)</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; e1</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (if (= x 2)</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; e2</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; e3)))</FONT></SPAN>
</P>

<P><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">using</FONT></SPAN>
</P>

<P><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&nbsp;(if (x . &lt; . 2)</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&nbsp;&nbsp;&nbsp;&nbsp; (if (x . &lt; . 1)</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; e0</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; e1)</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&nbsp;&nbsp;&nbsp;&nbsp; (if (x . &lt; . 3)</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; e2</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; e3))</FONT></SPAN>
</P>

<P><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">?&nbsp; </FONT></SPAN>
</P>

<P><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">At Thu, 29 Sep 2011 12:25:16 +0200, &quot;Jos Koot&quot; wrote:</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; Thanks Matthew.</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; I read the paper.</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; In my case I have a case form which dispatches on a character, 86 different</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; ones. Therefore I can dispatch by means of a vector. However, almost every</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; character has its own clause and therefore dispatching on the index of the</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; character would give no speed up. I already tried a hash-table and a vector</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; (making sure it is computed once only) The values in the table/vector are</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; procedures that run the body of a clause. The vector is used as follows:</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; </FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; (define (parse-fmt-instr parser-state) ; Parses one single instruction.</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt;&nbsp; (skip-white-fmt-and-commas parser-state)</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt;&nbsp; (let ((char (pop-fmt-char parser-state #f)))</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt;&nbsp;&nbsp; (and char</FONT></SPAN>

<BR><SPAN LANG="el"><FONT SIZE=2 FACE="Courier New Greek">&gt;&nbsp;&nbsp;&nbsp; (if (char=? char #\¶ň) call-proc-instr</FONT></SPAN><SPAN LANG="es"></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt;&nbsp;&nbsp;&nbsp;&nbsp; (let ((i (char-&gt;integer char)))</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (if (&lt; i 128)</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ((vector-ref parser-table i) parser-state char)</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (fmt-error parser-state)))))))</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; </FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; However, as you predicted, I found no speed up. With a hash table in some</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; cases even a slow down.</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; The gain in speed of dispatching seems to be destroyed by the extra</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; procedure call.</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; I think Clinger's paper is particularly useful for case forms wih many keys</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; but few clauses.</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; Thanks for your help.</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; Jos </FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; </FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; -----Original Message-----</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; From: Matthew Flatt [</FONT></SPAN><A HREF="mailto:mflatt@cs.utah.edu"><SPAN LANG="es"><U><FONT COLOR="#0000FF" SIZE=2 FACE="Courier New">mailto:mflatt@cs.utah.edu</FONT></U></SPAN></A><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">] </FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; Sent: mi®¶rcoles, 28 de septiembre de 2011 22:59</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; To: Jos Koot</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; Cc: 'Racket-users'</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; Subject: RE: [racket] case form implemented with a hash</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; </FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; I had in mind the comment on page 64, bottom right, but I see that it's</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; a smaller comment than in my memory.</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; </FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; Overall, I think it will work better to use a hash table to go from a</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; value to an index, and then use a binary search on the index as in</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; Clinger's paper. Indirect dispatch via thunks in a hash table will most</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; likely be slower.</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; </FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; At Wed, 28 Sep 2011 22:55:08 +0200, &quot;Jos Koot&quot; wrote:</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; Hi Hatthew,</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; I am still trying to implement 'case' by means of a hash.</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; Can you give me a more specific pointer. I followed your pointer but did</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; not</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; see anything relevant to my question.</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; Jos </FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; </FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; -----Original Message-----</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; From: Matthew Flatt [</FONT></SPAN><A HREF="mailto:mflatt@cs.utah.edu"><SPAN LANG="es"><U><FONT COLOR="#0000FF" SIZE=2 FACE="Courier New">mailto:mflatt@cs.utah.edu</FONT></U></SPAN></A><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">] </FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; Sent: mi®¶rcoles, 28 de septiembre de 2011 22:20</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; To: Jos Koot</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; Cc: 'Racket-users'</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; Subject: Re: [racket] case form implemented with a hash</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; </FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; At Wed, 28 Sep 2011 22:08:44 +0200, &quot;Jos Koot&quot; wrote:</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; &gt; By inspection with the macro stepper I found that case forms are</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; expanded</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; to</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; &gt; nested if-forms. For case forms with many clauses, this may be</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; inefficient.</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; &gt; I have tried to prepare a hash-case form using a hash table in order to</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; &gt; select the desired clause more efficiently. So far my attempts failed. I</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; am</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; &gt; still trying. However, has anybody else on this list thought of using a</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; hash</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; &gt; for case forms with many clauses? Does it exist? If not, would anyone be</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; &gt; interested in a hash-case form that has the same shape as a case-form,</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; but</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; &gt; uses a hash-table to select the appropriate clause? The hash table</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; should</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; be</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; &gt; a map onto thunks and macro hash-case simply would have to retrieve the</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; &gt; thunk and call it.</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; </FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; See &quot;Rapid Case Dispatch in Scheme&quot;, Clinger, Scheme'06.</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; </FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; If you implement a revised `case' that consistently works better, then</FONT></SPAN>

<BR><SPAN LANG="es"><FONT SIZE=2 FACE="Courier New">&gt; &gt; I'd be happy to use it as a replacement for the current `case'.</FONT></SPAN>
</P>

</BODY>
</HTML>