- Haskell-Cafe - Haskell.org

strange stack overflow with Data.Map
by David Roundy 30 Dec '05

30 Dec '05

Hi all, I've got a problem that I'm seeing using either Data.Map or Data.IntMap. > module Main where > import Data.List > import qualified Data.IntMap as Map > stats elems = foldl add_elem Map.empty elems > add_elem m x = Map.insertWith (+) x 1 m > main = print $ stats $ take 1000000 $ repeat 1 This program has a space leak and runs out of stack space. I'm guessing that I'm being bit here by an unnatural amount of laziness in Map.insertWith, but I can't see how to fix this. :( I'm sure it's something elementary... I tried defining add_elem m x = let m' = Map.insertWith (+) x 1 m Just num = Map.lookup x m' in seq num m' to force the (+) to be evaluated strictly, but that didn't help. -- David Roundy http://www.darcs.net

7 8

Re: [Haskell-cafe] GHC for Windows - no installer
by Paul Moore 30 Dec '05

30 Dec '05

On 12/29/05, Simon Peyton-Jones <simonpj(a)microsoft.com> wrote: > Yes, it should work > http://www.haskell.org/ghc/docs/latest/html/users_guide/sec-install-wind > ows.html Thanks. Sorry I missed that link, and thanks for the pointer. Paul.

1 0

How to read this syntax?
by David F. Place 30 Dec '05

30 Dec '05

Hi, I am trying to read _Arrows, Robots, and Functional Reactive Programming_ by Hudak, et al. http://www.haskell.org/yampa/AFPLectureNotes.pdf In section 2.1 there are a number of equations of the form: g’ :: SF A C g’ = arr g = arr f1 >>> arr f2 and i’ :: SF (A,C) (B,D) i’ = arr i = arr (f1 . fst) &&& arr (f2 . snd) = (arr fst >>> arr f1) &&& (arr snd >>> arr f2) I can't find any reference to the syntax where the function left hand side is just "space." I'd greatly appreciate any insight. -------------------------------- David F. Place mailto:d@vidplace.com

2 1

Re: [Haskell-cafe] strange stack overflow with Data.Map
by David Roundy 29 Dec '05

29 Dec '05

On Thu, Dec 29, 2005 at 04:24:02PM +0100, Jean-Philippe Bernardy wrote: > On 12/29/05, David Roundy <droundy(a)abridgegame.org> wrote: > > On Thu, Dec 29, 2005 at 01:42:29PM +0100, Christian Maeder wrote: > > > David Roundy wrote: > > > >>stats elems = foldl add_elem Map.empty elems > > > >>add_elem m x = Map.insertWith (+) x 1 m > > > > > > > >>main = print $ stats $ take 1000000 $ repeat 1 > > > > > > > >This program has a space leak and runs out of stack space. I'm guessing > > > >that I'm being bit here by an unnatural amount of laziness in > > > >Map.insertWith, but I can't see how to fix this. :( I'm sure it's > > > >something elementary... > > > try: > > > > > > stats = foldl' add_elem Map.empty > > > add_elem m x = myinsertWith (+) x 1 m > > > > > > myinsertWith f k v m = > > > case Map.lookup k m of > > > Nothing -> Map.insert k v m > > > Just w -> let r = f v w in r `seq` Map.insert k r m > > > > Thanks, that does it! I had tried something like that, but without the > > foldl', and had tried foldl', but without the myinsertWith. The reason I > > didn't spend much time using this implementation is that for large maps, it > > will take twice as long as Map.insertWith, so I assumed (incorrectly) that > > Map.insertWith should be written so that it behaves in a non-leaky manner. > > I'm not sure I understand this ... Do you say that the leaky program > is faster than the non-leaky one ? No, what I mean is that Map.insertWith only traverses the Map once, while myinsertWith has to traverse it twice, so for a large map, each call to myinsertWith will take twice as long as Map.insertWith. Or to put it a different way, if myinsertWith were part of the Map module, it could be twice as fast. > > Should the Map modules have an additional Map.insertWith' that behaves > > strictly, or might it be the case that you always want strict behavior when > > using insertWith? > > IMO, there is always a possibility for needing the lazy version. I > also have to say that making a strict version for each "...With" does > not fill my heart with joy. :) Such cases call for cheapness analysis, > or optimistic evaluation, or some other kind of solution implemented > at the compiler level, IMHO. I agree, there is a possibility for wanting the lazy version. If you only want to provite one insertWith, I suppose you'd want to figure out whether the lazy or strict version is more commonly needed (or "safer"), and make people wanting the other version implement it themselves. In my opinion, the strict version seems nicer, largely because HNF is cheap for most "large" computations I do, so strictness wouldn't cost much. On the subject of excessive functions, what are the uses of insertWithKey? It seems like anything you do with insertWithKey you could just as efficiently do with insertWith... it seems pretty trivial to write insertWithKey f k x = insertWith (f k) k x There may be a use to all the WithKey variants, but I'd much rather have strict varients... -- David Roundy http://www.darcs.net

1 0

GHC for Windows - no installer
by Paul Moore 29 Dec '05

29 Dec '05

I'd like to have GHC available to me, but some of the PCs I work on are extremely tight on space, or "locked down" in such a way that I can't install GHC on them. To get around this, I was considering copying GHC from my development PC onto a pen drive, and then using that (setting PATH when I needed access to GHC). My question is, will this work? Can the Windows install of GHC be copied around, or does it rely on registry entries or other system configuration in such a way that it has to be "properly" installed? Thanks, Paul.

1 0

RE: GHC optimization issue
by Simon Peyton-Jones 29 Dec '05

29 Dec '05

I did look into this a little. There are several things going on * GHC doesn't really expect you to use INLINE and SPECIALISE together. INLINE says to inline a copy of the function at every call site, which is the best possible form of specialisation, so SPECIALISE is a bit redundant if you are happy to do that. (Incidentally, INLINE is ignored for recursive functions, whereas SPECIALISE works fine.) * If you have both INLINE and SPECIALISE, GHC makes a specialised copy of the function, and the specialised copy takes precedence. So a call at the specialised type turns into a call to the specialised function. (A call at any other type would not use the specialisation, and so the un-specialised function would be inlined.) Moreover, the specialised copies are themselves not marked INLINE. * GHC's HEAD in CVS (i.e 6.5) has a new feature {#- SPECIALISE INLINE f :: <type> #-} which tells GHC to specialise f and inline the specialised copy (only). Ordinary, un-specialised calls will not be inlined. * When you delete the pragmas, GHC uses a size-based heuristic to decide when to inline a function at a call site. Oddly, this heuristic decides (just) to inline the un-specialised function, but when it's specialised GHC thinks it's bigger and doesn't inline it. You can increase the threshold for inlining with -funfolding-use-threshold=20, say. http://www.haskell.org/ghc/docs/latest/html/users_guide/options-optimise .html#options-f This really is a bit odd, but I don't want to fiddle with GHC's inlining heuristics without doing lots of benchmark runs etc. Actually, it'd be quite an easy thing for others to try fiddling with, and I bet there are performance gains to be had. Simon | -----Original Message----- | From: Joel Reymont [mailto:joelr1@gmail.com] | Sent: 22 December 2005 14:09 | To: Haskell-Cafe Cafe | Cc: Simon Peyton-Jones; Simon Marlow | Subject: GHC optimization issue | | Folks, | | I have been trying to improve my byte swapping routines as part of my | effort to speed up serialization. I then tried to look at the core | output from GHC to see what it was converting my code into. Brandon | (skew on #haskell) helped me code a TH version but then I went with a | regular CPP version instead. | | The point of contention is that the logical approach to optimization | does not produce expected results. The only difference between the | following two core outputs is the presence or absence of specialize | and inline pragmas. The code is the same. | | The version without pragmas inlines foo1 into | | Main.foo1 :: GHC.Word.Word16 | [GlobalId] | [Str: DmdType] | Main.foo1 = case GHC.Word.Word16 GHC.Word.$wshift3 __word 3855 (-8) | of ww1_a2eo { __DEFAULT -> | case GHC.Word.Word16 GHC.Word.$wshift3 __word 15 8 of | ww_a2f4 { __DEFAULT -> | GHC.Word.W16# (GHC.Prim.narrow16Word# | (GHC.Prim.plusWord# ww1_a2eo ww_a2f4)) | } | } | | Whereas the version _with_ pragmas produces a function call: | | Main.foo1 :: GHC.Word.Word16 | [GlobalId] | [Str: DmdType] | Main.foo1 = case GHC.Word.Word16 Swap1.$w$sswap16 __word 3855 | of ww1_s1Ia { __DEFAULT -> | GHC.Word.W16# ww1_s1Ia | } | | Is there a reasonable explanation? | | Both versions compiled thusly: ghc --make Foo.hs -O -ddump-simpl > foo | | Swap: | | {-# OPTIONS_GHC -fglasgow-exts -cpp #-} | module Swap1 | ( | swap16 | ) | where | | import Data.Word | import Data.Int | import Data.Bits | | #define BIG_ENDIAN 1 | | {-# SPECIALIZE swap16 :: Word16 -> Word16 #-} | {-# SPECIALIZE swap16 :: Int16 -> Int16 #-} | {-# INLINE swap16 #-} | | swap16 :: Bits a => a -> a | #ifdef BIG_ENDIAN | swap16 v = (v `shiftR` 8) + ((v .&. 0xFF) `shiftL` 8) | #else | swap16 v = v | #endif | | Foo: | | module Main where | | import Data.Word | import Swap1 | | foo1 :: Word16 | foo1 = swap16 0x0f0f | | main = putStrLn $ show foo1 | | Core output for the version WITH pragmas, see the version w/o pragmas | way below | | ==================== Tidy Core Rules ==================== | "SPEC Swap1.swap16" __forall {$dBits_X1Co :: {Data.Bits.Bits | GHC.Int.Int16}} | Swap1.swap16 @ GHC.Int.Int16 $dBits_X1Co | = Swap1.$sswap16 ; | "SPEC Swap1.swap16" __forall {$dBits_X1Cv :: {Data.Bits.Bits | GHC.Word.Word16}} | Swap1.swap16 @ GHC.Word.Word16 $dBits_X1Cv | = Swap1.$sswap161 ; | | | ==================== Tidy Core ==================== | Main.foo1 :: GHC.Word.Word16 | [GlobalId] | [Str: DmdType] | Main.foo1 = case GHC.Word.Word16 Swap1.$w$sswap16 __word 3855 | of ww1_s1Ia { __DEFAULT -> | GHC.Word.W16# ww1_s1Ia | } | | ==================== Tidy Core ==================== | Swap1.$w$sswap16 :: GHC.Prim.Word# -> GHC.Prim.Word# | [GlobalId] | [Arity 1 | NoCafRefs | Str: DmdType L] | Swap1.$w$sswap16 = \ (ww_s1I5 :: GHC.Prim.Word#) -> | case GHC.Prim.Word# GHC.Word.$wshift3 ww_s1I5 | (-8) of ww1_a1Gx { __DEFAULT -> | case GHC.Prim.Word# GHC.Word.$wshift3 | (GHC.Prim.and# ww_s1I5 __word 255) 8 | of ww11_a1Hd { __DEFAULT -> | GHC.Prim.narrow16Word# (GHC.Prim.plusWord# | ww1_a1Gx ww11_a1Hd) | } | } | | Swap1.$w$sswap161 :: GHC.Prim.Int# -> GHC.Prim.Int# | [GlobalId] | [Arity 1 | NoCafRefs | Str: DmdType L] | Swap1.$w$sswap161 = \ (ww_s1HV :: GHC.Prim.Int#) -> | case GHC.Prim.Int# GHC.Int.$wshift2 ww_s1HV | (-8) of ww1_a1Fk { __DEFAULT -> | case GHC.Prim.Int# GHC.Int.$wshift2 | (GHC.Prim.word2Int# | (GHC.Prim.and# (GHC.Prim.int2Word# ww_s1HV) __word 255)) | 8 | of ww11_a1G5 { __DEFAULT -> | GHC.Prim.narrow16Int# (GHC.Prim.+# ww1_a1Fk | ww11_a1G5) | } | } | | Swap1.$sswap16 :: GHC.Int.Int16 -> GHC.Int.Int16 | [GlobalId] | [Arity 1 | Worker Swap1.$w$sswap161 | NoCafRefs | Str: DmdType U(L)m] | Swap1.$sswap16 = __inline_me (\ (w_s1HT :: GHC.Int.Int16) -> | case GHC.Int.Int16 w_s1HT of w1_X1I5 | { GHC.Int.I16# ww_s1HV -> | case GHC.Int.Int16 Swap1.$w$sswap161 | ww_s1HV of ww1_s1I0 { __DEFAULT -> | GHC.Int.I16# ww1_s1I0 | } | }) | | Swap1.$sswap161 :: GHC.Word.Word16 -> GHC.Word.Word16 | [GlobalId] | [Arity 1 | Worker Swap1.$w$sswap16 | NoCafRefs | Str: DmdType U(L)m] | Swap1.$sswap161 = __inline_me (\ (w_s1I3 :: GHC.Word.Word16) -> | case GHC.Word.Word16 w_s1I3 of | w1_X1Ih { GHC.Word.W16# ww_s1I5 -> | case GHC.Word.Word16 Swap1.$w | $sswap16 ww_s1I5 of ww1_s1Ia { __DEFAULT -> | GHC.Word.W16# ww1_s1Ia | } | }) | | Swap1.swap16 :: forall a_a1aQ. (Data.Bits.Bits a_a1aQ) => a_a1aQ -> | a_a1aQ | [GlobalId] | [Arity 1 | NoCafRefs | Str: DmdType L] | Swap1.swap16 = __inline_me (\ (@ a_a1dB) | ($dBits_a1ip :: {Data.Bits.Bits | a_a1dB}) -> | let { | $dNum_s1BO :: {GHC.Num.Num a_a1dB} | [Str: DmdType {a1ip->U | (SAAAAAAAAAAAAAAAAA)}] | $dNum_s1BO = Data.Bits.$p1Bits @ | a_a1dB $dBits_a1ip } in | let { | lit_s1BN :: a_a1dB | [Str: DmdType {a1ip->U | (SAAAAAAAAAAAAAAAAA) s1BO->U(AAAAAAAAS)}] | lit_s1BN = GHC.Num.fromInteger @ | a_a1dB $dNum_s1BO (GHC.Num.S# 255) | } in | \ (v_a1aW :: a_a1dB) -> | GHC.Num.+ | @ a_a1dB | $dNum_s1BO | (Data.Bits.shiftR @ a_a1dB | $dBits_a1ip v_a1aW (GHC.Base.I# 8)) | (Data.Bits.shiftL | @ a_a1dB | $dBits_a1ip | (Data.Bits..&. @ a_a1dB | $dBits_a1ip v_a1aW lit_s1BN) | (GHC.Base.I# 8))) | | | Core output without pragmas: | | Main.foo1 :: GHC.Word.Word16 | [GlobalId] | [Str: DmdType] | Main.foo1 = case GHC.Word.Word16 GHC.Word.$wshift3 __word 3855 (-8) | of ww1_a2eo { __DEFAULT -> | case GHC.Word.Word16 GHC.Word.$wshift3 __word 15 8 of | ww_a2f4 { __DEFAULT -> | GHC.Word.W16# (GHC.Prim.narrow16Word# | (GHC.Prim.plusWord# ww1_a2eo ww_a2f4)) | } | } | | --- | Swap1.swap16 :: forall a_a1aQ. (Data.Bits.Bits a_a1aQ) => a_a1aQ -> | a_a1aQ | [GlobalId] | [Arity 1 | NoCafRefs | Str: DmdType L] | Swap1.swap16 = \ (@ a_a1dB) ($dBits_a1ip :: {Data.Bits.Bits a_a1dB}) -> | let { | $dNum_s1BK :: {GHC.Num.Num a_a1dB} | [Str: DmdType] | $dNum_s1BK = case {GHC.Num.Num a_a1dB} $dBits_a1ip | of tpl_B1 { Data.Bits.:DBits tpl1_B2 | tpl2_B3 tpl3_B4 tpl4_B5 tpl5_B6 tpl6_B7 tpl7_B8 tpl8_B9 tpl9_Ba | tpl10_Bb tpl11_Bc tpl12_Bd tpl13_Be tpl14_Bf tpl15_Bg tpl16_Bh | tpl17_Bi tpl18_Bj -> | tpl1_B2 | } } in | let { | lit_s1BM :: a_a1dB | [Str: DmdType] | lit_s1BM = case a_a1dB $dNum_s1BK | of tpl_B1 { GHC.Num.:DNum tpl1_B2 | tpl2_B3 tpl3_B4 tpl4_B5 tpl5_B6 tpl6_B7 tpl7_B8 tpl8_B9 tpl9_Ba -> | tpl9_Ba Swap1.lvl1 | } | } in | \ (v_a1aW :: a_a1dB) -> | tpl3_B4 | (case a_a1dB $dBits_a1ip | of tpl10_Xy { Data.Bits.:DBits tpl11_XB | tpl12_XD tpl13_XF tpl14_XH tpl15_XJ tpl16_XL tpl17_XN tpl18_XP | tpl19_XR tpl20_Bb tpl21_Bc tpl22_Bd tpl23_Be tpl24_Bf tpl25_Bg | tpl26_Bh tpl27_Bi tpl28_Bj -> | tpl26_Bh v_a1aW Swap1.lvl | }) | (case a_a1dB $dBits_a1ip | of tpl10_Xy { Data.Bits.:DBits tpl11_XB | tpl12_XD tpl13_XF tpl14_XH tpl15_XJ tpl16_XL tpl17_XN tpl18_XP | tpl19_XR tpl20_Bb tpl21_Bc tpl22_Bd tpl23_Be tpl24_Bf tpl25_Bg | tpl26_Bh tpl27_Bi tpl28_Bj -> | tpl25_Bg (tpl12_XD v_a1aW lit_s1BM) Swap1.lvl | }) | | -- | http://wagerlabs.com/ | | | |

1 0

RE: Erlang vs. Haskell (was Re: [Haskell-cafe] binary IO)
by Simon Peyton-Jones 29 Dec '05

29 Dec '05

| Using Haskell for this networking app forced me to focus on all the | issues _but_ the business logic. Type constraints, binary IO and | serialization, minimizing memory use and fighting laziness, timers, | tweaking concurrency and setting up message channels, you name it. That's a disappointing result. Mostly I think Haskell lets you precisely focus on the logic of your program, because lots else is taken care of behind the scenes. You found precisely the reverse. It'd be interesting to understand which of these issues are - language issues - library issues - compiler/run-time issues My (ill-informed) hypothesis is that better libraries would have solved much of your problems. A good example is a fast, generic serialisation library. If you felt able (sometime) to distil your experience under headings like the above, only more concretely and precisely, I think it might help to motivate Haskellers to start solving them. Simon

1 0

RE: [Haskell-cafe] Re: Haskell Speed
by Branimir Maksimovic 29 Dec '05

29 Dec '05

>From: Isaac Gouy <igouy(a)yahoo.com> >To: haskell-cafe(a)haskell.org >Subject: [Haskell-cafe] Re: Haskell Speed >Date: Tue, 27 Dec 2005 20:12:01 -0800 (PST) > >Branimir Maksimovic wrote: > > Of course, first example uses [String] instead of >Data.HashTable > > as other languages do. Imagine C program does not >use > > hash,rather list, how it will perform:) > >And the author comments his program >-- This is a purely functional solution to the >problem. >-- An alternative which keeps a mutable table of >occurences would >-- be faster. > Yes, I saw that but that does not qualifies for benchmark with hash tables. I mean program is ok, but this is aplles to oranges. >We'll be happy to also show a Haskell program that >uses Data.HashTable - first, someone needs to >contribute that program. Ok , i've attached hash table version. As I'm Haskell newbie I suppose there is someone which can do much better. > > > > I didn't look further after that. > >Ideal - you may criticize without the risk that others >will criticize what you do. Attachment follows, you can cricize my poor Haskell skills as much you want :) This version si actually D program trnslated to Haskell + file parsing code from original Haskell program. Now wou can compare no matter how slow it is :) Greetings, Bane. _________________________________________________________________ Don't just search. Find. Check out the new MSN Search! http://search.msn.click-url.com/go/onm00200636ave/direct/01/

1 0

Shared/Exclusive Locks
by John Goerzen 29 Dec '05

29 Dec '05

Hello, I have the need for a locking object that can provide shared and exclusive locks in much the same manner as the POSIX flock() function. A thread that acquires an exclusive lock has a guarantee that no other thread holds any locks. A thread that acquires a shared lock has a guarantee that no other thread holds an exclusive lock, though any number of other threads hold shared locks. My intuition tells me that this could be implemented in terms of an MVar somehow. (At least, I've used MVars for simple locks for quite some time.) But I can't quite figure out how. Any ideas? Thanks, -- John

4 6

NewBinary on Ptrs
by Pupeno 28 Dec '05

28 Dec '05

Hello, After trying my own code and reading the whole thread I started to understand NewBinary. I'm going to give it a try. My question now is how to turn a Ptr into a BinHandle to use NewBinary on it, or is there another way to do it ? Thanks. -- Pupeno <pupeno(a)pupeno.com> (http://pupeno.com)

2 1