Here is a problem that affects package vector, sometimes resulting in much slower code with Data.Vector.Storable (based on ForeignPtr and Storable) compared to Data.Vector.Unboxed (based on ByteArrays). Suppose we have a recursive function: foo :: Vector Int -> Maybe Int -> ... foo v x = ... foo v (Just (v ! i)) ... If v comes from Data.Vector.Unboxed, this eventually becomes: foo v x = ... foo v (Just (I# (indexIntArray# arr# i#))) ... Now SpecConstr kicks in, specialises foo for this particular call pattern and we get a nice unboxed loop: foo' :: Vector Int -> Int# -> ... foo' v n# = let x = Just (I# n#) in ... foo' v (indexIntArray# arr# i#) ... Alas, this doesn't work for Data.Vector.Storable. Here, we have to use peek which gives us this: foo v x = ... foo v (Just (case readIntOffAddr# p# i# realWorld# of { (# s#, n# #) -> case touch# fp s# of { _ -> I# n# }})) ... SpecConstr eliminates the Just but can't unbox the Int. With enough fiddling, it would be possible to implement collective operations such that they only touch# once at the end rather than after each element access. This significantly complicates stream fusion, however, and doesn't help with SpecConstr anyway since the stateful read still gets in the way. So the question is: would it perhaps be a good idea for Storable to include support for marshalling from constant memory? Also, can we do something about touch#? Perhaps it could have type (a -> b -> b) and then we could make SpecConstr look through it? Roman
Roman | Alas, this doesn't work for Data.Vector.Storable. Here, we have to use peek | which gives us this: | | foo v x = ... foo v (Just (case readIntOffAddr# p# i# realWorld# of { (# s#, | n# #) -> | case touch# fp s# of { _ -> I# n# }})) ... | | SpecConstr eliminates the Just but can't unbox the Int. But it should be able to unbox that Int. It's not dissimilar to the situation when we have a rule f (g x) ---> e and we find an expression f (let w = rhs in g w) The rule-matcher automatically floats the let, so that it behaves just as if you'd written let w = rhs in f (g w) So the rule fires. In this case you have an ok-for-speculation primop instead of a let, but that should not get in the way. In your example, it should jolly well behave as if you had written | foo v x = ... case readIntOffAddr# p# i# realWorld# of { (# s#, n# #) -> | case touch# fp s# of { _ -> foo v (Just (I# n# }})) ... I'll implement that fix. It should catch cases like this where the primops involves are - ok-for-speculation - have just one result (ie only one case alternative Can you send me a small test case that will show the difference? Simon
Simon, On 23/04/2010, at 16:49, Simon Peyton-Jones wrote:
| foo v x = ... case readIntOffAddr# p# i# realWorld# of { (# s#, n# #) -> | case touch# fp s# of { _ -> foo v (Just (I# n# }})) ...
I'll implement that fix. It should catch cases like this where the primops involves are - ok-for-speculation - have just one result (ie only one case alternative
I don't think touch# is ok-for-speculation. primop TouchOp "touch#" GenPrimOp o -> State# RealWorld -> State# RealWorld with has_side_effects = True Note the has_side_effects part. In fact, wouldn't it be eliminated altogether in this case if it was ok-for-speculation? Roman
Bother. It seems like a good improvement to SpecConstr anyway. But it's disappointing that it doesn't hit this case. In fact it seems that it should. It's not ok to discard a 'touch' but it's fine to move it around. Maybe what we want is primOpIsCheap? Which is currently defined to be the same as primOpOkForSpeculation, but perhaps it should not be. Simon | -----Original Message----- | From: Roman Leshchinskiy [mailto:rl@cse.unsw.edu.au] | Sent: 23 April 2010 07:55 | To: Simon Peyton-Jones | Cc: Haskell Libraries | Subject: Re: Storable and constant memory | | Simon, | | On 23/04/2010, at 16:49, Simon Peyton-Jones wrote: | | > | foo v x = ... case readIntOffAddr# p# i# realWorld# of { (# s#, n# #) -> | > | case touch# fp s# of { _ -> | > foo v (Just (I# n# }})) ... | > | > I'll implement that fix. It should catch cases like this where the primops | involves are | > - ok-for-speculation | > - have just one result (ie only one case alternative | | I don't think touch# is ok-for-speculation. | | primop TouchOp "touch#" GenPrimOp | o -> State# RealWorld -> State# RealWorld | with | has_side_effects = True | | Note the has_side_effects part. In fact, wouldn't it be eliminated altogether | in this case if it was ok-for-speculation? | | Roman | |
On 23/04/2010, at 17:27, Simon Peyton-Jones wrote:
Bother. It seems like a good improvement to SpecConstr anyway.
Actually, aren't ok-for-speculation terms let-bound? Is there ever a (case e of ...) where e is unboxed and ok-for-speculation?
But it's disappointing that it doesn't hit this case. In fact it seems that it should. It's not ok to discard a 'touch' but it's fine to move it around. Maybe what we want is primOpIsCheap? Which is currently defined to be the same as primOpOkForSpeculation, but perhaps it should not be.
I'm not sure if it's that simple. You want SpecConstr (and the rule matcher?) to somehow go from this: foo v x = ... foo v (Just (case readIntOffAddr# p# i# realWorld# of { (# s#, n# #) -> case touch# fp s# of { _ -> I# n# }})) ... to this: foo v x = ... case readIntOffAddr# p# i# realWorld# of { (# s#, n# #) -> case touch# fp s# of { _ -> foo v (Just (I# n# }})) ... But if touch# has side effects, then it isn't safe to do so because foo might never evaluate it in the original version. In this particular case, neither touch# nor readIntOffAddr# really have side effects even though they say they do so it's ok to evaluate them speculatively. It is also ok to drop them both but it is not ok to drop touch# without dropping the read. In a different mail, I suggested combining touching and reading into one operation. That would also work here as that operation could be ok-for-speculation. BTW, at the moment readIntOffAddr# is also marked as has-side-effects. I'm not sure if that is really necessary. Roman
| -----Original Message----- | From: Roman Leshchinskiy [mailto:rl@cse.unsw.edu.au] | Sent: 23 April 2010 07:55 | To: Simon Peyton-Jones | Cc: Haskell Libraries | Subject: Re: Storable and constant memory | | Simon, | | On 23/04/2010, at 16:49, Simon Peyton-Jones wrote: | | > | foo v x = ... case readIntOffAddr# p# i# realWorld# of { (# s#, n# #) -> | > | case touch# fp s# of { _ -> | > foo v (Just (I# n# }})) ... | > | > I'll implement that fix. It should catch cases like this where the primops | involves are | > - ok-for-speculation | > - have just one result (ie only one case alternative | | I don't think touch# is ok-for-speculation. | | primop TouchOp "touch#" GenPrimOp | o -> State# RealWorld -> State# RealWorld | with | has_side_effects = True | | Note the has_side_effects part. In fact, wouldn't it be eliminated altogether | in this case if it was ok-for-speculation? | | Roman | |
participants (2)
-
Roman Leshchinskiy -
Simon Peyton-Jones