As others have pointed out, the fact that in the visitor pattern version you (individually) heap-allocate all your shapes in each iteration does skew the results. I replaced the Box with an enum that represents the union of all Shapes enum ShapeUnion { Circle(Circle), Rectangle(Rectangle), Square(Square), } impl for &'a ShapeUnion { fn into(self) -> &'a dyn Shape { match self { ShapeUnion::Circle(c) => c, ShapeUnion::Rectangle(c) => c, ShapeUnion::Square(c) => c, } } } and replaced the relevant code. It yielded an average of about 6.6ms for the visitor pattern vs 6.9ms for the (pure) pattern matching. Is this solution useful realistically? It might be if you are already stuck using traits and you really need the performance advantage of using a tagged union on the stack instead of boxed trait objects. Otherwise it's just much more verbose. Just creating the Vec once instead of in each iteration led to about 21.5ms for the visitor pattern pattern vs 5.5 ms for the pattern matching. The original code yielded about 168ms for the visitor pattern vs 6.8ms for the pattern matching.
That is equivalent to the second example with pattern matching; just with additional unnecessary abstractions. It's a tradeoff between being dynamic, allowing extensibility outside the module itself (i.e. as libraries) versus, knowing the types ahead of time in code you own. Traits helps with the former, pattern matching helps with the latter.
@@dealloc That's assuming you haven't actually written any code yet. If you have already used that trait in a bunch of places, an enum wrapper might be a better solution in certain situations than doing a massive refactor.
I think the reason why Visitor DP were created is because it was impossible to add the functionality (methods) to already implemented classes in languages such as Java and C#, but in Rust, there is possibility to add additional methods to existing structs via traits (also in Go via interfaces).
I agree, you can always add more functionality to a struct by making it implement a trait. But also, there are interfaces in Java and C# which basically serve the same cause. I think the visitor pattern mainly shines by increasing the modularity and flexibility, all while keeping the functionality in a separate space. But as always in software design, good design is very situational and subjective.
Somewhat. The limitation with traits is that you cannot implement own traits on foreign types, without having to create a newtype that wraps those foreign types which makes it marginally more difficult to extend functionality for third-party implementation that you don't own. An example of this is seen in serde which uses the visitor pattern to support for de/serialization of different data types and formats. But it also works well for implementations that does some form of traversal over data, especially in tree-like structures (ASTs, XML, etc.)
Hey Jan, thank you very much for the thoughtful comment! I appreciate when discussions about technical topics arise in the comments. I agree that a big driver of the inefficiency of the visitor pattern is the dynamic memory allocation. However, without boxing, no dynamic dispatch, and without dynamic dispatch, no visitor pattern. So I think it's fair to account for some dynamic memory allocation in the benchmark. The example I showed is probably a bit on the extreme side though, I see. Allocating 15 shapes on the heap in every iteration is a worst case scenario. Only allocating all of them once seems a bit optimistic though, in terms of comparison to real world application. The truth is probably somewhere in the middle. Just for the fun of it, I re-ran the benchmark and created all the shape enum variants for the pattern matching code on the heap as well. A factor of 2x still remains, which is now mainly caused by the dynamic dispatch of the visitor pattern vs the static dispatch of pattern matching. But of course, a 2x increase in performance, although significant if applied to a hot path in real applications, does not make for a good thumbnail :D I hope to see you back on the channel! Stay healthy
That's the whole idea behind the visitor pattern. Watch my dedicated video on it, and you will find out why it is desirable to separate state and functionality.
@GreenTeaCoding I just watched but this not on the vistor, but still why not one visit method with pattern match or even switch? Now shape must have knowledge that visit_shape method exists otherwise every apply method can be the same... Maybe I must watch again becase my brain don't get this pattern enough 😅
Yeah, the visitor patter is a bit of a weird one if you start getting into it. The "trick" is that every shape knows which method to call on the visitor, i.e. the circle will call visit_circle(). Like this, you don't have to do reflection/introspection.
dynamic dispatch for me means that types might be added on runtime, or you create things other code binds to; otherwise however, i usually rather use traits, and implement them on the struct, because i find that they change much less, so i might need to think about whether i can apply the visitor pattern more to my code.
@@GreenTeaCoding The OOP approach is virtual functions that must be implemented in each class, violating Open/Closed Principle. But by adding a new trait, all implementations of that trait can be located in the same place (just like a visitor class implementation), and you don't even have to implement a function that accepts the visitor on each type. Adding a new trait is much closer to the pattern matching approach, except that the compiler does the pattern matching (the dispatch).
Congratulations for the channel. Really good content and well made.
Thank you for the nice words :)
As others have pointed out, the fact that in the visitor pattern version you (individually) heap-allocate all your shapes in each iteration does skew the results. I replaced the Box with an enum that represents the union of all Shapes
enum ShapeUnion {
Circle(Circle),
Rectangle(Rectangle),
Square(Square),
}
impl for &'a ShapeUnion {
fn into(self) -> &'a dyn Shape {
match self {
ShapeUnion::Circle(c) => c,
ShapeUnion::Rectangle(c) => c,
ShapeUnion::Square(c) => c,
}
}
}
and replaced the relevant code. It yielded an average of about 6.6ms for the visitor pattern vs 6.9ms for the (pure) pattern matching. Is this solution useful realistically? It might be if you are already stuck using traits and you really need the performance advantage of using a tagged union on the stack instead of boxed trait objects. Otherwise it's just much more verbose.
Just creating the Vec once instead of in each iteration led to about 21.5ms for the visitor pattern pattern vs 5.5 ms for the pattern matching.
The original code yielded about 168ms for the visitor pattern vs 6.8ms for the pattern matching.
That is equivalent to the second example with pattern matching; just with additional unnecessary abstractions.
It's a tradeoff between being dynamic, allowing extensibility outside the module itself (i.e. as libraries) versus, knowing the types ahead of time in code you own. Traits helps with the former, pattern matching helps with the latter.
@@dealloc That's assuming you haven't actually written any code yet. If you have already used that trait in a bunch of places, an enum wrapper might be a better solution in certain situations than doing a massive refactor.
I think the reason why Visitor DP were created is because it was impossible to add the functionality (methods) to already implemented classes in languages such as Java and C#, but in Rust, there is possibility to add additional methods to existing structs via traits (also in Go via interfaces).
I agree, you can always add more functionality to a struct by making it implement a trait. But also, there are interfaces in Java and C# which basically serve the same cause. I think the visitor pattern mainly shines by increasing the modularity and flexibility, all while keeping the functionality in a separate space. But as always in software design, good design is very situational and subjective.
Somewhat. The limitation with traits is that you cannot implement own traits on foreign types, without having to create a newtype that wraps those foreign types which makes it marginally more difficult to extend functionality for third-party implementation that you don't own.
An example of this is seen in serde which uses the visitor pattern to support for de/serialization of different data types and formats. But it also works well for implementations that does some form of traversal over data, especially in tree-like structures (ASTs, XML, etc.)
Nicely done and very thorough!
Glad it was helpful!
Hi, I really like your Videos
Hey Jan,
thank you very much for the thoughtful comment! I appreciate when discussions about technical topics arise in the comments.
I agree that a big driver of the inefficiency of the visitor pattern is the dynamic memory allocation. However, without boxing, no dynamic dispatch, and without dynamic dispatch, no visitor pattern. So I think it's fair to account for some dynamic memory allocation in the benchmark.
The example I showed is probably a bit on the extreme side though, I see. Allocating 15 shapes on the heap in every iteration is a worst case scenario. Only allocating all of them once seems a bit optimistic though, in terms of comparison to real world application. The truth is probably somewhere in the middle.
Just for the fun of it, I re-ran the benchmark and created all the shape enum variants for the pattern matching code on the heap as well. A factor of 2x still remains, which is now mainly caused by the dynamic dispatch of the visitor pattern vs the static dispatch of pattern matching. But of course, a 2x increase in performance, although significant if applied to a hot path in real applications, does not make for a good thumbnail :D
I hope to see you back on the channel! Stay healthy
I have question about first code, why separate methods to every shape? Does it not only move our problems to the other side?
That's the whole idea behind the visitor pattern. Watch my dedicated video on it, and you will find out why it is desirable to separate state and functionality.
@GreenTeaCoding I just watched but this not on the vistor, but still why not one visit method with pattern match or even switch? Now shape must have knowledge that visit_shape method exists otherwise every apply method can be the same...
Maybe I must watch again becase my brain don't get this pattern enough 😅
Yeah, the visitor patter is a bit of a weird one if you start getting into it. The "trick" is that every shape knows which method to call on the visitor, i.e. the circle will call visit_circle(). Like this, you don't have to do reflection/introspection.
dynamic dispatch for me means that types might be added on runtime, or you create things other code binds to; otherwise however, i usually rather use traits, and implement them on the struct, because i find that they change much less, so i might need to think about whether i can apply the visitor pattern more to my code.
Sooo, why can't I just create a trait with the method area and implement it for all the shapes as I create new ones and call it a day?🤔
That's the default OOP approach. It works, but has different characteristics compared to the visitor pattern. It is explained in the video.
@@GreenTeaCoding The OOP approach is virtual functions that must be implemented in each class, violating Open/Closed Principle. But by adding a new trait, all implementations of that trait can be located in the same place (just like a visitor class implementation), and you don't even have to implement a function that accepts the visitor on each type. Adding a new trait is much closer to the pattern matching approach, except that the compiler does the pattern matching (the dispatch).
I would like to believe the performance gets butchered due to the syscal overhead. Is there a way to re-use heap allocations? 13:20
True, this is a big part of it. I answered this issue in depth on the comment of @jhscheer.
now transform the vec of enums to a struct of vecs and speed up even more