January 2006 - Glasgow-haskell-users

RE: storing highly shared data structures
by Simon Marlow 12 Jan '06

12 Jan '06

On 22 December 2005 13:43, Christian Maeder wrote: > for storing highly shared data structures we use so called Annotated > Terms (shortly ATerms, details below). > > http://www.cwi.nl/htbin/sen1/twiki/bin/view/SEN1/ATerm > > In contrast to the Binary (or GhcBinary) class we compute the sharing, > which saves a lot of space for data types that keep redundant > information. > > With this we can store some of our data structures (of course only > non-cyclic and finite ones) in a few KBs that need MBs if stored > without sharing (as when using the Binary or the Show/Read > classes). > > So far so good. The problem remaining is that an object is _traversed_ > as if being unshared and thus the _time_ for the ATermTable > construction becomes too long for us. > > GHC's internal data structures (on the heap) are in many cases shared, > by pointer references. I.e. if I add a (single) symbol table to every > symbol that I use, then the symbol table will not be copied, but only > a reference added to my symbol. > > How can I detect this sharing in order to avoid traversing the very > same symbol table for every symbol? > > I've tried to use a "Map (Ptr ()) ShATerm". So before traversing an > object I look up its address and check if is was traversed before (if > not I traverse it and store it in my map for future lookups). > > 1.) I'm not sure if it is safe to use "Ptr ()" (meanwhile garbage > collection, heap compaction and what not could happen). Right - Ptr isn't the right thing here, because GC will move objects around. That's why we have StablePtr and StableName. In fact, what you really want here is the pointer-equality memo table implementation in the Memo module (package util). This is scheduled to be removed in 6.6, but it will be available as a Cabal package. Cheers, Simon

5 15

The -static option of ghc, and choice between user-supplied library types (Unix)
by Dimitry Golubovsky 12 Jan '06

12 Jan '06

The Paragraph 4.10.7 of the GHC users guide contains this: -static Tell the linker to avoid shared Haskell libraries, if possible. This is the default. -dynamic Tell the linker to use shared Haskell libraries, if available (this option is only supported on Mac OS X at the moment, and also note that your distribution of GHC may not have been supplied with shared libraries). As I understand, this is related to the GHC own libraries. What about user-supplied libraries (listed in the `extra-libraries' field of a Cabal package description) e. g.: extra-libraries: gd, jpeg, m from http://www.cs.chalmers.se/~bringert/darcs/haskell-gd/gd.cabal There are usually files like libm.a and libm.so together in the same directory where GHC looks for libraries. Does the -static / -dynamic ghc flag affect the choice which library to link against?Or, to control this, one has to descend to the linker options, and the default would be the linker default? I believe, this is Unix-specific: AFAIR on Windows (and OS/2) dynamic implibs were indistinguishable by their names from static libraries and had the .lib suffix anyway? -- Dimitry Golubovsky Anywhere on the Web

2 1

storing highly shared data structures
by Christian Maeder 11 Jan '06

11 Jan '06

Dear Haskell Experts, for storing highly shared data structures we use so called Annotated Terms (shortly ATerms, details below). http://www.cwi.nl/htbin/sen1/twiki/bin/view/SEN1/ATerm In contrast to the Binary (or GhcBinary) class we compute the sharing, which saves a lot of space for data types that keep redundant information. With this we can store some of our data structures (of course only non-cyclic and finite ones) in a few KBs that need MBs if stored without sharing (as when using the Binary or the Show/Read classes). So far so good. The problem remaining is that an object is _traversed_ as if being unshared and thus the _time_ for the ATermTable construction becomes too long for us. GHC's internal data structures (on the heap) are in many cases shared, by pointer references. I.e. if I add a (single) symbol table to every symbol that I use, then the symbol table will not be copied, but only a reference added to my symbol. How can I detect this sharing in order to avoid traversing the very same symbol table for every symbol? I've tried to use a "Map (Ptr ()) ShATerm". So before traversing an object I look up its address and check if is was traversed before (if not I traverse it and store it in my map for future lookups). 1.) I'm not sure if it is safe to use "Ptr ()" (meanwhile garbage collection, heap compaction and what not could happen). 2.) A single "Map (Ptr ()) ShATerm" does not work! It seems that sometimes objects are shared that have different types (as tests revealed). This seems obvious for newtypes but also happens (I think) without newtype declarations. However, shared ATerms are always different for different types, because the corresponding data constructors are different. So, I'm now thinking if I should try using the type of my data as key as well, i.e. using "Map (TypeRep, Ptr ()) ShATerm" to avoid duplicate traversals. Would this be worth the effort? What other possibilities could I try? An obvious solution is to avoid the redundancy in the first place (i.e. simply don't store the symbol table with every symbol), but that would require a major change of our sources, and would the code become clearer? (Many functions would need more arguments.) Finally, _reading in_ shared ATerms is fast, since ghc seems to exploit the sharing given by the injective ATermTable. Thanks for any help Christian More details: Brand, M.G.J. van den, H.A. de Jong, P. Klint, and P.A. Olivier (2000). "Efficient Annotated Terms." Software -- Practice & Experience 30:259--291. (The link "ATerm Library" http://www.cwi.nl/projects/MetaEnv/haterm/ under http://www.haskell.org/libraries/#compilation looks outdated to me. We have extra source code that - at the moment - cannot be distributed separately) Via an extension to DrIFT, http://repetae.net/john/computer/haskell/DrIFT, we generate class instances (similar to the Binary class) for our types that we want to store. Our ATerms are (basically) constructor terms of the form: data ShATerm = ShAAppl String [Int] deriving (Eq, Ord) (The annotation part of ATerms is omitted here since we don't use it) The Int-list contains the arguments as indices into an ATermTable being an injective "IntMap ShATerm" with update and lookup functions: addATerm :: ShATerm -> ATermTable -> (ATermTable, Int) getATerm :: Int -> ATermTable -> ShATerm The class (that DriFT derives instances for) looks as follows: class ShATermConvertible t where toShATerm :: ATermTable -> t -> (ATermTable, Int) fromShATerm :: (ATermTable, Int) -> t The automatically derived instance of i.e. a user-defined List data type "data List a = Nil | Cons a (List a)" is: instance ShATermConvertible a => ShATermConvertible (List a) where toShATerm att0 Nil = addATerm (ShAAppl "Nil" []) att0 toShATerm att0 (Cons a b) = case toShATerm att0 a of { (att1, a') -> case toShATerm att1 b of { (att2, b') -> addATerm (ShAAppl "Cons" [a', b']) att2 }} fromShATerm (att, i) = case getATerm i att of ShAAppl "Nil" [] -> Nil ShAAppl "Cons" [a, b] -> case fromShATerm (att, a) of { a' -> case fromShATerm (att, b) of { b' -> Cons a' b' }} _ -> error "ShATermConvertible List" (Internally the ATermTable also keeps an inverse "Map ShATerm Int" to support the efficient implementation of addATerm.) We can use the "baffle" tool to convert our files from shared (TAF) to unshared ATerm format and vice versa.

4 6

darcs switchover
by Simon Marlow 09 Jan '06

09 Jan '06

Hi Folks, As you probably know, there is a mirror of the GHC source tree in a darcs repository. (information about accessing the darcs repository is here: http://cvs.haskell.org/trac/ghc/wiki/GhcDarcs) The aim is to eventually switch over to using darcs for our revision control. The point of this message is to find out what constraints people have that will affect when we can throw the switch. It doesn't look like we'll be able to keep a CVS mirror going once we switch to darcs, so darcs will be the only way to get an up-to-date GHC source tree. How will it affect you? - If you just get the GHC sources from anonymous cvs, then you have to switch to getting sources using darcs. It's pretty simple. - If you are a developer, then you need to: (a) get sources from darcs, and (b) use 'darcs push' instead of 'cvs commit'. - You won't be able to browse the CVS repository via cvsweb any more. You can browse the contents of the darcs repository directly, and we hope to set up some kind of darcs-aware browsing too. We've switched some of our nightly builds over to using darcs, and it seems to be working nicely. darcs get --partial can actually get the sources quicker than anonymous CVS used to. Please let me know if the switchover is going to adversely affect your life, so that we can formulate a plan and timescale for switching over. Malcolm, Ross - since you both also use the CVS libraries tree, is it going to be possible for you to switch to using darcs to get the libraries? Any idea how long you'll need? Cheers, Simon

9 17

"Failed to load interface for ..."
by Bulat Ziganshin 09 Jan '06

09 Jan '06

Hello , how about adding suggestion to use "--make" to the following error message? it would be very helpful for novices. i have run into this problem several times before memoized that suggestion to use "-v" actually means that i forgot to add "--make" :) C:\!\Haskell\cpphs> ghc -O2 Main.hs Main.hs:17:0: Failed to load interface for `RunCpphs': Could not find module `RunCpphs': use -v to see a list of the files searched for -- Best regards, Bulat mailto:bulatz@HotPOP.com

3 3

problem with ghcprof on windows
by Conal Elliott 09 Jan '06

09 Jan '06

When run ghcprof under Windows XP I get this message in uDraw: "Error: Cannot start application C:/TEMP/ghcprof30164.sh". That file does exist as a shell script: bash-3.00$ ls -l C:/TEMP/ghcprof30164.sh -rwxr-xr-x 1 Conal None 109 Jan 7 12:12 C:/TEMP/ghcprof30164.sh bash-3.00$ cat C:/TEMP/ghcprof30164.sh #!/bin/sh /usr/local/cgprof C:/TEMP/ghcprof30164 0 "i386-unknown-mingw32" "" 10.0 12.0 13.0 0.0 0 1 1 2 1900 bash-3.00$ Any idea what's going wrong and how to fix? Thanks, - Conal

2 1

Re: cvs commit: fptools/libraries/base/Data IntMap.hs Map.hs Sequence.hs Set.hs fptools/libraries/base/Data/Generics Instances.hs Twins.hs
by Jim Apple 09 Jan '06

09 Jan '06

Simon Peyton Jones wrote: > simonpj 2006/01/06 07:51:23 PST > > Modified files: > libraries/base/Data IntMap.hs Map.hs Sequence.hs Set.hs > libraries/base/Data/Generics Instances.hs Twins.hs > Log: > Eta-expand some higher-rank functions. GHC is about to > move to *invariant* rather than *contra-variant* in function > arguments, so far as type subsumption is concerned. These > eta-expansions are simple, and allow type inference to > go through with invariance. Why drop contra-variace? Jim

1 0

object code blow up by optimization
by Christian Maeder 05 Jan '06

05 Jan '06

Hi, I've a few files that produce ten times bigger .o files when compiled with optimization (-O). This blow-up prevents linking on a mac. How could I find out what is causing this blow up? Thanks, Christian

2 4

tracing segfaults with FFI
by Gaal Yahas 04 Jan '06

04 Jan '06

Hello, I have these two functions: freezeNode node = do ptr <- newStablePtr node new (castPtr $ castStablePtrToPtr ptr) thawNode nodePtr = do deRefStablePtr (castPtrToStablePtr nodePtr) I use the first to pack a Haskell structure and hand it over to a c library with FFI. It calls me back (traces show I do get the original address) but deRefStablePtr causes a segfault. What am I doing wrong? More generally, how do I approach this kind of problem? What tools exist that can help me debug FFI code? -- Gaal Yahas <gaal(a)forum2.org> http://gaal.livejournal.com/

2 2

Unboxed types and FFI (GHC Users Guide, Section 8.1.1)
by Dimitry Golubovsky 04 Jan '06

04 Jan '06

The section 8.1.1 of the GHC User's Guide says this: The following unboxed types may be used as basic foreign types (see FFI Addendum, Section 3.2): Int#, Word#, Char#, etc Does this mean that when declaring a foreign function import for a C function int fun(int) I may write foreign import ccall "bla.h fun" fun :: Int# -> Int# instead of using CInt? Are there any examples of using unboxed types with FFI? -- Dimitry Golubovsky Anywhere on the Web

2 1