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

Raul Silvera rsilvera at google.com
Tue Jan 21 10:07:47 PST 2014

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>

More information about the llvm-dev mailing list