[Haskell-cafe] Re: FASTER primes

[Will Ness]

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

> 
> 
> Am Mittwoch 06 Januar 2010 00:09:07 schrieb Will Ness:
> > Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> > > Am Montag 04 Januar 2010 22:25:28 schrieb Daniel Fischer:
> > > Fix rfold:
> > >
> > > rfold f [x] = x
> > > rfold f xs = rfold f (pairwise f xs)
> > >
> > > and it's faster also for those.
> >
> 
> The memory is almost completely due to the tree-merging of the multiples for
> the fastest runner. While it produces faster than flat merging, the
> exponential growth of the trees makes  a bad memory citizen.


Isn't the number of nodes the same in any two trees with the same number of 
leafs?

BTW using

 compos ps = fst $ tfold mergeSP $ nwise 1 mergeSP $ map pmults ps

instead of 

 compos ps = fst $ tfold mergeSP $ nwise 1 mergeSP 
                                 $ pairwise mergeSP $ map pmults ps

brings down memory consumption further by 25%..45% on 1..8 mln primes produced, 
while slowing it down by about 0%..2% (that's after eliminating the lazy 
pattern in tfold as per your advice).


> > 'pairwise' puts odd leafs higher on the right. It might be better if it was
> > so on the left, for the frequency of production is higher.
> 
> Maybe. But how would you do it? I tried passing the length to rfold, so when
> there was an odd numberof trees in the list, it would move the first out of
> the recursion. Any possible gains in production have been more than eaten up
> by the control code (not a big difference, but it was there).


yes I've seen this too now. BTW, at a price of further slowing down, memory can 
be lowered yet more with


 compos ps = fst $ tfold mergeSP $ nwise 1 0.4 mergeSP $ map pmults ps
 nwise k d f xs = let (ys,zs) = splitAt (round k) xs 
                  in rfold f ys : nwise (k+d) d f zs


It really looks like the nearer the structure is to linear list, the lower the 
memory consumption becomes. Of course using 0.0 in place of 0.4 would make it 
into a plain list.