haskell
Inline the common case of link for Set and Map
I'm seeing some decent improvements in union, difference, etc. on inlining the no-rebalance Bin-Bin case of link
https://github.com/haskell/containers/blob/82c21f0e348660dca3c2c2d08f42a419df7db9e7/containers/src/Data/Map/Internal.hs#L4019-L4025
This is just like #1053, that the common case is one where no balancing is required, and making sure that's fast pays off.
I'll prepare a PR for it.
While I'm here, I'm going to change link to delegate to left-only and right-only variants of link. This better represents what's going on, i.e. link never switches directions. I've thought about this but didn't have a good reason to touch the code before.
This isn't a big win as I first thought.
There are significant improvements (20-30%) but mostly in benchmarks where the two trees don't have a large intersection (and thus the operation is pretty fast anyway), and less (3-5%) otherwise. I'll try to understand this better before making a PR.