Orchid Win7 v1 <voi### [at] devnull> wrote:
> So 16 bytes of space overhead per node is worth it if you can avoid one 
> indirect jump instruction?

  No, it's worth it if you can avoid one extraneous memory allocation
(or having to manage the allocated memory manually).

  A memory allocation will easily consume those 16 bytes of extra space
anyways (the memory allocator bookkeeping, memory alignment, and the pointer
used to refer to the allocated object), so it's not like you are gaining
anything.

> Mmm, I hadn't even thought of using an /array/. I suppose the upper 
> bound on the tree size is statically known, so why not?

  The array doesn't necessarily have to be fixed in size.

> >    It's sometimes quite a bummer, but when writing efficient C++ you have
> > to always think "how many memory allocations will this perform?"

> Right. So what you're saying is that it's not dynamic binding /itself/ 
> which is slow, but rather the dynamic allocations which necessarily go 
> with it. (?)

  Calling a virtual function is in practice not any slower than calling
a regular function.

  Calling 'new', however, can be really slow (comparatively speaking).

  If you can reduce x millions of 'new' calls into eg. log(x millions) of
'new' calls, your program will probably become much faster.

> Out of curiosity, if /you/ were writing a piece of code that's supposed 
> to take a text string, parse it as an expression, and then execute the 
> resulting expression, how would you implement that?

  You mean like this? http://warp.povusers.org/FunctionParser/

> The most obvious way 
> is to make every valid kind of expression be a different class, and have 
> an abstract base class with an "execute this" method, which gets 
> implemented differently for each type of expression. But this 
> necessarily involves dynamic binding and dynamic allocation, which you 
> seem to make out is the Ultimate Evil to be avoided at all costs. So how 
> would you do it?

  If the parser consists of some dozens expression parsers which are added
to the core module once at program start, then the slowness of memory
allocation becomes completely irrelevant. You are not performing millions
of 'new' operations, only a few dozen of them. The virtual function calls
themselves are pretty efficient. (What you *should* avoid is calling 'new'
and 'delete' during the parsing, if you want it to be as fast as possible.)

  The major design issue becomes the management of those dynamically
allocated objects. (Smart pointers may be a good solution to this.)

  Of course there are other approaches which are more efficient in terms
of memory usage, but they are usually less flexible (in that it's harder
to add new expressions to the parser from the outside without modifying
the source code of the parser module).

> OK, well, if there is a single TreeNode class, I could write something like

>    TreeNode(TreeNode t0, TreeNode t1)
>    {
>      child0 = new TreeNode;
>      child1 = new TreeNode;
>      *child0 = t0;
>      *child1 = t1;
>    }

  Since TreeNode there is managing dynamically allocated memory, you'll
have to write a proper copy constructor and assignment operator or else
you have a leak and/or accesses to deleted memory. (And as I said in my
previous post, that's not trivial because of all the options you have.)

> If, however, the TreeNode class is abstract, obviously this won't work 
> at all. I now need to know what the /actual/ type of t0 is before I can 
> allocate sufficient space for it.

  Well, that's easy. You should do this:

    class TreeNode
    {
     protected:
        virtual TreeNode* clone() const = 0;

     public:
         TreeNode(const TreeNode& t0, const TreeNode& t1):
             child0(t0.clone()),
             child1(t1.clone())
         {}

         // Implement destructor, copy constructor and assignment
         // operator appropriately here.
    };

  Then every inherited class implements that 'clone()' method like:

    class FancyNode: public TreeNode
    {
     protected:
        virtual TreeNode* clone() const
        {
            return new FancyNode(*this);
        }
    };

> (I'm also fuzzy on what happens when 
> you try to delete a pointer - does it know what the "real" size of the 
> object is, or does it use the declared type of the pointer?)

  If the pointer is handling a dynamically bound object, then the
destructor of the base class has to be virtual. Then 'delete' is able
to destroy the object appropriately.

-- 
                                                          - Warp

Post a reply to this message