primitive
primitive copied to clipboard
haskell
traverse Array with Maybe more quickly
WIP. I still need to handle SmallArray. I also need to make this work with Either, but the backwards-compatibility story there is more annoying because of the historical absence of ExceptT. I also want to do this for State. Probably not Writer though since it has abysmal performance anyway.
I like this. For Either, you can either copy the basics of ExceptT from transformers or (perhaps better) just manually work it into the code for traverseArrayP.
Side note: it's most unfortunate for RULES that we don't have, e.g., Applicative (ExceptT e m) :- Applicative m, and that we have no way to match on the use of a particular instance dictionary either. So all these rules have to be pretty much monomorphic.
I've just added Either, State, and Reader and some documentation of what's going on here. To keep things simple, I think I'll just disable the Either optimization if the user builds with transformers older than 0.4. I suspect that creating copies of traverseArrayP for all three of these types that manually inline the monad instance dictionaries (eschewing the use of the monad transformers entirely) doesn't actually cause GHC to generate better code at the use site. I'll add a benchmark soon to confirm this.
Aside from that, are there other issues you see with this? Other types worth supporting?
I don't understand why you think the manual copies (with rewrite rules to match) wouldn't help.
Quite possibly, but you won't be depending on having ExceptT in transformers.
On Apr 22, 2018 10:58 AM, "Andrew Martin" [email protected] wrote:
I think GHC will produce the same core.
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/haskell/primitive/pull/142#issuecomment-383387491, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_VIxxCgLXNeO_AbANLNZKCV4NYIzks5trJqYgaJpZM4Tdr0z .
Ah, it was consistent behavior with all versions of containers that was your concern. I've changed it as you suggested. Also, I added a benchmark just to see if there was a performance difference between the two implementations. They have identical performance (Wooh GHC!).
All these rewrite rules (including the ones I wrote) feel somewhat unsatisfactory, because they completely fall down for transformers. I'm wondering if there might be a way to catch known transformations of known base monads, using rewrite rules with fall-backs. Roughly speaking, rewrite applications of known transformers recursively until we reach a known base monad (in which case we can rewrite to something particularly efficient) or fail to do so, in which case we ultimately inline to the usual case.
By the way: what sorts of benchmark speed-ups were you able to demonstrate from the Maybe and Either e rules?
I've just added a benchmark to compare the two:
benchmarked Array/implementations/traverse/Either/inlined
time 36.32 μs (31.90 μs .. 41.36 μs)
0.928 R² (0.884 R² .. 0.998 R²)
mean 32.20 μs (31.49 μs .. 33.72 μs)
std dev 3.534 μs (1.644 μs .. 5.927 μs)
variance introduced by outliers: 65% (severely inflated)
benchmarked Array/implementations/traverse/Either/closure
time 172.3 μs (166.3 μs .. 179.7 μs)
0.981 R² (0.965 R² .. 0.994 R²)
mean 168.8 μs (166.1 μs .. 172.5 μs)
std dev 10.94 μs (7.326 μs .. 15.23 μs)
variance introduced by outliers: 42% (moderately inflated)
This is on a pretty noisy box, but there's about a 5x speedup. On PrimArray, it's much more pronounced:
benchmarked PrimArray/traverse/Maybe/Applicative
time 1.215 ms (1.191 ms .. 1.237 ms)
0.996 R² (0.991 R² .. 0.999 R²)
mean 1.181 ms (1.171 ms .. 1.195 ms)
std dev 41.17 μs (30.35 μs .. 68.63 μs)
variance introduced by outliers: 17% (moderately inflated)
benchmarked PrimArray/traverse/Maybe/PrimMonad
time 5.985 μs (5.817 μs .. 6.189 μs)
0.996 R² (0.993 R² .. 0.999 R²)
mean 5.858 μs (5.827 μs .. 5.921 μs)
std dev 135.6 ns (82.21 ns .. 233.3 ns)
About a 200x speedup on my noisy box. This is because, for PrimArray, the specialized traversals do zero allocations (other than the original allocation of the new array).
I like your idea about recursively rewriting. I'm going to give this a try.
All these rewrite rules (including the ones I wrote) feel somewhat unsatisfactory, because they completely fall down for transformers. I'm wondering if there might be a way to catch known transformations of known base monads, using rewrite rules with fall-backs.
I can't find a way to make this work. Consider what a rewrite rule for MaybeT might look like:
"traverse/MaybeT" forall (f :: a -> MaybeT m b). traverseArray f = ...
Here's the problem: in the rewrite rule, we have no way to tell GHC that m needs to have a PrimMonad constraint. GHC appears to have a syntax that tricks the user into thinking they can do this, but it doesn't actually work.
In fact, in the rewrite rule, GHC doesn't even know that m has an Applicative instance.
You certainly can't do it that way. I'm not sure if you can do it at all or not, but if so it will require rewrite rules "all the way down" to a base type a rule matches on.
On Mon, Apr 23, 2018, 3:36 PM Andrew Martin [email protected] wrote:
All these rewrite rules (including the ones I wrote) feel somewhat unsatisfactory, because they completely fall down for transformers. I'm wondering if there might be a way to catch known transformations of known base monads, using rewrite rules with fall-backs.
I can't find a way to make this work. Consider what a rewrite rule for MaybeT might look like:
"traverse/MaybeT" forall (f :: a -> MaybeT m b). traverseArray f = ...
Here's the problem: in the rewrite rule, we have no way to tell GHC that m needs to have a PrimMonad constraint. GHC appears to have a syntax that tricks the user into thinking they can do this, but it doesn't actually work.
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/haskell/primitive/pull/142#issuecomment-383696469, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_dZCqTaNqZmbf1VIp02zVy3_B4Aaks5tri04gaJpZM4Tdr0z .
The basic idea would be to step through the layers of monad transformers you recognize, recording how each one transforms a monad. Then at the bottom, find a base monad you recognize and build up the ultimate bind and return. I'm not sure this can be done, but I strongly suspect it can.
On Mon, Apr 23, 2018, 3:43 PM Andrew Martin [email protected] wrote:
In fact, in the rewrite rule, GHC doesn't even know that m has an Applicative instance.
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/haskell/primitive/pull/142#issuecomment-383698478, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_bT_4FDHXBWsf7sCOMq0KZFsl94lks5tri7igaJpZM4Tdr0z .
I'm still not able to follow how this is supposed to look. Going back to MaybeT:
"traverse/MaybeT" forall (f :: a -> MaybeT m b). traverseArray f = ...
I cannot see anything that could go on the RHS (other than traverseArray f) that is both correct and satisfies the type checker.
Wait, I think I might be beginning to see a way.
Me too 😉
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/haskell/primitive/pull/142#issuecomment-383705732, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_UxLd-9G6tLrM5RAYiQkfb2cd6_xks5trjSQgaJpZM4Tdr0z .
I think we can get MaybeT, ExceptT, and StateT, but not WriterT, RWST, or ErrorT (since those have side constraints). I haven't actually tested my rules, though, so I don't know if they fire or, if they do, whether they produce decent code.
On Mon, Apr 23, 2018, 4:12 PM David Feuer [email protected] wrote:
Wait, I think I might be beginning to see a way.
Me too 😉
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/haskell/primitive/pull/142#issuecomment-383705732, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_UxLd-9G6tLrM5RAYiQkfb2cd6_xks5trjSQgaJpZM4Tdr0z .
No. Thus far they're pretty much faked up. When I'm home I'll (try to) make them a bit less fake and push to show you.
On Mon, Apr 23, 2018, 4:53 PM Andrew Martin [email protected] wrote:
Have you pushed these somewhere?
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/haskell/primitive/pull/142#issuecomment-383719183, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_aDZfEmPXOF-IzFWAsJpLuOxWDjDks5trj9TgaJpZM4Tdr0z .
Until then, I strongly urge you to give it a good try. You may well come up with a better idea than I did, and in any case you'll certainly learn some things.
On Mon, Apr 23, 2018, 5:05 PM David Feuer [email protected] wrote:
No. Thus far they're pretty much faked up. When I'm home I'll (try to) make them a bit less fake and push to show you.
On Mon, Apr 23, 2018, 4:53 PM Andrew Martin [email protected] wrote:
Have you pushed these somewhere?
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/haskell/primitive/pull/142#issuecomment-383719183, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_aDZfEmPXOF-IzFWAsJpLuOxWDjDks5trj9TgaJpZM4Tdr0z .
Hrmm... I'm able to write code that at least type checks to handle (some) transformers on top of ST and IO, but I'm actually not sure how to handle transformers on top of Maybe, Either, Identity, etc. Do you think it's doable? If not for the annoying limits on instance discovery, do you think you could write rules? Maybe those could inspire. Anyway, I'll upload what I have within the hour.
It feels like we’re bordering on feature / ideas for improving rules based optimization. What is it we wish we could say / can only express via hand scripted hermit tool optimization’s?
David: have you tried out hermit?
On Mon, Apr 23, 2018 at 9:21 PM David Feuer [email protected] wrote:
Hrmm... I'm able to write code that at least type checks to handle (some) transformers on top of ST and IO, but I'm actually not sure how to handle transformers on top of Maybe, Either, Identity, etc. Do you think it's doable? If not for the annoying limits on instance discovery, do you think you could write rules? Maybe those could inspire. Anyway, I'll upload what I have within the hour.
— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/haskell/primitive/pull/142#issuecomment-383772437, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAQwoT8qU8bQdwXqJnxjl4erPb-ylDkks5trn4jgaJpZM4Tdr0z .
@cartazio, I've only looked at hermit briefly. It's rather complicated. The basic limitation is basically that the instance resolution derivations drop away after type checking. So for example the simplifier doesn't know how GHC resolved PrimMonad (WriterT w m) and therefore doesn't know Monad m or Monoid w.
Is there ways this could be changed in ghc?
Seems like it would be at least a useful discussion as feature request motivated by what optimization’s you want to be able to say simply.
I’d like it if we can keep primitive simple if we can. At some point too much rules optImitation can hinder easy of changing internals. Though we don’t have much internals going on :)
On Mon, Apr 23, 2018 at 11:50 PM David Feuer [email protected] wrote:
@cartazio https://github.com/cartazio, I've only looked at hermit briefly. It's rather complicated. The basic limitation is basically that the instance resolution derivations drop away after type checking. So for example the simplifier doesn't know how GHC resolved PrimMonad (WriterT w m) and therefore doesn't know Monad m or Monoid w.
— You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub https://github.com/haskell/primitive/pull/142#issuecomment-383794951, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAQwp1B8vcjC9gp9iAxWzcxqVfS4i63ks5trqD8gaJpZM4Tdr0z .
For stacks based on ST or IO, my version seems much simpler, and involves far fewer enormous piles of code that need to go away. I suggest you just ignore those stacks altogether and try to come up with a solution for stacks based on Maybe, Either, Identity, etc. It should be easy to use both solutions at the same time.
Separately, I'm considering a simpler general version that might work somewhat better than the one I put in before. In particular, we can go back to something somewhat list-like, but using a list that holds multiple elements per cons. I need to do some benchmarking.
Undoubtedly, yours is much simpler. In my most recent commit, I was mostly playing around just to see what it takes to make things like Maybe and Either accepted as the base monad. It’s helped me understand the problem better. I have another idea for how to extend your solution to accept different base monads that I am going to try soon.
Question: why do we need the rewrite rules?
a) is it because we can better specialize the code ?
b) is it because you want to be "Afine/ linear resource safe"?
We want rewrite rules for speed. They're not supposed to change semantics any.
On Fri, Apr 27, 2018, 12:33 PM Carter Tazio Schonwald < [email protected]> wrote:
Question: why do we need the rewrite rules?
a) is it because we can better specialize the code ?
b) is it because you want to be "Afine/ linear resource safe"?
— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/haskell/primitive/pull/142#issuecomment-385021217, or mute the thread https://github.com/notifications/unsubscribe-auth/ABzi_RDKD9u2DR7vKBuuEX15qtO00cceks5ts0hUgaJpZM4Tdr0z .
@cartazio, the fast way to traverse an array is to
- Create a mutable array.
- For each element of the given array, a. Perform an action to get an element and b. Write that element to the mutable array.
- Freeze the mutable array and return the resulting immutable array.
We'd like traverse to do that whenever it can, but it's not always possible. Even ignoring safety, note that Compose m n is not generally a PrimMonad, or even a Monad, even if m and n both are.