- Haskell-Cafe - Haskell.org

Non-blocking keyboard peek
by Adrian May 02 Oct '03

02 Oct '03

Hi folks, I have simulator which should grind away all night but check the keyboard once per iteration to see if I'm trying to view the results, change parameters or terminate it. Therefore I need a non-blocking keyboard peek function. So far, my searching only lead to some stuff about using threads in GHC but that seems far too complicated and messy. I have no reason to open a new thread and would still have to fight over some resource lock at the very position in the program where I would normally have just peeked at the keyboard and maybe called the menu procedure. I don't think such a peek function would affect referential transparency or be considered gauche for any other reason. Does it really not exist? Can I write it for a reasonable amount of effort? Thanks in advance, AM PS. This is the second of these mails I sent 'cos the first one just didnt show up on the list. ______________________________________________________________________________ Zwei Mal Platz 1 mit dem jeweils besten Testergebnis! WEB.DE FreeMail und WEB.DE Club bei Stiftung Warentest! http://f.web.de/?mc=021183

2 1

RE: Haskell-beginners problem with memory consuption
by Simon Marlow 02 Oct '03

02 Oct '03

> Keep in mind that Strings are lists of characters. I think (somebody > correct me if I'm wrong) GHC will store a character inside a cons > cell, but that still leaves 8 bytes per character. Worst case it will > store the 8-byte cons cell pointing to a 32-bit char value, 12 bytes > per character. (Strings as lists-of-char is very useful, but not > terribly efficient). Worst case: 16 bytes per character, usual case (all characters <= '\xff'): 8 bytes per character, because we have static copies of characters 0-255 in the RTS. Using Data.PackedString or UArray Char: 4 bytes per character. Cheers, Simon

1 0

RE: Lazy IO is useful! [Was: "interact" behaves oddly...]
by Simon Marlow 02 Oct '03

02 Oct '03

> main = > do let mylist = [1..10000] > writeFile "myfile.txt" (unlines (map show mylist)) This part does run in O(1) space and isn't problematic. > -- ... > mylist' <- (map read . lines) `fmap` readFile "myfile.txt" > let result = sum mylist' > print result Indeed, this works by interleaving the I/O and the computation of the result. It is a convenient way to program, because you can use ordinary list operations on the I/O stream. We know it is not "safe": a programmer can observe the fact that implicit I/O is going on. It is also not a good way to program: you have no way to catch errors and take appropriate action if the implicit I/O should fail in some way. Should we really be encouraging the writing of programs that have no error checking? > With lazy IO, this program too should run in constant space, and the > functions that consume the large intermediate structure can remain > unchanged! > > So, I think a lazy programming language should support not only lazy > evaluation, but also lazy IO! When it is appropriate to abstract away > from the details of when IO happens, lazy IO is useful. It can > facilitate separation of concerns and modularity, just like lazy > evaluation. Appropriate lazy IO should not compromise the > purity of the language or be an obstacle to optimistic evaluation. I look forward to seeing a form of lazy I/O that doesn't suffer from these problems! (although I suspect I still won't use it :-p) Cheers, Simon

1 0

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