RFR 8005698 : Handle Frequent HashMap Collisions with Balanced Trees (original) (raw)

Jeff Hain jeffhain at rocketmail.com
Thu May 23 20:47:30 UTC 2013

Hello.

Implementing some RB-tree I found out that

a lot of the null checks from CLR code could be removed from balancing operations.

Looking at TreeBin (http://cr.openjdk.java.net/~bchristi/8005698/webrev.01/) I found some places where such checks could also be removed.

In putTreeNode(...) (see comments):         if (x == xp.right) {             rotateLeft(x = xp);             // Rotation adds a parent,             // and xpp was not null, so the new xpp             // is not null either (even though we             // did x = xp).             //xpp = (xp = x.parent) == null ? null : xp.parent;             xpp = (xp = x.parent).parent;         }         //if (xp != null) {             xp.red = false;             //if (xpp != null) {                 xpp.red = true;                 rotateRight(xpp);             //}         //} (...)         if (x == xp.left) {             rotateRight(x = xp);             // Rotation adds a parent,             // and xp was not null, so the new xp             // is not null either (even though we             // did x = xp).             //xpp = (xp = x.parent) == null ? null : xp.parent;             xpp = (xp = x.parent).parent;         }         //if (xp != null) {             xp.red = false;             if (xpp != null) {                 xpp.red = true;                 rotateLeft(xpp);             }         //} (...)

        // p is not null so root is not null.         //if (r != null && r.red) {         if (r.red) {             r.red = false;         }

Similar rotation-related simplifications could be done in deleteTreeNode(...).

Doing a lot of random add/remove calls (for integers in bounded ranges, for removes to actually work not too rarely), it seemed that null checks could actually be removed for all remaining calls to leftOf/rightOf/setColor (not for getColor), but since I didn't figure out why I didn't  touch these.

-Jeff

More information about the core-libs-dev mailing list