[email protected]
[Top] [All Lists]

Re: [Haskell-cafe] Re: FASTER primes

Subject: Re: [Haskell-cafe] Re: FASTER primes
From: Daniel Fischer
Date: Thu, 7 Jan 2010 01:59:09 +0100

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 [email protected](x:xs) [email protected](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.

_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
<Prev in Thread] Current Thread [Next in Thread>