harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Mikhail Fursov" <mike.fur...@gmail.com>
Subject Re: [drlvm][jitrino] Problem on the implementation of UnionFind class
Date Fri, 09 Nov 2007 14:28:06 GMT
Daizi Sheng,
you're absolutely right - we have a bug here. It was hidden for us for
a long period of time because it affects compilation time performance
only.
I'm going to fix this issue as you proposed.


On Nov 8, 2007 1:16 PM, daizi sheng <daizisheng@gmail.com> wrote:
> The file is: working_vm\vm\jitrino\src\shared\unionfind.h .
>
> In this file, one data structure is implemented to support
>  the following 3 operations:
>
>          MAKE_SET, FIND_SET, UNION_SET
>
> To achieve high efficiency, there are two heuristics--"union by rank"
> and "path compression" to improve the performance.
>
> 1. find () function implements two version of "path compression"
>
> 2. link () function try to implement the "union by rank" algorithm, but
> unfortunately, it does not implement it correctly.
>
> Here is the original code snippet
>
>     void link(UnionFind *other) {
>         assert(other);
>
>         UnionFind *aroot = find();
>         UnionFind *broot = other->find();
>
>         if (aroot->rank < broot->rank) {
>             aroot->parent = broot;
>         } else {
>             if (aroot->rank == broot->rank) {
>                 broot->rank += 1;
>             }
>             broot->parent = aroot;
>         }
>     };
>
>
> And you can check the original algorithm on the following page for more
> details if
> you want: section 22.3 in page
>
>
> http://acm2.ustc.edu.cn/~daizisheng/algorithm/clrs/clrs_1st/book6/chap22.htm
>
> Generally, the algorithm try to link the node with lower rank to the node
> with higher
>  rank (rank is the height of the sub-tree rooted at current node, e.g.
> height of
> one-node-tree is 1), If both tree owns same rank (the if statement), we
> break the
> tie arbitrarily, here we set broot to be a child of aroot, and SO,
>
>       rank of node aroot should be increased by 1, not rank of node broot.
>
> What we need to do to fix it is just changing the statement
>
>                 broot->rank += 1;
> into
>
>                 aroot->rank += 1;
>
> ANYWAY, such error does not lead to any invalidation, but it do lead an
> efficiency problem.
>
> Not sure whether it is a real bug, but at least, it
>
>    does not work as what the author expected.
>



-- 
Mikhail Fursov

Mime
View raw message