- Haskell-Cafe - Haskell.org

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

haddock depencies to std-modules
by Patrick Scheibe 29 Sep '03

29 Sep '03

hello 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? Cheers Patrick

1 0

(Off-topic) Question about categories
by Peter J. Veger 28 Sep '03

28 Sep '03

> I'm not sure if anyone mentioned the examples of a poset and a monoid as categories. > There is no "internal" structure in these. In the former, the objects are the > elements and there is a morphism between a and b iff a <= b. A functor then becomes > an order preserving map. In the latter, there is one object and the morphisms are > the elements. The identity is the identity map and if x and y are two elements / > morphisms then composition is xy. A functor is then a homomorphism. > Dominic. It is probably better to use the example of a preordered set. A Preordered set is a set with a relation <=, that is reflexive (x<=x) and transtive (x<=y & y<=z --> x<=z) (but not necessarily antisymmetric, x<=y & y<=x --> x=y as for a poset). If, in a preordered set, a is the unique morphism: x -> y and b the unique morphism: y -> x, then (writing x for the identity morphism id(x)) a.b=y and b.a=x Categorically, x and y are isomorphic. Concluding that x=y is not in the categorical language. Of course, you should distinguish the category of preorders (posets, monoids) from preorder (poset, monoid) as a category. As for literature, you have the classic: Saunders Mac Lane: Categories for the Working mathematician but the working computer scientist may prefer: Andrea Asperti and Guiseppe Longo: Categories, Types, and Structures (MIT Press, 1991) Michael Barr and Charles Wells: Category Theory for Computing Science (3rd ed., Les Publication CRM, 1999) idem, Introduction to Category Theory (www.let.uu.nl/esslli/Courses/barr-wells.html) Peter J. Veger, Best, Netherlands

1 0

(Off-topic) Question about categories
by Dominic Steinitz 27 Sep '03

27 Sep '03

Graham, I'm not sure if anyone mentioned the examples of a poset and a monoid as categories. There is no "internal" structure in these. In the former, the objects are the elements and there is a morphism between a and b iff a <= b. A functor then becomes an order preserving map. In the latter, there is one object and the morphisms are the elements. The identity is the identity map and if x and y are two elements / morphisms then composition is xy. A functor is then a homomorphism. Dominic.

1 0