Sounds like the work done by tree traversals weren't high overhead in general for your workload. But it does matter for some workloads.
> Similarly, I worked a lot on a browser engine in the past and virtual method dispatch was again not this clear cut performance killer.
We're seeing large gains from, as far as we can tell, having fewer virtual method calls than other engines. Eliminating virtual dispatch opens up a huge range of call-site optimizations since the methods can often be statically inlined (as well as reducing the load on the branch target buffer).
That doesn't match my experience. Devirtualization opens up lots of inlining opportunities, and inlining is one of the most critical optimizations that compilers can do (mostly because of the other optimizations that it opens up; e.g. const propagation, GVN, etc. etc.)
See this study: http://hubicka.blogspot.com/2014/04/devirtualization-in-c-pa...
Devirtualization optimizations improve Dromaeo by 7-8%. That's a significant win, especially since devirtualization is only a best-effort optimization and Dromaeo has a lot of JS in it.