Re: Visitor pattern vs if-ladder
On Thu, 23 Apr 2009, Philipp wrote:
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
--
unconstrained by any considerations of humanity or decency