containers
containers copied to clipboard
haskell
Add RULES for Data.IntMap.alterF
Adds afterF rewrite RULES for the Identity functor.
Effect on Performance
Identity
Since Identity a is isomorphic to a we can rewrite alterF to to use the more efficient alter which has complexity O(min(n,w)) compared to O(log n) of alterF. alter also has a smaller constant factor because it only needs to traverse the map once whereas alterF must do so twice (once to find the element and then again to delete).
Testing
- Adds unit tests for alterF for
[],Identity, andConst - Property test comparing the rewritten versions to versions operating on isomorphic structures
Benchmark
Benchmarks performed using GHC 8.2.2
benchmarking alterF_IdentityNoRewrite
time 1.101 ms (1.089 ms .. 1.113 ms)
0.999 R² (0.998 R² .. 1.000 R²)
mean 1.099 ms (1.091 ms .. 1.111 ms)
std dev 31.16 μs (22.66 μs .. 48.93 μs)
variance introduced by outliers: 18% (moderately inflated)
benchmarking alterF_IdentityRewrite
time 903.7 μs (865.3 μs .. 946.8 μs)
0.989 R² (0.981 R² .. 0.996 R²)
mean 864.9 μs (848.6 μs .. 886.1 μs)
std dev 63.00 μs (50.28 μs .. 95.92 μs)
variance introduced by outliers: 59% (severely inflated)
benchmarking alterF_Const
time 19.25 μs (18.28 μs .. 20.68 μs)
0.971 R² (0.962 R² .. 0.985 R²)
mean 20.66 μs (19.74 μs .. 21.61 μs)
std dev 3.234 μs (2.766 μs .. 3.837 μs)
variance introduced by outliers: 94% (severely inflated)
No rewrite RULES were added for Const because the benchmark results showed no meaningful difference.
This addresses #325.
Latest failure is due to CI issue, failed to install ghc for one of the versions.
@m-renaud, you can click the restart button (circle with arrow) next to the test that failed in the Travis interface. Or at least I think you can. If not, let me know and I'll see about getting permissions fixed.
Found it, thanks! I originally wasn't logged in and was on my phone so it wasn't very apparent. Addressed your comments, PTAL.
Const, getConst, Const . getConst, and runIdentity should all be very reliably equivalent to coerce, at least when optimizations are enabled. The issue that comes with the Identity rule is that
runIdentity . f = coerce . f =?= coerce f
Why is that last equality questionable?
coerce . undefined = \x -> coerce (undefined x) = \ _ -> undefined /= undefined
Yuck! Because of this, GHC will (generally at least) only turn g (runIdentity . f) into coerce g f if it either
- Knows that
fhas an arity of at least 1, or - Knows that
gonly usesfby applying it to an argument, and doesn't do something shady like usingseqon it. I believe this currently requires thatgbe inlined, but I could be wrong.
In practice, GHC is pretty good at this stuff, but sometimes it goofs. In those circumstances where there's a risk, it's probably best to help it out. In first-order circumstances, there's generally no reason to bother (and make the code less clear).
Thanks for the explanation! Do you have any more comments, or is this ready to be merged?
I don't understand the benchmark results. What does each of them mean? Please clarify in the commit message and PR text. How does the rewrite rule change performance for Identity and for Const? Be careful; if you define your own versions of Identity and Const to test with, be sure to copy the Functor and Applicative instances from base; there's some coercion magic about, as I recall.
For Identity:
instance Functor Identity where
fmap = coerce
instance Applicative Identity where
pure = Identity
(<*>) = coerce
liftA2 = coerce
For Const,
instance Monoid m => Applicative (Const m) where
pure _ = Const mempty
liftA2 _ (Const x) (Const y) = Const (x `mappend` y)
(<*>) = coerce (mappend :: m -> m -> m)
Added a section to the PR text, I can add it to the squashed commit when the branch is merged as well.
be sure to copy the Functor and Applicative instances from base
Good catch, thanks for pointing that out! The TestConst functor instance was the same, but I've updated TestIdentityto use coerce. There's no need to define an applicative instance because alterF only requires Functor.
No, I mean what does each line in the benchmark results actually represent? Most especially, what does the alterF line mean?
Ohhh, sorry, I misunderstood. I'll rename (and rework the benchmarks) as soon as I get a chance. I was thinking:
-
alterF_IdentityNoRewrite(using TestIdentity) -
alterF_IdentityRewrite(using Identity) -
alterF_ConstNoRewrite(using TestConst) -
alterF_ConstRewrite(using Const)
Does that sound better?
Yes, much.
On Jan 4, 2018 11:16 AM, "Matt Renaud" [email protected] wrote:
Ohhh, sorry, I misunderstood. I'll rename (and rework the benchmarks) as soon as I get a chance. I was thinking:
- alterF_IdentityNoRewrite (using TestIdentity)
- alterF_IdentityRewrite (using Identity)
- alterF_ConstNoRewrite (using TestConst)
- alterF_ConstRewrite (using Const)
Does that sound better?
— You are receiving this because your review was requested.
Reply to this email directly, view it on GitHub https://github.com/haskell/containers/pull/467#issuecomment-355325182, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_cXl_HsvhkxRTZSHW-Plp-DMFVT8ks5tHPljgaJpZM4RPdHz .
You have bona fide CI failures. It looks like you forgot to import Data.Coerce (coerce) some places.
By the way, there are buttons to restart or cancel CI runs on the Travis page. Do you see those? Please restart your own when there are silly problems, and please try to cancel your own when they're out of date or doomed to fail. Canceling useless builds saves time for the whole Haskell organization. Speaking of which, as I think I said, you should use [ci skip] where appropriate. In particular, your whole tutorial project should be [ci skip] unless and until we make Travis build those docs. Since we don't even make Travis build the Haddocks, I don't think that's going to happen anytime soon.
Sorry for the delay, I only had a few minutes here and there over the weekend to look at this stuff. I've re-organized the benchmarks as discussed and fixed the import.
It also appears that the import for Data.Coerce in IntMap/Internal.hs was redundant since it's been included in __GLASGOW_HASKELL__ >= 709, do I need to add another conditional to import if base >= 4.8 and GLASGOW_HASKELL > 709?
Something is really weird here, and it makes me nervous. Why on Earth do we need to specialize Const like that? GHC's automatic specialization should be taking care of that one for us! What happens if you change the NOINLINE [1] to INLINABLE [1]? Does the difference for Const go away?
Um.... I wasn't telling you to just change that. I was suggesting that you check what that does to the benchmarks. I want to understand why there's a difference for Const, which I don't think there should be.
I originally had a todo to see if alterF should be marked INLINABLE [1] or NOINLINE [1] but it somehow got clobbered (I went with NOINLINE to be safe). The difference in Const mostly goes away (see benchmark results in commit description), I think the remaining difference may just be noise (but I wanted to see what you thought). With such a small difference I'm not sure the custom rules for Const are necessary now, wdyt?
Oh, I missed the new benchmark results in your commit. I think you should run more tests. See what happens if you reverse the order the benchmarks run in, for example. If the difference remains, it would be nice to understand why, but we should probably keep the rule. If the difference is really just noise, scrap the rule.
I ran it several more times and changed the order of benchmarks but the results remain about the same.
Interesting. Let's keep the rule for now but maybe try to dig into Core and such some other time. We should get this merged.
On Mon, Jan 8, 2018 at 4:06 PM, Matt Renaud [email protected] wrote:
I ran it several more times and changed the order of benchmarks but the results remain about the same.
— You are receiving this because your review was requested. Reply to this email directly, view it on GitHub https://github.com/haskell/containers/pull/467#issuecomment-356096472, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_cuF1OY557-Wgz68NGXgefyI3o_lks5tIoNugaJpZM4RPdHz .
Woah woah woah, I ran it a few more times for good measure and got the below results which indicate that the rewrite is now slower than the non-rewritten version :/
benchmarking alterF_ConstRewrite
time 23.26 μs (22.48 μs .. 23.70 μs)
0.993 R² (0.986 R² .. 0.997 R²)
mean 22.07 μs (21.30 μs .. 22.63 μs)
std dev 2.207 μs (1.692 μs .. 2.816 μs)
variance introduced by outliers: 85% (severely inflated)
benchmarking alterF_ConstNoRewrite
time 18.75 μs (17.94 μs .. 19.86 μs)
0.978 R² (0.968 R² .. 0.992 R²)
mean 20.02 μs (19.11 μs .. 21.07 μs)
std dev 3.218 μs (2.715 μs .. 3.618 μs)
variance introduced by outliers: 94% (severely inflated)
This sounds like some sort of silliness. Maybe some code alignment nonsense or something. It sounds like they're probably pretty much the same in reality, so get rid of the Const rule and we can merge.
On Mon, Jan 8, 2018 at 5:22 PM, Matt Renaud [email protected] wrote:
Woah woah woah, I ran it a few more times for good measure and got the below results which indicate that the rewrite is now slower than the non-rewritten version :/
benchmarking alterF_ConstRewrite time 23.26 μs (22.48 μs .. 23.70 μs) 0.993 R² (0.986 R² .. 0.997 R²) mean 22.07 μs (21.30 μs .. 22.63 μs) std dev 2.207 μs (1.692 μs .. 2.816 μs) variance introduced by outliers: 85% (severely inflated)
benchmarking alterF_ConstNoRewrite time 18.75 μs (17.94 μs .. 19.86 μs) 0.978 R² (0.968 R² .. 0.992 R²) mean 20.02 μs (19.11 μs .. 21.07 μs) std dev 3.218 μs (2.715 μs .. 3.618 μs) variance introduced by outliers: 94% (severely inflated)
— You are receiving this because your review was requested. Reply to this email directly, view it on GitHub https://github.com/haskell/containers/pull/467#issuecomment-356115581, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_bdxGFiD5IRtsrpj0cilZMyprF8gks5tIpUZgaJpZM4RPdHz .
Done. I've left a few of the tests and benchmarks in case we want to revisit this in the future.
Also, please indicate in the commit what GHC version you used for benchmarking, and use GHC >= 8.2. I don't know if the new join point system affects this stuff, but I would not be at all surprised. NB: when you squash this thing, make sure the final commit message is the one with the latest/correctest benchmarks.
Updated PR description with new benchmark results and note on what GHC version used. Is rewording an already pushed commit allowed? I thought it may mess up history or something.
Speaking of GHC changes, I should probably rerun the benchmarks that led to my choice of alterF Identity specialization for Data.Map.
You've pushed these commits to a branch. You're absolutely free to amend
them, rebase them, etc., etc.
Once they're actually merged to master, neither you nor I has the authority
to touch them. BTW, my
git-fu is horrible (I made a very serious hash of the git history of
Data.Sequence last year by moving
a file the wrong way :-( ). But I can tell you that git rebase -i is
very useful. Just type git rebase -i base,
where base is the last commit before your branch, and you'll get a pretty
much totally self-explanatory way
to fix everything. If you only want one commit, you can set the first one
to "pick" and all the rest to "squash";
this will open an editor with all the texts of all your commits, and you
can delete/condense/etc. to get one
good message. If you're doing something where multiple commits make sense
(here, that might be
one commit for the benchmarks followed by another for the changes), you can
pick a couple, squash
others, etc. If you want to modify something and push that back in time,
you can add a new commit for
it, rebase -i, and move the new commit up higher and then (perhaps) squash
it onto a previous one.
On Mon, Jan 8, 2018 at 7:31 PM, Matt Renaud [email protected] wrote:
Updated PR description with new benchmark results and note on what GHC version used. Is rewording an already pushed commit allowed? I thought it may mess up history or something.
— You are receiving this because your review was requested. Reply to this email directly, view it on GitHub https://github.com/haskell/containers/pull/467#issuecomment-356141327, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_X7nBX85o5KkNglpCR3fLe37mMbRks5tIrNjgaJpZM4RPdHz .
Sooo, these benchmarks tell a different story than the other ones. TL;DR; rewrite rules perform better in casses when the element being altered is present, but worse when the element is absent. See the commit message for more details.