- Glasgow-haskell-users

HEAD ghci crash on ppc OS X
by David Kirkman 28 Jan '07

28 Jan '07

I just built ghc from HEAD on OS X (ppc), and get the following error when starting ghci: ---start [15:15:15][david@isengard]$ compiler/stage2/ghc-inplace --interactive ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.7, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. ghc-6.7(9972,0xa000ed88) malloc: *** error for object 0x3807ff8: pointer being reallocated was not allocated ghc-6.7(9972,0xa000ed88) malloc: *** set a breakpoint in szone_error to debug malloc: failed on request for 11359964 bytes; message: ocAllocateJumpIslands ---end despite the suggestion, a breakpoint in szone_error catches nothing. But a breakpoint in malloc_printf (both szone_error and malloc_printf in the OS, not ghc) gives the following backtrace for an rts compiled with the -g flag: --start Breakpoint 1, 0x9012bb94 in malloc_printf () (gdb) bt #0 0x9012bb94 in malloc_printf () #1 0x90018388 in szone_realloc () #2 0x90018098 in realloc () #3 0x00e6f5c4 in stgReallocBytes (p=0x901a4df4, n=11359964, msg=0xfd9704 "ocAllocateJumpIslands") at RtsUtils.c:209 #4 0x00e97cbc in ocAllocateJumpIslands (oc=0x2b005d0, count=372, first=14502) at Linker.c:1598 #5 0x00e98954 in loadObj (path=0x2e63268 "/Network/Sid/Users/david/ ghc-crap/ghc/libraries/base/HSbase.o") at Linker.c:3743 #6 0x005b660c in s1wt_info () #7 0x00e8a220 in schedule (initialCapability=0x901a4df4, task=0x2e63268) at Schedule.c:608 #8 0x00c60e18 in main (argc=-1877324300, argv=0x3807ff8) at Main.c:105 (gdb) --end The call to failing call to stgReallocBytes occurs at line 1598 of Linker.c, in the following context: --start Linker.c, lines 1597 --> 1602 oc->image -= misalignment; oc->image = stgReallocBytes( oc->image, misalignment + aligned + sizeof (ppcJumpIsland) * count, "ocAllocateJumpIslands" ); oc->image += misalignment; --end oc->image is allocated at line 1326 of Linker.c (listing below), and then never modified until misalignment is subtracted from it at line 1598. Both the comment in the code fragment below, and the actual code in the fragment above seem to indicate that oc->image should be offset by misalignment. --start Linker.c, lines 1315 --> 1327 # elif defined(darwin_HOST_OS) // In a Mach-O .o file, all sections can and will be misaligned // if the total size of the headers is not a multiple of the // desired alignment. This is fine for .o files that only serve // as input for the static linker, but it's not fine for us, // as SSE (used by gcc for floating point) and Altivec require // 16-byte alignment. // We calculate the correct alignment from the header before // reading the file, and then we misalign oc->image on purpose so // that the actual sections end up aligned again. oc->misalignment = machoGetMisalignment(f); oc->image = stgMallocBytes(oc->fileSize + oc->misalignment, "loadObj(image)"); # else ---end The comment above seems to be begging for a oc->image += oc->misalignment; statement right after the call to stgMallocBytes. But I'm assuming it must normally be done someplace else -- I just can't figure out where. Anyway, I've verified that os->image is still pointing to the value returned from stgMallocBytes when misalignment (non-zero) is subtracted from it just before the call to stgReallocBytes. So in my build at least, the execution path is not hitting whatever part of the code that should be applying the misalignment offset to oc->image. Let me know if there is any more information I can give. -david k.

3 4

ANN: regex-tdfa 0.56
by Chris Kuklewicz 28 Jan '07

28 Jan '07

Greetings, My new regular expression backend "regex-tdfa" is passing all the tests I have been throwing at it, so it is time to share the good news. First up: Where is it? Version 0.56 is in my "stable" location at > darcs get --partial darcs.haskell.org:/home/darcs/packages/regex-tdfa The version that will get updated and broken more often is "unstable" at > darcs get --partial darcs.haskell.org:/home/darcs/packages/regex-unstable/regex-tdfa It needs a slightly updated regex-base package (version >= 0.80) at > darcs get --partial darcs.haskell.org:/home/darcs/packages/regex-unstable/regex-base It has only been tested (on Max OS X) with GHC 6.6 and depends on base >= 2.0 for Data.ByteString, Data.ByteString.Lazy, and Data.Sequence. ** What does regex-tdfa do? It runs POSIX regular expression searches correctly. No other regular expression backend for Haskell does this correctly. The regular expression can be chosen to be from a String, ByteString, ByteString.Lazy, or (Data.Seq Char). Independent of that choice the searched text can also be any of those types. ** Properties and benefits of regex-tdfa: It follows a known standard: POSIX. (If you find that it disagrees with the standard then I will fix it.) It is written in Haskell, so there is no C library to compile and install. Though it is currently only written for GHC 6.6, it could be ported to any other compiler with only minor changes. (I expect that if you drop the polymorphic MPTC interface of regex-base it could be made Haskell98). It works with Unicode since it can be used on [Char] (and it works if there are '\NUL' characters around). It is lazy in the regular expression: it only builds the DFA if you use it, and only builds the state it needs, which are memoized in a lazy Trie. It is lazy in the searched text, and the pure function that searches the text only evaluates the text until the next match is done and does not hold onto the initial text. Thus you could efficiently search a [Char] up to the size of the Position type, which is an Int for now. It is free, the regex-tdfa library is under a BSD-3 license. ** Does it work? Yes. The regex-posix backend that come with GHC does not run all the searches correctly: it is buggy (example at end of announcement). And the regex-posix backend is also impossibly slow -- the slowest backend by far -- orders of magnitude slower. The regex-tre backend that wraps the TRE library has exposed this very fast library to the harsh gaze of QuickCheck. The lesson from QuickCheck is to never use regex-tre because the TRE library (version 0.7.4) is buggy. For regex-tdfa backend I took/stole ideas from Ville Laurikari's Master thesis which describes the algorithm that TRE uses. And I made a pure Haskell implementation that now passes all the tests at http://www.research.att.com/~gsf/testregex/testregex.html and follows the notes at http://www.research.att.com/~gsf/testregex/re-interpretation.html and passes those tests as well. And it "passes" QuickCheck tests which actually just compare the answers that regex-posix, regex-tre, and regex-tdfa since I do not have a bug free reference implementation to compare against. ** Why the name TDFA? Tagged Deterministic Finite Automata. The Tagged part is from Ville Laurikari's thesis work. ** Speed: If you do not care only about the match as a whole and not about subexpression matching then you can set the captureGroups ExecOption to False: makeMyRegex = makeRegex defaultCompOpt myExecOpt where myExecOpt = defaultExecOpt { captureGroups = False } And redefine (=~) and (=~~) to use makeMyRegex instead of makeRegex: (=~) :: (RegexMaker Regex CompOption ExecOption source,RegexContext Regex source1 target) => source1 -> source -> target (=~) s r = let re = makeMyRegex r :: Regex in match re s (=~~) :: (RegexMaker Regex CompOption ExecOption source,RegexContext Regex source1 target,Monad m)=> source1 -> source -> m target (=~~) s r = let re = makeMyRegex r :: Regex in match re s The benefit to this is speed, as it then proceeds to run all matches of "b(..?c)?d" against a large test file *faster* than the the TRE C library backend. My compliments to those who worked on ghc and -O2. It even runs nearly as fast as regex-dfa in this mode. Thus regex-dfa is (mostly) obsolete. If you use the default and capture the subgroups then the speed is reduced by a factor of about 4. This is because of the very simple data structures that keep track of the run time state. I intend to improve this aspect of the design now that I have a working algorithm. I have not benchmarked the speed of compiling the regular expression from the String. This compiling is done with very lazy data structures, so the DFA size is really only as big as you actually explore while running the match. ** Examples of bugs in regex-posix and regex-tre: An example for regex-posix: > *Main> "ab" Posix.=~ "((a)|(b)){2,}" :: MatchArray > array (0,3) [(0,(0,2)),(1,(1,1)),(2,(0,1)),(3,(1,1)) The array holds (group #, (match offset, match length)) The 0th group is the whole match "ab". The 2nd group is (a) and it matched the first "a" and the third group is (b) and matched the "b". But the second group is a child of the first group ((a)|(b)) which matched "b". The standard requires that captured groups are nested inside their parents, and here "a" is not not nested inside "b". So the regex-posix C backend that comes with GHC is buggy. The correct answer is, where the second group matched nothing: > *Main> "ab" TDFA.=~ "((a)|(b)){2,}" :: MatchArray > array (0,3) [(0,(0,2)),(1,(1,1)),(2,(-1,0)),(3,(1,1))] An example for regex-tre: "yyyyyy" TRE.=~ "(yyy|(x?)){2,4}" array (0,2) [(0,("yyyyyy",(0,6))),(1,("yyy",(3,3))),(2,("yyy",(3,3)))],"") Here TRE reports that the second group (x?) which should only match "" or "x" somehow matched "yyy". This is even more wrong than the regex-posix bug above. The correct answer, where the second group does not match: array (0,2) [(0,("yyyyyy",(0,6))),(1,("yyy",(3,3))),(2,("",(-1,0)))],"") -- Chris Kuklewicz

1 0

RE: [Haskell-cafe] proposal: HaBench, a Haskell Benchmark Suite
by Simon Peyton-Jones 26 Jan '07

26 Jan '07

| Following up and the threads on haskell and haskell-cafe, I'd like to | gather ideas, comments and suggestions for a standarized Haskell | Benchmark Suite. Great idea. Maybe this can subsume nofib. I recommend reading the nofib paper though: http://citeseer.ist.psu.edu/partain93nofib.html Simon

1 0

ByteArr# - nullByteArr# anyone?
by John Meacham 26 Jan '07

26 Jan '07

I would like to create a datatype that contains some memory managed by the GHC runtime, the natural fit is ByteArr#, however, in the common case, the ByteArr# won't actually have anything in it. would it be possible to have a single constant 'nullByteArr#'? I can't define a top level value of type ByteArr# and creating these values is in very performance critical code so I am not quite sure what to do. It would also be nice if byteArrContents# returned 'nullAddr#' for such byte arrays, but it is not a strict requirement. John -- John Meacham - ⑆repetae.net⑆john⑈

2 2

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