Question for the haskell implementors: Arrays, unsafePerformIO, runST
So, I finally decided that jhc needs real arrays, but am running into an issue and was wondering how other compilers solve it, or if there is a general accepted way to do so. here is what I have so far
-- The opaque internal array type data Array__ a
-- the array transformer quasi-monad newtype AT a = AT (Array__ -> Array__)
seqAT__ :: AT a -> AT a -> AT a seqAT__ (AT a1) (AT a2) = AT $ \a -> a2 (a1 a)
doneAT__ :: AT a doneAT__ = AT id
newAT__ :: Int -> AT a -> Array__ a newAT__ n (AT a1) = a1 (prim_newAT__ n)
writeAT__ :: Int -> a -> AT a writeAT__ i x = AT $ \a -> prim_writeAT__ i x a
-- none of these routines have run-time checks foreign import primitive "prim_newAT__" :: Int -> Array__ -- performs *update-in-place* foreign import primitive "prim_writeAT__" :: Int -> a -> Array__ -> Array__ foreign import primitive "unsafeAt__" :: Array__ a -> Int -> a
-- example use newArray :: [a] -> Array__ a newArray xs = newAT__ (length as) $ foldr assign doneAT (zip [0..] xs) where assign (i,v) rs = writeAT__ i v `seqAT__` rs
now, the problem occurs in newAT__
newAT__ :: Int -> AT a -> Array__ a newAT__ n (AT a1) = a1 (prim_newAT__ n) ^ this gets floated out as a CAF.
it all seems good, but the call to (prim_newAT__ n) is a constant and hence gets pulled to the top level and all arrays end up being the same array! this is no good. I always knew in the back of my mind that 'unsafePerformIO' had the same problem, but sort of punted solving it since unsafePerformIO is not really used in any critical paths. However, it pretty much fundamentally breaks arrays! I imagine the same issue would arise with runST. so, any idea how to solve it? I could brute force it and make the compiler recognize calles to prim_newAT__ as special, but I really don't like that idea. it is hard to guarentee such things across all possible optimizations and I'd like a general solution rather than hardcoding a bunch of routines as special. So far, my best idea though I don't know if it will work is adding a primitive:
foreign import primitive "prim_newWorld__" :: forall a . a -> World__
which will throw away its argument and produce a World__. but since it is primtive, the compiler will assume the world it returns might depend on its argument. then I could do something like:
foreign import primitive "prim_newAT__" :: World__ -> Int -> Array__
newAT__ :: Int -> AT a -> Array__ a newAT__ n (AT a1) = a1 (prim_newAT__ (prim_newWorld__ a1) n)
so the initial call to newAT__ now depends on the array transformer and can't be floated out as a CAF. I have reduced several magic primitives to just one, the world creation one. but I am still not sure how happy I am about it and wanted to know what other compilers did. John -- John Meacham - ⑆repetae.net⑆john⑈
On 2/15/06, John Meacham <john@repetae.net> wrote:
foreign import primitive "prim_newWorld__" :: forall a . a -> World__
which will throw away its argument and produce a World__. but since it is primtive, the compiler will assume the world it returns might depend on its argument. then I could do something like:
GHC uses ST, which uses RealWorld#... -- Taral <taralx@gmail.com> "Computer science is no more about computers than astronomy is about telescopes." -- Edsger Dijkstra
On Feb 15, 2006, at 10:53 PM, John Meacham wrote:
So, I finally decided that jhc needs real arrays, but am running into an issue and was wondering how other compilers solve it, or if there is a general accepted way to do so. ... now, the problem occurs in newAT__
newAT__ :: Int -> AT a -> Array__ a newAT__ n (AT a1) = a1 (prim_newAT__ n) ^ this gets floated out as a CAF.
Yes, you need to have some construct in the language which can't be floated out. When you implement runST / unsafePerformIO you quickly learn that you can't rely on data dependency alone (though you'll get lucky a surprising proportion of the time if you try). In phc, due to our pH heritage we had a set of compiler primitives which were known to be unfloatable. We were otherwise shockingly generous about floating things around (most of the other limitations got switched off in Haskell mode and only kicked in when you were compiling pH, which let you stick imperative stuff in without monads). -Jan-Willem Maessen
Data.Array.ST has runSTArray :: Ix i => (forall s . ST s (STArray s i e)) -> Array i e I think if you can implement that, then all your problems will be solved. -- Ben
John Meacham wrote:
So, I finally decided that jhc needs real arrays, but am running into an issue and was wondering how other compilers solve it, or if there is a general accepted way to do so.
here is what I have so far
-- The opaque internal array type data Array__ a
-- the array transformer quasi-monad newtype AT a = AT (Array__ -> Array__)
seqAT__ :: AT a -> AT a -> AT a seqAT__ (AT a1) (AT a2) = AT $ \a -> a2 (a1 a)
doneAT__ :: AT a doneAT__ = AT id
newAT__ :: Int -> AT a -> Array__ a newAT__ n (AT a1) = a1 (prim_newAT__ n)
writeAT__ :: Int -> a -> AT a writeAT__ i x = AT $ \a -> prim_writeAT__ i x a
-- none of these routines have run-time checks foreign import primitive "prim_newAT__" :: Int -> Array__ -- performs *update-in-place* foreign import primitive "prim_writeAT__" :: Int -> a -> Array__ -> Array__ foreign import primitive "unsafeAt__" :: Array__ a -> Int -> a
-- example use newArray :: [a] -> Array__ a newArray xs = newAT__ (length as) $ foldr assign doneAT (zip [0..] xs) where assign (i,v) rs = writeAT__ i v `seqAT__` rs
now, the problem occurs in newAT__
newAT__ :: Int -> AT a -> Array__ a newAT__ n (AT a1) = a1 (prim_newAT__ n) ^ this gets floated out as a CAF.
In GHC, the primitive is this: newArray# :: Int# -> a -> State# s -> (# State# s, MutArr# s a #) that is, it takes a state and returns a new state. In order for calls to newArray# to not be shared more than we want, we have to make sure that the state argument to newArray# is never a constant visible to the compiler. This entails, as you guessed, not inlining the definition of unsafePerformIO or runST. See comments near the definition of runST in libraries/base/GHC/ST.lhs for a description of exactly the problem you describe. Cheers, Simon
After reading all the interesting responses I decided to go with a slight generalization of my original idea, and it surprisingly turns out to have other generally useful unintended uses, which is the point that a 'hack' becomes a 'feature'. :) before I had a primitive: newWorld__ :: a -> World__ which took an arbitrary value, discarded it, and returned a world. thus letting your World__ depend on an arbitrary haskell expression and therefore not be floatable any further than said expression. I generalized this primitive to drop__ :: a -> b -> b which discards its first argument and just passes on its second. so newWorld__ becomes newWorld__ x = drop__ x World__ now, the interesting thing is that with the drop__ primitive you can generally solve floating and cse problems. imagine f x = ... where z = cheapfunction constant where cheapfunction produces something big youd rather the garbage collector not hold on to between calls to f, then you can do f x = ... where z = cheapfunction (drop__ x constant) now the call artificaly depends on the argument x so it won't be floated out and is guarenteed to be reevaluated on every call to f. Another issue drop__ can help with is unintential CSE, generally an issue with global variables forcing you too turn off CSE module-wide to avoid issues (or perhaps program-wide in the presence of whole-program compilation). {-# NOINLINE var1 #-} var1 :: IORef Int var1 = unsafePerformIO $ newIORef 0 {-# NOINLINE var2 #-} var2 :: IORef Int var2 = unsafePerformIO $ newIORef 0 now, var1 and var2 have the exact same body and type and thus are candidates for CSE, which would be quite bad as it would replace two variables with one. data Var1 = Var1 data Var2 = Var2 var1 = unsafePerformIO $ newIORef (drop__ Var1 0) var2 = unsafePerformIO $ newIORef (drop__ Var2 0) now they can't be commoned up because Var1 and Var2 are distinct. In any case, this seems like it might be a useful primitive for other haskell implementations to provide and solves a few problems custom pragmas have been proposed for in the past. John -- John Meacham - ⑆repetae.net⑆john⑈
John Meacham <john@repetae.net> wrote:
I generalized this primitive to
drop__ :: a -> b -> b
Also known in the Prelude as "const"... The difference is that you propose it be primitive, with the intention that a clever compiler should not be able to bypass it by inlining its definition and propagating the loss of the first argument outwards. Regards, Malcolm
On Tue, Feb 21, 2006 at 10:15:59AM +0000, Malcolm Wallace wrote:
John Meacham <john@repetae.net> wrote:
I generalized this primitive to
drop__ :: a -> b -> b
Also known in the Prelude as "const"...
well, 'flip const' but yes.
The difference is that you propose it be primitive, with the intention that a clever compiler should not be able to bypass it by inlining its definition and propagating the loss of the first argument outwards.
sure, well whatever is required on a given compiler to ensure it has the above qualities, which might mean making it a primitive or have it have some compiler-specific pragmas attached. John -- John Meacham - ⑆repetae.net⑆john⑈
John Meacham wrote:
On Tue, Feb 21, 2006 at 10:15:59AM +0000, Malcolm Wallace wrote:
John Meacham <john@repetae.net> wrote:
I generalized this primitive to
drop__ :: a -> b -> b
Also known in the Prelude as "const"...
well, 'flip const' but yes.
The difference is that you propose it be primitive, with the intention that a clever compiler should not be able to bypass it by inlining its definition and propagating the loss of the first argument outwards.
sure, well whatever is required on a given compiler to ensure it has the above qualities, which might mean making it a primitive or have it have some compiler-specific pragmas attached.
Your drop__ reminds me of GHC's touch#, which is like drop__ in the IO monad. We use it to control lifetimes, eg. inside withForeignPtr. You could implement drop in terms of touch#: drop__ a b = case touch# a realworld# of s -> b I'm not sure about the other way around. Something like "touch# a s = drop__ (a,s) s" looks possible, but is wrong - the compiler can see the same s is returned. touch# compiles to no code at all in GHC, which is what you want, but it does keep its argument alive as far as the GC is concerned - that behaviour isn't necessary (is undesirable?) for drop__. Cheers, Simon
On Tue, Feb 21, 2006 at 11:04:40PM +0000, Simon Marlow wrote:
Your drop__ reminds me of GHC's touch#, which is like drop__ in the IO monad. We use it to control lifetimes, eg. inside withForeignPtr. You could implement drop in terms of touch#:
drop__ a b = case touch# a realworld# of s -> b
Ah, cool. there isn't an optimization that can determine that b is passed through unchanged is there? some sort of core level points-to analysis for instance.
I'm not sure about the other way around. Something like "touch# a s = drop__ (a,s) s" looks possible, but is wrong - the compiler can see the same s is returned.
Also, drop__ completly disapears when grin is first generated from jhc core and more grin-level optimizations are done that could loose the fact a should exist at least as long as s. some sort of grin-level primitive for touch# would be needed in jhc (or some sort of explicit region annotations? I have not thought enough about those).
touch# compiles to no code at all in GHC, which is what you want, but it does keep its argument alive as far as the GC is concerned - that behaviour isn't necessary (is undesirable?) for drop__.
I would think undesirable. simply because there is no need and one of drop__s uses is to fine-tune memory management. though, I don't think it makes a big difference in the examples I gave. I think perhaps drop__ might be useful enough to standardize on, if not in haskell' then perhaps as a common convention between ghc and jhc because it solves a couple issues that have come up on the list before in a way that is more lightweight than hypothetical PRAGMAs. I am not attached to the name drop__ BTW, double underscores at the end of a name in jhc are equivalent in intent to # at the end in ghc, it just means "this might be special in some way" but if we were to have a common name, it should be something more descriptive. perhaps `dependingOn` ?
dependingOn :: a -> b -> a dependingOn = flip drop__
f x = ... where y = foo (z `dependingOn` x)
John -- John Meacham - ⑆repetae.net⑆john⑈
participants (6)
-
Ben Rudiak-Gould -
Jan-Willem Maessen -
John Meacham -
Malcolm Wallace -
Simon Marlow -
Taral