Re: [Haskell-cafe] How on Earth Do You Reason about Space?
From: "Edward Z. Yang" <ezyang@MIT.EDU>
Hello Aleksandar,
It is possible that the iteratees library is space leaking; I recall some recent discussion to this effect. Your example seems simple enough that you might recompile with a version of iteratees that has -auto-all enabled. Unfortunately, it's not really a safe bet to assume your libraries are leak free, and if you've pinpointed it down to a single line, and there doesn't seem a way to squash the leak, I'd bet it's the library's fault.
Edward
I can't reproduce the space leak here. I tried Aleksander's original code, my iteratee version, the Ngrams version posted by Johan Tibell, and a lazy bytestring version. my iteratee version (only f' has changed from Aleksander's code): f' :: Monad m => I.Iteratee S.ByteString m Wordcounts f' = I.joinI $ (enumLinesBS I.><> I.filter (not . S.null)) $ I.foldl' (\t s -> T.insertWith (+) s 1 t) T.empty my lazy bytestring version
import Data.Iteratee.Char import Data.List (foldl')import Data.Char (toLower)
import Data.Ord (comparing) import Data.List (sortBy) import System.Environment (getArgs) import qualified Data.ByteString.Lazy.Char8 as L import qualified Data.HashMap.Strict as T
f'2 = foldl' (\t s -> T.insertWith (+) s 1 t) T.empty . filter (not . L.null) . L.lines
main2 :: IO () main2 = getArgs >>= L.readFile .head >>= print . T.keys . f'2
None of these leak space for me (all compiled with ghc-7.0.3 -O2). Performance was pretty comparable for every version, although Aleksander's original did seem to have a very small edge. As someone already pointed out, keep in mind that this will use a lot of memory anyway, unless there's a lot of repetition of words. I'd be happy to help track down a space leak in iteratee, but for now I'm not seeing one. Best, John Lato
On Tue, May 31, 2011 at 11:30:06PM +0100, John Lato wrote:
I can't reproduce the space leak here. I tried Aleksander's original code, my iteratee version, the Ngrams version posted by Johan Tibell, and a lazy bytestring version.
I unfortunately can't post the actual corpus here, because it's copyrighted. But there's plenty of ways to retrieve large amounts of data from the Internet. See below.
f' :: Monad m => I.Iteratee S.ByteString m Wordcounts f' = I.joinI $ (enumLinesBS I.><> I.filter (not . S.null)) $ I.foldl' (\t s -> T.insertWith (+) s 1 t) T.empty
Neat, folding the specialised function into the enumeratee is nifty! One can tell that my experience with iteratee/enumerator has been only a day's worth for now :-\
None of these leak space for me (all compiled with ghc-7.0.3 -O2). Performance was pretty comparable for every version, although Aleksander's original did seem to have a very small edge.
How big were your input corpora? Here's an absolutely evil shell script that is going to make me donate money to project Gutenberg. It will gather a corpus that is still very small, but at least realistic in its distributional properties. +++ scrape.sh #!/bin/sh textfile=all_text.txt touch $textfile text=0 size=0 for i in `seq 10 300`; do wget -q "http://www.gutenberg.org/files/$i/$i.zip" if [ -f $i.zip ]; then unzip -qq $i.zip tr -sc '[[:alpha:]]' '\n' < $i.txt >> $textfile text=`dc -e "$text 1 + p"` size=`du -h $textfile | cut -f 1` rm -f $i.zip $i.txt fi echo -n "\rFound $text of $i texts, total $size." done echo "\rFound $text texts, total $size" +++ It'll take a while to run, and the resulting corpus is just a fraction of what I'm using, but it serves well to illustrate the problem. If you want, you can increase the amount of data gathered by simply tweaking the numerical range in the seq statement. (If you make it gobble up more bandwidth, it might be polite to put a sleep somewhere in the inner loop. I'd host the resulting file myself, but I don't know if there aren't any conditions on that.) If you did not tweak the script, it should've gathered some 100MB of data. Running my unmodified original program, htop records 320MB of RAM usage towards the end (*without* profiling being enabled.) So it seems that I can't get rid of a factor of around 3x the input file size. Luckily, the dependency seems to be linear. Here's some profiling: <<ghc: 30478883712 bytes, 57638 GCs, 41925397/143688744 avg/max bytes residency (189 samples), 322M in use, 0.00 INIT (0.00 elapsed), 23.73 MUT (24.94 elapsed), 26.71 GC (27.10 elapsed) :ghc>> ../src/cafe/tools/iterTable 106M_text.txt +RTS -tstderr 50.44s user 1.50s system 99% cpu 52.064 total ghc itself reports 38MB avg (can live with that,) and 140MB max (too much.) Redirecting the program's output to a file will yield a mere 2.2M for the data gathered by the above script. Since those 2.2M of data are all I care about, why do I need so much more RAM to compute them? Are my demands unreasonable?
I'd be happy to help track down a space leak in iteratee, but for now I'm not seeing one.
Thank you for your offer! Maybe I'm just seeing ghosts, and there is no space leak. But I really do think that the program is eating too much RAM. Regards, Aleks
On Wed, Jun 1, 2011 at 12:55 AM, Aleksandar Dimitrov < aleks.dimitrov@googlemail.com> wrote:
On Tue, May 31, 2011 at 11:30:06PM +0100, John Lato wrote:
None of these leak space for me (all compiled with ghc-7.0.3 -O2). Performance was pretty comparable for every version, although Aleksander's original did seem to have a very small edge.
How big were your input corpora?
Today I was using multiple copies of War & Peace, as Brandon specified. Total size is about 90M.
So it seems that I can't get rid of a factor of around 3x the input file size. Luckily, the dependency seems to be linear. Here's some profiling:
<<ghc: 30478883712 bytes, 57638 GCs, 41925397/143688744 avg/max bytes residency (189 samples), 322M in use, 0.00 INIT (0.00 elapsed), 23.73 MUT (24.94 elapsed), 26.71 GC (27.10 elapsed) :ghc>> ../src/cafe/tools/iterTable 106M_text.txt +RTS -tstderr 50.44s user 1.50s system 99% cpu 52.064 total
ghc itself reports 38MB avg (can live with that,) and 140MB max (too much.)
Redirecting the program's output to a file will yield a mere 2.2M for the data gathered by the above script. Since those 2.2M of data are all I care about, why do I need so much more RAM to compute them?
Are my demands unreasonable?
I think the issue is data sharing, as Brandon mentioned. A bytestring consists of an offset, length, and a pointer. You're using a chunk size of 64k, which means the generated bytestrings all have a pointer to that 64k of data. Suppose there's one new word in that 64k, and it's near the beginning of the chunk. Even though the word may only be a few characters long, it'll reference the entire chunk and keep it from being GC'd. There are a few solutions to this. The first is to make a copy of the bytestring so only the required data is retained. In my experiments this wasn't helpful, but it would depend on your corpus. The second is to start with smaller chunks. Using a chunk size of 1024 worked fairly well for me. If your corpus is similar to natural language, I think it'll probably work better for you as well. Note that Johan's Ngram code also only keeps the minimum required data, giving it a good memory profile. I didn't notice this last night because I was testing with different data, and unfortunately the peculiar distribution of that data masked this problem. John L
On Wednesday 01 June 2011 12:28:28, John Lato wrote:
There are a few solutions to this. The first is to make a copy of the bytestring so only the required data is retained. In my experiments this wasn't helpful, but it would depend on your corpus. The second is to start with smaller chunks.
The third, check whether the word is already known, and *make a copy if not*. That should only keep the required parts (including the currently processed chunk) in memory.
That sounds like a plausible reason why naive copying explodes space. Something like string interning would be good here... and since you're hashing already... Edward Excerpts from Daniel Fischer's message of Wed Jun 01 06:46:24 -0400 2011:
On Wednesday 01 June 2011 12:28:28, John Lato wrote:
There are a few solutions to this. The first is to make a copy of the bytestring so only the required data is retained. In my experiments this wasn't helpful, but it would depend on your corpus. The second is to start with smaller chunks.
The third, check whether the word is already known, and *make a copy if not*. That should only keep the required parts (including the currently processed chunk) in memory.
Hi John,
I think the issue is data sharing, as Brandon mentioned. A bytestring consists of an offset, length, and a pointer. You're using a chunk size of 64k, which means the generated bytestrings all have a pointer to that 64k of data. Suppose there's one new word in that 64k, and it's near the beginning of the chunk. Even though the word may only be a few characters long, it'll reference the entire chunk and keep it from being GC'd.
This seems to be the issue indeed! If the bytestrings on the hash map are holding references to the chunks, it is clear that we're going to consume memory scaling with the size of the input file, in case there are *any* new chunks generated. As I understand it, this what not a problem with the multiple copies of War and Peace, because all byte strings were already found on the hash table! On reading new input, old entries were found on the hash table, so only old chunks were kept in memory, the new ones could be gc'ed. In *realistic* data, however, the Long Tail is the reason that, after a while, some chunks of input would only be kept because there were a few byte strings referencing them. New words are rare, but they need not occur more frequently than once per chunk, in order to keep the whole chunk in memory, even though the chunk was mostly useless (most other data in this chunk would already be on the hash map.)
There are a few solutions to this. The first is to make a copy of the bytestring so only the required data is retained. In my experiments this wasn't helpful, but it would depend on your corpus. The second is to start with smaller chunks. Using a chunk size of 1024 worked fairly well for me. If your corpus is similar to natural language, I think it'll probably work better for you as well.
I think I solved this problem elegantly: I used Data.Text as hash map keys, instead of Data.ByteString. See the modified program below:
import qualified Data.Iteratee as I import Data.Iteratee.Char import Data.Iteratee.IO
import qualified Data.HashMap.Strict as T
import Data.Ord (comparing) import Data.List (sortBy) import System.Environment (getArgs)
import qualified Data.ByteString as S import qualified Data.Text as X import Data.Text.Encoding (decodeUtf8)
type Wordcounts = T.HashMap X.Text Int
f' :: Monad m => I.Iteratee S.ByteString m Wordcounts f' = I.joinI $ (enumLinesBS I.><> I.filter (not.S.null)) $ I.foldl' (\t s -> T.insertWith (+) (convert s) 1 t) T.empty where convert = decodeUtf8
main :: IO () main = getArgs >>= fileDriverVBuf 65536 f'.head >>= mapM_ (\(w,c)-> putStrLn $ X.unpack w ++ "\t" ++ show c).sortM where sortM = sortBy (comparing snd) . T.toList
Initial benchmarks on the realistic 100MB Gutenberg corpus I downloaded with my script yesterday report the following: htop says 120M memory residency towards the end of the life-cycle. <<ghc: 40928992256 bytes, 77984 GCs, 20939886/46665600 avg/max bytes residency (455 samples), 133M in use, 0.00 INIT (0.00 elapsed), 26.01 MUT (26.20 elapsed), 32.96 GC (33.09 elapsed) :ghc>> 19MB avg, 44MB max residency, 133M in use (which is similar to what htop told me) and the heap profile clearly shows allocation and deallocation of the bytestrings: http://imgur.com/U1nyw (I'm attributing the ruggedness of the profile with the frequent little spikes to the iteratee chunk allocation and deallocation.) It seems I can't get rid of 50% of the heap being lag state. I don't quite understand yet what that is. I also don't know what INHERENT_USE is. But in any case, I now have a program that I can reasonably expect to run if I could fit the input file into memory. I might try to implement an analogous program in C++ or Java, just to see whether that would do better or similarly in terms of memory consumption.
Note that Johan's Ngram code also only keeps the minimum required data, giving it a good memory profile. I didn't notice this last night because I was testing with different data, and unfortunately the peculiar distribution of that data masked this problem.
This is kind of the big problem here: whether or not you'll see the particular behaviour I was so upset about seemed to depend on the corpus' distributional properties. In any case, I would like to thank you all for helping me understand and address the issue. I probably still have a long way to go in terms of understanding space-behaviour of Haskell programs, but at least I don't see ByteStrings as this black box of efficiency anymore, but actually understand how they're structured, and what they're good at, and what they aren't good at. (take home lesson: Data.Text is really nice. Also: if iteratee has a space leak, I probably didn't hit it, really. But: if reading byte-strings, one should mind the pointers that byte-strings actually are.) Regards, Aleks
Just out of interest, did you try reading the input as plain old Strings? They may be unfashionable these days, and have their own type of badness in space and time performance, but might perhaps be a win over ByteStrings for extremely large datasets. Regards, Malcolm On 01 Jun, 2011,at 02:49 PM, Aleksandar Dimitrov <aleks.dimitrov@googlemail.com> wrote: Hi John,
I think the issue is data sharing, as Brandon mentioned. A bytestring consists of an offset, length, and a pointer. You're using a chunk size of 64k, which means the generated bytestrings all have a pointer to that 64k of data. Suppose there's one new word in that 64k, and it's near the beginning of the chunk. Even though the word may only be a few characters long, it'll reference the entire chunk and keep it from being GC'd.
This seems to be the issue indeed! If the bytestrings on the hash map are holding references to the chunks, it is clear that we're going to consume memory scaling with the size of the input file, in case there are *any* new chunks generated. As I understand it, this what not a problem with the multiple copies of War and Peace, because all byte strings were already found on the hash table! On reading new input, old entries were found on the hash table, so only old chunks were kept in memory, the new ones could be gc'ed. In *realistic* data, however, the Long Tail is the reason that, after a while, some chunks of input would only be kept because there were a few byte strings referencing them. New words are rare, but they need not occur more frequently than once per chunk, in order to keep the whole chunk in memory, even though the chunk was mostly useless (most other data in this chunk would already be on the hash map.)
There are a few solutions to this. The first is to make a copy of the bytestring so only the required data is retained. In my experiments this wasn't helpful, but it would depend on your corpus. The second is to start with smaller chunks. Using a chunk size of 1024 worked fairly well for me. If your corpus is similar to natural language, I think it'll probably work better for you as well.
I think I solved this problem elegantly: I used Data.Text as hash map keys, instead of Data.ByteString. See the modified program below:
import qualified Data.Iteratee as I import Data.IterateeChar import Data.Iteratee.IO
import qualified Data.HashMap.Strict as T
import Data.Ord (comparing) import Data.List (sortBy) import System.Environment (getArgs)
import qualified DataByteString as S import qualified Data.Text as X import Data.Text.Encoding (decodeUtf8)
type Wordcounts = T.HashMap X.Text Int
f' :: Monad m => I.Iteratee S.ByteString m Wordcounts f' = I.joinI $ (enumLinesBS I.><> I.filter (not.S.null)) $ I.foldl' (\t s -> T.insertWith (+) (convert s) 1 t) T.empty where convert = decodeUtf8
main :: IO () main = getArgs >>= fileDriverVBuf 65536 f'.head
= mapM_ (\(w,c)-> putStrLn $ X.unpack w ++ "\t" ++ show c)sortM where sortM = sortBy (comparing snd) . T.toList
Initial benchmarks on the realistic 100MB Gutenberg corpus I downloaded with my script yesterday report the following: htop says 120M memory residency towards the end of the life-cycle. <<ghc: 40928992256 bytes, 77984 GCs, 20939886/46665600 avg/max bytes residency (455 samples), 133M in use, 0.00 INIT (0.00 elapsed), 26.01 MUT (26.20 elapsed), 32.96 GC (33.09 elapsed) :ghc>> 19MB avg, 44MB max residency, 133M in use (which is similar to what htop told me) and the heap profile clearly shows allocation and deallocation of the bytestrings: http://imgur.com/U1nyw (I'm attributing the ruggedness of the profile with the frequent little spikes to the iteratee chunk allocation and deallocation.) It seems I can't get rid of 50% of the heap being lag state. I don't quite understand yet what that is. I also don't know what INHERENT_USE is. But in any case, I now have a program that I can reasonably expect to run if I could fit the input file into memory. I might try to implement an analogous program in C++ or Java, just to see whether that would do better or similarly in terms of memory consumption.
Note that Johan's Ngram code also only keeps the minimum required data, giving it a good memory profile. I didn't notice this last night because I was testing with different data, and unfortunately the peculiar distribution of that data masked this problem.
This is kind of the big problem here: whether or not you'll see the particular behaviour I was so upset about seemed to depend on the corpus' distributional properties. In any case, I would like to thank you all for helping me understand and address the issue. I probably still have a long way to go in terms of understanding space-behaviour of Haskell programs, but at least I don't see ByteStrings as this black box of efficiency anymore, but actually understand how they're structured, and what they're good at, and what they aren't good at. (take home lesson: Data.Text is really nice. Also: if iteratee has a space leak, I probably didn't hit it, really. But: if reading byte-strings, one should mind the pointers that byte-strings actually are.) Regards, Aleks _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (5)
-
Aleksandar Dimitrov -
Daniel Fischer -
Edward Z. Yang -
John Lato -
malcolm.wallace