Zero-Overhead Tree Processing with the Visitor Pattern | Hacker News Reader

Zero-Overhead Tree Processing with the Visitor Pattern

lihaoyi.com

215 pointslihaoyi80 comments

In 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" :)

> 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

I 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!

Not quite a part of "Java culture". See Roslyn compiler, .NET Expression tree, C++ `std::visit` or tons of DOM tree rewriting js stuff.

Actually `visitor` and `pattern matching` are not mutually exclusive. imo the only difference is that in the visitor pattern, if you don't have anything to update, you just return the original node.

Thank you! I agree that just using of pattern matching may be not enough. But, instead of Visitor Pattern, I would use generic traversal "strategies" (combinators). My ideal is a DSL with first-class term rewriting rules + user definable strategies which take these rules as arguments. In fact, I already use such DSL for compiler writing :)

I think you've (re)discovered the -morphisms. E.g. anamorphism, catamorphism, hylomorphism. Data structure traversals of various kinds can usually be cast in terms of these morphisms.

As it turns out GHC is usually pretty good at optimizing this kind of thing due to the extremely aggressive inlining which is possible when you know that there are no side effects. It'll often handle compositions of traversals with no sweat. (I think it's sort of all lumped in as "fusion".)

EDIT: See tel's comment in this thread. He always understands and explains it much better than I can.

> For some reason almost every good compiler/compiler textbook uses pattern matching: Appel, nanopass, CompCert, DMS etc.

Here is Appel's Java-based compiler book: https://eden.dei.uc.pt/~amilcar/pdf/CompilerInJava.pdf. It's full of visitors. If the same book's ML version uses pattern matching instead, then that says a lot about the different implementation languages and not much about what you wanted to claim.

Well, it's another "Java-related compiler textbook". And this edition has a coauthor (Jens Palsberg) who is responsible for all OOP/Java-related things in the book. I recommend to read original ML edition even for Java developers. And I'm not the only one who recommends it.

"Comment by Vladimir N. Makarov: Another good book to start to study compilers from parser to code generation and basic optimizations. I especially like the version in ML (Modern compiler implementation in ML).

Comment by Steven Bosscher: The version in ML is the best of the three. The other two look too much like "had to do this"-books where algorithms are translated from ML, which makes them look very unnatural in C/Java." [1]

[1] http://gcc.gnu.org/wiki/ListOfCompilerBooks

Pattern matching isn't used in the Java community because it doesn't exist, and there is nothing inherent in pattern matching that makes it less performant than double virtual dispatch. And anyone who thinks the visitor pattern is more readable is probably not someone I want to code with. The visitor pattern is very high on boilerplate and makes the flow of your code harder to read.

The Clang and Swift compilers use Visitors for just about everything AST related.

This 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

> 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.

The general solution for heterogenous layers requires indexing the layers. The x type variable ends up having kind `Index -> *` for your index type Index.

Wadler, Philip (1990). "Deforestation: transforming programs to eliminate trees". Theoretical Computer Science. 73 (2): 231–248.

http://homepages.inf.ed.ac.uk/wadler/papers/deforest/defores...

Not 100% the same thing, but definitely related. Thanks for the reference :)

How is it zero-overhead? The visitor pattern at the very least requires dynamic dispatch, which isn't free.

The zero-overhead here seems to refer to not constructing intermediate representations when chaining visitors.

The 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.

The visitor pattern uses dynamic dispatch on the type of the visitor.

Did you mix up dynamic dispatch with double dispatch in your comment?

Yes, my bad. Although the point still stands, visitor is normally an alternative to languages without dynamic dispatch.

Visitor was conceived in Smalltalk and adapted to other languages later.

So that seems like quite a stretch.

I take it back, you are correct.

In JVM languages maybe, in C++ with the CRTP there's zero overhead for sure

Why the CRTP? Plenty of zero-overhead Visitors have been implemented with regular templates. I don't see the connection.

It'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.

Is 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.

Almost 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.

Polymorhic call sites can hardly be called 'zero overhead' - they remove any chance for inlining to begin with. So no, JVM is not amongst them

I don’t think this is true. If you know the set of functions that can be dispatched to, you could inline them in a jump table / switch statement. JVM could definitely do this since it doesn’t even need to know the full set; it could inline new functions as it encounters them. This is all theoretical, of course.

This is exactly what the JVM does. See [0].

[0] https://mechanical-sympathy.blogspot.com/2012/04/invoke-inte...

>>jump table / switch statement.

>This is exactly what the JVM does. See [0].

The jump table from Martin's blog is the virtual call one.

Monomophisation is a common optimization on the JVM, combined with a guard condition that de-optimizes should the type assertion fail. Not sure if that only affects the hot path.

There are inline caches (IC) and JVM uses that to a point. The inline caching for hotspot is 2 targets with guard checks[0] and then a polymorphic call. However if there are no dominating/common calls the IC is useless.

On top of that JVM has an inline budget and just stops at a point. So the switch stuff ain't happening for megamorph.

[0]:https://blog.h2o.ai/2010/04/inline-caches-and-call-site-opti...

Since 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.

Overhead would "loosely" relate to better performance, and v-table dispatch type that visitor pattern is built upon, cannot be considered 'zero overhead'.

It's a trade off and the article shows no proof the of an improved performance by reducing the 'overhead'. For example object allocation in JVM is really cheap (pointer bump in the TLAB + check&perfectly predicted jump), reusing objects in a cycling list/buffer is similar, etc. In the end the post is about performance and I pointed that the multiple mentions of 'zero overhead' are incorrect.

Ah yes. So triggering a GC in the middle of your duplicated tree-on-heap traversal will totally not risk any pipeline stalls. I'm sure that N vtable calls per node is totally worse than re-enumerating the objects on the heap N times.

When I talk about how the OO community has anti-intellectual toxicity can try to buzzword bingo architecture away, Visitor is my go to example. Because that's sure what it seems like to me.

You will 100% end up with pipeline stalls with a sufficiently large, random input anyways. This complaint about vtables is not substantial in this case, and I welcome you to prove they do.

Not 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.

It 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.

Meta 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.

I've never read or written Scala and had no trouble following this. The author wasn't doing anything fancy.

The 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.

The parsing example is very similar to "push" / event based parsers e.g. the SAX XML parsing API.

I 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.

Or, use pattern matching for significantly less boilerplate. Double dispatch isn’t free either.

Or 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).

I 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.

The 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.

> the basic OO principle of encapsulating state and behavior

Not everything you might want to program necessarily fits the principles of your religion.

An abstract syntax tree in particular isn't something where information hiding makes a lot of sense. You need the details in the tree.

You're looking at an example use of the Visitor pattern that both simplifies and optimizes code.

> It fundamentally violates the basic OO principle of encapsulating state and behaviour.

The kind of principle that most realise is a mistake of enormous proportions.

We absolutely use a variant of this technique in Haskell. We absolutely do not need type classes (of any order) to make it work (although type classes and type families certainly clean up the implication). We need a Fixpoint lifting, a way to consider an object as a functor (which we could do at the value level). The rest is simple functions.

I was surprised how similar it looks in Java. I hadn't considered how it would look.

Is this actually double dispatch? Visitor is a pattern that can be used for double dispatch, but I only count one guaranteed dispatch here.

I'm not convinced that folks here saying, "We just us pattern matching like functional programming does" actually know how modern functional programming does this. From the perspective of runtime overhead and code size, this approach is very similar to recursion-schemes.

Where RS excels over this approach is not in the use of pattern matching, but in the fact that it can reuse the functor structure to not even have to write the descending algorithm; it comes for free as part of your fixpoint functor.

Or, for an example of actual-zero-overhead tree processing using the visitor pattern:

https://medium.com/@swortelbernux/libraryless-reflection-in-...

Yeah, 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.

For 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....

(Written in 2011. In the article, multimethods are used rather than protocols)

I 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?

He 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.

From a functional perspective, aren’t visitors just a case of ‘map’ with potential side effects? That handles composition, streaming, and so on

Yes, 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-sc...

Looks 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.

this is a fairly trivial thing to do in computer science.

This is how all of Rust's iterators and iteration protocol work. Including standard library and other tree structures, graphs, etc.

This 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...

Why 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.

It's advantageous for unit testing (smaller units) and debugging too, IMO.

A nostalgic article into coding practices of 15 years ago.

Do you know of any more modern technique?

This 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.

Free dispatch

this is completely trivial in functional programming.

Fellow (?) 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.

Our 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.

This 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.

You and I weren't there so without details it's hard to say whether it's sensible or over-engineered

Given 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."

Visitor 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.

I'm not referring to the Visitor pattern in Abstract, I'm referring to the specific solution the author of the article we are discussing employed.

There is no such thing as a pattern that always increases clarity. That's not what patterns are for, so that's unsurprising. It's the case though that this specific application has pretty much only benefits.

Reply on news.ycombinator.com