[Haskell-cafe] Re: FASTER primes

[Will Ness]

Daniel Fischer <daniel.is.fischer <at> web.de> writes:

> 
> Am Sonntag 03 Januar 2010 09:54:37 schrieb Will Ness:
> >
> > The quesion of a memory blowup with the treefolding merge still remains.
> > For some reason using its second copy for a feeder doesn't reduce the
> > memory (as reported by standalone compiled program, GHCi reported values
> > are useless) - it causes it to increase twice.....
> >
> 
> I have a partial solution. The big problem is that the feeder holds on to 
> the beginning of comps while the main runner holds on to a later part. Thus
> the entire segment between these two points must be in memory. 
>
> So have two lists of composites (yeah, you know that, but it didn't work
> so far).
>
> But you have to force the compiler not to share them: enter -fno-cse.
> The attached code does that (I've also expanded the wheel), it reduces the
> memory requirements much (a small part is due to the larger wheel, a factor
> of ~5 due to the non-sharing).


I don't understand. What is there to be shared? Each multiples list is consumed 
only at one point; there's nothing to be shared. Do you mean the compiler still 
hangs on to them? If so, why?? 

I used the switch; it didn't help at all. The only thing I can see is different 
is that all my interim data which I named with inner vars you moved out to the 
top level as functions. Is that what did the trick? What would be the reason to 
hang on to the already consumed data that is inaccessible to any active 
consumer? Why not make the forgetful behaviour the norm - especially where 
remembering is pointless??




> It still uses much more memory than the PQ, and while the PQ's memory
> requirements grow very slowly, the tree-fold merge's still grow rather fast
> (don't go much beyond the 10,000,000th prime), I'm not sure why.


You did it! It's now 7M for 1,000,000th prime, instead of 52M before. Making 
the pattern lazy in mergeSP was probably an important fix too. :)

Unfortunately it grows, as you've said - 23MB for 2 mln. :|  

PQ stays at just 2MB. 



> 
> Attachment (V13Primes.hs): text/x-haskell, 3621 bytes
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>