[Haskell-cafe] Re: FASTER primes
Will Ness
will_n48 at yahoo.com
Sat Jan 9 02:42:52 EST 2010
Heinrich Apfelmus <apfelmus <at> quantentunnel.de> writes:
>
> Will Ness wrote:
> > But I get the impression that GHC isn't working through equational
> > reasoning?..
> > I see all this talk about thunks etc.
>
> Sure it does. Concerning the thunks, they're part of the implementation
> of the reduction model (call-by-need aka lazy evaluation).
At run-time? I meant to eliminate as much calculation as possible, pre-run-time.
I would expect the best efforts of the best minds to go into searching for ways
how to eliminate computations altogether, instead of how to perform them better.
> >> Concerning the sieves, there is a fundamental difference between the
> >> imperative sieve and the functional sieves, regardless of whether the
> >> latter start at p or p^2 or use a priority queue. [...]
> >
> > We can directy jump to the next multiple too, it is called (+). :) :)
> >
> > But seriously, the real issue is that we have to merge the produced
> > streams of multiples, while the mutable-storage code works on same one,
> > so its "merging cost" is zero.
>
> Not quite, I think there are two things going on:
>
> 1. In contrast to the standard imperative version, we are implementing
> an on-line algorithm that produces arbitrarily many primes on demand.
> Any imperative on-line version will need to think about storage for
> pending prime filters as well.
True.
> 2. Even the imperative algorithm can be interpreted as "merging" arrays,
> just that the composites are magically merged at the right place (at
> distance p from each other) because arrays offer O(1) "jumps".
i.e. with a merging cost of zero. :)
> In contrast, the functional version needs O(log something) time to
> calculate where to put the next composite.
when thinking it terms of the finally produced sequence, yes. We have to
produce numbers one by one and take care of their ordering ourselves; _they_
just /throw/ the numbers at the shared canvas and let _it_ take care of
ordering them automagically, _later_, on the final sweep through. ISWYM.
>
> > If you could take a look at the tree-merging primes and why it uses
> > too much memory, it would be great.
>
> Fortunately, Daniel already took a detailed look. :)
Yes he really came through! He finally found, and fixed, the space leak. It was
hiding in
mergeSP_BAD (a,b) ~(c,d) = let (bc,b') = spMerge b c
in (a ++ bc, merge b' d)
where
spMerge :: (Ord a) => [a] -> [a] -> ([a],[a])
spMerge a@(x:xs) b@(y:ys) = case compare x y of
LT -> (x:c,d) where (c,d) = spMerge xs b
EQ -> (x:c,d) where (c,d) = spMerge xs ys
GT -> (y:c,d) where (c,d) = spMerge a ys
spMerge a [] = ([] ,a)
spMerge [] b = ([] ,b)
which really ought to have been
mergeSP (a,b) ~(c,d) = let ~(bc,bd) = spMerge b c d
in (a ++ bc, bd)
where
spMerge u [] d = ([], merge u d)
spMerge u@(x:xs) w@(y:ys) d = case compare x y of
LT -> spCons x $ spMerge xs w d
EQ -> spCons x $ spMerge xs ys d
GT -> spCons y $ spMerge u ys d
spCons x ~(a,b) = (x:a,b)
Can you spot the difference? :) :)
> Aww, why remove the cutesy name? The VIPs will be angry for being ignored!
It runs faster on plain pairs, and on less memory, equals for equals. For some
reason. :)
More information about the Haskell-Cafe
mailing list