On 14/03/2012 02:15 PM, Warp wrote:
> 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.

Heh, really? Most languages I work with can allocate new objects in O(1) 
time and using O(1) memory for bookkeeping. I'm not used to dynamic 
allocation being anything to worry about.

>> 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 does if it's static. Either that or the source I'm reading is 
incorrect...

>    Calling a virtual function is in practice not any slower than calling
> a regular function.
>
>    Calling 'new', however, can be really slow (comparatively speaking).

Mmm, OK.

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

Well, sure. If I was going to allocate, I don't know, one object for 
every pixel on the screen, then sure, I'd try to find a way to not do 
that dynamically. But for two-dozen objects of a few bytes each, I 
really wouldn't expect dynamic allocation to be a big deal. (Then again, 
I don't write C++ for a living...)

>> 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/

...I'd sit down and study that, but I'm guessing it's designed more for 
usability than readability.

>> 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.
>
>    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.)

That was my feeling. The typical data sizes I'm working with are so 
minute that efficiency becomes almost moot. Even an exponential-time 
algorithm is pretty quick given small enough input. ;-)

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

Well, yes... I'm certainly not looking forward to tracking down memory 
management faults. :-/

>> 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.)

How about if I never actually need to duplicate the tree? Does that make 
things any simpler?

>> 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 definitely need to find a more thorough reading source; some of that 
syntax isn't even /explained/ on the site I read...

>> (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.

Right. So as long as you remember to make the destructor virtual, it 
will look up the correct code from the vtable.

Post a reply to this message