Re: [Texmacs-dev] Efficiency of C++ switch-statements

[David Allouche]

On Tue, Nov 11, 2003 at 04:06:28PM +0100, Gabriel Dos Reis wrote:
> "Dan Martens" <address@hidden> writes:

> > This is a very general statement.  If I were to compare a single
> > integer to a 150 possible values and branch to various code, how
> > would virtual function calls in an object heirarchy facilitate this?
> 
> The key notion I got from his mail is:
> 
>    I am interested in the following situation: I have 150 built-in
>    TeXmacs tags and a few places in the code where some action has to
>    be undertaken which is different for about 10 tags and the same for
>    the remaining 140 tags.
> 
> I assume those tags actually identify Texmacs entities.  No?

Absolutely right. Actually, I have been thinking that all this explicit
dispatch on tree labels is quite ugly.

> > Virtual function calls and switch statements are meant for 2 totally
> > different purposes.  
> 
>   Not really.  An illustrative example is the Visitor Deisgn Pattern.

The amount of Design Patterns Joris seems to has put unknowingly in
TeXmacs code is quite amazing. But it seems that one has fallen through
the cracks :-)

But (correct me if I am wrong, I do not have my GOF book nearby) the
Visitor Design Pattern is a way to implement multimethods. That is
virtual dispatching on several types for a single method. In this case,
simple virtual methods do the job.

> > One is for quick code executing dependant upons individual values or
> > ranges of variables of primitive types, the other is meant for
> > object orientated programming and polymorphism. 
> 
>   That is a very restricted and unuseful view of what virtual functions
> are about.  There are very few, limited cases where switch statements
> are better alternatives to virtual functions.  Note: I'm not saying
> virtual functions should be used about every thing in place of every
> switch statement.  I'm saying that, basically, when you're switching on
> tags, consider whether virtual functions would not offer a better
> alternative.  Virtual functions are implementations of switch
> statement at the compiler level.  An illustration is the visitor
> design pattern.

Practically, the basic do-everything structure in TeXmacs is "tree". It
is carefully implemented _not_ to contain a virtual dispatch table
pointer.

    class tree_rep: concrete_struct {
    public:
      const tree_label op;
          inline tree_rep (tree_label op2): op (op2) {}
      friend class tree; };

    class atomic_rep: public tree_rep {
    public:
      string label;
      inline atomic_rep (string l): tree_rep (STRING), label (l) {}
      friend class tree; };

    class compound_rep: public tree_rep {
    public:
      array<tree> a;
      inline compound_rep (tree_label l, array<tree> a2): tree_rep (l), a (a2) 
{}
      friend class tree; };

The big switch statements are done on the value of "tree_rep::op". Note
that this instance member variable is _const_. I sneaked this
qualifier in a while ago so the semantics would be compatible with
virtual methods.

To use virtual methods, things would have to be redesigned a bit

  class tree_rep: abstract_struct {
  public:
    virtual ~tree_rep() {}
    virtual tree_label label() = 0;
    virtual tree exec(edit_env_rep* e) = 0;
    friend class tree; };

  class atomic_rep: public tree_rep {
  public:
    string label;
    virtual ~atomic_rep() {}
    virtual tree_label label(); // return STRING
    inline atomic_rep (string l);
    virtual tree exec(edit_env_rep* e); // return this
  };

  class compound_rep: public tree_rep {
  public:
    array<tree> a;
    inline compound_rep (tree_label l, array<tree> a2): tree_rep (l), a (a2) {}
    virtual ~compound_rep() {}
    virtual tree exec(edit_env_rep* e); // default case
    
  // An example class for a compound tree
  class decorate_atoms_rep: public compound_rep {
    inline decorate_atoms_rep (tree_label l, array<tree> a2): compound_rep (l, 
a2) {}
    virtual tree_label label(); // return DECORATE_ATOMS
    virtual tree exec(edit_env_rep* e); // handle this case
  };

A good thing with this approach is that an appropriate class hierarchy
can explicit a lot of the common structure of the big switches.

Locality of code can be preserved by defining virtual methods with the
same name in the compilation unit where they are used. So this would
lead to compact code (good cache behaviour) and a maintainability
comparably to switch statements (all definitions are toghether).

For small cases, this would do a bit more reference counting (since
return values are always counted). But this is negligible compared to
the rest of the reference counting insanity...

The main problem is this will create tons of little repetitive classes.
Very annoying to code, and thus error-prone. But things can be factored
out by a clever use of templates or preprocessor macros... Templates are
not ideal for debugging (since trees are a really ubiquitous structure)
and preprocessor macros are not ideal for maintenance...

Maybe there is an extra twist to avoid this problem... but I cannot find
it from the top of my head.

Maybe this would be worth trying, but since the case values are always
consecutive (I am not sure I understood the "dense" matter correctly)
and as TeXmacs anyway should always be compiled with -O2 or -O3, the
case statement probably always use dispatch tables. So there would be
little to gain here.

-- 
                                                            -- ddaa