<div dir="ltr"><div class="gmail_default" style="font-family:verdana,sans-serif">Hi, Stepan...</div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">
Each insertion in the tree will be O(log(N)), which would make the whole process O(N log(N)), right?</div><div class="gmail_default" style="font-family:verdana,sans-serif">It is still an improvement over an O(N^2) all-to-all check, of course....</div>
<div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">Have you explored alternatives by improving the hashing or doing some secondary hashing? That might have an even bigger impact, potentially making it O(N) on cases with perfect-hashing.</div>
<div class="gmail_default" style="font-family:verdana,sans-serif"><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Jan 17, 2014 at 12:25 PM, Stepan Dyatkovskiy <span dir="ltr"><<a href="mailto:stpworld@narod.ru" target="_blank">stpworld@narod.ru</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi all,<br>
<br>
I propose simple improvement for MergeFunctions pass, that reduced its complexity from O(N^2) to O(log(N)), where N is number of functions in module.<br>
<br>
The idea, is to replace the result of comparison from "bool" to "-1,0,1". In another words: define order relation on functions set.<br>
To be sure, that functions could be comparable that way, we have to prove that order relation is possible on all comparison stage.<br>
<br>
The last one is possible, if for each comparison stage we implement has next properties:<br>
* reflexivity (a <= a, a == a, a >= a),<br>
* antisymmetry (if a <= b and b <= a then a  == b),<br>
* transitivity (a <= b and b <= c, then a <= c)<br>
* asymmetry (if a < b, then a > b or a == b).<br>
<br>
Once we have defined order relation we can store all the functions in binary tree and perform lookup in O(log(N)) time.<br>
<br>
This post has two attachments:<br>
1. The patch, that has implementation of this idea.<br>
2. The MergeFunctions pass detailed description, with explanation how order relation could be possible.<br>
<br>
Hope it helps to make things better!<span class="HOEnZb"><font color="#888888"><br>
<br>
-Stepan.<br>
</font></span><br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br><div dir="ltr"><div><font size="4" face="arial black, sans-serif" style="background-color:rgb(0,0,0)" color="#b45f06"> Raúl E. Silvera </font></div><div><br>
</div></div>
</div>