Contributions to msieve source code

[mickfrancis]

Glad it was of some use. Thanks, by the way Jason for the great software and making it PD - very generous!

[bsquared]

Agreed, a nice update, although in some brief tests I saw essentially no change in speed.

I had forgotten that this core routine always did a prefetch. Modern processors tend do a much better job with cache management, and have much larger caches, than older processors did... so I tried simply commenting out the prefetch and saw a 8% speedup (tested on a c75, c80 and c82, on a Xeon E5-2687W).

This result will be very CPU dependent of course, but I think for most systems today the prefetch would not help much.

[mickfrancis]

Nice one! I get 8% speed-up on a C80.

There is also a PREFETCH without an #ifdef MANUAL_PREFETCH in sieve_line.c. I haven't had a chance to see if this has any effect yet.

[bsquared]

Originally Posted by mickfrancis

Nice one! I get 8% speed-up on a C80.

There is also a PREFETCH without an #ifdef MANUAL_PREFETCH in sieve_line.c. I haven't had a chance to see if this has any effect yet.

sieve_line.c is msieve's NFS line siever, so it won't have any effect on QS timings. It may help improve the line siever, but on the other hand I doubt if anyone still uses it.

[henryzz]

Originally Posted by bsquared

sieve_line.c is msieve's NFS line siever, so it won't have any effect on QS timings. It may help improve the line siever, but on the other hand I doubt if anyone still uses it.

I don't think it works currently.

[mickfrancis]

Just got a 7% speed-up on a C100 by removing the PREFETCH, so looks like it scales, which is great. This is on an Intel i7-3770.

[Nooby]

windows:
stat() fails on large files with EOVERFLOW.

I see some workarounds in current code but mine actually work.

Index: savefile.c
===================================================================
--- savefile.c (revision 962)
+++ savefile.c (working copy)
@@ -95,8 +95,12 @@
  char *open_string;
 #ifndef NO_ZLIB
  char name_gz[256];
+#if defined(WIN32) || defined(_WIN64)
+ struct _stat64 dummy;
+#else
  struct stat dummy;
 #endif
+#endif
 
  if (flags & SAVEFILE_APPEND)
   open_string = "a";
@@ -111,8 +115,13 @@
 
 #ifndef NO_ZLIB
  sprintf(name_gz, "%s.gz", s->name);
+#if defined(WIN32) || defined(_WIN64)
+ if (_stat64(name_gz, &dummy) == 0) {
+  if (_stat64(s->name, &dummy) == 0) {
+#else
  if (stat(name_gz, &dummy) == 0) {
   if (stat(s->name, &dummy) == 0) {
+#endif
    printf("error: both '%s' and '%s' exist. "
           "Remove the wrong one and restart\n",
     s->name, name_gz);
@@ -189,8 +198,8 @@
 uint32 savefile_exists(savefile_t *s) {
  
 #if defined(WIN32) || defined(_WIN64)
- struct _stat dummy;
- return (_stat(s->name, &dummy) == 0);
+ struct _stat64 dummy;
+ return (_stat64(s->name, &dummy) == 0);
 #else
  struct stat dummy;
  return (stat(s->name, &dummy) == 0);

Index: util.c
===================================================================
--- util.c (revision 962)
+++ util.c (working copy)
@@ -477,20 +477,17 @@
 uint64 get_file_size(char *name) {
 
 #if defined(WIN32) || defined(_WIN64)
- WIN32_FILE_ATTRIBUTE_DATA tmp;
+ struct _stat64 tmp;
 
- if (GetFileAttributesEx((LPCTSTR)name, 
-   GetFileExInfoStandard, &tmp) == 0) {
+ if (_stat64(name, &tmp) != 0) {
   char name_gz[256];
   sprintf(name_gz, "%s.gz", name);
-  if (GetFileAttributesEx((LPCTSTR)name_gz,
-   GetFileExInfoStandard, &tmp) == 0)
+  if (_stat64(name_gz, &tmp) != 0)
    return 0;
-
-  return ((uint64)tmp.nFileSizeHigh << 32 | tmp.nFileSizeLow) << 1;
+  return (tmp.st_size / 11) * 20;
  }
 
- return (uint64)tmp.nFileSizeHigh << 32 | tmp.nFileSizeLow;
+ return tmp.st_size;
 
 #else
  struct stat tmp;

[jasonp]

Thanks for the fixes. MinGW doesn't have the _stat64 function (discussion here); it would be preferable to use _stati64 instead.

[debrouxl]

Several weeks ago, I posted about a modest (~2%), but seemingly consistent optimization to filtering:

Index: gnfs/relation.c
===================================================================
--- gnfs/relation.c	(révision 961)
+++ gnfs/relation.c	(copie de travail)
@@ -16,7 +16,11 @@
 #include "gnfs.h"
 
 /*--------------------------------------------------------------------*/
-static uint32 divide_factor_out(mpz_t polyval, uint64 p, 
+static inline
+#ifdef __GNUC__
+__attribute__((always_inline))
+#endif
+uint32 divide_factor_out(mpz_t polyval, uint64 p, 
 				uint8 *factors, uint32 *array_size_in,
 				uint32 *num_factors, uint32 compress,
 				mpz_t tmp1, mpz_t tmp2, mpz_t tmp3) {

See http://www.mersenneforum.org/showpos...7&postcount=14 for numbers and details, and a question

[jasonp]

Sorry Lionel, I read your original post but forgot to fold it in. Will do so soon.

[mickfrancis]

I appreciate that people are more concerned with GNFS than SIQS, but I just thought I'd mention that I've got a speedup of around 6% (for C80, C90 and C100) by making the following change in sieve.c (conditional on __MDF__):

	/* choose the largest factor base prime that does not
	   use hashtables or reciprocals. We could make this
	   range empty, but it's better to start using hashtables
	   with primes somewhat larger than the block size.
	   This greatly reduces the amount of memory used by
	   the hashtables, and trial factoring by primes in this
	   range is extremely cheap */

	for (; i < fb_size && conf.factor_base[i].prime <
#if defined(__MDF__)
            sieve_block_size; i++) {
#else
            3 * sieve_block_size; i++) {
#endif
		/* nothing */
	}

I also tried using sieve_block_size/2, but that degrades performance. This is on an Intel i7-3770. Testing was after removing the PREFETCH in add_to_hashtable() in sieve_core.c, which may be important as that function will be more heavily loaded by this change if I'm not mistaken.

Cheers,

Mick.