On Sun, Jun 17, 2012 at 2:26 AM, Tillmann Rendel
Hi,
David Menendez wrote:
As you noticed, you can get somewhat better performance by using the combinators that convert to S.Set internally, because they eliminate redundant computations later on.
"Somewhat better"? My example was three times faster, and I guess that the fast variant is O(n) and the slow variant is O(n²). So I expect that for some applications, the Set interface is more than fast enough and the MonadPlus-interface is much too slow.
Yes, that should have been "significantly better".
(Why is unioned faster then numbers? Is union doing some rebalancing? Can I trigger that effect directly?)
It's because mplus a b>>= f turns into mplus (a>>= f) (b>>= f), whereas unioned takes the union before calling f.
Here, you compare mplused to unioned, but in the parentheses, I asked about numbers and unioned (from my last email).
You're right. That may have been caused by the time to compute numbers
itself; I saw that numbers `times` numbers was faster than unioned
`times` unioned the second time I ran it.
Additionally, I haven't done any serious performance testing, but
there also seems to be a speedup when the following lines are added to
run:
run (Bind (Plus (Prim sa) mb) f) = run (Bind (S.union sa (run mb)) f)
run (Bind (Plus ma (Prim sb)) f) = run (Bind (S.union (run ma) sb) f)
--
Dave Menendez