Hi -- I'm loading a big file (~2G), again, with 72-byte C structs. I've done pretty well [thanks to everyone] interpreting the fields, but I'm finding the traversal of the file to be pretty inefficient. I do the following: breakUp s | L.null s = [] | otherwise = h:(breakUp r) where (h,r) = L.splitAt 72 s Running this on the 2G file blows up the stack pretty quickly, taking the first 1 million records (there are 20M of them) with a big stack parameter gives about 25% productivity, with GC taking the other 75%. My understanding is that while this looks tail recursive, it isn't really because of laziness. I've tried throwing seq operators around, but they don't seem to do much to help the efficiency. Any help's appreciated. Ranjan
Hello,
breakUp s | L.null s = [] | otherwise = h:(breakUp r) where (h,r) = L.splitAt 72 s
Running this on the 2G file blows up the stack pretty quickly, taking the first 1 million records (there are 20M of them) with a big stack parameter gives about 25% productivity, with GC taking the other 75%.
My understanding is that while this looks tail recursive, it isn't really because of laziness. I've tried throwing seq operators around, but they don't seem to do much to help the efficiency.
The function is not tail-recursive as written (you're returning h:breakUp r) but that shouldn't be a problem because of lazy evaluation. Can you give more context, particularly what happens to the result of breakUp? -Jeff
On Fri, Dec 29, 2006 at 04:56:34PM -0800, Ranjan Bagchi wrote:
I'm loading a big file (~2G), again, with 72-byte C structs. I've done pretty well [thanks to everyone] interpreting the fields, but I'm finding the traversal of the file to be pretty inefficient.
breakUp s | L.null s = [] | otherwise = h:(breakUp r) where (h,r) = L.splitAt 72 s
My understanding is that while this looks tail recursive, it isn't really because of laziness. I've tried throwing seq operators around, but they don't seem to do much to help the efficiency.
That looks like the correct lazy way to do it; by itself that breakUp should be virtually instantaneous and consume neglible stack because of laziness. What kind of list consumer are you using? (ie don't use foldl, use foldl' or foldr, foldl is very prone to high stack use.) Also, your breakUp is an unfold: \begin{code} import Data.List(unfoldr) breakUp = unfoldr takeChunk where takeChunk s | L.null s = Nothing | otherwise = Just $ L.splitAt 72 s \end{code}
breakUp s | L.null s = [] | otherwise = h:(breakUp r) where (h,r) = L.splitAt 72 s
Running this on the 2G file blows up the stack pretty quickly, taking the first 1 million records (there are 20M of them) with a big stack parameter gives about 25% productivity, with GC taking the other 75%.
My understanding is that while this looks tail recursive, it isn't really because of laziness. I've tried throwing seq operators around, but they don't seem to do much to help the efficiency.
This function by itself doesn't really have any particular behaviour with respect to stack and heap usage, since it is just a linear mapping from one lazy sequence to another. To understand the stack blowout, you'll need to look at what you are doing with the result of this function. For example, a foldl over the result might be building a big thunk on the heap, which could blow the stack when evaluated*. If this is the case, you might avoid building the big thunk by using foldl', a version of foldl which evaluates as it folds. Invoking GHC with optimisation might also help, since the strictness evaluator can often do the equivalent of converting foldl to foldl' at the appropriate places. Have you looked at the Performance pages on the Wiki, in particular, the Strictness and Laziness pages? http://www.haskell.org/haskellwiki/Performance In my (limited) Haskell experience, I was continually being surprised by inexplicable stack blowouts until I spent a little time doing some focussed experiments, mainly involving folds over large lists. If you haven't done that, I would recommend it. * - Note that foldl is tail recursive, so clearly tail recursion doesn't necessarily result in a well-behaved loop in a lazy implementation!
On 30/12/2006, at 1:32 PM, Matthew Brecknell wrote:
In my (limited) Haskell experience, I was continually being surprised by inexplicable stack blowouts until I spent a little time doing some focussed experiments, mainly involving folds over large lists. If you haven't done that, I would recommend it.
I think this is very good advice. Bernie.
On Dec 29, 2006, at 6:32 PM, Matthew Brecknell wrote:
breakUp s | L.null s = [] | otherwise = h:(breakUp r) where (h,r) = L.splitAt 72 s
Running this on the 2G file blows up the stack pretty quickly, taking the first 1 million records (there are 20M of them) with a big stack parameter gives about 25% productivity, with GC taking the other 75%.
My understanding is that while this looks tail recursive, it isn't really because of laziness. I've tried throwing seq operators around, but they don't seem to do much to help the efficiency.
This function by itself doesn't really have any particular behaviour with respect to stack and heap usage, since it is just a linear mapping from one lazy sequence to another. To understand the stack blowout, you'll need to look at what you are doing with the result of this function.
For example, a foldl over the result might be building a big thunk on the heap, which could blow the stack when evaluated*. If this is the case, you might avoid building the big thunk by using foldl', a version of foldl which evaluates as it folds.
I guess the consumer's really important (Didn't even occur to me, I was concentrating on how I was generating the list). I was trying to de-lazy the list, I did the following: bs = [...] recs' = (take 1000000) breakUp bs recs = foldr seq recs' recs' print $ length recs Would the fold be blowing the stack? Ranjan
On 30/12/06, Ranjan Bagchi
I guess the consumer's really important (Didn't even occur to me, I was concentrating on how I was generating the list). I was trying to de-lazy the list, I did the following:
bs = [...] recs' = (take 1000000) breakUp bs recs = foldr seq recs' recs' print $ length recs
Would the fold be blowing the stack?
Ranjan
Is there a really good reason to de-lazy the list? That's usually a bad idea if the list is long. If your application can do any kind of stream processing at all, then it's a better idea to allow it to work with the list lazily. If it can't, and you're basically producing some kind of summary of the input data, you're probably better off using a strict left fold and consuming the list in a strict fashion, but not forcing it earlier than actually needed. By strictifying the list, you're making it impossible to work with the first cons without computing the last one. That means that the following consumption of the list by length can't even start until it's finished building the whole thing in memory (you're wasting both time and space). Holding a large list like that in memory all at once has few benefits. If you're currently doing lazy IO and are concerned about the file changing as you're processing it, you're better off copying the whole file into memory as one big block and still building the list lazily from that copy in memory. If you're coming from any sort of imperative background, you can basically think of a list as a loop which has not yet happened. If you can generate the indices for the loop on the fly, you're probably not going to want to waste time putting them all in memory beforehand, regardless of what that loop is doing (how the list is being consumed). There are a few cases where strictifying production of data is good, but it's far more common to want strict consumption and lazy production. - Cale
participants (6)
-
Bernie Pope -
Cale Gibbard -
jeff p -
Matthew Brecknell -
Ranjan Bagchi -
Stefan O'Rear