Arie Peterson | 10 Oct 15:02 2013
Picon
Picon

Increasing memory use in stream computation

(Sorry for the long email.)

Summary: why does the attached program have non-constant memory use?

==== Introduction ====

I've written a program to do a big computation. Unfortunately, the computation 
takes a very long time (expectedly), and the memory use increases slowly 
(unexpectedly), until it fills up the entire memory and swap space of the 
computer (many gigabytes).

The rough structure of the program is:

• create a long (up to 20 million) list of objects;
• compute a number for each of those objects;
• compute the sum of the resulting list.

I switched the intermediate data structure from a list to a Stream (from the 
stream-fusion package), hoping to fix the memory issue. It decreased both the 
memory use and the rate of its increase, but after a long time, the program 
still uses up all available memory.

==== A simple program

After many hours of cutting down my program, I now have a small program 
(attached) that shows the same behaviour. It uses only said stream-fusion 
package, and vector. (I haven't yet tried to cut out the use of vector. I hope 
it is irrelevant, because all vectors are of fixed small size.)

I compile the program with ghc-7.6.1 using
(Continue reading)

Claude Heiland-Allen | 10 Oct 16:39 2013
Picon

Re: Increasing memory use in stream computation

Hi Arie,

On 10/10/13 14:02, Arie Peterson wrote:
> (Sorry for the long email.)
> 
> Summary: why does the attached program have non-constant memory use?

Looking at the heap profile graph (generated with +RTS -h, no need to
compile with profiling) I see the increasing memory use is split about
evenly between STACK and BLACKHOLE.  I don't know what that means or why
it occurs, but replacing `small` solved that problem for me:

small = V.fromList <$> S.stream (replicateM 7 [-1,0,0,1])

I get the same output 3999744 from your version and my changed version.

Claude

> 
> 
> ==== Introduction ====
> 
> I've written a program to do a big computation. Unfortunately, the computation 
> takes a very long time (expectedly), and the memory use increases slowly 
> (unexpectedly), until it fills up the entire memory and swap space of the 
> computer (many gigabytes).
> 
> The rough structure of the program is:
> 
> • create a long (up to 20 million) list of objects;
(Continue reading)

Arie Peterson | 10 Oct 20:05 2013
Picon
Picon

Re: Increasing memory use in stream computation

Hi Claude,

> Looking at the heap profile graph (generated with +RTS -h, no need to
> compile with profiling) I see the increasing memory use is split about
> evenly between STACK and BLACKHOLE.  I don't know what that means or why
> it occurs, but replacing `small` solved that problem for me:
> 
> small = V.fromList <$> S.stream (replicateM 7 [-1,0,0,1])

Interesting!

Unfortunately, my real code is more complicated, and I can't simplify its 
"small" function in this way. (The list [-1,0,0,1], that is being streamed in 
the do block, in the full program depends on some parameter that changes on 
each iteration.)

Although, maybe I can do all the logic of the "small" function in the list 
monad, and stream the resulting list, as you do in the above.
Arie Peterson | 14 Oct 17:01 2013
Picon
Picon

Re: Increasing memory use in stream computation

Hi Claude,

On Thursday 10 October 2013 20:05:37 I wrote:
> Although, maybe I can do all the logic of the "small" function in the list 
> monad, and stream the resulting list, as you do in the above.

I tried a corresponding variant of my full program, but the memory use is 
quite a lot higher at the start, and increases by large amounts (compared to 
the version that streams at all levels).

So, I'm still at a loss.

Regards,

Arie
Bertram Felgenhauer | 10 Oct 19:03 2013

Re: Increasing memory use in stream computation

Arie Peterson wrote:
> (Sorry for the long email.)
> 
> Summary: why does the attached program have non-constant memory use?

Unfortunately, I don't know. I'll intersperse some remarks and
propose an alternative to stream fusion at the end, which allows
your test program to run in constant space.

> ==== A simple program
> 
> When running the program, the resident memory quickly grows to about 3.5 MB 
> (which I am fine with); this stays constant for a long time, but after about 7 
> minutes, it starts to grow further. The growth is slow, but I really would 
> hope this program to run in constant memory.

A quicker way to spot the increased memory usage is to look at GC
statistics. I used

> ./Test +RTS -Sstderr 2>&1 | grep 'Gen:  1'
   569904      8192     65488  0.00  0.00    0.01    0.01    0    0  (Gen:  1)
   516520      9768     67080  0.00  0.00    4.23    4.23    0    0  (Gen:  1)
   513824     14136     71448  0.00  0.00    8.43    8.44    0    0  (Gen:  1)
   515856     16728     74040  0.00  0.00   12.70   12.75    0    0  (Gen:  1)
   515416     19080     76392  0.00  0.00   17.01   17.11    0    0  (Gen:  1)
   515856     22248     79560  0.00  0.00   21.33   21.48    0    0  (Gen:  1)
   514936     25080     82392  0.00  0.00   25.65   25.84    0    0  (Gen:  1)
   514936     28632     85944  0.00  0.00   29.94   30.16    0    0  (Gen:  1)
   513512     32328     89640  0.00  0.00   34.24   34.48    0    0  (Gen:  1)
   515224     37032    127112  0.00  0.00   38.35   38.62    0    0  (Gen:  1)
(Continue reading)

Arie Peterson | 10 Oct 20:23 2013
Picon
Picon

Re: Increasing memory use in stream computation

Hi Bertram,

> Unfortunately, I don't know. I'll intersperse some remarks and
> propose an alternative to stream fusion at the end, which allows
> your test program to run in constant space.
> 
> 
> A quicker way to spot the increased memory usage is to look at GC
> statistics. I used
> 
> > ./Test +RTS -Sstderr 2>&1 | grep 'Gen:  1'
> 
> […]

Thanks for the suggestion.

> I had a glimpse at the core code generated by ghc, but the amount of
> code is overwhelming. From reading the source code, and as far as my
> intuition goes, the code *should* run in constant space.

Yes, my intuition says the same. For me though, this is only based on an 
informal imperative interpretation of the code, not on any understanding of 
the Stream internals.

> As an experiment, I rewrote the code using difference lists, and the
> result ran in constant memory. I then tried to abstract this idea into
> a nice data type. (I lost the low-level difference list code on the way,
> but the code was quite hard to read anyway.)
> […]> 
> I'll attach the full code below (it's a separate module, "Stream.hs"
(Continue reading)


Gmane