<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link="#0563C1" vlink="#954F72"><div class=WordSection1><p class=MsoNormal>I’ve been doing profiling on Clang’s static analyzer, and a big portion of the time spent in the static analyzer is looking up elements in an llvm::FoldingSet. The static analyzer will frequently have a FoldingSet with 150,000 – 200,000 elements in it. <o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I have found the FoldingSetNodeID abstraction to cause processor cache issues. When FindNodeOrInsertPos gets called, each element in the associated bucket needs to be inspected. With a FoldingSetNodeID, a large portion of the object needs to be pulled into the cache in order test for equality, even if some of the early data members would have proven the item as not-equal. The FoldingSetTrait doesn’t give much flexibility to avoid pulling in an entire object, as the ‘Equals’ signature pre-supposes FoldingSetNodeIDs.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I propose adding a new FoldingSet variant. It will still be an intrusive hash set, but will instead use a more general trait class. The trait’s ‘concept’ would look something like the following:<o:p></o:p></p><p class=MsoNormal>struct NewFoldingSetTrait {<o:p></o:p></p><p class=MsoNormal> static bool Equals(const T &lhs, const T &rhs);<o:p></o:p></p><p class=MsoNormal> // Sometimes, you need to search for an element with an 'identity' <o:p></o:p></p><p class=MsoNormal> // object, instead of an object of type T. You must provide Equals <o:p></o:p></p><p class=MsoNormal> // implementations if you want this heterogenous comparison to work.<o:p></o:p></p><p class=MsoNormal> static bool Equals(const SomeNodeID &lhs, const T &rhs);<o:p></o:p></p><p class=MsoNormal> static bool Equals(const T &lhs, const SomeNodeID &rhs);<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> static unsigned ComputeHash(const T &X);<o:p></o:p></p><p class=MsoNormal> // If an object 't' of type T and an object 's' of type SomeNodeID<o:p></o:p></p><p class=MsoNormal> // return true from Equals(t, s), then the hash for 't' and the hash<o:p></o:p></p><p class=MsoNormal> // for 's' must be equal.<o:p></o:p></p><p class=MsoNormal> static unsigned ComputeHash(const SomeNodeID &X);<o:p></o:p></p><p class=MsoNormal>};<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I think that this trait class would allow migration to the new FoldingSet to happen gradually. A legacy / compatibility version of the trait could even allow a type T to be compared to a FoldingSetNodeID and / or a FoldingSetNodeIDRef.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I’ve had good results with my initial profiling just while changing clang::ExplodedGraph::Nodes over to the new FoldingSet. Before I progress further, I would like to get some feedback from the community.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Also, any suggestions on a name? IntrusiveHash? intrusive_hash? FoldingSet2?<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>Employee of Qualcomm Innovation Center, Inc.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:"Courier New"'>Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project<o:p></o:p></span></p><p class=MsoNormal><o:p> </o:p></p></div></body></html>