GHC: Ticket Query
http://ghc.haskell.org/trac/ghc/query?status=!closed&reporter=MikeIzbicki&order=priority
The Glasgow Haskell Compileren-USGHChttp://ghc.haskell.org/trac/ghc/chrome/site/ghc_logo.png
http://ghc.haskell.org/trac/ghc/query?status=!closed&reporter=MikeIzbicki&order=priority
Trac 1.0.1
http://ghc.haskell.org/trac/ghc/ticket/8095
http://ghc.haskell.org/trac/ghc/ticket/8095#8095: TypeFamilies painfully slowSat, 27 Jul 2013 02:54:34 GMTMikeIzbicki<p>
I'm using the TypeFamilies extension to generate types that are quite large. GHC can handle these large types fine when they are created manually, but when type families get involved, GHC's performance dies.
</p>
<p>
Unlike in ticket <a class="closed ticket" href="http://ghc.haskell.org/trac/ghc/ticket/5321" title="bug: Very slow constraint solving for type families (closed: fixed)">#5321</a>, using tail recursion does not eliminate the problem, and the order of arguments greatly affects compile time.
</p>
<p>
I've attached a file Types.hs that demonstrates the problems. This file generates another Haskell file which has the problems. It takes 3 flags. The first is the size of the type to generate, the second is which type family function to use, and the third is whether to call the type family or just use a manually generated type.
</p>
<p>
Here are my performance results:
</p>
<p>
Using non-tail recursion, I get these results. I have to increase the stack size based on the size of the type I want to generate.
</p>
<pre class="wiki">$ ./Types 200 a a > test.hs && time ghc test.hs > /dev/null -fcontext-stack=250
real 0m2.973s
$ ./Types 300 a a > test.hs && time ghc test.hs > /dev/null -fcontext-stack=350
real 0m6.018s
$ ./Types 400 a a > test.hs && time ghc test.hs > /dev/null -fcontext-stack=450
real 0m9.995s
$ ./Types 500 a a > test.hs && time ghc test.hs > /dev/null -fcontext-stack=550
real 0m15.645s
</pre><p>
Tail recursion generates much slower compile times for some reason, and I still need to adjust the stack size:
</p>
<pre class="wiki">$ ./Types 200 b a > test.hs && time ghc test.hs > /dev/null -fcontext-stack=250
real 0m16.120s
</pre><p>
Changing the order of arguments to the recursive type family greatly changes the run times:
</p>
<pre class="wiki">$ ./Types 200 c a > test.hs && time ghc test.hs > /dev/null -fcontext-stack=250
real 0m6.095s
</pre><p>
Without the type family, I get MUCH better performance:
</p>
<pre class="wiki">$ ./Types 10000 a d > test.hs && time ghc test.hs > /dev/null
real 0m2.271s
</pre>Resultshttp://ghc.haskell.org/trac/ghc/ticket/8095#changelog
http://ghc.haskell.org/trac/ghc/ticket/8165
http://ghc.haskell.org/trac/ghc/ticket/8165#8165: Use GeneralizedNewtypeDeriving to automatically create associated type familiesFri, 23 Aug 2013 20:56:05 GMTMikeIzbicki<p>
Here's a simple example:
</p>
<pre class="wiki">class C a where
type T a
instance C Int where
type T Int = Bool
newtype NT = NT Int
deriving C
</pre>Resultshttp://ghc.haskell.org/trac/ghc/ticket/8165#changelog
http://ghc.haskell.org/trac/ghc/ticket/8697
http://ghc.haskell.org/trac/ghc/ticket/8697#8697: Type rationalsSat, 25 Jan 2014 01:40:02 GMTMikeIzbicki<p>
I've used GHC's Type Nats to implement my own type level rationals (code below). This works fine, but the syntax is a little funky because you have to write out the number as a fraction. For example, you must write 13/10 instead of 1.3; or even worse, 13/1 instead of 13. It would be nice to just write the decimal notation.
</p>
<p>
I only see one potential problem with this feature: the dot in the decimal notation could interfere with the dot in forall statements. I guess this can be parsed unambiguously, but maybe not.
</p>
<pre class="wiki">data Frac = Frac Nat Nat
data instance Sing (n::Frac) = SFrac Integer Integer
instance (SingI a, SingI b) => SingI ('Frac a b) where
sing = SFrac (fromSing (sing :: Sing a)) (fromSing (sing :: Sing b))
instance Fractional r => SingE (Kind :: Frac) r where
fromSing (SFrac a b) = fromIntegral a/fromIntegral b
type (/) a b = 'Frac a b
</pre>Resultshttp://ghc.haskell.org/trac/ghc/ticket/8697#changelog
http://ghc.haskell.org/trac/ghc/ticket/9353
http://ghc.haskell.org/trac/ghc/ticket/9353#9353: prefetch primops are not currently usefulWed, 23 Jul 2014 19:24:31 GMTMikeIzbicki<p>
I wanted to use GHC's new prefetch primops to speed up a cover tree data structure I've been working on. The current implementation, however, is insufficient. The pure primops do not work at all. I propose an alternative using a seq-like syntax.
</p>
<hr />
<p>
<strong>The problem</strong>
</p>
<p>
Consider the function:
</p>
<pre class="wiki">prefetchAddr3# :: Addr# -> Int# -> Addr#
</pre><p>
It is used like:
</p>
<pre class="wiki">-- addr# :: Addr#
let prefetchAddr# = prefetchAddr3# addr# 0
... do some stuff not involving addr#
doRealWork prefetchAddr#
</pre><p>
The problem is that we want the prefetch operation to get inserted at the let statement before "do some stuff...", but it doesn't get inserted there. It gets inserted directly before the call to doRealWork. This doesn't give the prefetch enough time to actually put the memory in cache, and so we still get a cache miss. I made several attempts to get around this, but they all failed due to dead code elimination.
</p>
<p>
The <tt>prefetchMutableByteArray#</tt> functions solve this problem by incorporating an explicit state parameter. This forces the compiler to insert the prefetch operation at the location it is actually called in the code. This function, however, can only be used within the ST and IO monads, so it is of limited use.
</p>
<hr />
<p>
<strong> The solution</strong>
</p>
<p>
The solution is to restructure the pure primops to use a seq-like format. For example, the prefetchAddr3# function above would become:
</p>
<pre class="wiki">prefetchAddr3# :: Addr# -> Int# -> a -> a
</pre><p>
Then we would call the function like:
</p>
<pre class="wiki">prefetchAddr3# addr# someOtherOp
... do some stuff not involving addr#
doRealWork prefetchAddr#
</pre><p>
This would correctly insert the prefetch instruction at the location it appears in the haskell code. In particular, the prefetch will occur whenever the second parameter is evaluated.
</p>
<p>
This format has the advantage that it can work in non-monadic code. In my cover tree structure, I've implemented searching the tree as a <tt>fold</tt> operation. Every time the fold branches, only one of the branches is guaranteed to be in the cache. So I get a cache miss when I go down the other branches. I want to use the prefetch primop to prefetch the next branch the fold will go down. The fold function is pure, and I don't want to have to wedge it into the ST monad just for prefetching.
</p>
Resultshttp://ghc.haskell.org/trac/ghc/ticket/9353#changelog
http://ghc.haskell.org/trac/ghc/ticket/9376
http://ghc.haskell.org/trac/ghc/ticket/9376#9376: More informative error messages when closed type families fail to simplifyTue, 29 Jul 2014 06:19:24 GMTMikeIzbicki<p>
In the following code, I am getting strange compiler errors that I suspect has to do with the recursive application of the OrdRec type family:
</p>
<pre class="wiki">import GHC.Prim
import Data.Proxy
import qualified Data.Set as Set
type family OrdRec (f :: * -> *) a b :: Constraint where
OrdRec f a (f b) = ( Ord a, Ord (f b), OrdRec f a b )
OrdRec f a b = ( Ord a, Ord b )
setmap :: OrdRec Set.Set a b => (a -> b) -> Set.Set a -> Set.Set b
setmap f set = Set.map f set
</pre><p>
GHC gives the error message:
</p>
<pre class="wiki">ClosedTypeFamilyRecursion.hs:11:16:
Could not deduce (Ord b) arising from a use of ‘Set.map’
from the context (OrdRec Set.Set a b)
bound by the type signature for
setmap :: (OrdRec Set.Set a b) =>
(a -> b) -> Set.Set a -> Set.Set b
at ClosedTypeFamilyRecursion.hs:10:11-66
Possible fix:
add (Ord b) to the context of
the type signature for
setmap :: (OrdRec Set.Set a b) =>
(a -> b) -> Set.Set a -> Set.Set b
In the expression: Set.map f set
In an equation for ‘setmap’: setmap f set = Set.map f set
Failed, modules loaded: none.
</pre><p>
If we modify the OrdRec type family to remove the recursive application:
</p>
<pre class="wiki">type family OrdRec (f :: * -> *) a b :: Constraint where
OrdRec f a (f b) = ( Ord a, Ord (f b) )
OrdRec f a b = ( Ord a, Ord b )
</pre><p>
Then GHC is able to compile the file fine.
</p>
<p>
What's extra weird, though, is that ghci appears to be able to evaluate the recursive type family correctly. If we comment out the setmap function, then load into ghci, we can verify that the OrdRec type family is giving the correct Ord constraints:
</p>
<pre class="wiki">ghci> :t Proxy :: Proxy (OrdRec [] Int Float)
Proxy :: Proxy (OrdRec [] Int Float) :: Proxy (Ord Int, Ord Float)
ghci> :t :t Proxy :: Proxy (OrdRec [] Int [Float])
Proxy :: Proxy (OrdRec [] Int [Float])
:: Proxy (Ord Int, Ord [Float], (Ord Int, Ord Float))
ghci> :t Proxy :: Proxy (OrdRec [] Int [[Float]])
Proxy :: Proxy (OrdRec [] Int [[Float]])
:: Proxy
(Ord Int,
Ord [[Float]],
(Ord Int, Ord [Float], (Ord Int, Ord Float)))
</pre><p>
But if I try to define the setmap function interactively in ghci, I get the same error message:
</p>
<pre class="wiki">ghci> > let setmap = (\f set -> Set.map f set) :: OrdRec Set.Set a b => (a -> b) -> Set.Set a -> Set.Set b
<interactive>:39:25:
Could not deduce (Ord b1) arising from a use of ‘Set.map’
from the context (OrdRec Set.Set a b)
bound by the inferred type of
setmap :: (OrdRec Set.Set a b) =>
(a -> b) -> Set.Set a -> Set.Set b
at <interactive>:39:5-98
or from (OrdRec Set.Set a1 b1)
bound by an expression type signature:
(OrdRec Set.Set a1 b1) => (a1 -> b1) -> Set.Set a1 -> Set.Set b1
at <interactive>:39:14-98
Possible fix:
add (Ord b1) to the context of
an expression type signature:
(OrdRec Set.Set a1 b1) => (a1 -> b1) -> Set.Set a1 -> Set.Set b1
or the inferred type of
setmap :: (OrdRec Set.Set a b) =>
(a -> b) -> Set.Set a -> Set.Set b
In the expression: Set.map f set
In the expression:
(\ f set -> Set.map f set) ::
OrdRec Set.Set a b => (a -> b) -> Set.Set a -> Set.Set b
In an equation for ‘setmap’:
setmap
= (\ f set -> Set.map f set) ::
OrdRec Set.Set a b => (a -> b) -> Set.Set a -> Set.Set b
</pre>Resultshttp://ghc.haskell.org/trac/ghc/ticket/9376#changelog
http://ghc.haskell.org/trac/ghc/ticket/9699
http://ghc.haskell.org/trac/ghc/ticket/9699#9699: TH function to list names in scopeThu, 16 Oct 2014 16:35:51 GMTMikeIzbicki<p>
I [asked about this on stackoverflow](<a class="ext-link" href="http://stackoverflow.com/questions/26394199/using-templatehaskell-to-list-all-names-in-a-namespace"><span class="icon"></span>http://stackoverflow.com/questions/26394199/using-templatehaskell-to-list-all-names-in-a-namespace</a>), and apparently it doesn't exist yet.
</p>
<p>
I want a <a class="wiki" href="http://ghc.haskell.org/trac/ghc/wiki/TemplateHaskell">TemplateHaskell</a> function <tt>variablesInScope :: Q [Name]</tt> that returns a list of the <tt>Name</tt>'s of all the variables in scope. <a class="wiki" href="http://ghc.haskell.org/trac/ghc/wiki/TemplateHaskell">TemplateHaskell</a> obviously has this information available in order to implement functions like <tt>reify :: Name -> Q Info</tt> and <tt>lookupValueName :: String -> Q (Maybe Name)</tt>. So it seems like this might be a pretty simple function to add.
</p>
Resultshttp://ghc.haskell.org/trac/ghc/ticket/9699#changelog