On Thu, Aug 12, 2010 at 6:07 PM, Simon Peyton-Jones <span dir="ltr"><<a href="mailto:simonpj@microsoft.com">simonpj@microsoft.com</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div lang="EN-GB" link="blue" vlink="purple">
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;color:#1F497D"><span>1.<span style="font:7.0pt "Times New Roman"">
</span></span></span><span style="font-size:11.0pt;color:#1F497D">You *<b>want</b>* a distinct blob of lookup code for each different key type, because you really do want a different lookup structure for each</span></p></div>
</div></blockquote><div><br></div><div>There are two reasons to want different blobs of code for the lookup function:</div><div><br></div><div>1. You want a different data structure (e.g. Patricia trees or weight balanced trees) for different key types.</div>
<div>2. You want the key type unboxed (e.g. Int#) to reduce indirection/reboxing and that way speed up the function by some constant factor.</div><div><br></div><div>The second could perhaps be achieved using SPECIALIZE pragmas, if they could be given in modules that uses the data type and not only in the module that defines the data type.</div>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div lang="EN-GB" link="blue" vlink="purple"><div>
<p><span style="font-size:11.0pt;color:#1F497D"><span>2.<span style="font:7.0pt "Times New Roman"">
</span></span></span><span style="font-size:11.0pt;color:#1F497D">For the most part you *<b>dont want</b>* a different blob of lookup code for each value type, because almost all of them are represented uniformly
by a pointer.</span></p></div></div></blockquote><div>I don't know if I want a different blob of lookup code for each value type. It seems to be that having a different blob of lookup code even for the value type could avoid some reboxing of the value when the caller will immediately unbox the value again.</div>
<div><br></div><div>What I definitely want is different data representation for each key/value type to avoid the four word overhead (two pointers and two constructors) for key/value types that can be unboxed into the data structures data constructors.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div lang="EN-GB" link="blue" vlink="purple"><div>
<p class="MsoNormal"><span class="Apple-style-span" style="font-size: 15px; color: rgb(31, 73, 125); ">So it’s be silly to generate all possible combinations of types.</span></p></div></div></blockquote><div><br></div><div>
My proposal is to do the generation lazily, only for the combination of types that are actually used, just like C++ does. If we can get the same result without code duplication that would be better.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div lang="EN-GB" link="blue" vlink="purple"><div><p class="MsoNormal"><span class="Apple-style-span" style="font-size: 15px; color: rgb(31, 73, 125); "> The exception to (2) is that you want different code for a handful of types that you want
to unbox into the tree structure itself: Int#, Float# etc. It would be good to design a convenient way to do that. It’s nothing directly to do with associated types. We’d like to allow Maybe Int#, say, but we don’t at the moment because that data structure
would really be represented differently. Some kind of data type and code cloning (a la C++) is probably the right thing. This is what Max meant by “just engineering” but it would require careful thought and design.</span></p>
</div></div></blockquote><div><br></div><div>The number of data types you might want to unbox may be larger than you think: All the Int types, all the Word types, Floats, Doubles, tuples, and user defined records (which are technically tuples I guess). Anything the UNPACK pragma applies to really.</div>
<div><br></div><div>The unboxing into the data type constructors is really what I'm after, the specialization of e.g. the lookup function to avoid reboxing seems to follow naturally from that.</div><div><br></div><div>
Cheers,</div><div>Johan</div><div><br></div></div>