Visitor pattern vs if-ladder

[Philipp]

Hello,
I think about replacing an if-ladder (with instanceof calls) in my
code with a visitor pattern, but the advantages are not really obvious
to me.
Pros:
- cleaner code (although I think this is debatable)
Cons:
- Needs modification of the original interface and classes (to add the
accept(Visitor) method)
- If new subclasses of the acceptor interface are added, both the
Visitor interface and it's implementation needs change (adding a new
visit(MyNewClass c); to the interface). In the ladder implementation,
you only need to change at one point and add an if(...)
- A bit slower than the ladder implementation (see below)

What advantages am I missing? Why is an if ladder seen as code smell
and not the visitor pattern?


About speed:
I compared the speed of execution of an if-ladder with the visitor
pattern for counting different types of Vehicles.
If ladder:
public void count(Vehicle vehicle){
if (vehicle instanceof Car) {
counts[0]++;
} else if (vehicle instanceof Motorbike) {
counts[1]++;
} else if (vehicle instanceof Bike) {
counts[2]++;
[...]

Visitor pattern:
public void visit(Car car) {
counts[0]++;
}
public void visit(Motorbike motorbike) {
counts[1]++;
}
public void visit(Bike bike) {
counts[2]++;
}
[...]

I ran the counting with 8 types of vehicle on 10^8 randomly produced
vehicles 10 times alternatively (each run is ~16 sec, all 20 runs are
in one JVM execution, so warm up should be accounted for). The ladder
implementation is about 10% faster (mean time per run: ladder 16800ms,
visitor 18380).
I'm not saying that this is a big difference or should influence the
decision very much. It's just FYI.

Phil

 

[Albert]

Philipp a écrit :

Hello,
I think about replacing an if-ladder (with instanceof calls) in my
code with a visitor pattern, but the advantages are not really obvious
to me.
Pros:
- cleaner code (although I think this is debatable)
Cons:
- Needs modification of the original interface and classes (to add the
accept(Visitor) method)
- If new subclasses of the acceptor interface are added, both the
Visitor interface and it's implementation needs change (adding a new
visit(MyNewClass c); to the interface). In the ladder implementation,
you only need to change at one point and add an if(...)
- A bit slower than the ladder implementation (see below)

What advantages am I missing? Why is an if ladder seen as code smell
and not the visitor pattern?


About speed:
I compared the speed of execution of an if-ladder with the visitor
pattern for counting different types of Vehicles.
If ladder:
public void count(Vehicle vehicle){
if (vehicle instanceof Car) {
counts[0]++;
} else if (vehicle instanceof Motorbike) {
counts[1]++;
} else if (vehicle instanceof Bike) {
counts[2]++;
[...]

Visitor pattern:
public void visit(Car car) {
counts[0]++;
}
public void visit(Motorbike motorbike) {
counts[1]++;
}
public void visit(Bike bike) {
counts[2]++;
}
[...]

I ran the counting with 8 types of vehicle on 10^8 randomly produced
vehicles 10 times alternatively (each run is ~16 sec, all 20 runs are
in one JVM execution, so warm up should be accounted for). The ladder
implementation is about 10% faster (mean time per run: ladder 16800ms,
visitor 18380).
I'm not saying that this is a big difference or should influence the
decision very much. It's just FYI.

For such a simple case, why not using simple overriding ? You could add
a method Vehicle.count(int[]) with one implementation for each subclass
of Vehicle.

 

[Philipp]

Philipp a écrit :

Hello,
I think about replacing an if-ladder (with instanceof calls) in my
code with a visitor pattern, but the advantages are not really obvious
to me.
Pros:
- cleaner code (although I think this is debatable)
Cons:
- Needs modification of the original interface and classes (to add the
accept(Visitor) method)
- If new subclasses of the acceptor interface are added, both the
Visitor interface and it's implementation needs change (adding a new
visit(MyNewClass c); to the interface). In the ladder implementation,
you only need to change at one point and add an if(...)
- A bit slower than the ladder implementation (see below)

What advantages am I missing? Why is an if ladder seen as code smell
and not the visitor pattern?

For such a simple case, why not using simple overriding ? You could add
a method Vehicle.count(int[]) with one implementation for each subclass
of Vehicle.

The example with Vehicles is not my real code, it was just used for
the measure of the speed.

You propose overriding, but this is precisely what I want to avoid. In
my real code, the same code base is shared among several places
(server/clients), but only on the client side do I need the special
action (the count() method in the simple example). So adding this
method to the Acceptor class would "pollute" the server with
unnecessary code. Besides, it would be very impractical, as the
implementation of this method requires access to classes which are
also only available on the client side (they are not part of the
shared code).

 

[Lew]

Philipp a écrit :
Micro-benchmarks are notoriously unreliable. Aside from that, the real cost
isn't run time but maintainability of the source.

For such a simple case, why not using simple overriding ? You could add
a method Vehicle.count(int[]) with one implementation for each subclass
of Vehicle.

This answer points up that a question of the form, "Should I do A or B?" is
often less powerful than, "Is there an alternative to A?" It might well be
that neither A nor B is the best option.

In the OP's case, I wouldn't have gone with the visitor pattern either. I see
the alternative to an if-ladder as polymorphism nearly always.

With an if-ladder, you have to recode for every possible scenario. With
polymorphic subclass implementations, there are idioms available that let you
configure reflectively at run time what options you have, with no recoding
necessary. If-ladders tend to be long blocks of code, polymorphic invocations
just a few lines, even if you don't use a run time configuration option.
If-ladders require a supertype to have explicit knowledge of subtypes, a very
limiting restriction. The combination of polymorphism and a factory method
frees a client from any such constraint.

It's one of my rules of thumb that blocks of if-checks for 'instanceof' should
be replaced by a polymorphic invocation.

 

[Albert]

Philipp a écrit :

Philipp a écrit :

Hello,
I think about replacing an if-ladder (with instanceof calls) in my
code with a visitor pattern, but the advantages are not really obvious
to me.
Pros:
- cleaner code (although I think this is debatable)
Cons:
- Needs modification of the original interface and classes (to add the
accept(Visitor) method)
- If new subclasses of the acceptor interface are added, both the
Visitor interface and it's implementation needs change (adding a new
visit(MyNewClass c); to the interface). In the ladder implementation,
you only need to change at one point and add an if(...)
- A bit slower than the ladder implementation (see below)
What advantages am I missing? Why is an if ladder seen as code smell
and not the visitor pattern?

For such a simple case, why not using simple overriding ? You could add
a method Vehicle.count(int[]) with one implementation for each subclass
of Vehicle.

The example with Vehicles is not my real code, it was just used for
the measure of the speed.

You propose overriding, but this is precisely what I want to avoid. In
my real code, the same code base is shared among several places
(server/clients), but only on the client side do I need the special
action (the count() method in the simple example). So adding this
method to the Acceptor class would "pollute" the server with
unnecessary code. Besides, it would be very impractical, as the
implementation of this method requires access to classes which are
also only available on the client side (they are not part of the
shared code).

if you can have only one method Vehicle.accept(Visitor v) {
v.visit(this); } and all visitor code is in the client part of the code,
then yes, it seems like to best way.

I would ask, are there other actions (beside count) that must be run on
the server ?

 

[Philipp]

I'm sure there are more ways of doing this. I don't think I know enough
about the real case to have an informed opinion on which I would use.

Sorry if my post wasn't clear. I don't really want to count anything.
I just made up this for the sake of measuring the speed difference
between using a ladder and the visitor pattern.

In my real code the actions which are taken for each subclass are much
more complicated and depend on other classes. (see my answer to Lew)

Phil

 

[Mark Space]

3. In general, I don't like tying the logical type of the vehicle so
closely to the implementing class. I can think of cases in which I might
want to have two different implementing classes to represent different
variants on a single logical vehicle, or find that a single class can
implement several logical vehicles conveniently.

This feels a bit like implementing one's own type system, something one
normally wants to avoid. The normal method is to use a marker interface
for different implementations with the same type:

class Car1 extends Vehicle implements Car {}
class Car2 extends Vehicle implements Car {}

gives the two implementations Car1 and Car2 the same type Car. However,
I don't see a good way to transform a type into a marker type. Anything
I can come up with seems pretty computationally intensive. If
performance is not a concern, that that's fine, but performance is
rarely of no concern. The "asSubclass() method of Class unfortunately
tends to return the same as Object.getClass() for marker types.

Once you get the marker type, then using your Map<T,Count> is easy.

Here's one idea:


package fubar;


public class SubClass
{
public static <T> Class<? extends T> asSubclassOf( Class<T> type,
Object o )
{
if( !type.isInstance( o ) ) {
return null; // or throw exception
}
Class<?> classX = o.getClass();
do {
Class<?>[] interfaces = classX.getInterfaces();
for( Class<?> c : interfaces ) {
Class<? extends T> subType = null;
try {
subType = c.asSubclass( type );
}
catch( ClassCastException x ) {
continue;
}
return subType;
}
classX = classX.getSuperclass();
} while( classX != null );
return null; // should never reach here
}

public static void main( String[] args )
{
Object[] test = {new Car1(), new Diesel(), new Car2(),
"Bob", new Carx(),};

for( Object o : test ) {
System.out.println( "class: " + asSubclassOf(
VehicleMarker.class, o ) );
}
}
}

interface VehicleMarker{}
interface Car extends VehicleMarker{}
interface Moped extends VehicleMarker{}
interface Truck extends VehicleMarker{}

class Car1 implements Car{}
class Car2 implements Car{}
class Diesel implements Truck{}
class Car3 implements Car{}
class Carx extends Car3{}


Output:
run:
class: interface fubar.Car
class: interface fubar.Truck
class: interface fubar.Car
class: null
class: interface fubar.Car
BUILD SUCCESSFUL (total time: 2 seconds)

 

[Mark Space]

I found a way to get rid of the try-catch. So no the method won't throw
exceptions as part of its normal operation if it has more than one
interface to parse through.

This should remove the biggest potential performance issue.

The trick is to use "isAssignableFrom()" before actually using
"asSubclass()".



public static <T> Class<? extends T> asSubclassOf( Class<T> type,
Object o )
{
if( !type.isInstance( o ) ) {
return null; // or throw exception
}
Class<?> classX = o.getClass();
do {
Class<?>[] interfaces = classX.getInterfaces();
for( Class<?> c : interfaces ) {
Class<? extends T> subType = null;
if( type.isAssignableFrom( c ) ) {
return c.asSubclass( type );
}
}
classX = classX.getSuperclass();
} while( classX != null );
return null; // should never reach here
}

 

[Philipp]

Philipp a écrit :
...

For such a simple case, why not using simple overriding ? You could add
a method Vehicle.count(int[]) with one implementation for each subclass
of Vehicle.

This answer points up that a question of the form, "Should I do A or B?" is
often less powerful than, "Is there an alternative to A?"  It might well be
that neither A nor B is the best option.

I agree with you. But this only works if you have somebody answering
who is ready to make a real effort to devise a solution. In my
experience you have more chance of getting an answer from somebody if
you ask "Would you choose solution A,B or C?" rather than asking
"What's a solution to this?". (people tend to be lazy, and answering
the former is certainly easier)

In the OP's case, I wouldn't have gone with the visitor pattern either.  I see
the alternative to an if-ladder as polymorphism nearly always.

Yes, my whole project to modify that if-ladder stems from the fact
that I also believe a polymorphic solution is better. I believed that
the visitor pattern was a clean and polymorphic solution to the
problem. (ok, it's not)

With an if-ladder, you have to recode for every possible scenario.  With
polymorphic subclass implementations, there are idioms available that let you
configure reflectively at run time what options you have, with no recoding
necessary.  If-ladders tend to be long blocks of code, polymorphic invocations
just a few lines, even if you don't use a run time configuration option.
If-ladders require a supertype to have explicit knowledge of subtypes, a very
limiting restriction.  The combination of polymorphism and a factory method
frees a client from any such constraint.

As I wrote in my answer to Albert, the same code is shared between a
client and a server. I don't want to include methods in the shared
classes which will only be of use to one side. I am thinking about
using an aggregated class, where calls to methods of the simpler,
shared class are delegated to an instance of it, and additional
methods are implemented. But as far as I see, this will result in the
ladder being in the factory.

public interface VehicleWithCounter extends Vehicle{
public int getVehicleTypeCode();
}

CarWrapper implements VehicleWithCounter, Car{
[...]


public VehicleWithCounter vehicleFactory(Vehicle v){
if(v instanceof Car){
return new CarWrapper((Car)v);
} else if ()
[...]


Phil

 

[Wojtek]

Philipp wrote :

Hello,
I compared the speed of execution of an if-ladder with the visitor
pattern for counting different types of Vehicles.
If ladder:
public void count(Vehicle vehicle){
if (vehicle instanceof Car) {
counts[0]++;
} else if (vehicle instanceof Motorbike) {
counts[1]++;
} else if (vehicle instanceof Bike) {
counts[2]++;
[...]

I set up an enum wich contains an instance of a class which does the
work:

public interface BaseWorker
{
public void doWork();
}

public class MotorBikeWorker implements BaseWorker
{
...

@Override
public void doWork()
{
.. do something
}
}

public enum CarWorker
{
MOTOR_BIKE(new MotorBikeWorker()),
BIKE(new BikeWorker());

private BaseWorker worker;

CarWorker( BaseWorker worker )
{
this.worker = worker;
}

public BaseWorker getWorker()
{
return this.worker;
}
}

public abstract class Vehicle
{
private CarWorker workerEnum;

public Vehicle(CarWorker workerEnum)
{
this.workerEnum = workerEnum;
}

public final CarWorker getWorkerEnum()
{
return this.workerEnum;
}
}

public class MotorBike extends Vehicle
{
public MotorBike()
{
super(CarWorker.MOTOR_BIKE);
}
}

You then set up the class with the correct enum. To get work done you
simply call:

vehicleInstance.getWorkerEnum().getWorker().doWork();

// um, this is from memory as my work machine is not connected to
anything

 

[Mark Space]

Class<?>[] interfaces = classX.getInterfaces();
for( Class<?> c : interfaces ) {
Class<? extends T> subType = null;

And of course subType is not longer used. That last line can be removed.

 

[Mark Space]

public VehicleWithCounter vehicleFactory(Vehicle v){
if(v instanceof Car){
return new CarWrapper((Car)v);
} else if ()

If I recall correctly, this factory pattern is exactly where Patricia's
suggestion gets used a lot.

public VehicleWithCounter vehicleFactory(Vehicle v)
{
Class<?> c = v.getClass();
Class<VehicleWrapper> vwClass = someMap.get( c );
VehicleWrapper vw = vwClass.newInstance();
vw.wrap(v);
return vw;
}


Not syntax checked or anything.

 

[Wojtek]

Wojtek wrote :

public enum CarWorker
{
MOTOR_BIKE(new MotorBikeWorker()),
BIKE(new BikeWorker());

private BaseWorker worker;

CarWorker( BaseWorker worker )
{
this.worker = worker;
}

public BaseWorker getWorker()
{
return this.worker;
}
}

Sorry, that should be:

public interface BaseWorker
{
public void doWork();

public BaseWorker getInstance();
}

and

public enum CarWorker
{

....

public BaseWorker getWorker()
{
return this.worker.getInstance();
}
}

and

public class MotorBikeWorker implements BaseWorker
{
...

@Override
public BaseWorker getInstance()
{
return new MotorBikeWorker();
}

@Override
public void doWork()
{
.. do something
}
}

 

[Mark Space]

And of course subType is not longer used. That last line can be removed.

Grammar is hard.

 

[Tom Anderson]

if you can have only one method Vehicle.accept(Visitor v) { v.visit(this); }
and all visitor code is in the client part of the code, then yes, it seems
like to best way.

You can't. You have to write the accept method (with exactly the same text
each time) in each subclass. This is one of the annoying things about the
Visitor pattern.

You do have all the visitor code in the client module, though.

tom

 

[Giovanni Azua]

Hi Tom,

You can't. You have to write the accept method (with exactly the same text
each time) in each subclass. This is one of the annoying things about the
Visitor pattern.

Not only annoying but also error-prone and pollutes the Element Model
hierarchy with unrelated concerns. But it does not have to be that way :]
e.g. there is no need for accept methods in the implementation below. The
elements are visit(ed) directly without accept roundtrips in order to
achieve the desired double-dispatch:

http://perfectjpattern.sourceforge.net/xref/org/perfectjpattern/core/behavioral/visitor/Example.html
http://perfectjpattern.sourceforge....ern/core/behavioral/visitor/PrintVisitor.html

HTH,
regards,
Giovanni

 

[Tom Anderson]

I think about replacing an if-ladder (with instanceof calls) in my
code with a visitor pattern, but the advantages are not really obvious
to me.
Pros:
- cleaner code (although I think this is debatable)

I think few people of substance would debate it. That doesn't mean they're
right, of course. Although in this case, they are.

Cons:
- Needs modification of the original interface and classes (to add the
accept(Visitor) method)

One line in the interface, a one-line method in each subclass. Plus you
have to write the visitor interface.

- If new subclasses of the acceptor interface are added, both the
Visitor interface and it's implementation needs change (adding a new
visit(MyNewClass c); to the interface).

You say that like it's a bad thing! The reason you have to change the
implementation classes is that there's a new acceptor type to deal with,
and so there has to be a new method. That seems perfectly reasonable to
me. Indeed, the strength of the Visitor pattern is that *forces* you to
deal with that.

In the ladder implementation, you only need to change at one point and
add an if(...)

And nothing forces you to, meaning that you can't statically know that
your instanceof cascades are correctly handling all the types that might
come at them.

- A bit slower than the ladder implementation (see below)

I was really surprised by that result.

What advantages am I missing? Why is an if ladder seen as code smell and
not the visitor pattern?

Because of the type safety.

About speed:

I reproduced your tests:

http://urchin.earth.li/~twic/VisitorBenchmark/

Run CountBench, with the name of a VehicleCounter implementation as a
parameter. I did that, with the -server flag; this is 1.5.0_16-b06-275 on
OS X 10.4 on PowerPC with 512 kB of L2 cache.

Times are in nanoseconds for a million Vehicles of one of three types,
giving the minimum, median, 95th centile and maximum of 101 runs:

LadderVehicleCounter - instanceof ladder
min: 43903000
med: 46210000
95%: 61168000
max: 103967000
MapVehicleCounter - keeps Count objects in a map keyed by class
min: 86440000
med: 90577000
95%: 119951000
max: 161484000
VisitingVehicleCounter - visitor
min: 65932000
med: 69357000
95%: 92353000
max: 128764000
SwitchingVehicleCounter - switch on an integer type code
min: 55286000
med: 58227000
95%: 85184000
max: 130509000

I'm surprised to see that the ladder is so much faster than the visitor,
and shocked to see that the ladder is faster than the switch! Thinking
about it, though, i would guess this is because the compiler boils the
ladder down to exactly that, a switch on an integer, where the integer is
some kind of class ID or something, and can be retrieved with a couple of
loads rather than the virtual method call it takes to get the type code.

I tried cacheing the type code, but it made all the benchmarks slower, i
assume because the objects were bigger.

I ran the counting with 8 types of vehicle on 10^8 randomly produced
vehicles 10 times alternatively (each run is ~16 sec, all 20 runs are in
one JVM execution, so warm up should be accounted for). The ladder
implementation is about 10% faster (mean time per run: ladder 16800ms,
visitor 18380).

You saw a 10% difference; i saw more like 50%. I would surmise that this
is because i had only three types of vehicle, as opposed to your eight. If
you get a chance, could you run my benchmark and post the results for
LadderVehicleCounter and VisitingVehicleCounter?

It would be interesting to generate a version of this test with, say, 100
vehicle types, and see is visitor is faster in that case!

tom

 

[Tom Anderson]

Not only annoying but also error-prone

How so?

and pollutes the Element Model hierarchy with unrelated concerns.

Not so. Exactly one short method has to be added, and that method is
fundamentally about how the hierarchy interacts, in a generic way, with
other classes, which is very much a concern of the hierarchy itself.

But it does not have to be that way :] e.g. there is no need for accept
methods in the implementation below. The elements are visit(ed) directly
without accept roundtrips in order to achieve the desired
double-dispatch:

http://perfectjpattern.sourceforge.net/xref/org/perfectjpattern/core/behavioral/visitor/Example.html
http://perfectjpattern.sourceforge....ern/core/behavioral/visitor/PrintVisitor.html

You left out the class which actually does the work:

http://perfectjpattern.sourceforge..../core/behavioral/visitor/AbstractVisitor.html

And which is based on a pretty shocking reflective strategy which gives
absolutely no type safety, and a lot of overhead (doubly so, because it's
a bad idea, badly implemented). How on earth could you describe Visitor as
'error-prone' and then offer this as an alternative?

tom

 

[Joshua Cranmer]

Not only annoying but also error-prone and pollutes the Element Model
hierarchy with unrelated concerns. But it does not have to be that way :]
e.g. there is no need for accept methods in the implementation below. The
elements are visit(ed) directly without accept roundtrips in order to
achieve the desired double-dispatch:

....

There are few cases where using reflection would actually be a good
idea. This is not on of those.

Several problems I see here:
1. You're not doing it right. If you're going to complain about the
visitor pattern being error-prone, the least you could do is to provide
a *correct* implementation.
2. Speed? Reflection is very slow and prohibits any kind of optimization
whatsoever.
3. Using reflection kills type safety, since you're essentially
prohibiting the compiler from figuring out what's going on. Another way
of putting it is that you've added dynamicism which pushes what should
be compile-time errors to runtime. Which is the wrong direction, in case
you didn't know.


Off the top of my head, I can think of only two reasons to use
reflection: either you have something akin to a scripting engine, or you
have a library that needs to be able to inspect running class methods
for various reasons.

The key thing is that reflection should be a tool of last resort, not a
cheap trick you use to get around laziness.

 

[John B. Matthews]

I dug out Effective Java by Joshua Bloch. He goes into factory patterns
in that book, including the Service Provider pattern. I stole his idea
and implemented a short example below how it might work. You should get
his book, good stuff in there. [instructive example elided]

That item[1] and others were recently reprinted in Dr. Dobbs. These and
the sample chapter on generics are exemplary of the entire book[2]:

[1]<http://www.ddj.com/java/208403883>
[2]<http://java.sun.com/docs/books/effective/>