Re: [boost] [RFC] Generic non-intrusive Visitor pattern utility

From: dizzy (dizzy_at_[hidden])
Date: 2008-01-10 09:48:48

On Thursday 10 January 2008 16:35:22 Sebastian Redl wrote:
> dizzy wrote:
> > The final (best?) solution I came with now is using RTTI. RTTI's typeid()
> > is by design non-intrusive (actually the way it is implemented by the
> > compiler is intrusive but it happens anyway for any polymorphic type so
> > why not use it) and it does not have any of the problems listed above,
> > the implementation is "small enough" that I can include it here:
>
> If I understand correctly, your implementation is O(n) with n =
> size(typelist), right? The advantage of virtual calls is that they're
> O(1), no matter how big the hierarchy.

Yes, that is true. But at the same time, AFAIK, the CPU optimizes my case 
better than jumping to a memory loaded address, in general code of the form:

if (case1) func1();
if (case2) func2();

Should be faster than of:

typedef void (*Function)();
Function funcs[2] = { &func1, &func2 };

funcs[getindex(input)]();

As I understand it in the first case it can realise the possible outcomes from 
analyzing of the CPU instructions loaded (and thus may start to load 
instructions at the possible jump locations it has seen), in the later it 
cannot until it has loaded the contents of the array from memory (it probably 
does not matter if that is already cached as it happens for often used 
vtables).

> Though if that is a problem in the real world is a different question.
> How big are visited class hierarchies usually?

In my case I use that visitor for 2 hierarchies of an average 5-6 visitable 
types.

Your questions make me think of possibly implementing a virtual function based 
solution too (with that parallel hierarchy template wrapper technique 
described in the previous mail) and maybe have the user decide which of them 
to use? As there are user variables here that may decide the best to use in 
terms of CPU and memory resources:
- number of visitable types
- number of visits (or better, the ratio of visits/visitable-types)

-- 
Mihai RUSU					Email: dizzy_at_[hidden]
			"Linux is obsolete" -- AST