<html><body><div>Just out of interest, did you try reading the input as plain old Strings? &nbsp;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.</div><div><pre style="font-family: Helvetica,Arial,sans-serif; font-size: 13px" _mce_style="font-family: Helvetica,Arial,sans-serif; font-size: 13px;">Regards,
    Malcolm</pre></div><div><br>On 01 Jun, 2011,at 02:49 PM, Aleksandar Dimitrov &lt;aleks.dimitrov@googlemail.com&gt; wrote:<br><br></div><div><blockquote type="cite"><div class="msg-quote"><div class="_stretch">Hi John,<br>
&gt; I think the issue is data sharing, as Brandon mentioned.  A bytestring<br>
&gt; consists of an offset, length, and a pointer.  You're using a chunk size of<br>
&gt; 64k, which means the generated bytestrings all have a pointer to that 64k of<br>
&gt; data.  Suppose there's one new word in that 64k, and it's near the beginning<br>
&gt; of the chunk.  Even though the word may only be a few characters long, it'll<br>
&gt; reference the entire chunk and keep it from being GC'd.<br>
<br>
This seems to be the issue indeed! If the bytestrings on the hash map are<br>
holding references to the chunks, it is clear that we're going to consume memory<br>
scaling with the size of the input file, in case there are *any* new chunks<br>
generated.<br>
<br>
As I understand it, this what not a problem with the multiple copies of War and<br>
Peace, because all byte strings were already found on the hash table! On reading<br>
new input, old entries were found on the hash table, so only old chunks were<br>
kept in memory, the new ones could be gc'ed.<br>
<br>
In *realistic* data, however, the Long Tail is the reason that, after a while,<br>
some chunks of input would only be kept because there were a few byte strings<br>
referencing them. New words are rare, but they need not occur more frequently<br>
than once per chunk, in order to keep the whole chunk in memory, even though the<br>
chunk was mostly useless (most other data in this chunk would already be on the<br>
hash map.)<br>
<br>
&gt; There are a few solutions to this.  The first is to make a copy of the<br>
&gt; bytestring so only the required data is retained.  In my experiments this<br>
&gt; wasn't helpful, but it would depend on your corpus.  The second is to start<br>
&gt; with smaller chunks.  Using a chunk size of 1024 worked fairly well for me.<br>
&gt;  If your corpus is similar to natural language, I think it'll probably work<br>
&gt; better for you as well.<br>
<br>
I think I solved this problem elegantly: I used Data.Text as hash map keys,<br>
instead of Data.ByteString. See the modified program below:<br>
<br>
&gt; import qualified Data.Iteratee as I<br>
&gt; import Data.Iteratee.Char<br>
&gt; import Data.Iteratee.IO<br>
&gt; <br>
&gt; import qualified Data.HashMap.Strict as T<br>
&gt; <br>
&gt; import Data.Ord (comparing)<br>
&gt; import Data.List (sortBy)<br>
&gt; import System.Environment (getArgs)<br>
&gt; <br>
&gt; import qualified Data.ByteString as S<br>
&gt; import qualified Data.Text as X<br>
&gt; import Data.Text.Encoding (decodeUtf8)<br>
&gt; <br>
&gt; type Wordcounts = T.HashMap X.Text Int<br>
&gt; <br>
&gt; f' :: Monad m =&gt; I.Iteratee S.ByteString m Wordcounts<br>
&gt; f' = I.joinI $ (enumLinesBS I.&gt;&lt;&gt; I.filter (not.S.null)) $ I.foldl'<br>
&gt;     (\t s -&gt; T.insertWith (+) (convert s) 1 t) T.empty<br>
&gt;     where convert = decodeUtf8<br>
&gt; <br>
&gt; main :: IO ()<br>
&gt; main = getArgs &gt;&gt;= fileDriverVBuf 65536 f'.head<br>
&gt;        &gt;&gt;= mapM_ (\(w,c)-&gt; putStrLn $ X.unpack w ++ "\t" ++ show c).sortM<br>
&gt;     where sortM = sortBy (comparing snd) . T.toList<br>
<br>
Initial benchmarks on the realistic 100MB Gutenberg corpus I downloaded with my<br>
script yesterday report the following: htop says 120M memory residency towards<br>
the end of the life-cycle.<br>
<br>
&lt;&lt;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&gt;&gt;<br>
<br>
19MB avg, 44MB max residency, 133M in use (which is similar to what htop told<br>
me) and the heap profile clearly shows allocation and deallocation of the<br>
bytestrings: <a href="http://imgur.com/U1nyw" _mce_href="http://imgur.com/U1nyw">http://imgur.com/U1nyw</a> (I'm attributing the ruggedness of the<br>
profile with the frequent little spikes to the iteratee chunk allocation and<br>
deallocation.) It seems I can't get rid of 50% of the heap being lag state. I<br>
don't quite understand yet what that is. I also don't know what INHERENT_USE is.<br>
<br>
But in any case, I now have a program that I can reasonably expect to run if I<br>
could fit the input file into memory. I might try to implement an analogous<br>
program in C++ or Java, just to see whether that would do better or similarly in<br>
terms of memory consumption.<br>
<br>
&gt; Note that Johan's Ngram code also only keeps the minimum required data,<br>
&gt; giving it a good memory profile.   I didn't notice this last night because I<br>
&gt; was testing with different data, and unfortunately the peculiar distribution<br>
&gt; of that data masked this problem.<br>
<br>
This is kind of the big problem here: whether or not you'll see the particular<br>
behaviour I was so upset about seemed to depend on the corpus' distributional<br>
properties.<br>
<br>
In any case, I would like to thank you all for helping me understand and address<br>
the issue. I probably still have a long way to go in terms of understanding<br>
space-behaviour of Haskell programs, but at least I don't see ByteStrings as<br>
this black box of efficiency anymore, but actually understand how they're<br>
structured, and what they're good at, and what they aren't good at.<br>
<br>
(take home lesson: Data.Text is really nice. Also: if iteratee has a space leak,<br>
I probably didn't hit it, really. But: if reading byte-strings, one should mind<br>
the pointers that byte-strings actually are.)<br>
<br>
Regards,<br>
Aleks<br>
</div><div class="_stretch">_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" _mce_href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" _mce_href="http://wwwhaskell.org/mailman/listinfo/haskell-cafe">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</div></div></blockquote></div></body></html>