<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><moving to llvmdev><div><br><div><div>On Feb 14, 2011, at 9:49 AM, Talin wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">A few additional thoughts on <meta charset="utf-8"><span class="Apple-style-span" style="border-collapse: collapse; font-family: arial, sans-serif; font-size: 13px; ">PR1210:</span><div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;"><br>
</span></font></div><div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;">I can think of three approaches to addressing this issue. The first approach is the one outlined in <span class="Apple-style-span" style="font-size: 13px; ">PR1210, which is to have the key have enough knowledge of the internals of the Type to be able to use the internal type array as the data for the key.</span></span></font></div>
<div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;"><br></span></font></div><div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;">The second approach is similar, which is to factor out the type array as a separate, immutable object which is shared by both the key and the type object. That is, you first create the type array, use that to look up the type, and if it doesn't find it, clone the type array and use it to construct a new type object, then use the same type array as the key.</span></font></div></blockquote><div><br></div>This is effectively what FoldingSet does. The actual bits are stored in the type if it exists. If it doesn't exist, the input vector of element types is hashed by the profiling function, and then the hash value is looked up. If there is no match, a type is created. The profile is designed to typically live on the stack to avoid a heap allocation.</div><div><br><blockquote type="cite">
<div><span class="Apple-style-span" style="border-collapse: collapse; font-family: arial, sans-serif; ">Note that you can't use the same type array that you used for the lookup, because otherwise the get-or-insert function would sometimes have to take ownership of the type array depending on whether the type existed or not, which would be confusing. </span></div></blockquote><div><br></div><div>Right: the idea is that a lookup (which hits an already created value) should not do a heap allocation.</div><br><blockquote type="cite">
<div><span class="Apple-style-span" style="border-collapse: collapse; font-family: arial, sans-serif; ">Another way around the ownership problem is to allocate all type arrays as part of the memory pool associated with the LLVMContext, and then 'intern' the type arrays so that they can be compared via pointer rather than by value. The type arrays go away when the context does, so you don't have to worry about who is responsible for freeing it. The downside is that you now have to do two hash lookups for the type object's get-or-create method.</span></div></blockquote><div><br></div>I don't really understand what you mean by this. You still need to hash on the identity of the type and the subclass of type still needs to have accessors for its elements.</div><div><br></div></div><div>-Chris</div></body></html>