- Haskell-Cafe - Haskell.org

SV: SV: Haskell-beginners problem with memory consuption
by Petter Egesund 02 Oct '03

02 Oct '03

Thanks for the tip - I will give it a try. PE -----Opprinnelig melding----- Fra: Ketil Malde [mailto:ketil+haskell@ii.uib.no] Sendt: 2. oktober 2003 09:02 Til: Petter Egesund Kopi: 'haskell-cafe(a)haskell.org' Emne: Re: SV: Haskell-beginners problem with memory consuption Petter Egesund <petter.egesund(a)kunnskapsforlaget.no> writes: > fun :: String -> String > look for pat1 in string - if found subst with sub1 > look for pat2 in string - if found subst with sub2 > look for pat3 in string - if found subst with sub3 > recurse until no pattern is found I would structure this as replace :: String -> [String] -> String replace input patterns = ... At each position of input, check for the presence of patterns (use isPrefixOf) and conditionally replace it, else output first char of input and recurse on input's tail. This should make the function "online", so that it can be streamed over a large but lazy list (say a file read with "readFile" -- hurry up before Simon takes it away! :-) without explicitly constructing the whole input or output String. -kzm -- If I haven't seen further, it is by standing in the footprints of giants

1 0

SV: Haskell-beginners problem with memory consuption
by Petter Egesund 02 Oct '03

02 Oct '03

Hi & thanks for answering; I should have been more precise, my function works like this: fun :: String -> String look for pat1 in string - if found subst with sub1 look for pat2 in string - if found subst with sub2 look for pat3 in string - if found subst with sub3 recurse until no pattern is found Cheers PE -----Opprinnelig melding----- Fra: Wolfgang Jeltsch [mailto:wolfgang@jeltsch.net] Sendt: 1. oktober 2003 15:36 Til: The Haskell Cafe Emne: Re: Haskell-beginners problem with memory consuption Am Mittwoch, 1. Oktober 2003, 15:18 schrieb Petter Egesund: > [...] > The problem is of course that the string is copied each time I do a > substitute, and I wonder if a more experienced haskeller has a better > solution to my problem. It doesn't have to be a problem that the string is copied each time. If you have, e.g., functions f1, f2, ..., fn :: String -> String and do something like f1 (f2 (... (fn string)...)) then string and the intermediate data can be removed by the garbage collector as soon as they are not needed. Unfortunately, from your message it's not very clear to me what exactly you mean, and, unfortunately again, I'm not an expert in Haskell memory management. > I have myself considered these solutions, but they all seems non-elegant; > [...] Indeed, they all look very non-elegant, and I think, there is a better solution. > Cheers, > > Petter Egesund Wolfgang _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1

Haskell-beginners problem with memory consuption
by Petter Egesund 02 Oct '03

02 Oct '03

Hi, I have just started using Haskell, and it has been really fun so far. But I have problems with memory usage when handling large files. What I do is the following; I load my file in one chunk, and does a lot of substitutes on the string - this is quick eating all my memory and the computers start to get really slow. The problem is of course that the string is copied each time I do a substitute, and I wonder if a more experienced haskeller has a better solution to my problem. I have myself considered these solutions, but they all seems non-elegant; 1. Use some IO extensions to fake a mutable variable - but solving a problem like this with a solution which is meant for IO does not seem right? 2. Split the file in smaller parts could be a solution, but then I would have to do a lot of preparsing to make sure I not spilt my file in the middle of a pattern. Sounds to me like developing a lex-like system for such a easy task is overkill? 3. I could maybe use some form of mutable arrays, but doing string regexps on an array...? 4. ? Any clues or opinions? Cheers, Petter Egesund

3 2

Another beginner's memory consumption problem...
by Bayley, Alistair 01 Oct '03

01 Oct '03

I'm trying the add-a-gram challenge from here: http://www.itasoftware.com/careers/programmers-archive.php ... and I'm also experiencing runaway memory consumption. If I load the supplied list of words (a 1.6M file) and search for shorter strings, things are OK. Memory consumption increases dramatically as I search for longer and longer trails. The function searchWord starts with a particular map and searches the maps below it (i.e. those containing shorter words), so when I search for longer trails, a larger number of maps must be examined. When I search for short trails, only a few (2-3 say) of the maps are examined. I think this implies some kind of lazy evaluation problem, but I'm not sure where to go from here. Was it a bad idea to use a Map of Maps as a data structure? Initially I had a list of Maps, but this wouldn't even load the full file (so I suppose lazy evaluation has allowed me to get a bit further...). Maps seemed like the right data structures to use for this problem. Is there some way I could force evaluation of the maps as the file is loaded? (Or is blaming the maps a red herring?) Program below: > module Main where > import Data.FiniteMap > import Data.List > import System.IO Data structure is a Map of Maps. The top-level Map holds Maps indexed by Int (for words of size n). Each of these Maps holds words of that size, where a key is the sorted list of chars for a word, and the value is the list of words whose sorted characters are that key i.e. all words constructed from the same set of characters. > type WordMaps = FiniteMap Int WordMap > type WordMap = FiniteMap String [String] > type MyWord = String ail + s = sail + n = nails + e = aliens + t = salient + r = entrails + c = clarinets + e = interlaces + d = CREDENTIALS (length 11) mar + c = cram + h = march + s = charms + o = chromas + n = monarchs + i = harmonics + a = maraschino + n = ANACHRONISM (length 11) ----------------------------------------------------------- > addWordToMap :: String -> WordMap -> WordMap > addWordToMap word m = > case lookupFM m key of > Just wlist -> addToFM m key (word:wlist) > Nothing -> addToFM m key [word] > where key = sort word > addWord :: String -> WordMaps -> WordMaps > addWord word maps = addToFM maps key newmap > where key = length word > newmap = addWordToMap word oldmap > oldmap = case (lookupFM maps key) of > Just m -> m > Nothing -> emptyFM > populateMaps :: WordMaps -> IO WordMaps > populateMaps maps = do > eof <- isEOF > if eof then return maps else do > word <- getLine > if (length word) > 0 -- test for blank lines > then populateMaps (addWord word maps) > else populateMaps maps ----------------------------------------------------------- > getMap :: WordMaps -> Int -> WordMap > getMap maps key = case (lookupFM maps key) of > Nothing -> emptyFM > Just m -> m > showWordList :: [String] -> String > showWordList = concat . intersperse ", " > printTrail :: WordMaps -> [String] -> String > printTrail _ [] = "" > printTrail maps (w:ws) = (showWordList elts) ++ "\n" ++ (printTrail maps ws) > where m = getMap maps (length w) > elts = lookupWithDefaultFM m [""] w > removeEachChar :: String -> [String] > removeEachChar word = removeEachChar' word (length word) [] > removeEachChar' :: String -> Int -> [String] -> [String] > removeEachChar' [] _ list = list > removeEachChar' _ 0 list = list > removeEachChar' word n list = removeEachChar' word (n-1) (newword:list) > where newword = (take (n-1) word) ++ (drop n word) > unfussyHead :: [[String]] -> [String] > unfussyHead [] = [] > unfussyHead l = head l Given a word (and a trail so far) this will return either an empty trail, or a trail to the first 3-char word that completes the search. A trail is just the list of keys, shortest first. > searchWord :: WordMaps -> [String] -> String -> [String] > searchWord maps trail word > | length word <= 3 = word:trail > | otherwise = > case lookupFM m word of > Nothing -> [] > Just _ -> unfussyHead $ filter ([] /=) $ map cont (removeEachChar word) > where cont = searchWord maps (word:trail) > m = getMap maps (length word) For each word (key) in a level, call searchWord. The first to return a non-empty list is the winner. If the list for this level is empty, then recurse with the next level down. > searchLevel :: WordMaps -> Int -> [String] > searchLevel _ 3 = [] > searchLevel maps level = > case (lookupFM maps level) of > Nothing -> [] > Just m -> let result = filter ([] /= ) $ map (searchWord maps []) (keysFM m) in > if result == [] > then searchLevel maps (level-1) > else head result Kick off search at top-level. > start :: WordMaps -> [String] > start maps = searchLevel maps (last (keysFM maps)) Look for a specific trail. For testing/debugging. > findw :: WordMaps -> [String] > findw maps = searchWord maps [] (sort "entrails") findw maps = searchWord maps [] (sort "nails") findw maps = searchWord maps [] (sort "salient") findw maps = searchWord maps [] (sort "entrails") findw maps = searchWord maps [] (sort "clarinets") > readWords :: IO String > readWords = do > wordMaps <- populateMaps emptyFM > return (printTrail wordMaps (findw wordMaps)) > -- This is how we'd normally start: > --return (printTrail wordMaps (start wordMaps)) > main :: IO () > main = do > s <- readWords > putStrLn s > return () ***************************************************************** The information in this email and in any attachments is confidential and intended solely for the attention and use of the named addressee(s). This information may be subject to legal professional or other privilege or may otherwise be protected by work product immunity or other legal rules. It must not be disclosed to any person without our authority. If you are not the intended recipient, or a person responsible for delivering it to the intended recipient, you are not authorised to and must not disclose, copy, distribute, or retain this message or any part of it. *****************************************************************

1 0

RE: swap leak problem
by Simon Marlow 01 Oct '03

01 Oct '03

> Oh yes, one more datum. If I run hs_perform_gc before each and every > mallocForeignPtrBytes and reallocBytes, the leak goes much > more slowly, and > the code gets much further in the job before getting killed. > But it still > leaks, and still gets killed. It could potentially be a memory leak in the RTS. There are two ways to proceed: if you have a GHC build around, you can compile up a debugging RTS and run with sanity checking enabled (+RTS -DS), which will check for memory leaks. If there are any memory leaks in the RTS, this will throw an assertion failure immediately. Alternatively, you can package up your code and send it to us with instructions on how to reproduce. Cheers, Simon

2 1

swap leak problem
by David Roundy 30 Sep '03

30 Sep '03

Hello. I've got a memory problem that is stumping me, and could use advice in trying to fix it. In brief, the heap of my application keeps increasing with time, until after a few hours it uses up all my swap and gets killed. There is no indication of a true memory leak. Heap profiling indicates that the haskell memory usage (including stacks, via -xt) remains below its initial peak value. Similarly, I've attached a sort of debugging counting finalizer to my foreignPtrs (a static int in C land), and it's clear that all the foreignPtrs I allocate are getting freed. Most of them are allocated with mallocForeignPtrBytes anyways, which should be about as safe an allocation method as one could use. The allocation pattern of my code is as follows. It reads a gzipped patch file into memory, parses it, then reads in a bunch of other files, and writes modified versions of them. Then it reads in the next patch and repeats. So it does large amounts of allocation and deallocation on a periodic basis. About half of the memory used is stored in foreignPtrs. With the exception of the patch files (which I'll get to later), all foreignPtrs are generated by mallocForeignPtrBytes or mallocForeignPtrArray. The patch files are gzip compressed, so I don't know their size until I've read them. I read the patch file one chunk at a time, and use reallocBytes to allocate a bit more memory each time. I don't expect in general to be calling reallocBytes more than four times per patch file. Of course, once I'm done I convert to a foreignPtr via newForeignPtr finalizerFree. My only idea as to the source of the problem is that it could be either a result of memory fragmentation or of not cleaning up before allocating. Neither theory is particularly convincing. Unfortunately, I'm at a loss as to how to track this problem down, so any advise would be appreciated. -- David Roundy http://www.abridgegame.org/darcs

1 1

RE: Database interface - would like advice on oracle library bind ing
by Bayley, Alistair 29 Sep '03

29 Sep '03

Yes, I know of it. Krasimir's code uses similar functions and types in the three bindings (MySQL, ODBC, PostgreSql), but the bindings do not share a common interface (AFAICT). Because they are so similar, making them support a common interface shouldn't be a lot of work. I was hoping the earlier discussions on database interfaces would converge to a solution most interested parties agreed on. I'm still sold on the left-fold interface discussed previously. Oleg claims it is sufficient, as it can be automatically converted to a stream-like interface. I bit of me agrees with you that I should be consistent with previous work, and another bit says make it simple and elegant, and this leads me towards Oleg's proposals (left-fold + auto-generated value extraction functions + auto-generated stream functions). Do others on this list (and elsewhere) have any further opinions as to how a database interface ought to look? > -----Original Message----- > From: Tim Docker [mailto:timd@macquarie.com.au] > Sent: 29 September 2003 13:43 > To: Bayley, Alistair; haskell-cafe(a)haskell.org > Subject: RE: Database interface - would like advice on oracle library > bind ing > > > > Alistair Bayley wrote: > > > Still making slow progress on an Oracle database binding... > > now I'm trying to fit the API I have into some sort of > > abstract interface (like the one(s) discussed previously: > > > Since the previous dicussion I've discovered Krasimir > Angelov's HSQL interface as part of his HTOOLKIT: > > https://sourceforge.net/project/showfiles.php?group_id=65248 > > This has a uniform abstract interface similar to the one > discussed, apparently implemented for MYSQL, ODBC, and > PostgreSQL. I've only played with the MYSQL variant. > > If possible, it would seem sensible to provide a consistent > interface for your Oracle binding. If not, it may be worth > persuading him to generalise the interface. > > Then again, perhaps you knew about this already. > > Tim ***************************************************************** The information in this email and in any attachments is confidential and intended solely for the attention and use of the named addressee(s). This information may be subject to legal professional or other privilege or may otherwise be protected by work product immunity or other legal rules. It must not be disclosed to any person without our authority. If you are not the intended recipient, or a person responsible for delivering it to the intended recipient, you are not authorised to and must not disclose, copy, distribute, or retain this message or any part of it. *****************************************************************

1 0

RE: Database interface - would like advice on oracle library bind ing
by Tim Docker 29 Sep '03

29 Sep '03

Alistair Bayley wrote: > Still making slow progress on an Oracle database binding... > now I'm trying to fit the API I have into some sort of > abstract interface (like the one(s) discussed previously: Since the previous dicussion I've discovered Krasimir Angelov's HSQL interface as part of his HTOOLKIT: https://sourceforge.net/project/showfiles.php?group_id=65248 This has a uniform abstract interface similar to the one discussed, apparently implemented for MYSQL, ODBC, and PostgreSQL. I've only played with the MYSQL variant. If possible, it would seem sensible to provide a consistent interface for your Oracle binding. If not, it may be worth persuading him to generalise the interface. Then again, perhaps you knew about this already. Tim

1 0

RFC: "Haskell for Perl Programmers" Presentation
by Shlomi Fish 29 Sep '03

29 Sep '03

At our local Perl Mongers club we have decided to hold a series of introductions to foreign language. Being a big fan of Haskell (except for any practical use), I wrote a "Haskell for Perl Programmers" intro: http://vipe.technion.ac.il/~shlomif/lecture/Perl/Haskell/slides/ It's more or less complete, but there may still be things to add or remove. Note that until now I did not write too much about the typing facilities of Haskell. I could, though. Regards, Shlomi Fish ---------------------------------------------------------------------- Shlomi Fish shlomif(a)vipe.technion.ac.il Home Page: http://t2.technion.ac.il/~shlomif/ An apple a day will keep a doctor away. Two apples a day will keep two doctors away. Falk Fish

1 0

RE: haddock depencies to std-modules
by Simon Marlow 29 Sep '03

29 Sep '03

> I use haddock to create documentation. Everything is fine > except of the > references to standard modules. If I am using standardtypes > like Int or > String haddock wants to create crossrefs to these modules and > fails because > of missing "sourcecode". > > Is there a simple way to fix this? I've heard of interface > files to create > right refs to existing docs, but that doesnt work. Whats the > right way? One way is to use the Haddock interface files that are distributed with GHC. I haven't put any effort into making the process easy yet - ideally Haddock should consult GHC's package database to find the interface files, but it doesn't currently do this. You'll find Haddock interface files in the same location as the documentation when you install GHC (eg. /usr/share/ghc-<version>/html/base/base.haddock on a Linux system). Cheers, Simon

1 0