Redefine recursive traversals via local helper functions

[sergv]

This should improve library's performance because:

1. There will be less arguments passed around on each function invocation
2. Redefined via recursive helpers functions like everywhere could be automatically inlined at the call site by GHC. Before this change they were not eligible for inlining because they were recursive. Now their inlining information is automatically added to the .hi file by ghc (tested with 8.2.2).

[sergv]

@dreixel Bump, please?

[dreixel]

I don't really maintain syb anymore, but I'm happy to transfer whatever's necessary to a new maintainer.

[sergv]

I wouldn't mind spending some time on maintaining syb. If you please, would you mind transfering maintainership to me?

I'll need Hackage upload access (add SergeyVinokurov to maintainers at http://hackage.haskell.org/package/syb/maintain) and access to the git repository. If you don't want repository hanging around you can transfer it, otherwise please just allow me to merge PRs.

[dreixel]

Would you mind just sending an email to cafe proposing to become the package maintainer? Just in case anyone else would also be interested.

[no-identd]

*pokes @rlaemmel & @simonpj to see if they'd have interest in taking the project back under their wings*

[simonpj]

pokes @rlaemmel & @simonpj to see if they'd have interest in taking the project back under their wings

Alas no: I'd be delighted if you became the maintainer.

[no-identd]

pokes @rlaemmel & @simonpj to see if they'd have interest in taking the project back under their wings

Alas no: I'd be delighted if you became the maintainer.

Glad to hear that, but I lack the time, and also, @sergv offered that, not me. However, y'all might want to check out https://github.com/Happstack/syb-with-class, which I just found after trying to reverse engineer what had happened to the project after coming across it via a a rather unlikely chain of events, since it seemed odd to me that it seemed to have died. By the way, the old documentation still exists here:

https://web.archive.org/web/20091024231432/http://www.cs.vu.nl:80/boilerplate/

https://web.archive.org/web/20170518091839/http://foswiki.cs.uu.nl/foswiki/GenericProgramming/SYB

Albeit by now, I suppose fancier tools than SYB exist for generic programming, at least going by the citation network of the original paper, which I looked at since posting the above. :)

[rlaemmel]

Thanks for scraping! I will not be able to step in here. Ralf

[sergv]

@dreixel Bump, my Haskell Cafe email went out almost half a year ago but nothing has happened out of it.

[dreixel]

Hey Sergey, I think @mpickering had a relevant question, could you perhaps answer that?

[sergv]

@dreixel I don't intend to do much as a maintainer. My only specific goal is to get my PR merged, but I'll be also merging other people's PRs, provided they're not too intrusive. I don't intend to change API or anything of the sorts.

[mpickering]

I don't think this change will gain anything substantial for performance because the statically known functions f are too polymorphic to unveil any more optimisation opportunities if they are inlined.

Do you have any examples where this makes a reasonable difference? I suppose there is no real harm in defining the functions in this way anyway.

[sergv]

While f's are typically polymorphic, what they're applied to is typically isn't. I.e. in everywhere :: (forall a. Data a => a -> a) -> (forall b. Data b => b -> b) the b could be specialised at the call site and avoid dictionary passing. Since functions are recursive, they're not going to be inlined. With this transform into recursive and non-recursive parts I think they should inline pretty well.

Also, there's really no need to pass the same f in all recursive calls as an argument - since it doesn't change, it is faster to not pass it.

Unfortunately, I don't have any benchmarks for SYB, but I notice it is being used a lot for working with ASTs in GHC API. However, this optimisation strategy does work in other contexts, e.g. https://github.com/haskell/bytestring/pull/151 that has benchmarks. Which makes me conclude that passing arguments vs binding something only once in the environment does have performance difference.

[dreixel]

Sergey, you should now have push rights to this repo, and you're also a maintainer in Hackage Thanks for volunteering to look after syb!

[sergv]

@dreixel Thanks a lot!