Initialization for lattice sieving

[R.D. Silverman]

Originally Posted by Prime95

Mr. Silverman was kind enough to send his source code for me to look at. Although I'm at somewhat of a disadvantage because I don't understand NFS, I do like computer optimization problems.

After looking at the amounts of data involved, I think my pie-in-the-sky no-sieve-array approach probably isn't best. Some kind of bucket sort looked most promising.

I've just emailed R.D. Silverman an updated source that cuts the sieving time by two-thirds. Whether this puts it on a par with Franke's siever, I do not know.

Unfortunately, I do not know NFS terminology so I cannot describe what I did. Mr. Silverman can fill y'all in later after he looks at what I've done.

I'm still learning how the code works and if I can find any further improvements I'll report them here.

Hi,

I just got the code. I will look at it ASAP. You seem to have implemented
some kind of bucket sieve. However, I need to look closely at what you
did. I tried a bucket sieve before and it was ineffective.

I believe your claims of speed improvement. If it truly reduces sieve time by 2/3, then I can turn to optimizing some other things that were not worth
doing before.

Thanks for the help. If you have any further comments on the code, let
me know.

I suspect that the code that does the resieving will need to be modified
in a different way from the primary sieve. Instead of adding a logarithm
to sieve[d][c], it instead checks to see

if (sieve[d][c] == GOOD)

then stores the prime, along with d and c. This storage does not happen too
often as most points are not successful candidates.

However, I expect that fetching sieve[d][c] to see if it is GOOD (i.e. a
potential candidate) is causing cache misses.

[Chris Card]

Originally Posted by R.D. Silverman

Hi,
if (sieve[d][c] == GOOD)

then stores the prime, along with d and c. This storage does not happen too
often as most points are not successful candidates.

However, I expect that fetching sieve[d][c] to see if it is GOOD (i.e. a
potential candidate) is causing cache misses.

I do something very similar in my code, and this is where it spends most of its time according to gprof. On the other hand, it must be faster than not checking and simply updating the the sieve points, surely?

[I have had a go at your example with my siever, but there are a few problems, e.g. I haven't tried it with such a large factor base before, and my code only allows special q primes for the non-linear polynomial at the moment, so it's not been a very successful test so far.]

Chris

[R.D. Silverman]

Originally Posted by Chris Card

I do something very similar in my code, and this is where it spends most of its time according to gprof. On the other hand, it must be faster than not checking and simply updating the the sieve points, surely?

[I have had a go at your example with my siever, but there are a few problems, e.g. I haven't tried it with such a large factor base before, and my code only allows special q primes for the non-linear polynomial at the moment, so it's not been a very successful test so far.]

Chris

Hi,

I chose to do special q's for the linear polynomial, because for most
factorizations the linear norm is larger.

BTW, George Woltman got my code, got it running, and modified it in less
than 2 days. Kudos to George!! I was astonished at how fast he did this!

[Prime95]

Originally Posted by Prime95

I've just emailed R.D. Silverman an updated source that cuts the sieving time by two-thirds.

This claim did not hold up. When benchmarked on a much larger factor base the savings were constant. That is, my small initial test case went from 3 seconds to 1 second, but the larger test case went from 8 seconds to 6 seconds.

The bucket sorting of vectors worked for dense smaller primes but not for the larger primes.

The good news is we can make these larger primes cache-friendly too. I allocate 128MB to hold the pending sieve updates. As I accumulate these I sort every 256KB while it is still in the L2 cache. When were done accumulating, we reread the 128MB from the beginning of each sorted chunk to insure that we update the sieve array in a cache-friendly way.

The improvements are significant. Source code is available for those that want to try something similar with their programs.

[ET_]

Originally Posted by Prime95

The good news is we can make these larger primes cache-friendly too. I allocate 128MB to hold the pending sieve updates. As I accumulate these I sort every 256KB while it is still in the L2 cache. When were done accumulating, we reread the 128MB from the beginning of each sorted chunk to insure that we update the sieve array in a cache-friendly way.

The improvements are significant. Source code is available for those that want to try something similar with their programs.

I'd be interested. May you mail the code at mc5225 at mclink dot it?

Thank you

Luigi

[R. Gerbicz]

Mr. Silverman can you send me the old and the new code, only the sieving part. To
robert ( DOT ) gerbicz ( AT ) gmail ( DOT ) com
Can you post some timings for the new code ( if it is possible for the same input numbers) ?
To see exactly what has been done Mr. Woltman and what is in while loop, I can't figure out. And also to speed up the code if I can, not very probable, but say.
For an average p prime there are about area/p sieve updates, is it correct?