[LLVMdev] MergeFunctions: reduce complexity to O(log(N))

[Raul Silvera]

Hi, Stepan...

Each insertion in the tree will be O(log(N)), which would make the whole
process O(N log(N)), right?
It is still an improvement over an O(N^2) all-to-all check, of course....

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.



On Fri, Jan 17, 2014 at 12:25 PM, Stepan Dyatkovskiy <stpworld at narod.ru>wrote:

> Hi all,
>
> 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.
>
> The idea, is to replace the result of comparison from "bool" to "-1,0,1".
> In another words: define order relation on functions set.
> To be sure, that functions could be comparable that way, we have to prove
> that order relation is possible on all comparison stage.
>
> The last one is possible, if for each comparison stage we implement has
> next properties:
> * reflexivity (a <= a, a == a, a >= a),
> * antisymmetry (if a <= b and b <= a then a  == b),
> * transitivity (a <= b and b <= c, then a <= c)
> * asymmetry (if a < b, then a > b or a == b).
>
> Once we have defined order relation we can store all the functions in
> binary tree and perform lookup in O(log(N)) time.
>
> This post has two attachments:
> 1. The patch, that has implementation of this idea.
> 2. The MergeFunctions pass detailed description, with explanation how
> order relation could be possible.
>
> Hope it helps to make things better!
>
> -Stepan.
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>


-- 
 Raúl E. Silvera
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140121/3ba0bbe3/attachment.html>