# TreeMap: optimization of method computeRedLevel()

XMLWordPrintable

#### Details

• Enhancement
• Resolution: Fixed
• P3
• 8
• b94
• windows_7

#### Description

A DESCRIPTION OF THE REQUEST :
This is how this method is implemented in the current jdk. The method is used to discover the level at which red nodes should start when build a Map from a sorted array.

private static int computeRedLevel(int sz) {
int level = 0;
for (int m = sz - 1; m >= 0; m = m / 2 - 1)
level++;
return level;
}

The method is computing the integer log of (sz + 1) base 2. It's running time is O(log(sz)).

The implementation below has fixed cost. It is straight line code with NO jumps. It should be faster for all numbers except for really small sizes.

JUSTIFICATION :
There are much faster ways to do this. Here is an alternative implementation that should be a direct replacement (the utility functions are from hacker's delight, second edition).

private static int computeRedDepth(final int size) {
return ilog(size + 1);
}

// Hacker's delight 2nd edition
private static final int u = 42; // This quantity is not used.
private static final int[] nlzTab = new int[]
{32, 31, u, 16, u, 30, 3, u, 15, u, u, u, 29, 10, 2, u,
u, u, 12, 14, 21, u, 19, u, u, 28, u, 25, u, 9, 1, u,
17, u, 4, u, u, u, 11, u, 13, 22, 20, u, 26, u, u, 18,
5, u, u, 23, u, 27, u, 6, u, 24, 7, u, 8, u, 0, u};

public static int nlz(final int y) {
int x = y;
x |= x >>> 1; // Propagate leftmost
x |= x >>> 2; // 1-bit to the right.
x |= x >>> 4;
x |= x >>> 8;
x |= x >>> 16;
x *= 0x06EB14F9; // Multiplier is 7*255**3.

return nlzTab[x >>> 26];
}

public static int ilog(final int y) {
return 31 - nlz(y);
}

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The two functions behave identically.

CUSTOMER SUBMITTED WORKAROUND :
This is not a bug. Just a suggestion for a small speed up.

#### People

Martin Buchholz
Webbug Group