QS/NFS crossover points

[factorn]

Originally Posted by VBCurtis

2.3.0 is the 2017 release. So, part of your post asks for a comparison to CADO from 5 years ago, while the other part asks about the latest release. The current 'git' repository is labeled 3.0.0, and has been for four years or so despite no 'official' release.

There hasn't been much speed improvement in the CADO code in a while, except when using even values of A along with adjust-strategy=2 (rather an edge case). The crossover between Ben's QS code and CADO is around 93 digits when not using AVX-512, but the QS code gets a really nice speedup from AVX-512; I don't have an AVX-512 CPU so Ben might comment on that crossover.

Originally Posted by bsquared

I'm having trouble building cado from the latest source. It's a weird error in the make process, not anything wrong with source code (yet). I also tried with the latest tagged version and got the same problem. Here are the last few lines including the error:

configure: creating ./config.status
config.status: creating version.sh
config.status: creating Makefile
config.status: creating tests/Makefile
config.status: creating src/Makefile
config.status: creating gf2x-fft/Makefile
config.status: creating gf2x/gf2x-config.h
config.status: linking /home/factoring/src/c/cado-nfs-git-2.0.1/gf2x/already_tuned/x86_64_pclmul/gf2x-thresholds.h to gf2x/gf2x-thresholds.h
config.status: linking /home/factoring/src/c/cado-nfs-git-2.0.1/gf2x/already_tuned/x86_64_pclmul/gf2x_mul1.h to gf2x/gf2x_mul1.h
config.status: linking /home/factoring/src/c/cado-nfs-git-2.0.1/gf2x/already_tuned/x86_64_pclmul/gf2x_mul2.h to gf2x/gf2x_mul2.h
config.status: linking /home/factoring/src/c/cado-nfs-git-2.0.1/gf2x/already_tuned/x86_64_pclmul/gf2x_mul3.h to gf2x/gf2x_mul3.h
config.status: linking /home/factoring/src/c/cado-nfs-git-2.0.1/gf2x/already_tuned/x86_64_pclmul/gf2x_mul4.h to gf2x/gf2x_mul4.h
config.status: linking /home/factoring/src/c/cado-nfs-git-2.0.1/gf2x/already_tuned/x86_64_pclmul/gf2x_mul5.h to gf2x/gf2x_mul5.h
config.status: linking /home/factoring/src/c/cado-nfs-git-2.0.1/gf2x/already_tuned/x86_64_pclmul/gf2x_mul6.h to gf2x/gf2x_mul6.h
config.status: linking /home/factoring/src/c/cado-nfs-git-2.0.1/gf2x/already_tuned/x86_64_pclmul/gf2x_mul7.h to gf2x/gf2x_mul7.h
config.status: linking /home/factoring/src/c/cado-nfs-git-2.0.1/gf2x/already_tuned/x86_64_pclmul/gf2x_mul8.h to gf2x/gf2x_mul8.h
config.status: linking /home/factoring/src/c/cado-nfs-git-2.0.1/gf2x/already_tuned/x86_64_pclmul/gf2x_mul9.h to gf2x/gf2x_mul9.h
config.status: executing depfiles commands
config.status: executing libtool commands
[  0%] Building gf2x
Making all in .
libtool: compile:  gcc-11.1.0 -DHAVE_CONFIG_H -I. -I/home/factoring/src/c/cado-nfs-git-2.0.1/gf2x -I./gf2x -I/home/factoring/src/c/cado-nfs-git-2.0.1/gf2x -I. -Wall -W -std=c99 -g -W -Wall -O2 -I/home/factoring/src/c/gmp_install/gmp-6.2.0/include -I/home/factoring/src/c/cado-nfs-git-2.0.1 -mpclmul -c /home/factoring/src/c/cado-nfs-git-2.0.1/gf2x/gf2x.c -o gf2x.o
In file included from /home/factoring/src/c/cado-nfs-git-2.0.1/gf2x/gf2x/gf2x-impl.h:24,
                 from /home/factoring/src/c/cado-nfs-git-2.0.1/gf2x/gf2x.c:27:
/home/factoring/src/c/cado-nfs-git-2.0.1/macros.h:123:31: warning: this use of "defined" may not be portable [-Wexpansion-to-defined]
  123 | #if GNUC_VERSION_ATLEAST(3,4,0)
      |                               ^
In file included from /home/factoring/src/c/cado-nfs-git-2.0.1/gf2x/gf2x/gf2x-small.h:85,
                 from /home/factoring/src/c/cado-nfs-git-2.0.1/gf2x/gf2x.c:30:
./gf2x/gf2x_mul1.h:1:1: error: expected identifier or '(' before '.' token
    1 | ../../src/mul1cl.c
      | ^

The file "gf2x_mul1.h", sure enough, just contains this text:
../../src/mul1cl.c

which pretty obviously isn't a valid C header.

As the instructions say, I'm just typing "make". local.sh defines my gmp location and names of gcc and g++ (which are gcc-11.1.0 and g++-11.1.0, respectively).

Is there some kind of configuration necessary before make?

I have built CADO several times in the past week and everything works. I built from commit 5d7ccce67fbf4d4c24d265f7d333778a6cdb1cff, but I just did a git pull to get the latest from the master branch and everything still builds fine. I had no issues, I used GCC-9.3 and G++-9.3 for some builds as well as GCC-10 and G++-10 for some other builds with no issue.

Try this:

make clean
<from CADO-NFS ROOT FOLDER> rm -rf build
make cmake
make

You need to run "make cmake" for CADO-NFS to pick up your local.sh changes. Also, you will get a lot of error messages around 60% build, along the lines of:

Git/cado-nfs/sieve/las.cpp:1356:9: error: ‘json’ was not declared in this scope; did you mean ‘nlohmann::json’?
1356 | json dirinfo;
| ^~~~
| nlohmann::json

Just go to file cado-nfs/sieve/las.cpp and after all the headers and before the code, at line 93 for example, add the line

using namespace nlohmann;

[charybdis]

Originally Posted by factorn

You need to run "make cmake" for CADO-NFS to pick up your local.sh changes.

Only if you have already built CADO without the changes. You can see from bsquared's terminal output that CADO successfully picked up the "gcc-11.1.0" command from his local.sh.

[bsquared]

Originally Posted by charybdis

First off, this looks like a broken symlink, see here.

Secondly, are you sure this is the latest CADO? "cado-nfs-git-2.0.1" suggests 2.0.1, which is pretty old...

Thanks, that got me much further along. (There I was just trying with an older version to see if anything was different.)

Now it is having problems seeing the gf2x library it made...

[ 63%] Built target bwc_base
[ 63%] Built target acollect
[ 65%] Built target blocklanczos
[ 65%] Built target bwccheck
[ 65%] Built target cleanup
[ 65%] Built target dispatch
[ 68%] Built target flint-fft
[ 68%] Built target gather
[ 68%] Built target krylov
[ 70%] Built target lingen_common_support
[ 70%] Built target lingen_pz_support
[ 71%] Built target lingen_pz
[ 71%] Built target lingen_u64k1_support
[ 71%] Linking CXX executable lingen_u64k1
/bin/ld: cannot find -lgf2x
collect2: error: ld returned 1 exit status
make[2]: *** [linalg/bwc/lingen_u64k1] Error 1
make[1]: *** [linalg/bwc/CMakeFiles/lingen_u64k1.dir/all] Error 2
make: *** [all] Error 2
make: *** [all] Error 1

I can see libgf2x in the build/gf2x directory and I modified my LD_LIBRARY_PATH environment variable to point to it, but still getting that linking error.

[bsquared]

I restarted the build on a different machine, one I have full access to, and after fixing the broken symlinks the build completed just fine. The previous system I did not have full access to; could not write to /usr/ for instance. That may have been the holdup.

Anyway now that I have a working CADO 3.0 I can do some comparisons.

[bsquared]

QS packages tested:
* yafu (2.08)

NFS packages tested:
* yafu-nfs-2.08 (msieve/ggnfs64)
* cado-nfs-3.0.0

Run on: Intel(R) Core(TM) i7-7800X CPU @ 3.50GHz (wsl2); all tests single threaded. Yafu-qs and cado are both using AVX-512.

Here is the total time data:

input digits	yafu-2.08 qs (t4)      yafu-2.08-nfs	cado-nfs-3.0.0 (t4)     cado-3.0-mf-params (t4)
60	           1.1 (0.35)		                      54.3 (37.1)
65	           3.3 (0.97)		                      74.9 (42.3)
70	           6.7 (2.3)		                      106 (56.4)
75	           22.5 (6.6)		                      208 (96)
80	           45.5 (14.1)	                              351 (124)
85	           132 (39.6)	                 	      652 (224)
90	           514 (143)	                 	      1377 (442)          892 (309)
95	           1550 (408)	                              2365                2126 (658)
100	           3413 (909)                                 3950	          2697 (958)
105	           11984	                              7405
110

Still gathering data. It looks like the crossover between yafu and cado is slightly over 100 digits with default params, and maybe around 97 digits with VBCurtis's improved params.

[factorn]

Awesome! Waiting for the final results! Is there a significant difference between having AVX-512 or not? Also, have you disable Hyper-Threading, i.e are you using the full resources of one core? Also, I have never been able to build yafu with nfs, can you make a dockerfile for it? That would be great!


Thanks.


~N

[VBCurtis]

Originally Posted by bsquared

Still gathering data. It looks like the crossover between yafu and cado is slightly over 100 digits.

Are you using the improved params files from the CADO subforum, or default? The ones posted in the forum here improve timings by 30-40% at 95-100 digits size.

[factorn]

VBCurtis, could you post the link to those please?


~N

[EdH]

Originally Posted by factorn

VBCurtis, could you post the link to those please?


~N

They can be found in the thread:

Improved params files for CADO

[bsquared]

Originally Posted by VBCurtis

Are you using the improved params files from the CADO subforum, or default? The ones posted in the forum here improve timings by 30-40% at 95-100 digits size.

I'm using the default for now. I'll go back and re-time with the improved params as well.

[VBCurtis]

About two years ago I compared CADO 3.0 to yafu-siqs (sorry, didn't record which version- but I don't use yafu regularly, so it would hav been whatever was current & easy to find at that time) on a 12-core Xeon haswell 2680v3.

Running 12-threaded on a C93, siqs took 229 seconds. CADO 12-threaded on default params took 336 sec, CADO on my params (tuned for this test, not the C95 file posted to the improved params thread) took 226 sec. I think the C95 file posted to the improved params thread took 252 sec.

I've attached this most recent c95 params here, as well as a c100 params that factored a C101 in 408 seconds (24-threaded, so using hyperthreads).