Visitor, dynamic_cast or ...

From: Ares Lagae (ares.lagae_at_student.kuleuven.ac.be)
Date: 10/25/03

  • Next message: Tobin Harris: "Re: Article: Mind Mapping for OOAD" 
    Date: Sat, 25 Oct 2003 00:14:37 +0200

    Each time i run into the same problem. I have a base class with sometimes as
    less as 2 derived classes. I put them in some datastructure (so i do need
    the base class (even with type safe containers like the ones in stl)). Then
    off course i loose type information. Sometimes this can be solved with
    virtual functions, sometimes not. In the cases where it cannot be solved
    with virtuals ,each time i find myselve considering these solutions:

    (1) use visitors
    (2) use dynamic_cast
    (3) group everything into a single class

    (2) i dont like dynamic_cast, also because it incurs a performance penalty
    (1) is faster than (2) but can lead to very awkward implementations
    sometimes (see further)
    (3) dont like this one

    To illustrate my problem: suppose you are building a set of classes to work
    with octrees. For those of you that are not familiar with octrees: An octree
    is a datastructure similar to a binary search tree. Start with a cube.
    Divide the cube into 8 equal octants, recursively apply the subdivision to
    some cells. This way you end op with a tree with two kinds of nodes:
    internal nodes have (exactly) 8 children, the children can be leaf nodes or
    internal nodes, the 8 children are not necesarily of the same type. Leaf
    nodes contain some data. This data structure can be used for range queries
    (like a kd-tree, but splits up each of the 3 dimensions in each node), or to
    represent sparse 3d arrays of data (cells with equal data are grouped).
    Octrees are used to represent such sparse grids that would otherwise not fit
    in memory.
    There are 2 important aspects: speed and low memory consumption.

    Lets model it using visitors:

    class Node
    {
        InternalNode * m_parent; /* pointer to parent */
        ...
    }

    class InternalNode : public Node
    {
        Node * m_children[8]; /* child pointers */
    }

    template <class T>
    class LeafNode : public Node
    {
        T m_data;
    };

    template <class T>
    class Octree /* octree to store data of type T)
    {
        Node * m_root;
    }

    A visitor would look like this:
    class NodeVisitor
    {
        virtual visit(LeafNode<T> * node)
        virtual visit(InternalNode * node)
    }

    whoops, we have a virtual method with a template parameter.

    We need to adapt the classes:
    class Node changed into template <class T> class Node { virtual void
    accept(NodeVisitor<T> & visitor); } /* this is the only place T is used
    in this class */
    class InternalNode changed into template <class T> class InternalNode { void
    accept(NodeVisitor<T> & visitor); } /* same here */
    class NodeVisitor changed into templat <class T> class NodeVisitor

    Ok, this works. Lets implement an iterator to iterate over an octree's
    nodes. The iterator keeps a stack (needed for pre- in and postorder
    traversal), and inherits from visitor:
    NodeIterator::visit(LeafNode<T> * node) { /* do nothing */
    NodeIterator::visit(InternalNode<T> * node) { /* put all children on the
    stack */ }
    To me, this is a first sign of weirdness. Anyway, this problem is
    encountered often with composited. You could provide a child access
    interface in Node (like suggested in GoF - composite pattern), then iterator
    whould not need to be a visitor, but i like that solution even less than
    this one.

    First test: iterate over an octree of about 2*10^6 nodes
    - Visitor: 500 msec
    - Visitor completely eliminated in the iterator, used dynamic_cast instead:
    800 msec.
    I expected that a double dispatch was going to be faster than RTTI.

    Alternative implementation: eliminate all inheritance, visitors,
    dynamic_casts, ...

    template <class T>
    class Node
    {
        Node * m_parent:
        T m_data;
        Node * m_children[8];
    }

    m_children is 0 for leaf nodes, and m_children = new Node * [8] for internal
    nodes. m_data is not used for internal nodes.
    Memory redundancy: m_data never used for internal nodes, m_children pointer
    never used for leaf nodes.

    Same test: iterate over an octree of about 2*10^6 nodes: 600 msec !!!!!!!!
    This is weird: no virtual functions, inlining, no double dispatch, ... but
    slower.

    Keeping in mind the original goals (speed, memory), visitors seem the way to
    go (although, certainly in this case (2 derived classes), they seem
    overkill).

    OK, lets do another test. Implement pruning. To build an octree from a 3d
    array, you can create a full octree (as many leaf nodes as cells in the
    array) and then prune the tree. Start from the bottom of the tree, replacing
    each internal node have 3 leaf nodes with identical data as children with a
    single leaf node.

    Recursive algorithm in pseudocode:

    node prune(node root)
    {
        if node is leaf return leaf /* first if statement */
        else /* node is internal node */
            child[i] i = 0...7 = prune(child[i])
            if child[i] 0...7 is leaf and data is identical return leaf(data) /*
    second if statement */
            else return root;
    }

    - with a single node class, this algorithm is easilly implemented
    - same for dynamic_cast
    - with visitors however, implementing this is hell (wont go into details).
    You need a first visitor for the first if statement in the loop, then you
    need a second for the second if statement in the loop. 2 classes ...

    timings: same result as previous ones, visitor is the fastest, dynamic_cast
    is the slowest, and again a single node-solution is in the middle.

    conclusion:
    - visitor is fast, but implementing some algorithms is very, very, very
    awkward
    - dynamic_cast is slow
    - no inheritance is memory-redundant and slower.

    I would very much appreciate comments on this. Are there alternatives (in
    general), and does someone see alternatives for the concrete problem here ?
    Does anyone have similar "problems" with class hierarchies? Are there other
    ways to do this i have overlooked ? I constantly feel like having to chose
    between 3 bad things... Also, a virtual function call seems very cheap
    nowdays...

    best regards,
    Ares Lagae

  • Next message: Tobin Harris: "Re: Article: Mind Mapping for OOAD"