[Haskell-cafe] Re: FASTER primes

[Daniel Fischer]

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:
> > > memory still grows, but much slower, in my tests, due to the much
> > > smaller GC time, it's a bit faster than the version with the original
> > > tfold.
> >
> > Not for larger inputs (but not so large that the tree-fold dies OOM).
> > Fix rfold:
> >
> > rfold f [x] = x
> > rfold f xs = rfold f (pairwise f xs)
> >
> > and it's faster also for those.
>
> Niiice!!!! This is just great!  :)
>
> I tried a two-step feed BTW (that's three separate sets of lists) , with
> the original structure. It ran with same speed as your new version (10..20%
> faster) but with the memory of the previous one :) (80M for 8 mil primes vs
> the new one's 10M).

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.
With the nwise and rfold, a two-step (or even three-step) feeding doesn't gain nearly as 
much (I found about 1% speedup).

> But your new structure is just great! I hoped there is
> something better, that's why I posted it here in the first place.
>

I have two more goodies :)
1. now that the trees don't grow so fast, don't use lazy patterns in the definition of 
tfold:

tfold f (a:b:c:xs) = (a `f` (b `f` c)) `f` tfold f xs

gains something like 6-7% here (and uses a little less memory).

2. Now we have a big wheel, 5760 differences per period. Then dropping a few thousand 
elements from the wheel after calculating how many in rollFrom is slow:

rollFrom n = go ((n-17) `rem` 30030) wheel13
      where
        go r xxs@(x:xs)
            | r < x     = roll n xxs
            | otherwise = go (r-x) xs

gains another couple of percents for large targets (~1% for the 10M prime, ~2% for 20M, I 
expect that to stay in th region of 1.5-3% for larger targets).

> '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).

>
>
> Thanks a lot for your comments!


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