19 ms·
Zero-Overhead Tree Processing with the Visitor Pattern
- lmz 8y agoThe parsing example is very similar to "push" / event based parsers e.g. the SAX XML parsing API.
- zaphar 8y agoI was going to say the same thing. I've converted XML processing code that took hours to run into code that took minutes just by switching to SAX parsing. The lower overhead has a drastic impact on runtime.
- ginko 8y agoHow is it zero-overhead? The visitor pattern at the very least requires dynamic dispatch, which isn't free.
- andreareina 8y agoThe zero-overhead here seems to refer to not constructing intermediate representations when chaining visitors.
- mping 8y agoThe visitor pattern is an alternative to dynamic dispatch. Normally instead of using dynamic dispatch you inverse caller and callee roles and pass 'this'. The article uses a variation of the classic visitor pattern.
- saurik 8y agoThe visitor pattern uses dynamic dispatch on the type of the visitor.
- jmartinpetersen 8y agoDid you mix up dynamic dispatch with double dispatch in your comment?
- IloveHN84 8y agoIn JVM languages maybe, in C++ with the CRTP there's zero overhead for sure
- frankzinger 8y agoWhy the CRTP? Plenty of zero-overhead Visitors have been implemented with regular templates. I don't see the connection.
- humanrebar 8y agoIt's moot either way. There is dynamic dispatch based on use provided inputs. There will always be lookups, jumps, and cache misses regardless of the syntax or semantics.
- frankzinger 8y agoIs it moot? With templates, the Visitor type is selected at compile time and needn't even be polymorphic. The member function call(s) can often be inlined. Pretty sure there is no dynamic dispatch or jumps in such a scenario. Cache misses, sure, but I don't think that's important in this case.
- humanrebar 8y agoAlmost always these systems operate on external inputs like source files or JSON blobs. You cannot compile time collapse the branching needed to parse that sort of thing.
- xxs 8y agoPolymorhic call sites can hardly be called 'zero overhead' - they remove any chance for inlining to begin with. So no, JVM is not amongst them
- KirinDave 8y agoSince you're on the hook for a polymorphic call anyways in a rewrite of a runtime runtime structure, I think this is not the "overhead" that anyone was talking about.
- Yoric 8y agoNot in all languages. You can easily implement a visitor pattern with purely static dispatch in, say, Rust or C++. I suspect that any JIT that performs sufficient specialization/inlining will also achieve the same result once warm.
- KirinDave 8y agoIt isn't overhead to have a dynamic dispatch; you're traversing a runtime structure with variable shape. I can always construct a Map that will force you into a the case of dynamic dispatch in JSON. The only way we could remove that overhead is by fully fixing the shape of the tree and all maps at compile time (which has its uses, but in a different context). The fact that you can fuse multiple passes into one alteration (or reconstruction) of the tree is what's a removal of overhead.
- bakhy 8y agoI think in C# nowadays I'd implement Select and SelectMany for the data type I want to visit, and then use LINQ. This is one pattern which is easier in a functional approach. I presume it would be easy to do something similar in Scala?
- louthy 8y agoOr, use pattern matching for significantly less boilerplate. Double dispatch isn’t free either.
- ScalaMilano 8y agoOr use type classes. I do think visitor pattern, type classes and pattern matching have different areas where responsibility lies and how it is distributed (with pattern matching the most local, visitor pattern extensible without by classes and type classes - which I prefer - extensible at the call site).
- dnomad 8y agoI think the Visitor pattern is an antipattern. I've never seen a non-trivial application that didn't become a huge mess. It fundamentally violates the basic OO principle of encapsulating state and behavior. Anything else -- reifying the events into first-class types, factoring out the overlap into a new type, generics, even Scala-style traits -- is better.
- quelltext 8y agoThe whole point is to separate behavior from the datastructure. Yes, this doesn't fit nicely into OO principles, but strictly that's true any time you externally query an object for state and make a conditional decision based on the result. Inevitably, any method (visitor, pattern matching, if elsif) of customizable walking of a tree datastructure separates behavior from the tree object. That's the point, though, again. Now, you can say wanting to do that (customizable tree walking) in itself is an antipattern and shouldn't be done. That just doesn't match well with reality. I've seen many cases where the visitor pattern is about the best one can do. Yes, it becomes ugly but that's usually due to the complexity of the attempted tree walking, e.g. for transformation. A lot of the alternative approaches in the functional world become ugly too once there's a need to offer maximum customizability, e.g. in terms of order of evaluation. If you are able to sufficiently constrain the domain you can get away with some simplied templates, but where I see visitors most often is in API's wanting to offer any kind of tree walking.
- ris 8y agoYeah, there is a neatness to it. I manage to achieve a similar thing with recursive generators in python quite often, which ends up being quite concise.
- richard_shelton 8y agoIn fact, it's a rather old question: what is better 1) a declarative approach with pattern matching or 2) Visitor pattern from OOP world. Ok, better for what? Let's take a practical example: AST transformations inside a compiler. You may find Visitor pattern use only in a few Java-related compiler textbooks. For some reason almost every good compiler/compiler textbook uses pattern matching: Appel, nanopass, CompCert, DMS etc. Ok, but the real point of the article is not that "visitors" are more readable and easy to use, but they are more perfomant, right? Do we have any profiling here? Maybe with a good GC it will cost almost nothing for us to build another tree in terms of speed? We remember the words about "premature optimization", and any "manual optimization" which makes the algorithm structure foggy is evil so (necessary evil -- in some rare cases). In some declarative languages pattern matching constructs are converted to a fast decision trees by compiler. There are some "lazy" approaches to pattern matching. Or you can just provide a list of transforming (maybe some composition of transformations) functions to your generic pattern matching function. It's almost the same as using "visitors", but you don't need to call "The Team Architect™, for supervising the object oriented quality of your software" :)
- lihaoyi 8y ago> You may find Visitor pattern use only in a few Java-related compiler textbook The Java standard library uses ASM heavily for it’s method handle JIT compiler implementation, which is all visitor based. As does the Scala compiler. ASM is extremely widespread for anyone doing jvm bytecode work and isn’t exactly something you find only in textbooks > Maybe with a good GC it will cost almost nothing for us to build another tree in terms of speed Not sure what environment you work in, but converting uPickle to a visitor-based architecture from recursive transformation sped it up 3x on the JVM and 10x on Node.js. I’d love to have a GC that could elide the intermediate trees but the GCs I have aren’t up to snuff
- richard_shelton 8y agoI guess things you've mentioned are widespread inside the Java community. But let's consider the things that have more global impact to compiler writers. For example, Scala LMS is a very interesting and promising recent project. Take a look at its source code -- no Visitor pattern inside. Visitor pattern may be necessary part of "Java culture", but for Scala I see no real reason to keep using it. P.S. Thanks for the real perfomance data!
- djsumdog 8y agoOur current principal engineer has implemented the visitor pattern for a bunch of things in our current project. It's a quite ugly implementation we shot down in code review and then we had an entire meeting where he defended it and eventually it got let in. He's used the visitor pattern in a few other areas as well. I'm not a big fan.
- KirinDave 8y agoThis technique improves readability, improves abstraction, improves testability, and improves performance. Please don't confuse your superstitions or local culture's distaste for properly researched architecture for a more general sense of code quality. Simply saying, "I saw the word visitor and got mad," not only is disrespectful to the author, but it's disrespectful to your entire profession.
- fenwick67 8y agoYou and I weren't there so without details it's hard to say whether it's sensible or over-engineered
- KirinDave 8y agoGiven the fact that this is a combination of well-known techniques, trivially offers performance benefits, and makes the transformation part of the code testable in isolation from the process or recursion, it's a smart first pass. I think most experienced OO engineers could sit down and write this in one pass. Calling it overengineered is pretty ridiculous IMO. "Over-engineered" doesn't mean, "Because software training is often inadequate someone might encounter this for the first time in industry rather than in school."
- phyzome 8y agoVisitor pattern definitely does not automatically improve readability or clarity. (In the general case! Summing values would be an exception.) In fact, I'd see it as a performance/readability tradeoff in any language where recursive tree processing is ergonomic. Not even knowing the language involved, there's really not much to say.
- OJFord 8y agoIt's advantageous for unit testing (smaller units) and debugging too, IMO.
- kizer 8y agoLooks like the pattern effectively linearizes the hierarchical structure. So you can stream or iterate over the ouput of a visitor run, as the author said. Could one just implement an iterator on top of a tree structure? This would be similar but be imperative right rather than declarative as you would not provide a “callback”, but pull out nodes directly.
- rs86 8y agothis is a fairly trivial thing to do in computer science.
- mark_edward 8y agoThis is how all of Rust's iterators and iteration protocol work. Including standard library and other tree structures, graphs, etc.
- rs86 8y agothis is completely trivial in functional programming.
- phyzome 8y agoFellow (?) functional programmer here. I would generally use a recursive descent algorithm on a tree. That's the natural approach, yes? But the entire point of the article was that if you use a streaming approach you can get some performance benefits. I would say it's not totally trivial in most languages, and that it's slightly more extra work in functional languages.
- falcolas 8y agoMeta about the article: "Let's use a simplified JSON style tree consisting of only a few types" followed immediately by "Here's the Scala code with a discussion of Scala specific implementation details". Not exactly all that friendly a method to discuss a topic. Someone at a point in their career where they may have derived value from this blog post is likely to be immediately and hopelessly lost. Instead, introduce one thing at a time. If you're talking about a new concept, don't introduce it using a complex language - use something the reader will be familiar with. I personally dislike JavaScript, but it's still a much better choice for this. Or Python. Or even plain old Java - lots of folks cut their teeth in college on Java.
- phyzome 8y agoI've never read or written Scala and had no trouble following this. The author wasn't doing anything fancy.
- philipkglass 8y agoThe author writes Scala libraries and tools and blogs about Scala. It's "not friendly" only if you're expecting him to write for a different audience than the one he's addressing.
- fnordsensei 8y agoFor processing JSON in Clojure, I've used zippers, modifying the tree or leaf nodes by protocol dispatch. More because it seems how the task is "supposed" to be done in Clojure rather than based on any particular understanding of whether there are alternative methods out there, and if so, which would be the better method. I found this blog post discussing the differences between visitors and zippers: http://www.ibm.com/developerworks/library/j-treevisit/index.html http://www.ibm.com/developerworks/library/j-treevisit/index.... (Written in 2011. In the article, multimethods are used rather than protocols)
- nbevans 8y agoA nostalgic article into coding practices of 15 years ago.
- Yoric 8y agoDo you know of any more modern technique?
- KirinDave 8y agoThis technique is still relevant today and even cutting edge papers often use a more general variant of this technique to get work done. But you're right, once upon a time, training and appropriate architectural decisions were a lot more valued by the OO community.
- swort 8y agoOr, for an example of actual-zero-overhead tree processing using the visitor pattern: https://medium.com/@swortelbernux/libraryless-reflection-in-c-288d7873e3a6 https://medium.com/@swortelbernux/libraryless-reflection-in-...
- hagreet 8y agoTell me more about your zero overhead JavaScript.
- peterkelly 8y agoWadler, Philip (1990). "Deforestation: transforming programs to eliminate trees". Theoretical Computer Science. 73 (2): 231–248. http://homepages.inf.ed.ac.uk/wadler/papers/deforest/deforest.ps http://homepages.inf.ed.ac.uk/wadler/papers/deforest/defores...
- Yoric 8y agoNot 100% the same thing, but definitely related. Thanks for the reference :)
- nebulous1 8y agoHe should have led with the reasons for using it, and his definition of zero-overhead. Composability without intermediate data structures seems to be the major use case.
- jacobtracey 8y agoFree dispatch
- mattbierner 8y agoFrom a functional perspective, aren’t visitors just a case of ‘map’ with potential side effects? That handles composition, streaming, and so on
- KirinDave 8y agoYes, but from a functional perspective you need to do extra work to make generalized recursive applications possible. If you're interested, the name is "Recursion Schemes". Avoid the paper, its notation is too challenging. This blog has a long running series which is much better: http://blog.sumtypeofway.com/an-introduction-to-recursion-schemes/ http://blog.sumtypeofway.com/an-introduction-to-recursion-sc...
- tel 8y agoThis is pretty common in Haskell using the "recursion schemes" technique. The idea is to note that any recursive data type can be constructed by laying many "layers" down. For instance data Json = Str String | Int Int | Dict [(String, Json)] has the "layer" type data JsonLayer x = StrL String | IntL Int | DictL [(String, x)] You could also "layerize" the list in here which is what the author did with the DictVisitor, but I'll leave it as is for simplicity now. We can recover the original type using the layers and the "type level fixed point operator" newtype Fix f = Fix { unwrap :: f (Fix f) } If you unwind this, it says Fix JsonLayer = JsonLayer (Fix JsonLayer) = JsonLayer (JsonLayer (Fix JsonLayer) = JsonLayer (JsonLayer (JsonLayer (...)) On the other hand, we can recursively consume values of `Fix JsonLayer` (and, equivalently, Json) with functions of the shape type Alg f a = f a -> a type JsonAlg a = JsonLayer a -> a In other words, it tells us how to get a result from a single layer (where the recursive parts have already had their results computed). This is the Json visitor, though you can rewrite the type to be something more familiar -- isomorphic to Alg JsonLayer a data JsonVisitor a = JsonVisitor { onStr :: String -> a , onInt :: Int -> a , onDict :: [(String, a)] -> a } You can write a function which consumes Fix'd data types using an appropriate Alg that is totally generic, or you can write a specific one for consuming Json using `Alg JsonLayer` -- commonly seen as consume :: (JsonLayer a -> a) -> (Json -> a) consume :: JsonVisitor a -> (Json -> a) consume v (Str s) = onStr v s consume v (Int i) = onInt v i consume v pairs = onDict v $ map (\(n, json) -> (n, consume v json)) pairs
- dllthomas 8y ago> You could also "layerize" the list in here Is that the answer to "how do recursion schemes handle heterogenous layers"? I'd love to learn more.
- tel 8y agoThe general solution for heterogenous layers requires indexing the layers. The x type variable ends up having kind `Index -> *` for your index type Index.
- drfrank 8y agoThis is the article that I share with my coworkers when I see them reaching for the Visitor Pattern: https://lostechies.com/derekgreer/2010/04/19/double-dispatch-is-a-code-smell/ https://lostechies.com/derekgreer/2010/04/19/double-dispatch...
- KirinDave 8y agoWhy is this article even remotely applicable here, Dr. Frank? Not only does this technique factor away the recursive part of the algorithm from the transformative, but it improves performance at the same time. Any time you can abstract to a simpler requirement (that is more testable) and gain performance, this is like finding a silver dollar at the beach. You should take it and be thankful. I think an awful lot of OO programmers see "visitor pattern" and immediately their body clenches because they've been given warnings over and over about how "multiple dispatch is dangerous and confusing." And when it's used in specialized code instead of generic code, that's true. But when it's used to separate business logic from algorithmic implementation, it's nearly always a net win.