- Glasgow-haskell-users

Statically linking a small piece of C into every GHC generated binary
by Johan Tibell 19 Jul '11

19 Jul '11

Hi, I'm trying to add support for the POPCNT instruction, which exists on some modern CPUs (e.g. Nehalem). The idea is to add a popCnt# primop which would generate a POPCNT instruction when compiling with -msse4.2. If the user didn't specified -msse4.2, the primop should fall back to some other implementation of population count. A good fallback, in terms of both speed and memory usage, is this lookup-table based function: static char popcount_table_8[256] = { /*0*/ 0, /*1*/ 1, /*2*/ 1, /*3*/ 2, /*4*/ 1, /*5*/ 2, /*6*/ 2, /*7*/ 3, /*8*/ 1, /*9*/ 2, /*10*/ 2, /*11*/ 3, ... }; /* Table-driven popcount, with 8-bit tables */ /* 6 ops plus 4 casts and 4 lookups, 0 long immediates, 4 stages */ inline uint32_t popcount(uint32_t x) { return popcount_table_8[(uint8_t)x] + popcount_table_8[(uint8_t)(x >> 8)] + popcount_table_8[(uint8_t)(x >> 16)] + popcount_table_8[(uint8_t)(x >> 24)]; } (GCC and LLVM use the same fallback method.) It's important that the fallback is as good as it gets so that the user of the primop doesn't have to implement their own fallback (which is very complicated as the user would have to detect whether -msse4.2 is used or not!). This precludes non-table based solutions (as they're slower). I've implemented the primop but run into some difficulty: to use the above fallback I need the code to be statically linked into every binary. I'm not quite sure how to achieve that. GCC manages by having the above function definition in libc, which is always statically linked. I think LLVM uses a small statically linked compiler run-time library for the same purpose. How would one go about having a small C library linked into every Haskell binary? If we go ahead and implement more of these modern instructions we're likely to need more fallbacks (so this isn't needed by just POPCNT). Cheers, Johan

2 2

Package abi hash and interface file versions
by Joachim Breitner 18 Jul '11

18 Jul '11

Hi, in Debian, we use the ghc-pkg ABI hashes to find out what packages we need to rebuild when. So far, the system has worked great. But now something unfortunate happened: Yesterday, I upgraded ghc from 7.0.3 to 7.0.4. The ABI hash of base and other libraries changed only on amd64 and kfreebsd-amd64, while they stays unmodified on the other architectures. That by itself is interesting, but nothing to worry about, as I assumed that the hashes ensure that packages are rebuild where required. But now I see this build log: https://buildd.debian.org/status/fetch.php?pkg=haskell-mtlparse&ver=0.1.2-1… with the relevant line: Text/ParserCombinators/MTLParse/MTLParseCore.hs:69:1: Bad interface file: /usr/lib/haskell-packages/ghc/lib/mtl-2.0.1.0/ghc-7.0.3/Control/Monad/Trans.hi mismatched interface file versions (wanted "7004", got "7003") Obviously, the ghc version is encoded into the .hi file and checked before using it, including the minor patch level. But it seems that this bit of information is not included in the calculation of the interface hash! So although the ABI hash did not change between 7.0.3 and 7.0.4, the package is broken. I see two solutions for this problem: a) (preferred) The ghc version number is not encoded in the .hi file any more. Instead, a version counter is used that is manually incremented if there has been an incompatible change to the interface – after all, not every minor release of ghc changes this format. b) The interface file version should be included in the hash generation, so that a package built against the base package of 7.0.3 will clearly state that it does not work with the base package of 7.0.4 and needs to be rebuild. (Actually, b) should be the case even if a) is done). Thanks, Joachim -- Joachim "nomeata" Breitner Debian Developer nomeata(a)debian.org | ICQ# 74513189 | GPG-Keyid: 4743206C JID: nomeata(a)joachim-breitner.de | http://people.debian.org/~nomeata

2 4

Deriving Typeable -- possible improvement
by Simon Peyton-Jones 14 Jul '11

14 Jul '11

| iterIO uses mkTyCon for the simple reason that ((Typeable t, Typeable | m) => Iter t m) is Typeable1 and there is no automatic way of deriving | Typeable1. This email is triggered by a thread on Haskell Cafe about changes to the Typeable class http://www.mail-archive.com/haskell-cafe@haskell.org/msg91830.html It proposes a modification to the way Typeable is derived; and concludes with a question. Simon David Mazieres and others comment that you can't derive Typeable for types like this: data T f = MkT (f Int) So he defines his own instance like this [C] instance Typable1 f => Typeable (T f) where typeOf = ... So why can't GHC do this? Well, here's what GHC does. Given a bog standard data type like Maybe data Maybe a = Nothing | Just a deriving( Typeable ) GHC generates this instance [A] instance Typeable1 Maybe where typeOf = ... Remember that Typeable1 takes a type *constructor*, of kind (*->*), as its argument. Now if we need (Typeable (Maybe Int)), GHC first uses an instance from the Typeable library: [B] instance (Typeable1 f, Typeable a) => Typeable (f a) where typeOf = ... And now it uses the (Typeable1 Maybe) instance [A]. So it's kind of cool... the applications are decomposed by [B], leaving the tycon to [A]. But this doesn't work for T above. We can't make (Typeable1 T) because T has kind ((*->*)->*), not (*->*) as Typeable1 requires. Hence David defining his own instance. GHC could do this too. Indeed it could do so for Maybe too, thus: instance Typeable a => Typeable (Maybe a) where typeOf = ... But then, alas, we could not get (Typeable (T Maybe)), because [C] needs Maybe to be in Typeable1. ========== PROPOSAL ============== So here is a compromise, which would at least do better than the current story: When deriving Typeable for a data type S of kind S :: k1 -> .. -> kn -> * -> ... -> * (where kn is not *, and there are M trailing * arguments), generate the instance instance (Typeable_x1 a1, ..., Typeable_xn an) => TypeableM (S a1 .. an) That is, knock off all the trailing * args, and then generate an instance for the remaining stub. ===================== EXAMPLE ============ Example from iterIO: newtype Iter (t :: *) (m :: *->*) (a :: *) = Iter { runIter :: Chunk t -> IterR t m a } deriving( Typeable ) This should generate instance (Typeable t, Typeable1 m) => Typeable1 (Iter t m) where we knock off the trailing (a :: *) argument. ================== QUESTION ================= This approach is not beautiful. It does not solve the underlying problem, which is a lack of kind polymorphism, but that is a battle for another day. Until that day, this alternative way of deriving Typeable would automate significantly more cases, I think. Of course, it also makes it more complicated to explain when "deriving Typeable" will succeed. Any opinions? Does anyone care? Simon

1 0

Fixing Performance Leaks at the Type Level
by Gershom Bazerman 12 Jul '11

12 Jul '11

This post is in literate Haskell. It describes how certain performance leaks are introduced in type level programming. These leaks do not affect program runtimes, but can cause compile times to grow drastically. They exist both with Functional Dependencies and Type Families, but are currently worse with the former, and have grown worse with the new constraint solver in GHC 7. It is intended both as a guide to those encountering these issues, and as a motivation for the GHC development team to address such issues as the constraint solver is developed and improved. > {-# OPTIONS_GHC -fcontext-stack=1000 #-} > {-# LANGUAGE FlexibleContexts, FlexibleInstances, FunctionalDependencies, MultiParamTypeClasses, OverlappingInstances, TypeSynonymInstances, TypeOperators, UndecidableInstances, TypeFamilies #-} > module TypePerformance where Our running example, for simplicity's sake, is a type-level map of a single function. For reference, here is the code for a simple value-level map of a single function. > vfoo = id > mapfoo (x : xs) = vfoo x : mapfoo xs > mapfoo [] = [] Because Haskell is a lazy language, this runs in O(n) time and constant stack. We now lift map to the type level, to operate over HLists. First, the basic HList types > infixr 3 :* > data x :* xs = x :* xs deriving Show > data HNil = HNil deriving Show Next, a large boring HList > -- Adds ten cells > addData x = i :* i :* d :* d :* s :* > i :* i :* d :* d :* s :* > x > where i = 1 :: Int > d = 1 :: Double > s = "" > > -- Has 70 cells. > sampleData = addData $ addData $ addData $ addData $ addData $ > addData $ addData $ > HNil Next, a simple polymorphic function to map > class Foo x y | x -> y > where foo :: x -> y > foo = undefined > instance Foo Int Double > instance Foo Double Int > instance Foo String String Now, our map > class HMapFoo1 as bs | as -> bs where > hMapFoo1 :: as -> bs > > instance (Foo a b, HMapFoo1 as bs) => HMapFoo1 (a :* as) (b :* bs) where > hMapFoo1 (x :* xs) = foo x :* hMapFoo1 xs > > instance HMapFoo1 HNil HNil where > hMapFoo1 _ = HNil If we enable the following line, compilation time is ~ 9 seconds. > testHMapFoo1 = hMapFoo1 sampleData Furthermore, playing with the size of sampleData, we see that the time spent in compilation is superlinear -- each additional cell costs a greater amount of time. This is because while Haskell is lazy at the value level, it is strict at the type level. Therefore, just as in a strict language, HMapFoo1's cost grows O(n^2) because even as we induct over the as, we build up a stack of bs. Just as in a strict language, the solution is to make hMapFoo tail recursive through introducing an accumulator. This also reverses the hlist, but never mind that. > class HMapFoo2 acc as bs | acc as -> bs where > hMapFoo2 :: acc -> as -> bs > > instance (Foo a b, HMapFoo2 (b :* bs) as res) => HMapFoo2 bs (a :* as) res where > hMapFoo2 acc (x :* xs) = hMapFoo2 (foo x :* acc) xs > > instance HMapFoo2 acc HNil acc where > hMapFoo2 acc _ = acc If we enable the following line, compilation time is a much more satisfying ~0.5s. > testHMapFoo2 = hMapFoo2 HNil sampleData But wait, there's trouble on the horizon! Consider the following version: > class HMapFoo3 acc as bs | acc as -> bs where > hMapFoo3 :: acc -> as -> bs > > instance (HMapFoo3 (b :* bs) as res, Foo a b) => HMapFoo3 bs (a :* as) res where > hMapFoo3 acc (x :* xs) = hMapFoo3 (foo x :* acc) xs > > instance HMapFoo3 acc HNil acc where > hMapFoo3 acc _ = acc The only difference between hMapFoo2 and hMapFoo3 is that the order of constraints on the inductive case has been reversed, with the recursive constraint first and the immediately checkable constraint second. Now, if we enable the following line, compilation time rockets to ~6s! > testHMapFoo3 = hMapFoo3 HNil sampleData Slowdowns such as those described here are not a purely hypothetical issue, but have caused real problems in production code. The example given above is fairly simple. The constraints used are minimal and easily checked. In real programs, the constraints are more difficult, increasing constant factors significantly. These constant factors, combined with unexpected algorithmic slowdowns due to the type inference engine, can lead (and have lead) to compilation times of HList-style code becoming deeply unwieldy-to-unusable, and can lead (and have lead) to this occuring only well after this code has been introduced and used on smaller cases without trouble. The constraint solver should certainly be smart enough to reduce the compile times of HMapFoo3 to those of HMapFoo2. In fact, with type families, the there is no difference (see below). Could the compiler be smart enough to do the same for HMapFoo1? I'm not sure. Certainly, it could at least knock down its own constant factors a bit, even if it can't improve the big-O performance there. ---- Appendix: Examples with Type Families As the below code demonstrates, the same issues demonstrated with Functional Dependencies also appear with Type Families, although less horribly, as their code-path seems more optimized in the current constraint solver: > class TFoo x where > type TFooFun x > tfoo :: x -> TFooFun x > tfoo = undefined > > instance TFoo Int where > type TFooFun Int = Double > instance TFoo Double where > type TFooFun Double = Int > instance TFoo String where > type TFooFun String = String > > class THMapFoo1 as where > type THMapFoo1Res as > thMapFoo1 :: as -> THMapFoo1Res as > > instance (TFoo a, THMapFoo1 as) => THMapFoo1 (a :* as) where > type THMapFoo1Res (a :* as) = TFooFun a :* THMapFoo1Res as > thMapFoo1 (x :* xs) = tfoo x :* thMapFoo1 xs > > instance THMapFoo1 HNil where > type THMapFoo1Res HNil = HNil > thMapFoo1 _ = HNil The following, when enabled, takes ~3.5s. This demonstrates that slowdown occurs with type families as well. > testTHMapFoo1 = thMapFoo1 sampleData > class THMapFoo2 acc as where > type THMapFoo2Res acc as > thMapFoo2 :: acc -> as -> THMapFoo2Res acc as > > instance (TFoo a, THMapFoo2 (TFooFun a :* acc) as) => THMapFoo2 acc (a :* as) where > type THMapFoo2Res acc (a :* as) = THMapFoo2Res (TFooFun a :* acc) as > thMapFoo2 acc (x :* xs) = thMapFoo2 (tfoo x :* acc) xs > > instance THMapFoo2 acc HNil where > type THMapFoo2Res acc HNil = acc > thMapFoo2 acc _ = acc The following, when enabled, takes ~0.6s. This demonstrates that the tail recursive transform fixes the slowdown with type families just as with fundeps. > testTHMapFoo2 = thMapFoo2 HNil sampleData > class THMapFoo3 acc as where > type THMapFoo3Res acc as > thMapFoo3 :: acc -> as -> THMapFoo3Res acc as > > instance (THMapFoo3 (TFooFun a :* acc) as, TFoo a) => THMapFoo3 acc (a :* as) where > type THMapFoo3Res acc (a :* as) = THMapFoo3Res (TFooFun a :* acc) as > thMapFoo3 acc (x :* xs) = thMapFoo3 (tfoo x :* acc) xs > > instance THMapFoo3 acc HNil where > type THMapFoo3Res acc HNil = acc > thMapFoo3 acc _ = acc The following, when enabled, also takes ~0.6s. This demonstrates that, unlike the fundep case, the order of type class constraints does not, in this instance, affect the performance of type families. > testTHMapFoo3 = thMapFoo3 HNil sampleData --Gershom

2 1

non-linear complexity of :reload combined with :module in ghci
by Simon Hengel 12 Jul '11

12 Jul '11

Hi all, I realized that ghci shows non-linear time complexity for a sequence of :module and :reload commands, say we do multiple times: :module *Foo :reload Steps to reproduce: time for i in {1..10}; do echo -e ':m Prelude\n:r'; done |ghci time for i in {1..99}; do echo -e ':m Prelude\n:r'; done |ghci On my system the first run uses 1 second of CPU time, the second 39 seconds. Is this considered a bug? Cheers, Simon

2 2

Locating extra-libraries
by Greg Steuck 12 Jul '11

12 Jul '11

Hello, I am integrating ghc-7.0.3 into our build system running on Linux-amd64. One of the features of said build system is full isolation from the host system. This means we do not use the default compilers and library paths. We further have separation between runtime and compile time paths. This means that libm.so is only available in the compile environment and is not anywhere in rpath of the ghc binary. Now, I try to compile a simple TH based program. GHC fails pretty quickly: <command line>: user specified .o/.so/.DLL could not be loaded (libm.so: cannot open shared object file: No such file or directory) Whilst trying to load: (dynamic) m Additional directories searched: (none) After some head scratching I add -L$(dirname $lib.so) to my GHC command line. Life is good? Not quite, the next blow is harder, if I try to compile a slightly more complicated project which requires run time loading of unix package, I get: Loading package unix-2.4.2.0 ... <command line>: can't load .so/.DLL for: pthread (libpthread.so: cannot open shared object file: No such file or directory) The unix package config file lists: extra-libraries: rt util dl pthread This seems to be the logical consequence of "we agreed that all extra-libraries should be found either on the search path or on the package's library-dirs." (http://hackage.haskell.org/trac/ghc/ticket/3930) Unfortunately my environment does not satisfy the preconditions. I will also be hard pressed to pinpoint the compile environment location ahead of time. Sticking the path into the package .conf is hard. All the compiler paths are set up with -pgm flags when I invoke GHC. So, I resort to making this patch diff --git a/ghc/compiler/ghci/Linker.lhs b/ghc/compiler/ghci/Linker.lhs index bd0bb35..192d416 100644 --- a/ghc/compiler/ghci/Linker.lhs +++ b/ghc/compiler/ghci/Linker.lhs @@ -1026,7 +1026,7 @@ linkPackages' dflags new_pks pls = do linkPackage :: DynFlags -> PackageConfig -> IO () linkPackage dflags pkg = do - let dirs = Packages.libraryDirs pkg + let dirs = Packages.libraryDirs pkg ++ libraryPaths dflags let libs = Packages.hsLibraries pkg -- The FFI GHCi import lib isn't needed as This effectively extends the extra-libraries search path to also include any -L paths specified on the command lines. Is there a better way to do what I'm doing? Is there any chance such a patch can be applied? Thanks Greg

2 3

Profile: zero total time
by Matthew Farkas-Dyck 11 Jul '11

11 Jul '11

I am trying to take a profile of a program, but when I run it, the total time (as given in the profiling report file) is zero! total time = 0.00 secs (0 ticks @ 20 ms) However, the -s option yields the following data: 3,429,300,984 bytes allocated in the heap 210,760,024 bytes copied during GC 23,647,224 bytes maximum residency (13 sample(s)) 3,536,968 bytes maximum slop 58 MB total memory in use (0 MB lost due to fragmentation) Generation 0: 6339 collections, 0 parallel, 1.14s, 1.42s elapsed Generation 1: 13 collections, 0 parallel, 0.28s, 0.34s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 96.60s (124.50s elapsed) GC time 1.42s ( 1.75s elapsed) RP time 0.00s ( 0.00s elapsed) PROF time 0.00s ( 0.00s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 98.02s (126.25s elapsed) %GC time 1.4% (1.4% elapsed) Alloc rate 35,498,347 bytes per MUT second Productivity 98.5% of total user, 76.5% of total elapsed The time taken by each cost centre is also zero. The program is compiled with options "-prof -auto-all -caf-all" by GHC 7.0.3 and run with RTS options "-p -s". The true time taken is certainly NOT zero. How is this possible? Thanks. Cheers, Matthew Farkas-Dyck

4 5

Reloading and templates
by Jonas Almström Duregård 11 Jul '11

11 Jul '11

Hi, In ghci, if you change a module that exports a TH template it will not recompile modules that use the template. Example: -- In A.hs {-#LANGUAGE TemplateHaskell#-} module A where import Language.Haskell.TH a = [d|x = 5|] -- in B.hs {-#LANGUAGE TemplateHaskell#-} import A a -- As expected in ghci B.hs: *Main> x 5 -- But if i change the def. of a to [d|x = 4|] and do :r [1 of 2] Compiling A ( A.hs, interpreted ) Ok, modules loaded: A, Main. *Main> x 5 The only workaround i know is to reload all modules. I assume you have the same problem when compiling with ghc. This has caused headaches for me on several occasions lately, is there a ticket for it or should i submit one? Regards, Jonas

2 1

Mysterious slowness/crashing in GHCi
by Simon Marlow 06 Jul '11

06 Jul '11

Hi folks, GHCi has some weird behaviour sometimes with one or more of these symptoms: - becoming very slow and/or unresponsive - gobbling up memory - crashing with "thread blocked indefinitely on MVar" Some people have reported this happening when they weren't even doing anything, GHCi was just sitting at the prompt. e.g. this ticket: http://hackage.haskell.org/trac/ghc/ticket/4245 All the reports were Windows, but I've seen it happen on Mac too (but not Linux). I really need a way to reproduce this. If anyone has any clues, or can offer any more information (even if it's just a "me too, on platform X"), please let us know. Cheers, Simon

1 0

Network.HaskellNet.IMAP over SSL connection
by HP Wei 29 Jun '11

29 Jun '11

I tried to use Network.HaskellNet.IMAP to read emails and failed: user error (NO: Plaintext authentication disallowed on non-secure (SSL/TLS) connections.) Any solution for reading emails over SSL connection ?? thanks HP

1 0