- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] Slow IO
by Daniel Fischer 14 Sep '06

14 Sep '06

Am Montag, 11. September 2006 17:44 schrieben Sie: > Daniel Fischer wrote: > > > Try Don Stewart's ByteString library > > > > -- and some data that made the programme segfault before now run in a > > couple of seconds. > > But that shouldn't happen! Segfaults aren't performance problems, but > errors. So your program contained a bug (lazyness where it isn't > useful, I suspect), and ByString is hiding it. Maybe I've misused the word segfault. What happened is: The programme consumed more and more memory (according to top), kswapd started to have a higher CPU-percentage than my programme, programme died, system yelling 'Speicherzugriffsfehler', top displays 'kswapd<defunct>'. I believe that means my programme demanded more memory than I have available (only 256MB RAM + 800MB swap). Is that a segfault or what is the correct term? That is probably due to (apart from the stupidity of my IO-code) the large overhead of Haskell lists. So the chunk of the file which easily fits into my RAM in ByteString form is too large as a list of ordinary Strings. However the problem might be too little lazyness, because if I explicitly read the file line by line, memory usage remains low enough -- but ByteString is *much* faster anyway. > > > So even if we just counted newlines, we would have to scan 1,700 million > > (1.7*10^9) chars per second. > > Could any ordinary computer of today do that, using whatever language? > > That rate should be no problem for a 2GHz machine. However, a 200MHz 64 > bit wide bus won't deliver the data fast enough and it is 50x as much as > the best hard disks could deliver in optimal circumstances. I guess, > most of the test cases are a lot smaller than your guesstimate. > I suppose so, too, but not knowing the test data, I assumed a bad case (uniform distribution of line-lengths and test-case-size in the specified range). > > Udo. Bulat: > are you mean arithmetic or geometric average? ;) I meant 'expected value'. If X_i are independent random variables uniformly distributed on [0 .. k], Y is a random variable (independent from the X_i) uniformly distributed on [1 .. n] and Z is the sum of the first Y of the X_i, then the expected value of Z is (n+1)*k/4. So we might call that a weighted arithmetic average, I suppose. Cheers, Daniel -- "In My Egotistical Opinion, most people's C programs should be indented six feet downward and covered with dirt." -- Blair P. Houghton

6 10

Optimization problem
by tpledger＠ihug.co.nz 14 Sep '06

14 Sep '06

Magnus Jonsson wrote: [...] > but your example fails on infinite lists [...] > take 2 $ snd $ head $ splitStreams (map (\x -> (0 ,x)) [1..]) Any approach, even sieving, will struggle with infinite lists, won't it? (take 2 . snd . head . splitStreams) [(i, i) | i <- [0..]] Regards, Tom

2 1

Re: [Haskell-cafe] Weak pointers and referential transparency???
by tpledger＠ihug.co.nz 13 Sep '06

13 Sep '06

Brian Hulley wrote: > tpledger(a)ihug.co.nz wrote: [...] > > My reading of the semantics > > (http://haskell.org/ghc/docs/latest/html/libraries/base/System-Mem-Weak.html…) > > is that you can be sure the proxy *object* is gone. > > My problem is that I don't know what to make of the word > "object" in the context of Haskell ie when can I be sure > that a value is actually being represented as a pointer > to a block of memory and not stored in registers or > optimized out? Or is the compiler clever enough to > preserve the concept of "object" despite such > optimizations? I had been designing my Model/Proxy data > types with the Java notion of "everything is a pointer to > an object" but is this always correct relative to Haskell > as a language or is it just a consequence of the current > GHC implementation? In the context of System.Mem.Weak, but not necessarily GHC, we're concerned solely with garbage collection of heap objects. So yes, that's Java-like. AFAIK. An example of something outside that context is a GHC Int# (unboxed Int). It never inhabits the heap, and isn't allowed to be passed to a function where a polymorphic parameter is expected (such as mkWeak). Regards, Tom

1 0

ffi question
by Maverick 13 Sep '06

13 Sep '06

Hi, I have a question about ffi in Hugs98 (WinHugs-May2006.exe), the Hugs98 documentation says: "Only the ccall, stdcall and dotnet calling conventions are supported. All others are flagged as errors." But I can't get a dotnet import, the ffihugs returns me an error: ffihugs "example.hs" "Prueba.cs" -lm runhugs: Error occurred ERROR "example.hs":6 - Foreign import calling convention "dotnet" not supported Why is this? hugs really don't support the "dotnet" calling convention or I have an error?. Thanks. Alvaro S. --------------------------------- LLama Gratis a cualquier PC del Mundo. Llamadas a fijos y móviles desde 1 céntimo por minuto. http://es.voice.yahoo.com

1 0

[OT] A DSL for state machines
by Stephane Bortzmeyer 13 Sep '06

13 Sep '06

Sorry, this is a bit off-topic but I post here because: * it is about a DSL and many Haskellers are fond of DSLs, * the first implementation is written in Haskell. http://www.cosmogol.fr/ describes a proposal to the IETF to standardize the language used for finite state machines (which are common in IETF standards), much like ABNF is standardized in RFC 4234, to describe grammars. The reference implementation, available at http://www.cosmogol.fr/shadok.html is in Haskell. Bug reports, patches, advices, flames, opinions and criticisms are welcome.

1 0

Why does this program eat RAM?
by John Goerzen 13 Sep '06

13 Sep '06

I have the below program, and I'm trying to run it on an input of about 90MB. It eats RAM like crazy, and I can't figure out why. I do know that the problem is not my custwords function (as you can see, I replaced the call to it with a call to the standard words function on the last line). It seems to be wordfreq, but I don't know why. For information about the problem, see http://changelog.complete.org/posts/535-A-Haskell-solution-to-Lars-Problem.… Here's the code: import System.Environment import Data.List import Data.Char import qualified Data.Map as Map custwords = filter (/= "") . lines . map (conv . toLower) where iswordchar x = isAlphaNum x && isAscii x conv x = if iswordchar x then x else '\n' wordfreq inp = Map.toList $ foldl' updatemap (Map.empty::Map.Map String Int) inp where updatemap nm word = Map.insertWith updatefunc word 1 nm updatefunc _ x = x + 1 freqsort (w1, c1) (w2, c2) = if c1 == c2 then compare w1 w2 else compare c2 c1 showit (word, count) = show count ++ " " ++ word main = do args <- getArgs interact $ unlines . map showit . take (read . head $ args) . sortBy freqsort . wordfreq . words

10 13

Retainer Profiling
by Mark Goldman 13 Sep '06

13 Sep '06

Ok, so I've done a biographical profile and gotten what (I think) are the top offenders in creating objects that never get used. (+RTS -hc -hbvoid) The GHC user's guide suggests that the next step is retainer profiling to see why things are being retained instead of trashed. Is anyone out there able to explain retainer profiling in more detail than the GHC user's guide because I've been guessing on both what I've been seeing and what it all means. Any response would be appreciated. -mdg -- Our problems are mostly behind us, now all we have to do is fight the solutions.

1 0

Weak pointers and referential transparency???
by tpledger＠ihug.co.nz 12 Sep '06

12 Sep '06

Brian Hulley wrote: [...] > Ref.write proxiesRef $! (weakProxy : proxies) (This is nothing to do with your main question, but the strict application looks unnecessary there. Its right hand side is already a constructor cell.) [...] > In other words, if the entry for the proxy > in the table stored in the Model dies, can > I be absolutely 100% sure that this means > the proxy no longer exists in any shape or > form in the running program? My reading of the semantics (http://haskell.org/ghc/docs/latest/html/libraries/base/System-Mem-Weak.html…) is that you can be sure the proxy *object* is gone. As for referential transparency... Fan-in: If you create equivalent proxies in different calls to createProxy, it's possible that they'll end up referring to the same object (e.g. if the compiler or RTS does something fancy, or you use a memoised smart constructor). So then a single live proxy object *could* protect many elements of your Weak Proxy list from scavenging. Fan-out: It would seem perverse to cry "referential transparency!" and spontaneously clone one of your proxy objects. That *could* lead to deRefWeak returning Nothing while an *equivalent* Proxy object is still alive. Might you run your program on an avant-garde distributed RTS? ;-) Regards, Tom

2 1

Slow IO
by Daniel Fischer 12 Sep '06

12 Sep '06

Hello all, Now I have an IO-problem, too. SPOJ problem 41 asks basically to determine whether a directed graph allows a path that uses every edge exactly once. The data from which the graphs are to be constructed are contained in a (huge) file, every item (number of test cases, size of test case, edges) on a single line. I've created my own test case file (much smaller, but already 217 MB, 2.2 million lines) to check my programme's performance. Now profiling reveals that over 90% of time and allocation are consumed by reading the file (line by line, reading the whole file as a lazy String and then chopping that to pieces is rather worse). So how do I quickly 1. read an Integer n from the file, 2. read the next n lines and 3. pass the first and last letter of those to the function that builds and checks the graph? When that is achieved, I could see whether my algorithm is good. Thanks for any help, Daniel -- "In My Egotistical Opinion, most people's C programs should be indented six feet downward and covered with dirt." -- Blair P. Houghton

4 5

haskell toolchain for slackware
by Andrea Rossato 12 Sep '06

12 Sep '06

Hello! Since there seems to be very little support for haskell in Slackware Linux, I'm putting together a repository with the most useful (for me) hasekll utilities. For the time being there are: 1. ghc-6.4.2 (precompiled binaries packaged for slackware) 2. haddock 3. darsc 4. hscurses 5. HaXml-1.13.2 6. HXT-6.1 with HTTP-20060707 I'm planning to add, very soon, Hugs, hs-plugins and fps-0.7. The repository should be accessible with slapt-get and swaret. I hope dependency checking is working with slapt-get. Here's the repo: http://gorgias.mine.nu/slack/ You can also grab the SlackBuild scripts (I started using Cabal with HaXml, HXT and HTTP) here: http://gorgias.mine.nu/repos/slackBuild/ or darcs get http://gorgias.mine.nu/repos/slackBuild/ I build my stuff in an almost current slack. Ciao Andrea

1 0