Is skipping "accept" where type is known, a valid optimization for the Visitor pattern?

Question

Consider the following visitor for a simple language interpreter.

public interface Visitor{
    void visit( VarStat vs);
    void visit( Ident i);
    void visit( IntLiteral a);
    void visit( Sum s);
}

For completeness I add some code that gives necessary implementation details (you can skip and read directly the question).

public interface Visitable{
    void accept( Visitor v);
}

public class VarStat implements Visitable{
    Ident i;
    Exp   e;

    public VarStat(Ident id, Exp ex){
        i = id;
        e = ex;
    }

    public Ident getIdent() { return i; }
    public Exp getExp() { return e; }

    @Override
    public void accept( Visitor v){
        v.visit( this);
    }
}

public interface Exp extends Visitable{

}

public class Ident implements Exp{
    @Override
    public void accept( Visitor v){
        v.visit( this);
    }
}

a var statement is defined like that:

VarStat ::== var Ident = Exp;
Exp ::== Exp + Exp | IntLiteral | Ident
IntLiteral ::== [0-9]{0,8}
Ident ::== [a-zA-Z]+

a valid language instance

var x = x+y+4;

An abstract way to represent the VarStat node is the following:

.               _____VarStat _____
.              /       /  | \     \ 
.             /       /   |  \     \  
.            /       /    |   \     \
.         "var"   Ident  "="  Exp   ";"

---

The Question

The usual VisitorPattern application would be

void visit( VarStat vs){
     vs.getIdent().accept( this);
     vs.getExp().accept( this);
     //...
}

however, since I know "Ident" is of type Ident a possible optimization is

void visit( VarStat vs){

     visit( vs.getIdent());
     vs.getExp().accept( this);
     //...
}

That would skip 2 method calls improving the performance (actually it gives a nice boost in my scenario).

Is that considered a design error that could lead to future problems?

Takishatakken

actually it gives a nice boost in my scenario . really ? How? – Arioso

Yes, I would also like to see the measured numbers. – Indolent

15% faster. exploited that in 20 places over 25 methods (the real visitor has 25 methods for now). Also easier to debug because stack trace becomes smaller, why timing matters for you? – Takishatakken

relevant - double-dispatch without visitor pattern - #21032517 – Dorsal

@Arioso - it's plausible. the new code is much easier to optimize for JVM; it's probably inlined. – Dorsal

I would like to see a number after running tests with JMH(openjdk.java.net/projects/code-tools/jmh). My feeling once the method runs of some time, JVM optimization as good as you can get. – Arioso

@Arioso if he has 20 leaf node types among 25 node types, it is very believable. – Dorsal

Answer 1

Visitor is just a complicated scaffold to implement double-dispatch on languages like Java.

When you deal with leaf types, you don't need double-dispatch; the runtime type is known at the compile time. Dispatch a leaf type directly is not only an optimization, it's more out of principle.

Of course, the problem is, in future, a leaf type may become a super type. With today's refactor tool in IDEs, this is not a huge problem.

It is better to make a simple design for present's requirement, than to make a complex design for unknown future requirements.

---

In java 8, we can implement double-dispatch with a syntax that's very close to the real double-dispatch

final DoubleDispatch<Root,Void> dd = new DoubleDispatch<>();

dd.register(X.class, x->
{
    do something with x; its compile time type is X
    return null;
});
dd.register(Y.class, y->
{
    do something with y; its compile time type is Y
    return null;
});
// etc

...
dd.invoke( something );



// ----

public class DoubleDispatch<T, R>
{
    public R invoke(T obj){...}

    public <C extends T> void register(Class<C> type, Function<C,R> func){...}
}

see also - Java Class.cast() and Overload

Dorsal

Answer 2

In this case it would not be a Visitor pattern. And it does not have to be if it suits your requirements, visitors are often misused and lead to over-architecturing.

However, you will loose potential benefits. For example, you will not be able to create a decorator or proxy for Ident and do something additional in the accept method before forwarding the call to the decorated/proxied object.

Indolent

Answer 3

Could it cause problems? Hard to say. (I guess it could cause surprises if the grammar changed ...)

But I think the real issue is whether this is a worthwhile optimization. Specifically, is saving two method calls going to make a significant difference in the big picture? My intuition is that it wouldn't.

And does the performance of this interpreter really matter?

And if it does, why are you using the visitor pattern in the interpreter? Shouldn't you be compiling to an intermediate virtual machine code? Or to bytecodes?

Beep