Hi > > No boilerplate removal code 1:30min > > Uniplate with PlateDirect (fastest method) 1:45min > > Uniplate with PlateData (based on SYB) 5min > > > > And I suspect directly using SYB would have been somewhere in the > > 10-15min range. > > > > It would be useful to have more information about the causes > for those timings. As I recall, the main sources of inefficiency > in SYB were (a) traversing irrelevant parts of the structure > (because everything is treated generically)
Yes, this is a big one. In particular Haskell String's being defined as [Char] makes SYB do a lot of redundant work on characters which are unlikely to be the target. SYB's types for everything/everywhere are too general to allow the Uniplate solution, but it would be easy to add universe/transform to SYB and implement them using them much more efficiently. , (b) combining > results in simple, but inefficient ways ((++) nesting with the > structure) In my experience a lot of uses of everything have (++) as their join operator. It's fairly simple to redefine a special everythingList = everything (++) which is smarter and avoids an O(n^2) append cost. It would be fairly easy to add a RULE doing this. This everythingList would correspond to universeBi in Uniplate. , (c) repeated runtime type checks to determine which function to > apply. Yes, very expensive. The absense of these tests doubles performance in Uniplate. I don't see a way to remove them using SYB. So, using rough intuition, I'd say a > c > b in terms of the cost. b is fairly trivial to fix, a requires an API change, c probably can't be eliminated easily. > As an extreme step, one could > prototype using SYB, then switch to handtuned traversals for successful but > inefficient prototypes. As Neil points out, that tuning need not even change > the interfaces. It's not even an extreme step, its the suggested way of working with Uniplate. Use PlateData (i.e. based on SYB), if you need more performance, switch to PlateDirect. > > My view is that anyone manipulating an abstract syntax tree inside a > > compiler without using some form of generic programming is doing it > > wrong. > > This also applies to other Ast manipulating tools. For this fairly general definition I had intended to treat Ast manipulation tools as generic programming :-) Thanks Neil _______________________________________________ Cvs-ghc mailing list [email protected] http://www.haskell.org/mailman/listinfo/cvs-ghc
