[Haskell-cafe] Re: FASTER primes

[Daniel Fischer]

Am Mittwoch 06 Januar 2010 19:13:01 schrieb 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?

Sure. And I don't know why it takes *that much* memory, but since a flat merge
doesn't consume much memory, it must be the trees.

>
> 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).
>
So much? Wow. I forgot the numbers, but I had tried that too, I thought the memory gain 
wasn't worth the speed loss. Another thing that reduces memory usage is


    compos :: [a] -> [a]
    compos ps = case pairwise mergeSP (multip ps) of
                    ((a,b):cs) -> a ++ funMerge b (nwise 1 mergeSP $ pairwise mergeSP cs)

    funMerge b (x:y:zs) = let (c,d) = mergeSP x y
                            in mfun b c d zs

    mfun u@(x:xs) w@(y:ys) d  l = case compare x y of
                LT -> x:mfun xs w d l
                EQ -> x:mfun xs ys d l
                GT -> y:mfun u ys d l
    mfun u [] d l = funMerge (merge u d) l

That's about the same speed as the latter of the above here and uses about 25% less 
memory. Removing one or two 'pairwise's brings memory down further, but makes it slower.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100106/d93c6608/attachment.html