Fast-IsA

This is a GEM from Game Programming Gems 8, by Joshua Grass, provides a better method for processing class hierarchy data that can increase the efficiency of IsA check from O(N) to O(1). Here is my summary after reading.

Given a typical class hierarchy like below:

WeChat Image_20180130164516

A normal way to perform IsA check, determine whether Class A is a subclass of Class B would be:

bool IsA(Class *pA, Class *pB)
{
    while (*pA != NULL)
    {
        if (pA == pB)
        {
            return true;
        }
        pA = pA -> GetParentClass();
    }
    return false;
}

The worst case of this algorithm would perform a traversal from leaf to root, which can be very expensive.

So let’s simplify the problem. Imagine we are lucky and the class is in a perfectly balanced binary hierarchy, which means each node branched exactly twice, just like below:

WeChat Image_20180130174959

In this situation the class hierarchy can be put into a contiguous array.

WeChat Screenshot_20180130175525

We noticed that on each level we add 2^(N-1) new nodes to the array, where N is the new level. According to the index in the array(the second row in above table), we can easily find the relationship between each node and its parent:

int parentIndex(int nodeIndex)
{
    return nodeIndex >> 1;
}

So according to this algorithm, on a perfectly balanced tree, we can improve IsA() from O(N) to O(logN):

bool IsA_Balanced2Tree(Class *pA, Class *pB)
{
    int nodeAIndex = pA -> GetClassIndex();
    int nodeBIndex = pB -> GetClassIndex();

    while (nodeAIndex != 0)
    {
        if (nodeAIndex == nodeBIndex)
        {
            return true;
        }
        nodeAIndex = nodeAIndex >> 1;
    }
    return false;
}

Actually once the index for a parent of A is less than the index for B, there is no way that they can be equal. So we can reduce worst-case scenario.

bool IsA_Balanced2Tree_V2(Class *pA, Class *pB)
{
    int nodeAIndex = pA -> GetClassIndex();
    int nodeBIndex = pB -> GetClassIndex();

    while (nodeAIndex >= nodeBIndex)
    {
        if (nodeAIndex == nodeBIndex)
        {
            return true;
        }
        nodeAIndex = nodeAIndex >> 1;
    }
    return false;
}

According to the relationship between a node and its parent, here is the algorithm to find the index of a child, depends on its position in the sub-tree:

int childIndex(int nodeIndex, bool bRight)
{
    if (bRight)
    {
        return (nodeIndex << 1) + 1;
    }
    else
    {
        return (nodeIndex << 1);
    }
}

The binary representation looks like this:

WeChat Image_20180130190605

We can observe that: if Class A is a child of Class B, then the leftmost N bits of B will match A, where N is the highest bit set in A.

Using this rule we can remove the while loop in IsA():

bool IsA_Balanced2Tree_V3(Class *pA, Class *pB)
{
    int nodeAIndex = pA -> GetClassIndex();
    int nodeBIndex = pB -> GetClassIndex();

    if (nodeAIndex > (BSR(nodeAIndex) - BSR(nodeBIndex));

    return nodeAIndex == nodeBIndex;
}

The BSR() here is a wrapper for an inline assembly function that uses the BSR assembly instruction BitScanReverse, which returns the index of the leftmost set bit. If would be easy to pre-calculate the most significant bit index even if the platform does not support BSR().

However, all of the previous work has been built upon the notion that our class hierarchy is a perfectly balanced tree. Fortunately, our IsA() function does not care about the depth between nodes, only ancestry matters. So we can convert the unbalanced tree into balanced tree by adding phantom class, as long as we keep them in fact ancestors.

WechatIMG144

The following algorithm is the simplest implementation for building the class tree.

void BuildTree(Class *pA)
{
    int nCurrentClassIndex = pA -> GetClassIndex();
    int nNumChildClasses = pA -> GetNumberOfChildClasses();
    int nNumLeverls = BSR(nNumChildClasses() + 1;
    int nChildIndexStart = nCurrentClassIndex << nNumLevels;

    for (int i = 0; i  GetChildClass(i);
        pChild -> SetClassIndex(nChildIndexStart + i);
        BuildTree(pChild);
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s