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 <[EMAIL PROTECTED]> 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
