January 2007 - Glasgow-haskell-users

Re: Replacement for GMP: Update
by Peter Tanski 24 Jan '07

24 Jan '07

On Tue, 23 Jan 2007, John Meacham wrote: > I think the benchmarks are flawed in an important way, I believe, (but > am not positive) that ARPREC uses a special factorized form of > representing numbers, which makes multiplicative type operations > extremely fast, but simple things like addition/subtraction quite > slow. Oh, don't worry. I've given up on ARPREC for the simple reason that *every* operation on small-size operands is very slow to say nothing of the time it would take to initialise ARPREC every time. ARPREC does store numbers using a representation similar to floating point, essentially an array of doubles where: (int)(array[0]) = array_size (int)(array[1]) = no_mantissa_words array[2] = exponent array[ 3 .. ] = mantissa I hope the tests aren't "flawed," in that the main purpose of performing those operations was to see the median-level performance (extreme performance being Integers with operands greater than, 10,000 or 30,000 bits). The crumby graphs do show that I made a low cutoff of 256 bits so the most common Integer-use ( < 128 bits, 4 uint32_t) wasn't even tested. I probably didn't clarify why I tested larger size operands. GHC should have something that is comparable to GMP, and that means speed (and precision) for medium-large operands as well as small operands. > you are only benchmarking multiplicative or similar routines, giving > ARPREC a huge lead, when in practice it might end up being slowest, as > addition/subtraction are extremely more common than multiplication. In the common case it is slowest--but not by much. > Also, how are you choosing the numbers to test with? it is possible > that > some packages are using 'sparse' representations or other specialized > forms if all your numbers happen to be powers of two or something. Random numbers--a different number for each iteration in size. I used a PRNG based on the SNOW2 stream cipher--something I wrote awhile ago, as fast as arc4random and tests well on DIEHARD and other statistical things. The GMP and OpenSSL random number generators were slower and I wanted to use the same generator across libraries. > also, pretty much all uses of integers will be for very small > integers, > we should be careful to not lose sight of speed for the common case > due > to pretty asymtotic bounds. All numbers were the same size, so cases like multiplying a 1024-bit operand by a 256-bit operand weren't tested; that could be a real flaw. It's all very sloppy--just to get an idea of where things generally line up. So, where am I now? I worked on the GHC-Win off and on and then went back to making a uniform API between GHC and the replacement, and I am re-writing the replacement. I thought I would be done several weeks ago but of course little things take over... One area of GHC I would really like to change is the memory-use. ForeignPtr seems to work well but places the full burden of memory management on the Integer library; for SIMD-use (AltiVec, SSE2), the library would require GHC to allocate memory aligned to 16-bytes. Right now, the only choice would be allocatePinned() (in rts/sm/Storage.c), which is 4-byte aligned and it is, of course, pinned so the GC can't move it. Imagine the RTS-memory problems you could have if you wrote a Haskell program using lots of small Integers allocated with, say, an allocatePinned_16() (16-byte aligned). The alternative would be to use normal memory but re-align the operands for the vectorized operations by peeling; o.k., doable (especially easy with AltiVec), but slower. In the meantime I have been working through SSE2 assembler, which doesn't have an addc (add-carry) operation and doesn't set a flag for overflow, so I have been experimenting with a SWAR-like algorithm--essentially the same thing as GMP's Nails--to make the normally 32-bit operands 31 bits with the last bit for a carry flag. Thorkil Naur and others have suggested writing the whole thing as small assembler operations and piece them together in Haskell; I have been looking into that as well but it seems to entail inlining every Integer function--imagine the code bloat. Cheers, Pete

2 1

Replacement for GMP: Update
by Peter Tanski 24 Jan '07

24 Jan '07

Simon PJ, Simon, Esa and John, Here is an update on what I have been doing so far in making a grand attempt to replace GMP. (1) evaluate replacement libraries LibTomMath: Pros- * has all the operators GMP offered Cons- * slow; about half as fast as OpenSSL in my tests for simple mathematical operations, much slower if you account for time to write or resize memory. (There is another MP library, which LibTomMath is based on, that is also very slow--student work) * not even reentrant; needs significant modification * beta-release; needs a bit of work to get it to production level * configuration needs to be written (not really portable, messy) ARPREC: Pros- * very fast (essentially does everything through the Floating Point Unit of a CPU) * complex mathematical operations * very precise * already thread safe (through C++ thread-safe statics) Cons- * no bitwise operations (not even left and right-shifts) * difficult configuration (everything runs by setting a precision level; ("precision level" ~= number of words (doubles) in array) it does not automatically resize memory; conversion from MP Real to Integer relies specially on careful precision-level) * memory inefficient (underestimates the number of real digits you can fit into a double, i.e., a 64-bit double has 48 bits of precision, holding about 9.6 digits per byte, resulting in an 848-byte array to hold an MP number with 1000 digits). OpenSSL: Crypto++ (http://www.eskimo.com/~weidai/cryptlib.html) Botan (http://botan.randombit.net/) Pros- * all of these are fast, since all use Integers to support cryptography; (Crypto++ and Botan are C++ crypto-libraries, all licenses good) * all of these provide most basic mathematical operations Cons- * none of these provide &, |, ^(xor) bitwise operators * Botan has least mathematical operators of the three * none provide lcm operator * all would realistically have to have the Integer libraries stripped out of the distribution and repackaged for GHC Summary: I finally settled on modifying OpenSSL, since that would be the easiest to work with under GHC's hood (plain C code, not C++). I have to: a. make OpenSSL's BN thread-safe (add thread local storage, at least) b. optimally add configure-conditional parallelism to BN (through PVM) c. add &, |, ^, lcm and a few other operations d. separate the BN from the rest of OpenSSL and rename the symbols to avoid conflicts (necessary because I have to modify the library anyway) (2) work on GHC: * finally understand C--; know what I need to modify * work through Makefiles: touch and go; I haven't mapped out all the variable settings from configure.in on down when it comes to DLLs Comment: for the Makefile in ghc/rts, in lines 300-346, GC_HC_OPTS += -optc-O3 --isn't this problematic? gcc, from -O2 on includes -fgcse which may *reduce* runtime performance in programs using computed gotos; -fgcse is actually run twice, because -frerun-cse-after-loop is also set at -O2. Would it be better to pass individual flags, such as -funroll-loops and -falign-loops=16 (ppc, Intel setting)? (3) I have been looking at how to implement a dual-constructor-in-a- pointer for Integer (i.e., merge constructors of small Integers and big Integers into the Int#). Would that solution be workable or might it break current Haskell programs? Just a thought. -Peter

11 29

ghci confused by hi files
by Yitzchak Gale 23 Jan '07

23 Jan '07

I have observed the following weird behavior: When I define an instance of a certain MPTC in a separate module from the definition of the class, ghci's ability to recognize the methods of the class seems to vary depending on whether or not hi files exist for the modules. I am using the current Debian build of GHC 6.6. Below are a set of three files that reproduce the behavior, and a shell session that demonstrates it. Before I compile the program, ghci works fine. After I compile with ghc - thus generating hi files - ghci gets confused. Then I delete the hi files and everything is fine again. Thanks, Yitz -- File Oops.hs {-# OPTIONS_GHC -fglasgow-exts #-} module Oops where class Oops a b c | a -> b c where foo :: a -> b -> a -- File Whoops.hs {-# OPTIONS_GHC -fglasgow-exts #-} module Whoops where import Oops instance Oops String Int Bool where foo x n = show (x, n) -- File runWhoops.hs module Main where import Whoops import Oops main = putStrLn $ foo "bar" 42 $ ghci Whoops / /_\// /_/ / / | | GHC Interactive, version 6.6, for Haskell 98. Loading package base ... linking ... done. [1 of 2] Compiling Oops ( Oops.hs, interpreted ) [2 of 2] Compiling Whoops ( Whoops.hs, interpreted ) Ok, modules loaded: Oops, Whoops. *Whoops> foo "baz" 7 "(\"baz\",7)" *Whoops> Leaving GHCi. $ ghc --make runWhoops.hs [1 of 3] Compiling Oops ( Oops.hs, Oops.o ) [2 of 3] Compiling Whoops ( Whoops.hs, Whoops.o ) [3 of 3] Compiling Main ( runWhoops.hs, runWhoops.o ) Linking runWhoops ... $ ghci Whoops / /_\// /_/ / / | | GHC Interactive, version 6.6, for Haskell 98. Loading package base ... linking ... done. Ok, modules loaded: Oops, Whoops. Prelude Whoops> foo "baz" 7 <interactive>:1:0: Not in scope: `foo' Prelude Whoops> Leaving GHCi. $ rm *.hi $ ghci Whoops / /_\// /_/ / / | | GHC Interactive, version 6.6, for Haskell 98. Loading package base ... linking ... done. [1 of 2] Compiling Oops ( Oops.hs, interpreted ) [2 of 2] Compiling Whoops ( Whoops.hs, interpreted ) Ok, modules loaded: Oops, Whoops. *Whoops> foo "baz" 7 "(\"baz\",7)"

2 3

BUG: GHC compiler error for 6.6
by Chris Kuklewicz 23 Jan '07

23 Jan '07

When compiling programs (ghc --make) that use regex-parsec I trigger an error in GHC 6.6: > ghc-6.6: panic! (the 'impossible' happened) > (GHC version 6.6 for powerpc-apple-darwin): > simplCore/Simplify.lhs:(1772,0)-(1788,47): Non-exhaustive patterns in function bind_args I don't have a simple test case yet, but will try to make one if requested. -- Chris

2 4

Sharing analysis
by Stefan Holdermans 23 Jan '07

23 Jan '07

Dear all, Does GHC (still) perform sharing analysis as described in 'Once Upon a Polymorphic Type' [2] and/or Keith Wansbrough's PhD thesis [1]? If so, how does one inspect the results of the analysis? Thanks in advance, Stefan ----- [1] Keith Wansbrough. Simple Polymorphic Usage Analysis. Ph.D. thesis, University of Cambridge, 2002. [2] Keith Wansbrough and Simon Peyton Jones. Once upon a polymorphic type. In POPL ’99, Proceedings of the 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, January 20–22, 1999, San Antonio, TX, pages 15–18. ACM Press, 1999.

2 1

Re: HEAD ghci crash on ppc OS X
by Peter Tanski 20 Jan '07

20 Jan '07

On 16 Jan 2007, David Kirkman wrote: > On 1/15/07, David Kirkman <dkirkman(a)gmail.com> wrote: >> >> The comment above seems to be begging for a >> >> oc->image += oc->misalignment; >> >> statement right after the call to stgMallocBytes. >> > > This did in fact work (patch for rts/Linker.c below). And it *was* in > the 6.6 sources, so it was removed in the last few months. Putting > the line back in seems to fix everything on ppc darwin: my code which > uses "ghc as a library" to do a bunch of dynamic compilation and > loading works again, and the test suite looks pretty much like the > results from the latest linux builds > (http://www.haskell.org/ghc/dist/current/logs/x86_64-unknown-linux- > test-summary) Awesome! (I bet you haven't heard that exclamation since the '80s.) > I can only get a partial darcs repository, so I can't figure out why > the line was removed -- presumably to fix something that my patch will > proceed to rebreak :) I doubt you would re-break anything: the change was created by a patch fixing Bug #885. If you look at the .dpatch in the listing for #885, the patch records at lines 329-335: hunk ./rts/Linker.c 1379 - oc->image += misalignment; - +# else + oc->image = stgMallocBytes(oc->fileSize, "loadObj(image)"); +# endif + but did not add your change back in. Cheers, Peter Tanski

1 0

Strange behavior with Network sockets
by mrd 20 Jan '07

20 Jan '07

This program listens on port 9000 and mirrors everything typed into the client onto stdout, IF it is working correctly. In GHC 6.6 (and HEAD), it seems to block unexpectedly, and this strange behavior is related to hIsOpen and hIsEOF, somehow. It acts like hIsOpen or hIsEOF is holding up the loop until input arrives, but it still blocks at hGetLine. The server ends up printing out lines that were typed into the client a while ago, as if it were stuck on some kind of backlog but could not catch up. Not sure how to explain this without showing it, maybe this: Client: Server: ------- ------- line1 handle isOpen = True; isEOF = False line2 line1 line3 handle isOpen = True; isEOF = False line4 line2 line5 line6 line7 Client has typed 7 lines and sent them to the server, but the server has only printed out 2 lines. If you remove the hIsOpen and hIsEOF calls, then the server will print out all 7 lines immediately as they are submitted. > import Control.Concurrent > import Control.Concurrent.STM > import System.IO > import Network > main = withSocketsDo $ do > sock <- listenOn $ PortNumber 9000 > (h,_,_) <- accept sock > ch <- atomically newTChan > -- thread which pumps lines read > -- from socket into channel > forkIO . sequence_ . repeat $ > hGetLine h >>= atomically . writeTChan ch > -- main thread just waits for data from channel > -- and prints it to screen > sequence_ . repeat $ > do isOpen <- hIsOpen h > isEOF <- hIsEOF h > putStrLn $ "handle isOpen = " ++ show isOpen > ++ "; isEOF = " ++ show isEOF > hFlush stdout > line <- atomically $ readTChan ch > putStrLn line > hFlush stdout Any idea what's going on? -- -- Matthew Danish -- user: mrd domain: cmu.edu -- OpenPGP public key: C24B6010 on keyring.debian.org

2 2

Final Call for Papers: TFP 2007, New York, USA
by TFP 2007 19 Jan '07

19 Jan '07

Dear Colleagues, The abstract submission deadline, February 1, is quickly approaching. We hope to see you at TFP 2007 in New York. NEW: Abstract submission is now open! Link: http://cs.shu.edu/tfp2007/submissions.html NEW: Invited Talk: John McCarthy, Standford University CALL FOR PAPERS Trends in Functional Programming 2007 New York, USA April 2-4, 2007 http://cs.shu.edu/tfp2007/ The symposium on Trends in Functional Programming (TFP) is an international forum for researchers with interests in all aspects of functional programming languages, focusing on providing a broad view of current and future trends in Functional Programming. It aspires to be a lively environment for presenting the latest research results through acceptance by extended abstracts. A formal post-symposium refereeing process then selects the best articles presented at the symposium for publication in a high-profile volume. TFP 2007 is co-hosted by Seton Hall University and The City College of New York (CCNY) and will be held in New York, USA, April 2-4, 2007 at the CCNY campus. SCOPE OF THE SYMPOSIUM The symposium recognizes that new trends may arise through various routes. As part of the Symposium's focus on trends we therefore identify the following five article categories. High-quality articles are solicited in any of these categories: Research Articles leading-edge, previously unpublished research work Position Articles on what new trends should or should not be Project Articles descriptions of recently started new projects Evaluation Articles what lessons can be drawn from a finished project Overview Articles summarizing work with respect to a trendy subject Articles must be original and not submitted for simultaneous publication to any other forum. They may consider any aspect of functional programming: theoretical, implementation-oriented, or more experience-oriented. Applications of functional programming techniques to other languages are also within the scope of the symposium. Articles on the following subject areas are particularly welcomed: o Dependently Typed Functional Programming o Validation and Verification of Functional Programs o Debugging for Functional Languages o Functional Programming and Security o Functional Programming and Mobility o Functional Programming to Animate/Prototype/Implement Systems from Formal or Semi-Formal Specifications o Functional Languages for Telecommunications Applications o Functional Languages for Embedded Systems o Functional Programming Applied to Global Computing o Functional GRIDs o Functional Programming Ideas in Imperative or Object-Oriented Settings (and the converse) o Interoperability with Imperative Programming Languages o Novel Memory Management Techniques o Parallel/Concurrent Functional Languages o Program Transformation Techniques o Empirical Performance Studies o Abstract/Virtual Machines and Compilers for Functional Languages o New Implementation Strategies o any new emerging trend in the functional programming area If you are in doubt on whether your article is within the scope of TFP, please contact the TFP 2007 program chair, Marco T. Morazan, at tfp2007(a)shu.edu. SUBMISSION AND DRAFT PROCEEDINGS Acceptance of articles for presentation at the symposium is based on the review of extended abstracts (6 to 10 pages in length) by the program committee. Accepted abstracts are to be completed to full papers before the symposium for publication in the draft proceedings and on-line. Further details can be found at the TFP 2007 website. POST-SYMPOSIUM REFEREEING AND PUBLICATION In addition to the draft symposium proceedings, we intend to continue the TFP tradition of publishing a high-quality subset of contributions in the Intellect series on Trends in Functional Programming. IMPORTANT DATES Abstract Submission: February 1, 2007 Notification of Acceptance: February 20, 2007 Registration Deadline: March 2, 2007 Camera Ready Full Paper Due: March 9, 2007 TFP Symposium: April 2-4, 2007 PROGRAMME COMMITTEE John Clements California Polytechnic State University, USA Marko van Eekelen Radboud Universiteit Nijmegen, The Netherlands Benjamin Goldberg New York University, USA Kevin Hammond University of St. Andrews, UK Patricia Johann Rutgers University, USA Hans-Wolfgang Loidl Ludwig-Maximilians Universität München, Germany Rita Loogen Philipps-Universität Marburg, Germany Greg Michaelson Heriot-Watt University, UK Marco T. Morazán (Chair) Seton Hall University, USA Henrik Nilsson University of Nottingham, UK Chris Okasaki United States Military Academy at West Point, USA Rex Page University of Oklahoma, USA Ricardo Pena Universidad Complutense de Madrid, Spain Benjamin C. Pierce University of Pennsylvania, USA John Reppy University of Chicago, USA Ulrik P. Schultz University of Southern Denmark, Denmark Clara Segura Universidad Complutense de Madrid, Spain Jocelyn Sérot Université Blaise Pascal, France Zhong Shao Yale University, USA Olin Shivers Georgia Institute of Technology, USA Phil Trinder Heriot-Watt University, UK David Walker Princeton University, USA ORGANIZATION Symposium Chair: Henrik Nilsson, University of Nottingham, UK Programme Chair: Marco T. Morazan, Seton Hall University, USA Treasurer: Greg Michaelson, Heriot-Watt University, UK Local Arrangements: Marco T. Morazan, Seton Hall University, USA ************************************************************************************ Dr. Marco T. Morazan TFP 2007 Program Committee Chair http://cs.shu.edu/tfp2007/

1 0

RE: [Haskell] A question about a possible bug in GHC regarding GADTs and type classes
by Simon Peyton-Jones 18 Jan '07

18 Jan '07

[redirecting to ghc-users] This code works with the HEAD, where I recently fixed the interaction between GADTs and type classes. You'll need to use a HEAD compiler (not 6.6) though. Someone else may help you with the TyRange stuff; I'm just referring to the Num constraint in your data type. Simon | -----Original Message----- | From: haskell-bounces(a)haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Pablo Nogueira | Sent: 17 January 2007 15:36 | To: haskell(a)haskell.org | Subject: [Haskell] A question about a possible bug in GHC regarding GADTs and type classes | | Hi, | | I've been told the following short code is correct but it's GHC's | fault it does not type check. | Is that the case? | | -- | {-# OPTIONS -fglasgow-exts #-} | | -- An expression GADT: | | data Exp :: * -> * where | LitNum :: Num a => a -> Exp a | LitBool :: Bool -> Exp Bool | Plus :: Num a => Exp a -> Exp a -> Exp a | And :: Exp Bool -> Exp Bool -> Exp Bool | If :: Exp Bool -> Exp a -> Exp a -> Exp a | | -- An expression evaluator: | | evalExp :: Exp a -> a | evalExp (LitNum i) = i | evalExp (LitBool b) = b | evalExp (Plus x y) = evalExp x + evalExp y | evalExp (And x y) = evalExp x && evalExp y | evalExp (If c t e) = if (evalExp c) then (evalExp t) else (evalExp e) | -- | | The type checker complains that evalExp needs a Num constraint on its | type signature. | This can't be right, for Bool is not an instance of Num, right? | | Is it the case that the interaction between GADTs and type classes is | not fully worked out yet?

1 0

Re : HDirect and GHC-6.6
by Fernand Lacas 17 Jan '07

17 Jan '07

Hi, Here are some details on my building of HDirect with ghc-6.6, and where I am stuck. Skipping details about deprecated libs (such as IOExts) and some name conflicts (NativeInfo), I succeeded in building the "ihc.exe", the "hdirect" and "com" libs. I installed the "com" lib as a package on my system: $ ghc-pkg.exe list c:/ghc/ghc-6.6\package.conf: [...] com-0.22, fgl-5.2, (ghc-6.6), [...] $ ghc-pkg.exe describe com name: com version: 0.22 [...] exposed: True exposed-modules: AutoPrim Automation ClassFactory Com ComDll ComException ComPrim ComServ Connection ConnectionPoint EnumInterface ExeServer HDirect Pointer PointerPrim SafeArray StdDispatch StdTypes TypeLib WideString [...] extra-libraries: kernel32 user32 ole32 oleaut32 advapi32 From here, I tried to bootstrap the ihc compiler with the support for typelibs. $ cd ../src $ rm -f *.o $ make depend SUPPORT_TYPELIBS=YES $ make SUPPORT_TYPELIBS=YES But the "make depend" fails : $ make depend SUPPORT_TYPELIBS=YES ghc -M -optdep-f -optdep.depend -optdep-o -optdepo -cpp -DBEGIN_SUPPORT_TYPELIB S='-}' -DEND_SUPPORT_TYPELIBS='{-' -DBEGIN_NOT_SUPPORT_TYPELIBS='{-' -DEND_NOT_S UPPORT_TYPELIBS='-}' -package com -fglasgow-exts -static -fvia-C -Rghc-timing -Wall -package com AbsHUtils.lhs AbstractH.lhs Attribute.lhs Bag.lhs BasicT ypes.lhs CStubGen.lhs CgMonad.lhs CodeGen.lhs CoreIDL.lhs CoreUtils.lhs DefGen.l hs Desugar.lhs DsMonad.lhs Env.lhs FiniteMap.lhs GetOpt.lhs HugsCodeGen.lhs IDLS yn.lhs IDLToken.lhs IDLUtils.lhs ImportLib.lhs JavaProxy.lhs Lex.lhs LexM.lhs Li bUtils.lhs Literal.lhs Main.lhs MarshallAbstract.lhs MarshallAuto.lhs MarshallCo re.lhs MarshallDep.lhs MarshallEnum.lhs MarshallFun.lhs MarshallJNI.lhs Marshall JServ.lhs MarshallMethod.lhs MarshallMonad.lhs MarshallServ.lhs MarshallStruct.l hs MarshallType.lhs MarshallUnion.lhs MarshallUtils.lhs MkImport.lhs NameSupply. lhs NormaliseType.lhs Opts.lhs PP.lhs PpAbstractH.lhs PpCore.lhs PpIDLSyn.lhs Pr eProc.lhs Pretty.lhs Rename.lhs RnMonad.lhs Skeleton.lhs SrcLoc.lhs SymbolTable. lhs TLBWriter.lhs TypeInfo.lhs Utils.lhs Validate.lhs CustomAttributes.hs Parser .hs Version.hs OmgParser.hs NativeInfo.hs ImportLib.lhs:39:7: Could not find module `TypeLib': I do not understand why "TypeLib" is not found, as it is included in the "com" package. This may be a newbie's question, excuse me if it has been answered millions of time. Sincerely yours, Samuel PS : if I use the option in the src/Makefile, which consists in using "-i../comlib" and other flags instead of "-package com", the "make depend" works, but the following make fails as follows : ghc -fglasgow-exts -static -fvia-C -Rghc-timing -Wall -i../lib -L../lib -I../lib -i../comlib -lole32 -loleaut32 -ladvapi32 -c ../comlib/AutoPrim.hs -o ../comlib/AutoPrim.o -osuf o ../comlib/AutoPrim.hs:69:0: Invalid type signature Hope this helps. ___________________________________________________________________________ Découvrez une nouvelle façon d'obtenir des réponses à toutes vos questions ! Profitez des connaissances, des opinions et des expériences des internautes sur Yahoo! Questions/Réponses http://fr.answers.yahoo.com

1 0