Sieving discussion thread

[Ken_g6]

From what I've seen on my Core 2 Quad, I got about a 2x speedup from a better memory access pattern, then a 3x speedup on top of that, for 32-bit only, from SSE2. So if 6x is expected, I suppose 7-8x isn't unreasonable.

I'm kind of in shock, too. But Geoff always said his code wasn't optimized for this many N's.

[axn]

Originally Posted by Ken_g6

From what I've seen on my Core 2 Quad, I got about a 2x speedup from a better memory access pattern, then a 3x speedup on top of that, for 32-bit only, from SSE2. So if 6x is expected, I suppose 7-8x isn't unreasonable.

I'm kind of in shock, too. But Geoff always said his code wasn't optimized for this many N's.

Actually, the latest speed I'm getting is about 3.9M @ 100G. That's another 3x speed increase over the speed at 30G (on same binary). And it's just getting faster and faster. I bet it'd be _even_ faster if I can suppress the screen output. Is there an option to do that? If not, can I get a build which suppresses the factor output?

[Ken_g6]

There doesn't seem to be a way to supresss the factor output to the screen. (Yet.) But you can add "> NUL" at the end on Windows ("> /dev/null" on Linux) to get rid of the output from any app.

I'm thinking next I should look at profiling the program. I can't think of a reason increasing P like that would speed it up, except maybe that factor output is more expensive than I realized.

[axn]

Originally Posted by Ken_g6

There doesn't seem to be a way to supresss the factor output to the screen. (Yet.) But you can add "> NUL" at the end on Windows ("> /dev/null" on Linux) to get rid of the output from any app.

Don't want that. I still want to see the progress reports.

Originally Posted by Ken_g6

I'm thinking next I should look at profiling the program. I can't think of a reason increasing P like that would speed it up, except maybe that factor output is more expensive than I realized.

False alarm. For some odd reason, it was only considering the first 2000 or so n's. The memory usage was around 400mb, and the factor density was much less. Wasted 2 hrs. Anyway, rerunning the range from start, and now it is back to around 1.45M (still faster than at 30G, but only slightly). I would still love to see if there is any potential speed gains from suppressing the screen output. Can you make a version with the relevant code commented out?

[geoff]

I've uploaded tpsieve 0.2.4 at http://www.geocities.com/g_w_reynolds/testing/ which just fixes the bug that prevented the proper nmax value being set ffrom a multi-n input file.

I don't have much time online at the moment, so I can't respond to all the issues about the program. But note that the multithreading is not ideal, only one thread at a time can be in certain parts of the prime generation code, so for benchmarking purposes it is best to use just a single thread. As the range of n changes, and also as the factor size changes, you will need to adjust the --qmax parameter to suit. (larger range of n and/or larger factor range should use a larger --qmax). Memory use can be reduced by using a hashtable instead of a bitmap, and reduced more by using a type of binary search of an ordered list, but there will be some performance tradeoff.

Anyway the source code is there, feel free to make changes.

Edit: The version numbering for source and binary are different, because I use the source to build a number of programs that share some of the code.

Edit2: The compiler I use for the 64-bit Windows executable is available here http://mingw-w64.sourceforge.net/ It can be used from Linux to produce Windows executables.

[Ken_g6]

Originally Posted by axn

For some odd reason, it was only considering the first 2000 or so n's. The memory usage was around 400mb, and the factor density was much less. Wasted 2 hrs. Anyway, rerunning the range from start, and now it is back to around 1.45M (still faster than at 30G, but only slightly). I would still love to see if there is any potential speed gains from suppressing the screen output. Can you make a version with the relevant code commented out?

I've added Geoff's fix to my zipfile, and added a flag "-q" to suppress factor output to the screen.

axn, is it possible that you gave the wrong value for the -N argument? (The new version doesn't need that.) If that's not what happened, could you please PM me with the command line you used, if you have it? (In case you didn't know, pressing the up arrow at the same command prompt might show it.)

[cipher]

Originally Posted by geoff

Memory use can be reduced by using a hashtable instead of a bitmap

Geoff i thought that setting was only available with sr2sieve and not tpsieve? How do you use hashtable with tpsieve?
thanks
cipher

[Flatlander]

I'm fiddling with tpsieve trying to get the hang of it. I now have a file tpfactors.txt that I want to remove from allc.txt but srfile doesn't like the file type. How do I remove the factors?

(100 ns in file. Windows.)

[cipher]

Flatlander check with gribozavr he has a perl script, to do that.

[TimSorbet]

Originally Posted by Ken_g6

I've added Geoff's fix to my zipfile, and added a flag "-q" to suppress factor output to the screen.

Can -q be set in tpconfig.txt? If so, would it be with -q or q or what?

[axn]

Originally Posted by Ken_g6

axn, is it possible that you gave the wrong value for the -N argument? (The new version doesn't need that.) If that's not what happened, could you please PM me with the command line you used, if you have it? (In case you didn't know, pressing the up arrow at the same command prompt might show it.)

The cmd line was fine. I aborted that run and restarted with the exact same command line, and things were fine. Must've been a freak mishap, is all I can think of.

<sse2-exe> -i <480kfile> -p 1e11 -P 2e11 -N 485000