Re: [sage-devel] NTL 11.4.4
True. Should be https://libntl.org On Friday, March 5, 2021 at 5:00:17 PM UTC-5 jus...@mac.com wrote: > Hi, Victor, > > It appears that the first link has a typo :-} > > > On Mar 5, 2021, at 13:35 , Victor Shoup wrote: > > > > Just posted a new version of NTL to https://libnlt.org > > BTW, NTL is also hosted on github: https://github.com/libntl/ntl > > > > Cheers > > > > -- > > You received this message because you are subscribed to the Google > Groups "sage-devel" group. > > To unsubscribe from this group and stop receiving emails from it, send > an email to sage-devel+...@googlegroups.com. > > To view this discussion on the web visit > https://groups.google.com/d/msgid/sage-devel/da4324b3-1ba6-43d7-971d-7975056429ddn%40googlegroups.com > . > > -- > Justin C. Walker, Curmudgeon-At-Large > Institute for the Absorption of Federal Funds > > If you're not confused, > You're not paying attention > > > > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/e7ff7810-18a4-47e9-b639-fd297b6dd2den%40googlegroups.com.
[sage-devel] NTL 11.4.4
Just posted a new version of NTL to https://libnlt.org BTW, NTL is also hosted on github: https://github.com/libntl/ntl Cheers -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/da4324b3-1ba6-43d7-971d-7975056429ddn%40googlegroups.com.
[sage-devel] NTL 11.4.3
I uploaded NTL 11.4.3 to https://www.shoup.net/ntl/ This fixes an embarrassing build problem in 11.4.2. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/0802bf99-b9db-4d1d-9585-e20874f96099%40googlegroups.com.
[sage-devel] NTL 11.4.2
I just uploaded NTL 11.4.2 to http://www.shoup.net/ntl This fixes a few small, obscure bugs, including one that prevents using the gf2x-1.3 library. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/992c77f6-ebf9-4049-8900-c45c6b89f4ed%40googlegroups.com.
[sage-devel] NTL 11.4.1
I've just posted NTL 11.4.1, which fixes a bug introduced in NTL 11.4.0. Details here: https://shoup.net/ntl/ -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/9de1e60f-c295-4f1c-bd57-5bd74c6693d4%40googlegroups.com.
[sage-devel] NTL 11.4.0
A new version of NTL is available. Details here: https://www.shoup.net/ntl/doc/tour-changes.html -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/932b840e-2b9b-4fce-90d5-91bad33c50d8%40googlegroups.com.
Re: [sage-devel] NTL 11.3.4
Wow! That is great!! Since I have to support this going forward, I'd like to understand it better before adopting it. For example, where does "mach_desch.h" get built? As far as the Wizard goes, we can discuss if there are any issues there that need special attention. Maybe a "make tune" that is run afterwords would be easier. On Saturday, September 7, 2019 at 11:23:14 PM UTC-4, Isuru Fernando wrote: > > I spent a few hours today adding a CMake build system as you mentioned > that you are open to having a cmake build system. My work is at > https://github.com/isuruf/ntl > > The CMake build system has all of the options in the perl script except > for the wizard. > > You can try it by doing, > > cmake -DNATIVE=1 -DBUILD_SHARED_LIBS=yes -DBUILD_TESTING=yes .. > make -j8 > ctest > > Let me know what you think. If you want to use this as the build system > for ntl going forward, then I can add support for the wizard as well. > > Isuru > > > On Sat, Sep 7, 2019 at 10:56 AM Victor Shoup > wrote: > >> I just posted NTL 11.3.4. >> >> Details here [ https://www.shoup.net/ntl/ ]. >> >> This (I hope) fixes the "-lpthread underlinking issue" reported here [ >> https://trac.sagemath.org/ticket/28406 ] and discussed at excessive >> length (mostly due to my own obstinance) here [ >> https://groups.google.com/forum/#!topic/sage-devel/Xjc5BZ9QUFs ]. >> >> My solution was to simply have NTL's makefile pass -lpthread to libtool >> when building the library (but only if the library is shared and >> multithreaded). There is also a way to explicitly override this behavior, >> if that is necessary (but I hope it's not). >> >> If this does not fix the issue, please let me know. >> >> Thanks to everyone for their help in sorting out the problem and for >> putting up with my foot dragging on the issue. >> >> Some day, I have to make NTL's build system more "standard". Some day, I >> have to put NTL on GitHub. Some day, I have to do a lot of things... >> >> -- >> You received this message because you are subscribed to the Google Groups >> "sage-devel" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to sage-...@googlegroups.com . >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/sage-devel/7495bf0a-c2ad-4c8d-a22f-4813c1ed6683%40googlegroups.com >> >> <https://groups.google.com/d/msgid/sage-devel/7495bf0a-c2ad-4c8d-a22f-4813c1ed6683%40googlegroups.com?utm_medium=email&utm_source=footer> >> . >> > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/49d61fcc-4025-428d-8262-eafe4811763b%40googlegroups.com.
[sage-devel] NTL 11.3.4
I just posted NTL 11.3.4. Details here [ https://www.shoup.net/ntl/ ]. This (I hope) fixes the "-lpthread underlinking issue" reported here [ https://trac.sagemath.org/ticket/28406 ] and discussed at excessive length (mostly due to my own obstinance) here [ https://groups.google.com/forum/#!topic/sage-devel/Xjc5BZ9QUFs ]. My solution was to simply have NTL's makefile pass -lpthread to libtool when building the library (but only if the library is shared and multithreaded). There is also a way to explicitly override this behavior, if that is necessary (but I hope it's not). If this does not fix the issue, please let me know. Thanks to everyone for their help in sorting out the problem and for putting up with my foot dragging on the issue. Some day, I have to make NTL's build system more "standard". Some day, I have to put NTL on GitHub. Some day, I have to do a lot of things... -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/7495bf0a-c2ad-4c8d-a22f-4813c1ed6683%40googlegroups.com.
Re: [sage-devel] Re: error building barvinok (sage 8.9.beta8 + system NTL)
I spent a couple of hours experimenting with your patch as well as with the solution of just changing NTL's makefile to stick -lpthread in the invocation of libtool: $(LIBTOOL) --tag=CXX --mode=link $(LINK) $(LIBTOOL_LINK_FLAGS) -o libntl.la $(OBJ:.o=.lo) $(GMP_OPT_LIBDIR) $(GMP_OPT_LIB) $(GF2X_OPT_LIBDIR) $(GF2X_OPT_LIB) $(LDLIBS) -lpthread -rpath $(LIBDIR) -version-info `cat VERSION_INFO` Examining the make output, they both yield essentially the same result. Your libtool patch ends up putting -lpthread in basically the same place. I have tested both approaches in linking another program (without specifying -pthread or -lpthread) and they both worked fine. I wasted a lot of time investigating why both approaches fail when linking a program that uses a static library that depends on NTLI got the error: /usr/lib64/libpthread.so.0: error adding symbols: DSO missing from command line I never really solved that puzzle. Instead of patching libtool (which is harder for me to maintain in the long run), I will just modify NTL's configure script to do the same thing (at least that is something under my direct control). I will modify NTL's config to define a makefile variable PTHREAD_LIB which will be set to -lpthread and passed to libtool when linking, if that seems like the right thing to do. The user running config can manually override PTHREAD_LIB if need be. This was a learning experience. I'm very used to linking static libraries, where you must explicitly list all libraries on the command line. Now dynamic libs come along and offer the feature of listing their own dependencies, which is a feature that build systems have apparently come to rely upon. That was news to me. Another bit of information: the only reason NTL relies on libpthread at all is because it is working around buggy implementations of the C++11 "thread_local" feature. It has been absolutely shocking to me that these bugs have been around for several years, and I'm not sure if they are still around or not...I trust my simple pthread implementation more than the buggy gcc/clang implementations. On Thursday, September 5, 2019 at 6:57:36 PM UTC-4, Dima Pasechnik wrote: > > On Thu, Sep 5, 2019 at 11:43 PM Victor Shoup > wrote: > > > > So NTL's configure script already provides a work-around. > > Just pass LIBTOOL_LINKER_FLAGS=-lpthread to NTL's configure script, > > and the problem goes away. > > No, it won'd magically go away, as one cannot blindly stick in this > `-lpthread` > there. This has already been explained, I think. > > We'd need to find out first whether this needs to be passed to the > configure > script. In particular as NTL provides no way for discovering whether > it is built with > pthreads or not. > E.g. for my task it means to do half a page of ugly hard to write and > maintain autoconf stuff > just because you refuse to apply the patch I already provided and > tested for you? > > We've been sending these dozens of emails back and force here for no > good reason... > > > > > > > > To the extent that NTL's configure interface is already a bit > non-standard, asking > > package managers to do this is probably OK...at least, it's not any > worse than the > > current situation. > > > > At a minimum, I can update NTL's documentation. > > I could also modify the configure script so that this setting is the > default. > > Or I can try to do something "automagical"... > > > > I'd rather do this than patch libtool itself. > > > > > > On Thursday, September 5, 2019 at 10:35:42 AM UTC-4, Antonio Rojas > wrote: > >> > >> > >> > >> El jueves, 5 de septiembre de 2019, 15:51:34 (UTC+2), Victor Shoup > escribió: > >>> > >>> We seem to be talking past each other. > >> > >> > >> Unfortunately it seems so. > >> > >>> It is also true that when I run ldd on libntl.so, I do not see > anything related to pthread. > >>> From the comments I'm reading in > https://trac.sagemath.org/ticket/28406, that seems > >>> to be what is "wrong". > >> > >> > >> Do you seriously not see why this is wrong? This is a textbook case of > underlinking. Your library is calling functions from the libpthread > library, so it *must* link to it. This is not a matter of "conventions" or > "choices", this is how dynamic linking works. If you refuse to acknowledge > that this is a problem then there's certainly nothing else to discuss. > >> > >>> When I actually build a progra
Re: [sage-devel] Re: error building barvinok (sage 8.9.beta8 + system NTL)
I'm really just trying to understand what's going on. So there is a good reason: my own education...although maybe you don't like that reason :-) In fact, I just tested my proposal, and it indeed doesn't work. I am convinced that the patch is the way to go. On Thursday, September 5, 2019 at 6:57:36 PM UTC-4, Dima Pasechnik wrote: > > On Thu, Sep 5, 2019 at 11:43 PM Victor Shoup > wrote: > > > > So NTL's configure script already provides a work-around. > > Just pass LIBTOOL_LINKER_FLAGS=-lpthread to NTL's configure script, > > and the problem goes away. > > No, it won'd magically go away, as one cannot blindly stick in this > `-lpthread` > there. This has already been explained, I think. > > We'd need to find out first whether this needs to be passed to the > configure > script. In particular as NTL provides no way for discovering whether > it is built with > pthreads or not. > E.g. for my task it means to do half a page of ugly hard to write and > maintain autoconf stuff > just because you refuse to apply the patch I already provided and > tested for you? > > We've been sending these dozens of emails back and force here for no > good reason... > > > > > > > > To the extent that NTL's configure interface is already a bit > non-standard, asking > > package managers to do this is probably OK...at least, it's not any > worse than the > > current situation. > > > > At a minimum, I can update NTL's documentation. > > I could also modify the configure script so that this setting is the > default. > > Or I can try to do something "automagical"... > > > > I'd rather do this than patch libtool itself. > > > > > > On Thursday, September 5, 2019 at 10:35:42 AM UTC-4, Antonio Rojas > wrote: > >> > >> > >> > >> El jueves, 5 de septiembre de 2019, 15:51:34 (UTC+2), Victor Shoup > escribió: > >>> > >>> We seem to be talking past each other. > >> > >> > >> Unfortunately it seems so. > >> > >>> It is also true that when I run ldd on libntl.so, I do not see > anything related to pthread. > >>> From the comments I'm reading in > https://trac.sagemath.org/ticket/28406, that seems > >>> to be what is "wrong". > >> > >> > >> Do you seriously not see why this is wrong? This is a textbook case of > underlinking. Your library is calling functions from the libpthread > library, so it *must* link to it. This is not a matter of "conventions" or > "choices", this is how dynamic linking works. If you refuse to acknowledge > that this is a problem then there's certainly nothing else to discuss. > >> > >>> When I actually build a program, either in the build directory using > NTL's makefile with libtool, > >>> or in another directory using a different makefile that uses g++, it > works fine. > >> > >> > >> And we already have two programs that don't work: latte-integrale (al > least the old version which I reported to you a year ago) and barvinok. > And no, building those programs with -pthread is definitely not the > solution: If a library A uses a function from library B and a program C > uses a function from library A but nothing from library B then C does not > have to and should not link to B: it's A's job to link to B. > >> > >>> So my understanding is that whenever you compile a multi-threaded > program > >>> you should pass -pthread to gcc. > >> > >> > >> Correct. But you should *not* have to pass -pthread when you compile a > single-threaded program and happens to use a multi-threaded library, which > is the case here. > > > > -- > > You received this message because you are subscribed to the Google > Groups "sage-devel" group. > > To unsubscribe from this group and stop receiving emails from it, send > an email to sage-...@googlegroups.com . > > To view this discussion on the web visit > https://groups.google.com/d/msgid/sage-devel/71bbcca2-89d0-4c97-b9fd-639cc695bee4%40googlegroups.com. > > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/b25bacdd-50ff-4cd5-b51d-a2864a2d4778%40googlegroups.com.
Re: [sage-devel] Re: error building barvinok (sage 8.9.beta8 + system NTL)
So NTL's configure script already provides a work-around. Just pass LIBTOOL_LINKER_FLAGS=-lpthread to NTL's configure script, and the problem goes away. To the extent that NTL's configure interface is already a bit non-standard, asking package managers to do this is probably OK...at least, it's not any worse than the current situation. At a minimum, I can update NTL's documentation. I could also modify the configure script so that this setting is the default. Or I can try to do something "automagical"... I'd rather do this than patch libtool itself. On Thursday, September 5, 2019 at 10:35:42 AM UTC-4, Antonio Rojas wrote: > > > > El jueves, 5 de septiembre de 2019, 15:51:34 (UTC+2), Victor Shoup > escribió: >> >> We seem to be talking past each other. >> > > Unfortunately it seems so. > > It is also true that when I run ldd on libntl.so, I do not see anything >> related to pthread. >> From the comments I'm reading in https://trac.sagemath.org/ticket/28406 >> <https://www.google.com/url?q=https%3A%2F%2Ftrac.sagemath.org%2Fticket%2F28406&sa=D&sntz=1&usg=AFQjCNGrwfVRTUQ4wc8gDByCwBimhxvMtA>, >> >> that seems >> to be what is "wrong". >> > > Do you seriously not see why this is wrong? This is a textbook case of > underlinking. Your library is calling functions from the libpthread > library, so it *must* link to it. This is not a matter of "conventions" or > "choices", this is how dynamic linking works. If you refuse to acknowledge > that this is a problem then there's certainly nothing else to discuss. > > When I actually build a program, either in the build directory using NTL's >> makefile with libtool, >> or in another directory using a different makefile that uses g++, it >> works fine. >> > > And we already have two programs that don't work: latte-integrale (al > least the old version which I reported to you a year ago) and barvinok. > And no, building those programs with -pthread is definitely not the > solution: If a library A uses a function from library B and a program C > uses a function from library A but nothing from library B then C does not > have to and should not link to B: it's A's job to link to B. > > So my understanding is that whenever you compile a multi-threaded program >> you should pass -pthread to gcc. >> > > Correct. But you should *not* have to pass -pthread when you compile a > single-threaded program and happens to use a multi-threaded library, which > is the case here. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/71bbcca2-89d0-4c97-b9fd-639cc695bee4%40googlegroups.com.
[sage-devel] PGFFT
I updated my PGFFT (Pretty Good FFT) library. Details here: https://www.shoup.net/PGFFT/ It is now almost as fast or faster than FFTW on transforms up to 100K or so, at least on AVX or AVX2 machines. I've posted some more timings. If anyone is curious, the only reason I did this is that for another project, I needed a reasonable performant FFT with a permissive license (like BSD), and after spending a couple of weeks testing out various possibilities, I gave up, and just re-purposed NTL's "small prime" FFT (aka NTT) for complex numbers. So there it is :-) I'm sure if I look harder, I can find other libraries out there that are just as good or much better, also with a permissive license... -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/9d312ac9-e539-4c35-b45c-344f6d5df4b1%40googlegroups.com.
Re: [sage-devel] Re: error building barvinok (sage 8.9.beta8 + system NTL)
Sigh. "...a textbook case of underlinking..." I guess I never read that textbook. I guess I just didn't know there was a whole community of people and projects who don't like putting -pthread in their makefiles. I feel like this is becoming a religious war. If it will keep the peace, I will patch my libbtool based on Dima's suggestion. Someday, I will make NTL's build system more conventional...maybe I can find a student who can help me out. On Thursday, September 5, 2019 at 10:35:42 AM UTC-4, Antonio Rojas wrote: > > > > El jueves, 5 de septiembre de 2019, 15:51:34 (UTC+2), Victor Shoup > escribió: >> >> We seem to be talking past each other. >> > > Unfortunately it seems so. > > It is also true that when I run ldd on libntl.so, I do not see anything >> related to pthread. >> From the comments I'm reading in https://trac.sagemath.org/ticket/28406 >> <https://www.google.com/url?q=https%3A%2F%2Ftrac.sagemath.org%2Fticket%2F28406&sa=D&sntz=1&usg=AFQjCNGrwfVRTUQ4wc8gDByCwBimhxvMtA>, >> >> that seems >> to be what is "wrong". >> > > Do you seriously not see why this is wrong? This is a textbook case of > underlinking. Your library is calling functions from the libpthread > library, so it *must* link to it. This is not a matter of "conventions" or > "choices", this is how dynamic linking works. If you refuse to acknowledge > that this is a problem then there's certainly nothing else to discuss. > > When I actually build a program, either in the build directory using NTL's >> makefile with libtool, >> or in another directory using a different makefile that uses g++, it >> works fine. >> > > And we already have two programs that don't work: latte-integrale (al > least the old version which I reported to you a year ago) and barvinok. > And no, building those programs with -pthread is definitely not the > solution: If a library A uses a function from library B and a program C > uses a function from library A but nothing from library B then C does not > have to and should not link to B: it's A's job to link to B. > > So my understanding is that whenever you compile a multi-threaded program >> you should pass -pthread to gcc. >> > > Correct. But you should *not* have to pass -pthread when you compile a > single-threaded program and happens to use a multi-threaded library, which > is the case here. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/4c15db12-02a6-4ee3-ad39-8bf9245812f3%40googlegroups.com.
Re: [sage-devel] Re: error building barvinok (sage 8.9.beta8 + system NTL)
We seem to be talking past each other. Here is my experience. My OS: Red Hat Enterprise Linux Server 7.7 (Maipo) My compiler: gcc 4.8.5 (yes, it's old!) Here is how I built NTL: $ ./configure SHARED=on PREFIX= /home/gid-shoupv/sw $ make $ make install Then, in another directory, where I am using NTL as a library in another program: $ g++ -std=c++11 -pthread -g -O2 -DFHE_THREAD -o Test_thinboot_x Test_thinboot.cpp fhe.a -lntl -lgmp -lm Then, ldd says: $ ldd Test_thinboot_x linux-vdso.so.1 => (0x7ffef18a) libntl.so.40 => /home/gid-shoupv/sw/lib/libntl.so.40 (0x7f51044d4000) libgmp.so.10 => /usr/local/lib/libgmp.so.10 (0x7f510425e000) libstdc++.so.6 => /lib64/libstdc++.so.6 (0x7f5103f45000) libm.so.6 => /lib64/libm.so.6 (0x7f5103c43000) libgcc_s.so.1 => /lib64/libgcc_s.so.1 (0x7f5103a2c000) libpthread.so.0 => /lib64/libpthread.so.0 (0x7f510381) libc.so.6 => /lib64/libc.so.6 (0x7f5103442000) /lib64/ld-linux-x86-64.so.2 (0x7f5104978000) This is what I mean by "everything just works". Also, when I build NTL with SHARED=on, if I build test programs in the build directory using the makefile there, then, for example, I get: $ make ThreadTest ./libtool-build/libtool --tag=CXX --mode=link g++ -I../include -I. -g -O2 -std=c++11 -pthread -march=native -o ThreadTest ThreadTest.cpp libntl.la #LSHAR libtool: link: g++ -I../include -I. -g -O2 -std=c++11 -pthread -march=native -o .libs/ThreadTest ThreadTest.cpp ./.libs/libntl.so -lgmp -pthread -Wl,-rpath -Wl,/home/gid-shoupv/sw/lib This works just fine: the program ThreadTest compiles, links, and runs just fine, but for some reason ldd says "not a dynamic executable". I'm not sure what's up with that. A quick google search indicates that ldd can sometimes be buggy in this way. This may not mean anything regarding the issues we are discussing. Now, Antonio posted some output that showed that when libtool is used to create the library, it uses g++ with -nostdlib. Indeed, that is what I see as well. But from where I'm sitting, this is not a problem. When I actually build a program, either in the build directory using NTL's makefile with libtool, or in another directory using a different makefile that uses g++, it works fine. It is also true that when I run ldd on libntl.so, I do not see anything related to pthread. >From the comments I'm reading in https://trac.sagemath.org/ticket/28406 <https://www.google.com/url?q=https%3A%2F%2Ftrac.sagemath.org%2Fticket%2F28406&sa=D&sntz=1&usg=AFQjCNGrwfVRTUQ4wc8gDByCwBimhxvMtA>, that seems to be what is "wrong". Looking closer at the comments there, I see that the command that does not as expected is this: $ gcc -o conftest -g -O2 -L/opt/sage/local/lib -Wl,-rpath,/opt/sage/local/lib conftest.c -lntl -lgmp That this should work is contrary to my understanding of the "-pthread" flag. man gcc says: -pthread Adds support for multithreading with the pthreads library. This option sets flags for both the preprocessor and linker. So my understanding is that whenever you compile a multi-threaded program you should pass -pthread to gcc. To me, this has nothing to do with libtool. Maybe, just maybe, the real "issue" is this: some build systems do not pass "-pthread" to gcc, but rather, they depend on libntl.so to contain a reference to libpthreads.so. If that is true, then I guess this "issue" is really just one of what the proper conventions are for who is responsible to passing the right flags to gcc. There is never going to be a perfect solution to this. For example, on some compiles, you have to pass "-std=c++11" to gcc in order to compile a program that includes NTL header files. That's just one more thing to keep straight. So I'm not convinced that patching libtool in NTL is the right thing to do. Before I fix anything, I'd like to know what it is I'm actually fixing. But probably if your build system needs t follow specific conventions not supported by libtool, then you can build NTL using a custom libtool that supports your conventions. That's probably where this ends. On Thursday, September 5, 2019 at 2:48:58 AM UTC-4, Dima Pasechnik wrote: > > > > On Thu, 5 Sep 2019 at 05:07, Victor Shoup > > wrote: > >> Please see comments/questions below... >> >> On Wednesday, September 4, 2019 at 6:04:42 AM UTC-4, Dima Pasechnik wrote: >>> >>> On Tue, Sep 3, 2019 at 2:21 PM Victor Shoup wrote: >>> > >>> >>> > When I compile a program that uses NTL, I always pass -pthread to g++. >>> > Doesn't that automatically cause the necessary pthread-specific >>> library to be linked in? >>> >>> it does, if you don&#x
Re: [sage-devel] Re: error building barvinok (sage 8.9.beta8 + system NTL)
Please see comments/questions below... On Wednesday, September 4, 2019 at 6:04:42 AM UTC-4, Dima Pasechnik wrote: > > On Tue, Sep 3, 2019 at 2:21 PM Victor Shoup > wrote: > > > > > When I compile a program that uses NTL, I always pass -pthread to g++. > > Doesn't that automatically cause the necessary pthread-specific library > to be linked in? > > it does, if you don't use libtool to link (and typically one would > link an executable with > an explicit call to g++). > So, based on that comment, it seems that there is no problem if you link with g++ rather than libtool. But who or what uses libtool to link? I would never have thought of doing that, as I thought libtool was a tool for creating libraries, not linking programs. > the problem is that libtool strips away the -pthread flag. > As long as you don't use it, there is no problem. See > > https://www.gnu.org/software/libtool/manual/libtool.html#Stripped-link-flags > "13.1 Why does libtool strip link flags when creating a library? > > When creating a shared library, but not when compiling or creating a > program, libtool drops some flags from the command line provided by > the user. This is done because flags unknown to libtool may interfere > with library creation or require additional support from libtool, and > because omitting flags is usually the conservative choice for a > successful build." > > This is confusing. If you use libtool to link, then the above quote would suggest that in that context, libtool should not strip away any linker flags. But you seem to be saying that it does. So...I am still confused. Regarding the libtool that I am bundling with NTL: 1) is it stripping some flags during compilation that should not be stripped? 2) is it stripping some flags during linking that should not be stripped? Again, when I build and install a shared NTL on a linux system, everything works fine. So I'm not even sure what the problem is: I can build it and link to it in the build directory using libtool. I can install it using libtool somewhere else and later link to it using g++. What am I missing?!? -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/15c39061-e49d-4c6b-951b-6763aaea5dd0%40googlegroups.com.
Re: [sage-devel] Re: error building barvinok (sage 8.9.beta8 + system NTL)
So, I'm willing to patch libtool using your patch, as you suggest. Just to confirm: I just replace ltmain.sh in libtool-origin with the patched version, and that's it. I have another question... I've installed NTL on Linux with libtool, and I've never had a problem. When I compile a program that uses NTL, I always pass -pthread to g++. Doesn't that automatically cause the necessary pthread-specific library to be linked in? As such, I'm still kind of confused as to what the problem is. Related to that, from what I read, -lpthread is less standard than -pthread: again, the latter is supposed to add the necessary linker flags. Thus, I'm still a bit hesitant to do this. I guess I still don't entirely understand the model. On Monday, September 2, 2019 at 6:24:00 PM UTC-4, Dima Pasechnik wrote: > > On Tue, Sep 3, 2019 at 1:05 AM Victor Shoup > wrote: > > > > OK. So this is really a bug in libtool. > it's a feature :-) > It's not hard to explicitly pass extra libraries to link to libtool, > and thus it's still like this. > > > It seems to me that even if I used autotools for everything, the same > problem would persist > > without a patch to ltmain.sh. > > > > Is that right? > > > no, if you use autotools, you'd just add a couple of macros to deal with > threads to configure.ac, and the rest will be done correctly, > as autotools are aware of this bug/feature of libtool and know > what to do. > > > > > On Monday, September 2, 2019 at 4:42:44 PM UTC-4, Dima Pasechnik wrote: > >> > >> On Mon, Sep 2, 2019 at 11:37 PM Victor Shoup wrote: > >> > > >> > A clarification and a question... > >> > > >> > NTL's config system does not use a pre-built ibtool script. Rather, > it builds a customized libtool by running a configure script on the host > machine, so it should, in principle, be using a libtool script that is > properly configured for the host machine. > >> > > >> > The configure script itself was built on a linux machine with > up-to-date autotools using the following configure.ac file: > >> > > >> > AC_INIT(ntl-libtool, 1.0) > >> > AM_INIT_AUTOMAKE([foreign]) > >> > AC_CONFIG_FILES([Makefile]) > >> > LT_INIT > >> > AC_PROG_CXX > >> > AC_PROG_CC > >> > AC_PROG_LIBTOOL > >> > AC_OUTPUT > >> > > >> > I don't remember where I got this...but it was from somebody who > seemed to know what they were talking about. > >> > > >> > Maybe the logic of this configure.ac file is not right? > >> > Any thoughts on this? > >> > >> it looks OK, and the libtool you get will ignore -pthread option for > gcc/g++, > >> (as this is by design), unless you apply the patch I posted earlier > before > >> buiding it. > >> > >> > >> > > >> > > >> > > >> > On Wednesday, August 28, 2019 at 9:55:38 AM UTC-4, vdelecroix wrote: > >> >> > >> >> Victor, as far as I understand the main configuration script of ntl > >> >> is the perl DoConfig script. It has nothing to do with libtool. > libtool > >> >> is robust if you let it handle the configuration. It will not try to > >> >> fix a given one. > >> >> > >> >> In a libtool configure.ac script you would just have a directive > >> >> AC_CHECK_LIB for pthread. > >> >> > >> >> In short, I would suggest > >> >> > >> >> 3) Replace DoConfig by a configure.ac script > >> >> > >> >> Vincent > >> >> > >> >> Le 28/08/2019 à 15:15, Victor Shoup a écrit : > >> >> > Thanks. I guess what I'm asking for is a solution. From what you > say here, > >> >> > and what is said in the links, the problem seems to be a bug in > libtool, > >> >> > not NTL. So a solution would be, either: > >> >> > 1) a patch other type of libtool workaround, or > >> >> > 2) an alternative to libtool. > >> >> > I though the whole point of libtool was to take care of all this > nonsense, > >> >> > and if it's not doing that, then > >> >> > it seems kind of pointless. > >> >> > > >> >> > On Tuesday, August 27, 2019 at 1:42:51 PM UTC-4, Antonio Rojas > wrote: > >> >
Re: [sage-devel] Re: error building barvinok (sage 8.9.beta8 + system NTL)
OK. So this is really a bug in libtool. It seems to me that even if I used autotools for everything, the same problem would persist without a patch to ltmain.sh. Is that right? On Monday, September 2, 2019 at 4:42:44 PM UTC-4, Dima Pasechnik wrote: > > On Mon, Sep 2, 2019 at 11:37 PM Victor Shoup > wrote: > > > > A clarification and a question... > > > > NTL's config system does not use a pre-built ibtool script. Rather, it > builds a customized libtool by running a configure script on the host > machine, so it should, in principle, be using a libtool script that is > properly configured for the host machine. > > > > The configure script itself was built on a linux machine with up-to-date > autotools using the following configure.ac file: > > > > AC_INIT(ntl-libtool, 1.0) > > AM_INIT_AUTOMAKE([foreign]) > > AC_CONFIG_FILES([Makefile]) > > LT_INIT > > AC_PROG_CXX > > AC_PROG_CC > > AC_PROG_LIBTOOL > > AC_OUTPUT > > > > I don't remember where I got this...but it was from somebody who seemed > to know what they were talking about. > > > > Maybe the logic of this configure.ac file is not right? > > Any thoughts on this? > > it looks OK, and the libtool you get will ignore -pthread option for > gcc/g++, > (as this is by design), unless you apply the patch I posted earlier before > buiding it. > > > > > > > > > > On Wednesday, August 28, 2019 at 9:55:38 AM UTC-4, vdelecroix wrote: > >> > >> Victor, as far as I understand the main configuration script of ntl > >> is the perl DoConfig script. It has nothing to do with libtool. libtool > >> is robust if you let it handle the configuration. It will not try to > >> fix a given one. > >> > >> In a libtool configure.ac script you would just have a directive > >> AC_CHECK_LIB for pthread. > >> > >> In short, I would suggest > >> > >> 3) Replace DoConfig by a configure.ac script > >> > >> Vincent > >> > >> Le 28/08/2019 à 15:15, Victor Shoup a écrit : > >> > Thanks. I guess what I'm asking for is a solution. From what you say > here, > >> > and what is said in the links, the problem seems to be a bug in > libtool, > >> > not NTL. So a solution would be, either: > >> > 1) a patch other type of libtool workaround, or > >> > 2) an alternative to libtool. > >> > I though the whole point of libtool was to take care of all this > nonsense, > >> > and if it's not doing that, then > >> > it seems kind of pointless. > >> > > >> > On Tuesday, August 27, 2019 at 1:42:51 PM UTC-4, Antonio Rojas wrote: > >> >> > >> >> > >> >> > >> >> El martes, 27 de agosto de 2019, 16:25:12 (UTC+2), Victor Shoup > escribió: > >> >>> > >> >>> I reviewed some comments which mentioned a problem with ntl and > threads. > >> >>> I’m happy to fix that, but I don’t think I understand what the > issue is. > >> >>> Can anyone explain? Thanks. > >> >> > >> >> > >> >> Hi Victor, > >> >> IIRC I reported this to you about a year ago. The problem is that > you are > >> >> using libtool as a build command, which calls the compiler with the > >> >> -nostdlib flag, which in turn overrides the -pthread flag, so the > binaries > >> >> end up not being linked to libpthread. See eg. [1][2] for more info. > >> >> > >> >> [1] https://bugzilla.redhat.com/show_bug.cgi?id=661333 > >> >> [2] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25460 > >> >> > >> > > > > > -- > > You received this message because you are subscribed to the Google > Groups "sage-devel" group. > > To unsubscribe from this group and stop receiving emails from it, send > an email to sage-...@googlegroups.com . > > To view this discussion on the web visit > https://groups.google.com/d/msgid/sage-devel/30264407-95c4-4057-a7a8-5dc0ea8b6437%40googlegroups.com. > > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/77278251-5ad4-42a2-a9f0-c0bf322fb972%40googlegroups.com.
Re: [sage-devel] Re: error building barvinok (sage 8.9.beta8 + system NTL)
A clarification and a question... NTL's config system does not use a pre-built ibtool script. Rather, it builds a customized libtool by running a configure script on the host machine, so it should, in principle, be using a libtool script that is properly configured for the host machine. The configure script itself was built on a linux machine with up-to-date autotools using the following configure.ac file: AC_INIT(ntl-libtool, 1.0) AM_INIT_AUTOMAKE([foreign]) AC_CONFIG_FILES([Makefile]) LT_INIT AC_PROG_CXX AC_PROG_CC AC_PROG_LIBTOOL AC_OUTPUT I don't remember where I got this...but it was from somebody who seemed to know what they were talking about. Maybe the logic of this configure.ac file is not right? Any thoughts on this? On Wednesday, August 28, 2019 at 9:55:38 AM UTC-4, vdelecroix wrote: > > Victor, as far as I understand the main configuration script of ntl > is the perl DoConfig script. It has nothing to do with libtool. libtool > is robust if you let it handle the configuration. It will not try to > fix a given one. > > In a libtool configure.ac script you would just have a directive > AC_CHECK_LIB for pthread. > > In short, I would suggest > > 3) Replace DoConfig by a configure.ac script > > Vincent > > Le 28/08/2019 à 15:15, Victor Shoup a écrit : > > Thanks. I guess what I'm asking for is a solution. From what you say > here, > > and what is said in the links, the problem seems to be a bug in libtool, > > not NTL. So a solution would be, either: > > 1) a patch other type of libtool workaround, or > > 2) an alternative to libtool. > > I though the whole point of libtool was to take care of all this > nonsense, > > and if it's not doing that, then > > it seems kind of pointless. > > > > On Tuesday, August 27, 2019 at 1:42:51 PM UTC-4, Antonio Rojas wrote: > >> > >> > >> > >> El martes, 27 de agosto de 2019, 16:25:12 (UTC+2), Victor Shoup > escribió: > >>> > >>> I reviewed some comments which mentioned a problem with ntl and > threads. > >>> I’m happy to fix that, but I don’t think I understand what the issue > is. > >>> Can anyone explain? Thanks. > >> > >> > >> Hi Victor, > >> IIRC I reported this to you about a year ago. The problem is that you > are > >> using libtool as a build command, which calls the compiler with the > >> -nostdlib flag, which in turn overrides the -pthread flag, so the > binaries > >> end up not being linked to libpthread. See eg. [1][2] for more info. > >> > >> [1] https://bugzilla.redhat.com/show_bug.cgi?id=661333 > >> [2] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25460 > >> > > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/30264407-95c4-4057-a7a8-5dc0ea8b6437%40googlegroups.com.
[sage-devel] PGFFT
PGFFT is a "pretty good FFT" for double-precision complex numbers, written in C++. It's main selling points are (1) it's not too slow, and (2) it's available under a BSD license. Details here: https://www.shoup.net/PGFFT/ -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/19946e29-2933-4825-9a76-b98ea7ed2ca2%40googlegroups.com.
[sage-devel] NTL 11.3.3
I've uploaded a new version of NTL. Details on changes are here: https://www.shoup.net/ntl/doc/tour-changes.html -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/9bc63254-7d6a-4cec-8e3a-0c004197a14f%40googlegroups.com.
Re: [sage-devel] Re: error building barvinok (sage 8.9.beta8 + system NTL)
No. System libtool is not the default. It is done the way it is because of advice I got from some other folks who knew more about these things than I did. Try configure with LIBTOOL= On Friday, August 30, 2019 at 4:52:37 AM UTC-4, Dima Pasechnik wrote: > > On Thu, Aug 29, 2019 at 5:13 PM Victor Shoup > wrote: > > > > Thanks for all of the thoughtful replies. > > > > I don't have time to rewrite the config script any time soon. > > According to the libtool documentation, it is supposed to be usable > > without relying on automake. > > NTL's config script allows you to override the default libtool with a > system libtool, > > so that seems like the simplest way to deal with this for now. > > I must say I didn't verify that in my experiment the bundled libtool was > used > (I thought it's the default, but I don't know). > > If it's not the case then on the Debian 10 (buster) system I tried running > this, > the system libtool is already fixed in some way to fix that `-pthread` > issue. > (and not that the patch I provided actually does the job) > > Dima > > > > If I rewrite any of NTL's config scripts, it will likely be to move it > over to cmake. > > > > > > On Thursday, August 29, 2019 at 3:43:33 AM UTC-4, Antonio Rojas wrote: > >> > >> > >> > >> El jueves, 29 de agosto de 2019, 0:06:49 (UTC+2), Dima Pasechnik > escribió: > >>> > >>> > >>> > Relying on patched bundled copies of dependencies is very much > frowned upon by distros. It would be much preferable to make this work with > unmodified libtool, which may be provided by the distribution. > >>> > >>> Well, libtool is just a shell script, more or less. NTL isn't unique > >>> in shipping its own version. > >>> Does Arch use its own libtool when building NTL, or the bundled one? > >>> > >> > >> Regardless of how simple if may be, bundling dependencies increases the > risk of introducing bugs and inconsistencies between distro packages. On > Arch we are building ntl using system's libtool. > >> Anyway, whatever solution is adopted is not such a big deal since there > is an easy workaround (pass LDLIBS='-lpthread' to configure) that distros > can keep using - It would just be nicer to fix it without resorting to > patched dependencies IMO. > > > > -- > > You received this message because you are subscribed to the Google > Groups "sage-devel" group. > > To unsubscribe from this group and stop receiving emails from it, send > an email to sage-...@googlegroups.com . > > To view this discussion on the web visit > https://groups.google.com/d/msgid/sage-devel/43feca19-aecc-42f4-a8a3-0e15472ada37%40googlegroups.com. > > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/8c18fca5-33e8-4c3a-adb1-b4d1506e1efa%40googlegroups.com.
Re: [sage-devel] Re: error building barvinok (sage 8.9.beta8 + system NTL)
Thanks for all of the thoughtful replies. I don't have time to rewrite the config script any time soon. According to the libtool documentation, it is supposed to be usable without relying on automake. NTL's config script allows you to override the default libtool with a system libtool, so that seems like the simplest way to deal with this for now. If I rewrite any of NTL's config scripts, it will likely be to move it over to cmake. On Thursday, August 29, 2019 at 3:43:33 AM UTC-4, Antonio Rojas wrote: > > > > El jueves, 29 de agosto de 2019, 0:06:49 (UTC+2), Dima Pasechnik escribió: >> >> >> > Relying on patched bundled copies of dependencies is very much frowned >> upon by distros. It would be much preferable to make this work with >> unmodified libtool, which may be provided by the distribution. >> >> Well, libtool is just a shell script, more or less. NTL isn't unique >> in shipping its own version. >> Does Arch use its own libtool when building NTL, or the bundled one? >> >> > Regardless of how simple if may be, bundling dependencies increases the > risk of introducing bugs and inconsistencies between distro packages. On > Arch we are building ntl using system's libtool. > Anyway, whatever solution is adopted is not such a big deal since there is > an easy workaround (pass LDLIBS='-lpthread' to configure) that distros can > keep using - It would just be nicer to fix it without resorting to patched > dependencies IMO. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/43feca19-aecc-42f4-a8a3-0e15472ada37%40googlegroups.com.
[sage-devel] Re: error building barvinok (sage 8.9.beta8 + system NTL)
Thanks. I guess what I'm asking for is a solution. From what you say here, and what is said in the links, the problem seems to be a bug in libtool, not NTL. So a solution would be, either: 1) a patch other type of libtool workaround, or 2) an alternative to libtool. I though the whole point of libtool was to take care of all this nonsense, and if it's not doing that, then it seems kind of pointless. On Tuesday, August 27, 2019 at 1:42:51 PM UTC-4, Antonio Rojas wrote: > > > > El martes, 27 de agosto de 2019, 16:25:12 (UTC+2), Victor Shoup escribió: >> >> I reviewed some comments which mentioned a problem with ntl and threads. >> I’m happy to fix that, but I don’t think I understand what the issue is. >> Can anyone explain? Thanks. > > > Hi Victor, > IIRC I reported this to you about a year ago. The problem is that you are > using libtool as a build command, which calls the compiler with the > -nostdlib flag, which in turn overrides the -pthread flag, so the binaries > end up not being linked to libpthread. See eg. [1][2] for more info. > > [1] https://bugzilla.redhat.com/show_bug.cgi?id=661333 > [2] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=25460 > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/8399069c-b8db-4ca5-ba63-54e14aba890e%40googlegroups.com.
[sage-devel] error building barvinok (sage 8.9.beta8 + system NTL)
I reviewed some comments which mentioned a problem with ntl and threads. I’m happy to fix that, but I don’t think I understand what the issue is. Can anyone explain? Thanks. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/498a5033-c89e-48bf-a520-6dd7f6cac6b0%40googlegroups.com.
[sage-devel] NTL 11.3.2
I just uploaded NTL 11.3.2 to https://www.shoup.net/ntl/ This fixes a performance issue in the ZZ PowerMod function (which also affects the prime testing and generating function). -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] NTL 11.3.2
I just posted NTL 11.3.2 to http://www.shoup.net/ntl This fixes a performance issue related the ZZ PowerMod function (and by implication primality testing and generating functions). -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] NTL 11.3.1
I just release NTL 11.3.1, which fixes a bug. See http://www.shoup.net/ntl/doc/tour-changes.html -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: zn_poly status?
I didn't run "make tune"...I guess I should to make things more fair. So I downloaded the version of zn_poly from https://gitlab.com/sagemath/zn_poly <https://www.google.com/url?q=https%3A%2F%2Fgitlab.com%2Fsagemath%2Fzn_poly&sa=D&sntz=1&usg=AFQjCNHKV7CN7KiCz4isAXYO88AhVo0zNg> I then built and installed this version after running make tune and tune, as per the instructions in the zn_poly README. I then re-ran the comparison of non-AVX NTL vs zn_poly. The results are almost identical: 512 0.70854 768 0.846024 1024 0.922126 1536 0.920149 2048 0.96085 3072 0.980663 4096 1.0842 6144 1.33045 8192 1.36914 12288 1.63375 16384 1.46481 24576 1.37829 32768 1.43536 49152 1.35335 65536 1.41785 98304 1.48913 131072 1.42141 196608 1.36 262144 1.42652 393216 1.61358 About the AVX-based implementation: it restricts the size of the moduli to <= 50 bits, as opposed to 60 (or 62) in the normal implementation. And because of CPU throttling, it can even slow down some computations. On Tuesday, September 11, 2018 at 10:31:16 AM UTC-4, Erik Bray wrote: > > On Tue, Sep 11, 2018 at 4:14 PM Victor Shoup > wrote: > > > > I got curious, so I collected some data. Here are timing results > comparing NTL's zz_pX multiplication > > to zn_poly's zn_array_mul. For various values of n, I multiplied > polynomials of degree < n > > modulo a 50 bit number. The values of n are powers of 2 and halfway > between powers of 2, > > ranging between 512 and 512K. > > Both NTL and zn_poly were compiled using their default configurations. > > By "default configurations" did you run `make tune` for zn_poly? > > > One can also compile NTL with an option that enables an AVX-based FFT > implementation. > > With that option set, the numbers look like this. > > The AVX support alone would seem like a major boon. > > > If anyone wants to the program I used for timing, let me know. > > This is not my wheelhouse, so I'm not invested beyond the fact that > zn_poly is currently supported. But thanks! > > If others want to look into using NTL to replace zn_poly in Sage they > should work on that and see if the benefits hold up. > > > > On Friday, September 7, 2018 at 9:53:43 AM UTC-4, Erik Bray wrote: > >> > >> Hi all, > >> > >> Does anyone know what that current status is of the upstream zn_poly > >> package? According to its website > >> http://cims.nyu.edu/~harvey/zn_poly/ it is "no longer maintained", > >> though it has been re-released under a BSD-compatible license. > >> > >> Since its last upstream release the package for it in Sage has > >> accumulated a number of patches as well, and I believe I may need to > >> add one more patch to it for building properly on Cygwin :( See > >> https://trac.sagemath.org/ticket/26050 > >> > >> If it's alright, I would propose creating a new repository for it > >> under the sagemath gitlab organization (or GitHub) which would become > >> the new "upstream" for zn_poly. Then we can merge in all these > >> patches; maybe even implement a new, more standard build system (I > >> would be happy to do this). In fact the current "build system" is > >> going to have problems long-term, as it currently consists primarily > >> of a Python script that will not work, as written, on Python 3. > > > > -- > > You received this message because you are subscribed to the Google > Groups "sage-devel" group. > > To unsubscribe from this group and stop receiving emails from it, send > an email to sage-devel+...@googlegroups.com . > > To post to this group, send email to sage-...@googlegroups.com > . > > Visit this group at https://groups.google.com/group/sage-devel. > > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: zn_poly status?
I got curious, so I collected some data. Here are timing results comparing NTL's zz_pX multiplication to zn_poly's zn_array_mul. For various values of n, I multiplied polynomials of degree < n modulo a 50 bit number. The values of n are powers of 2 and halfway between powers of 2, ranging between 512 and 512K. Both NTL and zn_poly were compiled using their default configurations. Timings were done on a Skylake Xeon using gcc 8.2.0. Each row reports n and the ratio (time for zn_poly)/(time for NTL). So a ratio > 1 means NTL is faster. Also, by now, NTL implements a divide-and-conquer style truncated FFT, using code some of which is ultimately derived from some other code originally written by David Harvey (fft62). 512 0.706683 768 0.84687 1024 0.922457 1536 0.923881 2048 1.02458 3072 0.982044 4096 1.0894 6144 1.32346 8192 1.33724 12288 1.61943 16384 1.44681 24576 1.35887 32768 1.43008 49152 1.34462 65536 1.40433 98304 1.48556 131072 1.42532 196608 1.3503 262144 1.43245 393216 1.61353 One can also compile NTL with an option that enables an AVX-based FFT implementation. With that option set, the numbers look like this. 512 1.30262 768 1.45693 1024 1.60583 1536 1.46475 2048 1.58405 3072 1.6219 4096 1.78167 6144 2.1571 8192 2 12288 2.52612 16384 2.25737 24576 2.25134 32768 2.32498 49152 2.28747 65536 2.15306 98304 2.52464 131072 2.18056 196608 2.22606 262144 2.13347 393216 2.56471 If anyone wants to the program I used for timing, let me know. On Friday, September 7, 2018 at 9:53:43 AM UTC-4, Erik Bray wrote: > > Hi all, > > Does anyone know what that current status is of the upstream zn_poly > package? According to its website > http://cims.nyu.edu/~harvey/zn_poly/ it is "no longer maintained", > though it has been re-released under a BSD-compatible license. > > Since its last upstream release the package for it in Sage has > accumulated a number of patches as well, and I believe I may need to > add one more patch to it for building properly on Cygwin :( See > https://trac.sagemath.org/ticket/26050 > > If it's alright, I would propose creating a new repository for it > under the sagemath gitlab organization (or GitHub) which would become > the new "upstream" for zn_poly. Then we can merge in all these > patches; maybe even implement a new, more standard build system (I > would be happy to do this). In fact the current "build system" is > going to have problems long-term, as it currently consists primarily > of a Python script that will not work, as written, on Python 3. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] NTL 11.3.0
I just uploaded NTL 11.3.0 to https://www.shoup.net/ntl/ Brief summary of what's new: - An AVX-based small-prime FFT - For a variety of reasons, this is an experimental feature that is not enabled by default. - Works with both AVX2 and AVX512. - It can give a 2-3x speedup for the small-prime FFT itself, but it can actually slow other things down, like the CRT code. It's a work in progress. To really get an overall speedup, I have to come up with a way to make the CRT code also exploit AVX instructions. - AVX512 integration in the Mat algorithms (which already use AVX). - Fast GCD and XGCD algorithms for GF2EX, zz_pEX, and ZZ_pEX. Thanks to Luis Felipe Tabera Alonso for porting and testing. So now all of NTL's classes for polynomials over finite fields come equipped with a fast GCD. See https://www.shoup.net/ntl/doc/tour-changes.html for more details. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] NTL 11.2.1
I just uploaded NTL 11.2.1 to http://www.shoup.net This fixes an embarrassing bug, which slipped into NTL 11.2.0. Any installations of NTL 11.2.0 should be replaced as soon as possible with NTL 11.2.1. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: NTL 11.2.0
Bill, Above the diagonal, I believe Flint is using a Kronecker substitution algorithm, while NTL is using a multi-modular FFT. NTL always outperformed Flint in this region. It is the region below the diagonal where both are using Schoenhage-Strassen, and there you can see that NTL still lags behind Flint somewhat, though not as much as it used to. The benchmark programs are available on the NTL web site, and I encourage anyone who wants to run similar benchmarks on a different platform to do so, and to verify that the benchmark software is fair. -Victor On Monday, July 9, 2018 at 8:33:12 AM UTC-4, Bill Hart wrote: > > These are ery interesting timings. In the region above the diagonal (and > sufficiently far to the right - degree 12 I think), I believe we still use > the SSA algorithm directly for polynomial arithmetic over Z. So your > timings indicate that you are actually beating the Flint FFT directly. > > This is quite remarkable given the work that went into it on in Flint (it > was already significantly faster than the FFT's in Magma and GMP, and > faster than the Gaudry, Kruppa, Zimmermann FFT. > > I congratulate you on what must be some truly impressive work. (I keep > telling whoever will listen that we should spend some time trying to catch > back up with the NTL benchmarks you have been publishing, but there seems > to be little opportunity to work on such projects these days, and there > seems to be a real shortage of young people taking on challenges like this. > We do know what needs to be done. It's more an issue of finding people who > could actually carry out the work.) > > Anyway, thanks again for the impressive work you've been doing on NTL, for > making your code Open Source, so that we can all learn from it, and for the > benchmarks you have been making available! > > Bill. > > On Saturday, 7 July 2018 20:39:59 UTC+2, Victor Shoup wrote: >> >> I just released NTL 11.2.0 at http://www.shoup.net/ntl >> >> The main change is a new and improved implementation of the >> Schoenhage-Strassen FFT for multiplication of polynomials over the >> integers. The new implementation includes a truncated FFT algorithm, the >> "sqrt 2" trick, and better engineered low-level "butterfly" code. See >> http://www.shoup.net/ntl/doc/tour-changes.html for details, including >> some benchmarks. >> >> Also see http://www.shoup.net/ntl/benchmarks.pdf for an updated version >> of NTL vs FLINT report. >> > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] NTL 11.2.0
I just released NTL 11.2.0 at http://www.shoup.net/ntl The main change is a new and improved implementation of the Schoenhage-Strassen FFT for multiplication of polynomials over the integers. The new implementation includes a truncated FFT algorithm, the "sqrt 2" trick, and better engineered low-level "butterfly" code. See http://www.shoup.net/ntl/doc/tour-changes.html for details, including some benchmarks. Also see http://www.shoup.net/ntl/benchmarks.pdf for an updated version of NTL vs FLINT report. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] NTL 11.1.0
Just posted a new version of NTL, version 11.1.0. I've completely re-written the low-level small-prime FFT to use a truncated FFT algorithm. More details here: http://www.shoup.net/ntl/doc/tour-changes.html -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] NTL v11
I just uploaded a new version of NTL, which is available at http://www.shoup.net/ntl In addition to a few performance improvements, I've also made the configuration script and makefile a bit more intelligent. I've also changed several defaults, so that now, by default, NTL builds in thread safe, thread boosted, safe vector, and C++11 modes. One can, of course, override these defaults. Please see http://www.shoup.net/ntl/doc/tour-changes.html for details on what's new. I also uploaded a new set of NTL vs FLINT benchmarks. Please see http://www.shoup.net/ntl/benchmarks.pdf Cheers! -Victor Shoup -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] NTL 10.3.0
Go to http://shoup.net/ntl for full details. Below is the latest entry in the change log. I've also updated the NTL/FLINT comparison document: http://shoup.net/ntl/benchmarks.pdf The only significant change is to the ZZ_pX factoring benchmarks (the new code in NTL speeds up mat_ZZ_p multiplication and indirectly CompMod and CanZass). === Changes in 10.3.0 === * Implementation of a multi-modular strategy for matrix multiplication over ZZ_p. Here are some benchmarks that compare the new strategy to the old (naive) one. Here, we consider n-by-n matrices modulo an n-bit prime. o n=128, speedup=6.8x o n=256, speedup=8.6x o n=512, speedup=9.3x o n=1024, speedup=18x o n=2048, speedup=37x I also compared NTL's new mat_ZZ_p multiplication to FLINT's fmpz_mat multiplication. The latter also uses a multi-modular strategy. For n=128,256,512,1024 as above, NTL's code is between 2.7 and 3.1 times faster than FLINT's (and we did not count the time it would take to reduce the entries mod p for the FLINT code). Part of this may be due to the AVX-enhanced small-prime matrix multiplication code used by NTL, and part may be due to better CRT code. * I also instrumented both the plain and multi-modular matrix multiplication for ZZ_p so that they are both "thread boosted" (i.e., will automatcally exploit multiple cores when possible). * As an initial application of this faster matrix multiplication, I implemented a new version of Brent/Kung modular composition for ZZ_pX, which is now between 2 and 5 times faster than the old one (depending on parameters). This is done with a new class called ZZ_pXNewArgument, which supersedes ZZ_pXArgument (retained for compatibility). This also makes the CanZass factoring algorithm for ZZ_pX faster (sometimes by a factor of almost 2, depending on parameters). It also makes CanZass more memory intensive (but while the overall memory usage increases, the memory access pattern is fairly cache friendly). * I would like to see if this faster matrix multiplication can be used to get faster linear algebra (determinants, inverses, more general Gaussian elimination) via reduction to matrix multiplication. If anyone wants to volunteer to work on this, please let me know. Presumably, the FLINT nmod_mat code could be repurposed for this. I won't have time to work on this for a few months, but would be glad to discuss ideas with anyone who wanted to do the work. Note that the "plain" versions of these routines also need some work. * I also added move methods to the Vec and Mat classes, and made a slight tweak to the Lazy class. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] NTL 10.2.0
Just posted a new version. In addition to a few performance improvements, I've added new routines that give direct access to the underlying "limbs" of a ZZ, which is a feature that has been requested from time to time. As usual, go to: http://www.shoup.net/ntl The next thing I will be working on is implementing a multi-modular algorithm for matrix multiplication over ZZ_p, using the now much faster matrix multiplication algorithms over zz_p. My preliminary estimates indicate that this should speed up NTL's mat_ZZ_p mul routines by a factor of 10-20x. And a multicore version should make it even faster. After I get faster matrix multiplication working, I want to first experiment with applying it to the modular composition algorithm used in the ZZ_pX factoring algorithm. I'm hoping to get a 2-3x speedup in the DDF routine. After that, I want to work on implementing the reductions from matrix inversion, etc, to matrix multiplication (over ZZ_p). For this I can probably "re-purpose" FLINT or other open-source code that has already been written. If anyone would like to help me with that, I would be grateful. This multi-modular approach to matrix mul is of course not new --- it is in Sage already via FFLAS, I think. But still, I'd like to work on getting a fairly decent implementation in NTL. It's a hobby :-) Note: Based on my benchmarks, for 20-bit primes, NTL's mat_zz_p multiplication is about 20% slower than FFLAS on an x86 with AVX2, so not too bad. Also, NTL's inversion routine is a bit faster than FFLAS's (between 15-35%). -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL 1v0.1.0
Sure. Will do. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL 1v0.1.0
I will anyway add routines to get and set the limbs of a ZZ. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL 1v0.1.0
Good! But it should be determined if there is an interface that ntl could provide so that this problem goes away -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL 1v0.1.0
That said, I think the quickest fix is to replace static_cast with (long*). But it's not a good long term solution. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL 1v0.1.0
I see. I don't do it on purpose... I looked at some singular source files, but I don't know if I have the most recent. But it looks like they are trying to look inside ntl's ZZ representation. That's a big no no. Right now, the only semi efficient way to do this with the existing interface is to use ZZToBytes (or something like that). I could add some special routines for direct gmp bignum conversions, if there was a demand for that. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL 1v0.1.0
Interesting. Looks like the singular code is using internal, undocumented NTL interfaces. I work very hard to keep the documented interfaces stable and reliable, but I can't guarantee anything for undocumented interfaces. If singular is going to do that, they will have to use ifdefs or something to work around the issue. Or ask me to provide an interface for some functionality that they need and that I can maintain. My guess is that this is related to changes I made in the transition to v10. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] NTL 1v0.1.0
I just uploaded NTL v10.1.0. After much foot dragging, and with the help and encouragement of folks here at sage-devel, I've finally got around to making (nearly) all of the packaging/build features that were requested. The big ones are locally generated libtool and $(MAKE). I did not implement that Singular/NTL_NEW_OP patch --- that is a Singular problem that should be fixed in Singular. I also added a new TUNE variable to the configuration script. TUNE=auto (the default) runs the performance-tuning wizard (as before). TUNE=x86 skips the wizard, and sets things up so it should work well on any x86. TUNE=generic skips the wizard, and sets things up so it should work not too badly on any not-too-old hardware (ARM, PowerPC). Please see http://shoup.net/ntl/doc/tour-changes.html for more details. I also polished up the installation documentation quite a bit. Please see http://shoup.net/ntl/doc/tour-unix.html for more details. Please let me know if there any issues with the packaging/build features. Maybe some day I will get around to going fully autotools. But that will take some tinkering to get right...hopefully, this new build system will be pretty useful "as is". Again...thanks for your help and encouragement! -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: NTL v10
Almost done with the new release! I've taken care of the recursive make patch and both of the libtool patches. While I'm not ready to go all autotools, I've started reading about it. I read about the DESTDIR trick that some package managers use, so I added support for that in the makefile. Although I suppose that may not be so relevant for Sage. I also added a few "recipes" that will allow you to skip the very slow Wizard step, at least for a few typical platforms. So now I'm working on updating the documentation, especially the unix installation instructions, which were anyway in need of some polishing. I will hopefully release tomorrow!! I'll continue reading about autotools. NTL does a few quirky things during the build process -- I have to see if all of that maps nicely into autotools world. Some NTL source files may also need some minor updates, too. BTW, I also remember using paper tape...but that was mainly just to backup my programs, if I recall correctly. Ahhh...those were the days :-) On Saturday, October 8, 2016 at 4:21:14 PM UTC-4, Victor Shoup wrote: > > I hope this is of some interest to the Sage community. > I've just released a new version of NTL at http://www.shoup.net/ntl > > Here is a summary of changes. > > *New License: LGPLv2.1* > >- With the permission of all relevant contributors, NTL is now >licensed under LGPLv2.1+ (the Lesser GNU Public License version 2.1 or >later). >- Previously, NTL was licensed under the GPL. This new, less >restrictive licensing should hopefully increase the impact of NTL. > > > *Long integer package restructuring* > >- I've restructured the long integer package so that the GMP and >"classical LIP" modules share much of the same code base. >- This greatly reduces the amount of redundant code, which will make >maintenance easier moving forward. >- As a bonus, the classical LIP module is simpler, faster, and >(finally) thread safe. >- As another bonus, the GMP module now is much closer to being >compatible with "non-empty nails". Although it has not been tested in that >mode as of yet, it may eventually be helpful in the future if I want to >replace some GMP code with code that exploits AVX-512 IFMA instructions. >- As a part of this transition, "make check" now includes much more >extensive "unit testing" of the long integer package. >- Despite the drastic changes "under the hood", this restructuring >should not affect at all any NTL client code that relies only on the >documented interface, including even the ancient legacy interfaces >pre-dating NTLv5a from 2000. > > > *File name restructuring* > >- I've renamed all the ".c" files to ".cpp" files in the Unix >distribution. This seems to be more in line with common practice, and >should make it easier to work with compilers and other software > development >tools. > > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: NTL v10
I looked at the singular patch, regarding the use of nothrow new. I dug up "ticket #852" which lead to that patch. In all honesty, it looks like singular is doing something wrong, so "fixing" NTL is just the wrong thing to do. So I won't implement that patch in NTL. This is a problem that should be fixed in singular, if it hasn't been already. On Saturday, October 8, 2016 at 4:21:14 PM UTC-4, Victor Shoup wrote: > > I hope this is of some interest to the Sage community. > I've just released a new version of NTL at http://www.shoup.net/ntl > > Here is a summary of changes. > > *New License: LGPLv2.1* > >- With the permission of all relevant contributors, NTL is now >licensed under LGPLv2.1+ (the Lesser GNU Public License version 2.1 or >later). >- Previously, NTL was licensed under the GPL. This new, less >restrictive licensing should hopefully increase the impact of NTL. > > > *Long integer package restructuring* > >- I've restructured the long integer package so that the GMP and >"classical LIP" modules share much of the same code base. >- This greatly reduces the amount of redundant code, which will make >maintenance easier moving forward. >- As a bonus, the classical LIP module is simpler, faster, and >(finally) thread safe. >- As another bonus, the GMP module now is much closer to being >compatible with "non-empty nails". Although it has not been tested in that >mode as of yet, it may eventually be helpful in the future if I want to >replace some GMP code with code that exploits AVX-512 IFMA instructions. >- As a part of this transition, "make check" now includes much more >extensive "unit testing" of the long integer package. >- Despite the drastic changes "under the hood", this restructuring >should not affect at all any NTL client code that relies only on the >documented interface, including even the ancient legacy interfaces >pre-dating NTLv5a from 2000. > > > *File name restructuring* > >- I've renamed all the ".c" files to ".cpp" files in the Unix >distribution. This seems to be more in line with common practice, and >should make it easier to work with compilers and other software > development >tools. > > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL v10
Anyway, like I said, I'm pretty much done, modulo a couple of things that I asked about two posts above. Hopefully, someone can clarify those points soon, and then there will be a distribution of NTL that does not require any patching :-) On Monday, October 10, 2016 at 8:16:17 PM UTC-4, François wrote: > > Autotools is nicer for a lot of things. sage does patch > to use libtools and I stayed away from that in Gentoo. > The main advantage as far as I am concerned is that it makes > it easier to produce shared libraries, correctly on a variety > of platforms. Just for linux, and OS X, you don’t strictly > need to do that but it is a good investment in the future. > > In that regard the current sage solution is a bit of a halfway point. > You really should couple it with automake and autoconf but that’s > more work. > > But we should have pestered you about make/$(MAKE) a lot more > as it is a much bigger sin ;) > > François > > > On 11/10/2016, at 13:03, Victor Shoup > > wrote: > > > > First, you are definitely wrong about punch cards. I started programming > > with Fortran on punch cards in the 70s. > > > > Second, a complete transition to auto tools still feels like overkill at > this point. > > But I agree that it could come one day. > > In any case, I am almost done with all the requested changes. > > I will follow up with a couple of quick questions, though. > > > > On Monday, October 10, 2016 at 5:09:48 PM UTC-4, Dima Pasechnik wrote: > > > > > > On Monday, October 10, 2016 at 9:09:38 PM UTC+1, François wrote: > > On 11/10/16 01:58, Victor Shoup wrote: > > > Another issue. I'm not sure if $(MAKE) is specific to gnu make or if > it is universal. > > > In general, I don't want to assume gnu. But I can certainly make this > the default, > > > and provide a config variable to override. > > > > I'll have another go at this when you use > > $(MAKE) inside a makefile you are making sure > > that the make command used is the same one that > > you called on the initial makefile. > > > > As other people mentioned it enable parallel make > > to proceed nicely, and in the case where there is > > several make command installed on the system > > you avoid funny things happening. I have AIX > > system which comes with its own posix make > > command. Something like ntl probably require > > gmake (GNU make), calling AIX make in the > > middle is not a good idea. > > > > > > Perhaps the most natural solution would be to change NTL build system so > that > > it uses the standard autotools chain (autoconf/automake etc), not only > libtool. > > Given that it uses very few external libraries, it ought to be an easy > task. > > > > Given that I am perhaps the only person in this thread who learned to > program using punch cards, > > I am a dinosaur from an earlier period, yet, I look into the future :-) > > > > Dima > > > > > > > > Francois > > > > -- > > You received this message because you are subscribed to the Google > Groups "sage-devel" group. > > To unsubscribe from this group and stop receiving emails from it, send > an email to sage-devel+...@googlegroups.com . > > To post to this group, send email to sage-...@googlegroups.com > . > > Visit this group at https://groups.google.com/group/sage-devel. > > For more options, visit https://groups.google.com/d/optout. > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL v10
I am almost done with everything!! I have just a couple of remaining questions. First, I am having a hard time understanding why singular is having a hard time with the definition of NTL_NEW_OP. It is defined that way for a reason, and this is completely standard C++ (standard, as in C++98). Could somebody explain what is going on? The suggested patch, here https://github.com/sagemath/sage/blob/master/build/pkgs/ntl/patches/new_singular.patch is not really the correct semantics. Second, I have two questions about the libtool flags patch, here: https://github.com/sagemath/sage/blob/master/build/pkgs/ntl/patches/libtool_flag.patch First, it would seem more logical to me to have a different flag for each libtool mode (i.e., compile, link, etc). That is easy enough to do. Does that seem right? Or is one global flag OK (but it will get added to every invocation of libtool). Second, in the patch, you write $(LINK) $(LIBTOOL_FLAGS) whereas it seems to me more logical to put $(LIBTOOL_FLAGS) $(LINK) so that the libtool flags come towards the beginning of the invocation of libtool. Otherwise, these are acting more like compiler flags. Maybe it would be much clearer if I knew what the typical use case of LIBTOOL_FLAGS actually was. Thanks! The sooner you clarify the issues, the sooner I can release the patched up version. I'm already done with all the other libtool and $(MAKE) issues. On Monday, October 10, 2016 at 5:58:05 AM UTC-4, Jean-Pierre Flori wrote: > > Thanks for the hint, we are already a few versions behind. > > I've opened #21676 for us to update, if anyone wants to review it: > * https://trac.sagemath.org/ticket/21676#ticket > > By the way we are still shipping a few patches, have a look at: > * https://github.com/sagemath/sage/blob/master/build/pkgs/ntl/patches/ > > I'd say the most annoying one is: > * > https://github.com/sagemath/sage/blob/master/build/pkgs/ntl/patches/configure.ac > We're just making an empty autotool project, running autoreconf, and > repackaging your tarball so that it provides its own version of libtool. > (All of this is done by this script: > * https://github.com/sagemath/sage/blob/master/build/pkgs/ntl/spkg-src > ) > Indeed some systems do not provide any "default" libtool script. > > And surely the following one is about using $MAKE rather than make in your > makefile: > * > https://github.com/sagemath/sage/blob/master/build/pkgs/ntl/patches/make.patch > Its purpose is quite obvious :) > > And finally, giving the ability to pass flags to libtool: > * > https://github.com/sagemath/sage/blob/master/build/pkgs/ntl/patches/libtool_flag.patch > This is useful when building on cygwin/mingw where libtool wants an > -no-undefined flag to even try to build a shared lib (without it it does > not even try). > > Best, > JPF > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL v10
First, you are definitely wrong about punch cards. I started programming with Fortran on punch cards in the 70s. Second, a complete transition to auto tools still feels like overkill at this point. But I agree that it could come one day. In any case, I am almost done with all the requested changes. I will follow up with a couple of quick questions, though. On Monday, October 10, 2016 at 5:09:48 PM UTC-4, Dima Pasechnik wrote: > > > > On Monday, October 10, 2016 at 9:09:38 PM UTC+1, François wrote: >> >> On 11/10/16 01:58, Victor Shoup wrote: >> > Another issue. I'm not sure if $(MAKE) is specific to gnu make or if it >> is universal. >> > In general, I don't want to assume gnu. But I can certainly make this >> the default, >> > and provide a config variable to override. >> >> I'll have another go at this when you use >> $(MAKE) inside a makefile you are making sure >> that the make command used is the same one that >> you called on the initial makefile. >> >> As other people mentioned it enable parallel make >> to proceed nicely, and in the case where there is >> several make command installed on the system >> you avoid funny things happening. I have AIX >> system which comes with its own posix make >> command. Something like ntl probably require >> gmake (GNU make), calling AIX make in the >> middle is not a good idea. >> >> > Perhaps the most natural solution would be to change NTL build system so > that > it uses the standard autotools chain (autoconf/automake etc), not only > libtool. > Given that it uses very few external libraries, it ought to be an easy > task. > > Given that I am perhaps the only person in this thread who learned to > program using punch cards, > I am a dinosaur from an earlier period, yet, I look into the future :-) > > Dima > > > > Francois >> > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL v10
About the make variable... I can definitely see it's utility with make -j... I would guess that's the main advantage, and that's easy enough to fix in the makefile itself. The other calls to make from other scripts are a bit more problematic. Would you say they are a priority? And if so, would one assume that a user would set the environment variable MAKE? As I understand it, in gnuc make, the variable MAKE is not an ordinary environment variable. It is a special variable with extra magic specific to make (including -j magic). -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL v10
One more question, relating to $(MAKE). There are a number of scripts besides the makefile that also invoke make. Should these also be modified? But then the mechanism would have to be different (environment variable?). Before I can sort that out, I would like to know what is the goal here? Is system make really not used in some environments? Or is there some magic in $(MAKE) within a makefile that is being used? If the latter, then I can probably just keep the other invocations of make are OK as is. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL v10
Let me get this straight... You say that the tarball does not contain a libtool script, but rather, contains a directory that contains files that will build a libtool script at compile time. Is that right? -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL v10
Ok, thanks. I will try to get this done this week. Your explanation was very helpful. Hopefully, I can piece together a solution based on the scripts you pointed to in your previous reply. I admit, I've been quite a dinosaur when it comes to autotools stuff...when I started, none of this really existed, and at any particular point in time, it seemed easier to "roll my own" scripts than to figure out autotools. In the short term, I will probably not change too much, but I agree that this libtool issue really needs to be fixed. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL v10
Ok, I will start working on these issues. The one I understand the least is libtool. It looks like you are saying I should generate a libtool script on the machine X on which I create the NTL tarball. But this seems very strange. How could that script be any better than one generated/installed on the machine Y where the build is taking place? Wouldn't it be better to generate libtool on Y? And why isn't there a libtool command on Y in the first place? I mean, if you assume the whole autoconf toolchain, why not assume libtool? Or, is it that maybe there are parts of the toolchain that are X but not Y? Sorry...I'm not much of an expert on libtool or autoconf. Another issue. I'm not sure if $(MAKE) is specific to gnu make or if it is universal. In general, I don't want to assume gnu. But I can certainly make this the default, and provide a config variable to override. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL v10
Haha, yes, that was one reason to do it. On Saturday, October 8, 2016 at 4:27:01 PM UTC-4, François wrote: > > > > On 9/10/2016, at 09:21, Victor Shoup > > wrote: > > > > • I've renamed all the ".c" files to ".cpp" files in the Unix > distribution. This seems to be more in line with common practice, and > should make it easier to work with compilers and other software development > tools. > > > > I have been doing some clang/clang++ build recently and clang++ complains > about compiling .c files (but does it anyway). So that should get rid of > some warnings. > > François -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] NTL v10
I hope this is of some interest to the Sage community. I've just released a new version of NTL at http://www.shoup.net/ntl Here is a summary of changes. *New License: LGPLv2.1* - With the permission of all relevant contributors, NTL is now licensed under LGPLv2.1+ (the Lesser GNU Public License version 2.1 or later). - Previously, NTL was licensed under the GPL. This new, less restrictive licensing should hopefully increase the impact of NTL. *Long integer package restructuring* - I've restructured the long integer package so that the GMP and "classical LIP" modules share much of the same code base. - This greatly reduces the amount of redundant code, which will make maintenance easier moving forward. - As a bonus, the classical LIP module is simpler, faster, and (finally) thread safe. - As another bonus, the GMP module now is much closer to being compatible with "non-empty nails". Although it has not been tested in that mode as of yet, it may eventually be helpful in the future if I want to replace some GMP code with code that exploits AVX-512 IFMA instructions. - As a part of this transition, "make check" now includes much more extensive "unit testing" of the long integer package. - Despite the drastic changes "under the hood", this restructuring should not affect at all any NTL client code that relies only on the documented interface, including even the ancient legacy interfaces pre-dating NTLv5a from 2000. *File name restructuring* - I've renamed all the ".c" files to ".cpp" files in the Unix distribution. This seems to be more in line with common practice, and should make it easier to work with compilers and other software development tools. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL new.h patch - singular-related - details?
Sorry if I never got around to dealing with all the patches. I'm will to look at it again, if someone is willing to spell it all out for me :-) On Thursday, May 26, 2016 at 10:55:25 AM UTC-4, Jean-Pierre Flori wrote: > > I tried to do archeology once for this one and found nothing conclusive... > > By the way, I've forwarded all of our patches/hackery to Victor Shoup some > monthes/years ago and he said he'll try to integrate them. > Maybe it's time to politely ask once again about what has not been > integrated (e.g. shipping its own libtool). > > On Thursday, May 26, 2016 at 11:59:55 AM UTC+2, François wrote: >> >> That’s old… After digging it looks like the first version of this is from >> #852. >> >> https://github.com/sagemath/sage/commit/02f6f87b554a6abebc9963076a00b7a48a4580b6 >> >> >> François >> >> > On 26/05/2016, at 21:46, Dima Pasechnik wrote: >> > >> > There is build/pkgs/ntl/patches/new_singular.patch that changes a macro >> (expanding to new rather than to new(std::nothrow)), and it is said to be >> related to Singular, without details or a link to a trac ticket. >> > >> > Where can I read more on this? >> > >> > Thanks, >> > Dima >> > >> > -- >> > You received this message because you are subscribed to the Google >> Groups "sage-devel" group. >> > To unsubscribe from this group and stop receiving emails from it, send >> an email to sage-devel+...@googlegroups.com. >> > To post to this group, send email to sage-...@googlegroups.com. >> > Visit this group at https://groups.google.com/group/sage-devel. >> > For more options, visit https://groups.google.com/d/optout. >> >> -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] NTL 9.8.0: thread safety for the masses
So I finally figured out a way to get NTL to work in thread-safe mode on a much broader range of platforms, including Mac OSX (10.10 and above) and Linux with somewhat older gcc's (gcc version 4.8 and above). This new version of NTL still requires many C++11 features in thread-safe mode, but it does not require "thread_local" storage. Rather, by default, it only uses gcc's older and simpler "__thread" storage, along with some direct calls to pthread library functions. One can override this default behavior by configuring with NTL_DISABLE_TLS_HACK=on. With this hack disabled, NTL still makes use of "__thread" storage wherever possible, and only uses "thread_local" storage for certain variables at block scope (and none at namespace scope). This generally leads to more efficient access to TLS variables and reduces the requirements on the compiler and run-time: many implementations of thread_local, especially at namespace scope, tend to be buggy and inefficient. To get thread safety, one still needs to configure with NTL_THREADS=on, or NTL_THREAD_BOOST=on. I have no idea if any of this works on Windows. It would be interesting to test some of this in Cygwin. I just learned that Cygwin can give you an LP64 data model, which is very nice. I don't have access to a Windows machine, so I can't test any of this myself. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] NTL 9.7.1
I uploaded a new NTL version (9.7.1) to http://www.shoup.net/ntl This version completes the implementation of faster matrix arithmetic (mul, inv, gauss, etc) modulo small primes. These new implementations are more cache friendly, and they make more intelligent use of available hardware (e.g., AVX). They also can be accelerated in a multicore environment. I've run some tests that show that this implementation is "not too bad" compared to FFLAS/FFPACK based on OpenBLAS. I've also updated my NTL vs FLINT comparisons to include some benchmarks for matrix arithmetic mod small primes. You can also see those results at http://www.shoup.net/ntl/benchmarks.pdf -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL 9.7.0
That is a bummer with the C++11 issues. The way I see it, C++11 is the future, and pretty much all C++ must eventually deal with it. Looking over the build issues with singular -- if the make files don't respect CFLAGS or CXXFLAGS, then maybe one can make the g++ command itself be a script that calls the "real" g++ with the right flags... On Saturday, March 12, 2016 at 8:17:15 PM UTC-5, François wrote: > > Thanks for adding a way to make binaries without avx/fma. > > The threading unfortunately requires C++11 (unless it changed). > In turns the inclusion of c++11 flags breaks the building of the > singular version shipped in sage. I don’t know about singular 4 > but it wouldn’t surprise me if it did too. > > François > > > On 13/03/2016, at 10:32, Victor Shoup > > wrote: > > > > Just released a new version of NTL! > > In a nutshell: faster, better matrix arithmetic over zz_p (small > moduli), > > some improved thread pooling facilities, > > and several other small improvements. > > > > For more details, go here: http://shoup.net/ntl/doc/tour-changes.html > > > > -- > > You received this message because you are subscribed to the Google > Groups "sage-devel" group. > > To unsubscribe from this group and stop receiving emails from it, send > an email to sage-devel+...@googlegroups.com . > > To post to this group, send email to sage-...@googlegroups.com > . > > Visit this group at https://groups.google.com/group/sage-devel. > > For more options, visit https://groups.google.com/d/optout. > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] NTL 9.7.0
Just released a new version of NTL! In a nutshell: faster, better matrix arithmetic over zz_p (small moduli), some improved thread pooling facilities, and several other small improvements. For more details, go here: http://shoup.net/ntl/doc/tour-changes.html -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Thread boosting in NTL
I implemented a simple thread pool, so threads are long lived and wake up when there is work to do. The thread pool class is pretty easy to use. Have not tried hyperthreading. The sys admins who are in charge of the machine are not keen to turn it on. All the code is available on my Web site. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Thread boosting in NTL
Just in case anyone is interested... I released a new version of NTL that offers a new "thread boosting" feature, which utilizes multiple cores to speed up certain computations. This is a work in progress...as of now, only basic operations in ZZ_pX are thread boosted. You can see a report on the effect of thread boosting on polynomial factorization here: http://www.shoup.net/ntl/boost.pdf Short synopsis: using 16 cores, NTL's (already pretty fast) algorithm for factoring polynomials over ZZ_p now runs 10-12 times faster. This is a result of boosting the low-level ZZ_pX arithmetic...the higher-level factoring routines are completely unchanged. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: FLINT/NTL benchmarks
Boost.SIMD library looks very promising! I would expect that within a few years, SIMD instruction sets continue to become more regular and useful, and that tools like Boost.SIMD will become more widely available and useful...and who knows, maybe even a part of C++... So I'd rather wait until that happens before diving in to all of the current muck... Hopefully, I won't be too old to write code :-) On Monday, October 5, 2015 at 10:22:08 AM UTC-4, bluescarni wrote: > > On 5 October 2015 at 13:13, Victor Shoup > > wrote: >> >> I hesitate somewhat to get involved in SIMD game, as all the assembly >> code / intrinsics stuff is a huge time sink that >> will yield code that will probably be obsolete in 10 years. Multicore, >> on the other hand, seems like a better >> investment, especially since C++11 (and C11) now standardize many aspects >> of it, so one can write portable >> code now. >> > > I have been thinking the same. It also seems like the number of cores in > CPUs has been increasing faster than the width of SIMD instructions. > > I know nothing about assembly language - so I am not sure how useful this > would be in practice - but I wish some type of SIMD support were > standardised in C++. The Boost.SIMD library, part of NT2, > > https://github.com/jfalcou/nt2 > https://meetingcpp.com/tl_files/mcpp/slides/12/simd.pdf > > looks promising though. > > Cheers, > > Francesco. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: FLINT/NTL benchmarks
Actually, I'll correct myself: SIMD can also be used to speed up the CRT operations in the multi-modular algorithm as well, at least up to a few thousand bits. So even in the grand and glorious SIMD future, there will probably be room to explore a variety of algorithmic approaches. On Monday, October 5, 2015 at 7:13:23 AM UTC-4, Victor Shoup wrote: > > Yes, I saw a paper by the mathemagix people recently...I believe they use > the floating point SIMD, and some > tricks with "fused multiply and add" to very nice effect. > They are basically implementing integer mod p arithmetic using floating > point. > I may want to play around with those ideas at some point. > Although, I may want to just wait a couple of years until Canonlakes > support the "IFMA52" instructions, which will > support everything we need for 52-bit prime FFT's very nicely. There will > be a tradeoff, of course, going back > to 52-bits from 60. Too bad Intel has no plans to support 64-bit MulHi in > SIMD anytime soon. > > Applying the mathemagix approach directly to NTL's multi-modular approach > for ZZ_pX mul may not > be that helpful, because of the cost of CRT on coefficients. But maybe > this will tip the scales > in favor of Kronecker substitution by way of 3-prime FFT large integer mul > in SIMD > especially if we get to AVX1024 someday :-) > > I hesitate somewhat to get involved in SIMD game, as all the assembly code > / intrinsics stuff is a huge time sink that > will yield code that will probably be obsolete in 10 years. Multicore, on > the other hand, seems like a better > investment, especially since C++11 (and C11) now standardize many aspects > of it, so one can write portable > code now. > > > On Monday, October 5, 2015 at 5:33:29 AM UTC-4, Bill Hart wrote: >> >> >> >> On Monday, 5 October 2015 04:18:27 UTC+2, Victor Shoup wrote: >>> >>> Thanks for the feedback, Bill! A bit of friendly competition is always >>> a good thing :-) >>> >> >> I agree. Software development is more interesting when there are people >> working on similar things. >> >> >>> >>> I've been looking into SIMD for small prime FFT's...unfortunately, there >>> is currently >>> no CPU out there that supports SIMD 64x64 -> high order 64 bits of >>> product. >>> So, it does not look very promising. >>> In a couple of years, Intel will eventually release a machine with SIMD >>> 52x52 -> high order 52 bits of product. >>> That may be interesting. >>> >> >> At a recent conference I saw some interesting work out of the Mathemagix >> group along these lines. They have papers on their website that give very >> impressive timings. >> >> >>> >>> Also, now that NTL is threadsafe, I'm looking at making some of the >>> low-level routines thread enhanced. >>> I'm currently finishing up makeing NTL's multi-modular ZZ_pX arithmetic >>> thread enhanced. >>> For up to 4 threads, I get close to linear speedup...but after that, it >>> starts to degrade: at 16 threads >>> I only get 8x speedup. I've also made the Brent/Kung modular >>> composition thread enhanced. >>> This gives much better multicore performance, as the bottleneck is a >>> rectangular matrix mul >>> which is trivial to parallelize. I'll hopefully make a release of all >>> this soonish. >>> >> >> Bill. >> > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: FLINT/NTL benchmarks
Yes, I saw a paper by the mathemagix people recently...I believe they use the floating point SIMD, and some tricks with "fused multiply and add" to very nice effect. They are basically implementing integer mod p arithmetic using floating point. I may want to play around with those ideas at some point. Although, I may want to just wait a couple of years until Canonlakes support the "IFMA52" instructions, which will support everything we need for 52-bit prime FFT's very nicely. There will be a tradeoff, of course, going back to 52-bits from 60. Too bad Intel has no plans to support 64-bit MulHi in SIMD anytime soon. Applying the mathemagix approach directly to NTL's multi-modular approach for ZZ_pX mul may not be that helpful, because of the cost of CRT on coefficients. But maybe this will tip the scales in favor of Kronecker substitution by way of 3-prime FFT large integer mul in SIMD especially if we get to AVX1024 someday :-) I hesitate somewhat to get involved in SIMD game, as all the assembly code / intrinsics stuff is a huge time sink that will yield code that will probably be obsolete in 10 years. Multicore, on the other hand, seems like a better investment, especially since C++11 (and C11) now standardize many aspects of it, so one can write portable code now. On Monday, October 5, 2015 at 5:33:29 AM UTC-4, Bill Hart wrote: > > > > On Monday, 5 October 2015 04:18:27 UTC+2, Victor Shoup wrote: >> >> Thanks for the feedback, Bill! A bit of friendly competition is always a >> good thing :-) >> > > I agree. Software development is more interesting when there are people > working on similar things. > > >> >> I've been looking into SIMD for small prime FFT's...unfortunately, there >> is currently >> no CPU out there that supports SIMD 64x64 -> high order 64 bits of >> product. >> So, it does not look very promising. >> In a couple of years, Intel will eventually release a machine with SIMD >> 52x52 -> high order 52 bits of product. >> That may be interesting. >> > > At a recent conference I saw some interesting work out of the Mathemagix > group along these lines. They have papers on their website that give very > impressive timings. > > >> >> Also, now that NTL is threadsafe, I'm looking at making some of the >> low-level routines thread enhanced. >> I'm currently finishing up makeing NTL's multi-modular ZZ_pX arithmetic >> thread enhanced. >> For up to 4 threads, I get close to linear speedup...but after that, it >> starts to degrade: at 16 threads >> I only get 8x speedup. I've also made the Brent/Kung modular composition >> thread enhanced. >> This gives much better multicore performance, as the bottleneck is a >> rectangular matrix mul >> which is trivial to parallelize. I'll hopefully make a release of all >> this soonish. >> > > Bill. > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] Re: FLINT/NTL benchmarks
Thanks for the feedback, Bill! A bit of friendly competition is always a good thing :-) I've been looking into SIMD for small prime FFT's...unfortunately, there is currently no CPU out there that supports SIMD 64x64 -> high order 64 bits of product. So, it does not look very promising. In a couple of years, Intel will eventually release a machine with SIMD 52x52 -> high order 52 bits of product. That may be interesting. Also, now that NTL is threadsafe, I'm looking at making some of the low-level routines thread enhanced. I'm currently finishing up makeing NTL's multi-modular ZZ_pX arithmetic thread enhanced. For up to 4 threads, I get close to linear speedup...but after that, it starts to degrade: at 16 threads I only get 8x speedup. I've also made the Brent/Kung modular composition thread enhanced. This gives much better multicore performance, as the bottleneck is a rectangular matrix mul which is trivial to parallelize. I'll hopefully make a release of all this soonish. On Sunday, October 4, 2015 at 8:06:26 PM UTC-4, Bill Hart wrote: > > This is really nice Victor. Thanks for sharing these benchmarks! > > There are two things we really need to do in Flint fairly soon: 1) make > better use of SIMD (e.g. small primes FFT is now probably competitive with > our Schoenhage-Strassen FFT) and 2) make use of threading. > > Flint is actually starting to look pretty slow on some benchmarks compared > to some of the new code that is being presented at conferences these days. > > Bill. > > On Monday, 5 October 2015 01:35:09 UTC+2, Victor Shoup wrote: >> >> I've recently done some benchmarking to compare FLINT and NTL. >> I've tried to be as fair as possible in the comparisons. >> If anyone is interested, you can see the results here: >> >> http://shoup.net/ntl/benchmarks.pdf >> >> The upshot is: FLINT is faster for some things, and NTL is faster >> for other things. >> > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] FLINT/NTL benchmarks
I've recently done some benchmarking to compare FLINT and NTL. I've tried to be as fair as possible in the comparisons. If anyone is interested, you can see the results here: http://shoup.net/ntl/benchmarks.pdf The upshot is: FLINT is faster for some things, and NTL is faster for other things. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] NTL v9.0
With much trepidation, I have introduced a (hopefully minor) backward incompatibility into NTL. The interface to the single-precision modular arithmetic routines has been modified slightly. This interface change allows for more flexible and more efficient implementation of these routines, which play a crucial role at many levels in NTL. Basically, these changes to the interface abstract away some implementation details that arguably should never been there in the first place. By coding to the new interface, NTL clients will be able to benefit from the current and future improvements. In particular, on 64-bit x86/GCC platforms, single precision moduli can now be up to 60 bits, rather than 50 bits. While some operations may in fact be a little slower, the most important ones (like MulModPrecon) should not be. Using larger moduli speeds up a number of things, like ZZ_pX arithmetic, as fewer primes need to be used in Chinese Remaindering steps. Other applications benefit from larger moduli as well. It is expected that most NTL clients will not be affected at all. Moreover, any code that needs to be updated will be detected by the compiler, and the updates should be simple and mechanical. There is also a configuration flag that will enable the legacy interface (although this is not recommended practice). For more, go to http://www.shoup.net/ntl -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] NTL v8 - exceptions!
I finally transformed the internals of NTL to be exception safe and to throw exceptions upon encountering an error (rather than the old "abort with error message" approach). This required a major overhaul of a lot of NTL internals, but the high level interfaces remain unchanged. To enable exceptions, you need to configure with NTL_EXCEPTIONS=on, and use a C++11 compiler (you need "lambdas" and C++11-style "noexcept"). Unfortunately, error handling in GMP is rather is still rather crude, and so the usefulness of all this is a bit limited if NTL is built using GMP. That said, the GMP developers are planning on adding proper error handling...hopefully soon. More details: http://www.shoup.net/ntl/doc/tour-changes.html http://www.shoup.net/ntl/doc/tour-struct.html#except Happy holidays!! -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] NTL updates
Thanks for the feedback. I don't know much about MPIR. I'm talking to some GMP developers. There is someone there who is planning on improving the situation there...at least, for the temporary memory allocations done by mpn-level routines in GMP, which is my main concern. On Monday, December 15, 2014 5:31:21 PM UTC-5, Jeroen Demeyer wrote: > > On 2014-12-15 20:15, Victor Shoup wrote: > > As I get closer to finishing this, I'm thinking more about gmp's lack of > > proper error handling, which is just like NTL's currently: print error > message and > > call abort. > No, MPIR (I haven't checked GMP, but I guess it's the same) is far > worse. MPIR doesn't print an error message, since there are no checks: > it just randomly crashes when something goes wrong. > > > Have you Sage people developed any workarounds? > > One idea I saw floating around on the Web: > >- override gmp's allocation routines, keeping track > > of all extant gmp allocations > >- if out of mem, throw an exception > >- in any code calling gmp routines, use RAII to clean up > > any extant gmp allocations (this should be fairly lightweight) > We have something. We can handle failed memory allocations using the > sig_on() mechanism, which is certainly a hack but it works. However, it > doesn't clear anything up after a failure. So it implements only the > second of your points. > > It also seems overkill to implement the above, since MPIR doesn't have > more general error checking: one can easily overflow integers leading to > all kind of corruption... > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
[sage-devel] NTL updates
I've just uploaded a bug-fix version of NTL (version 7.0.2) at www.shoup.net/ntl. Probably does not affect any Sage code, though. Also, I'm getting closer to finish my quixotic quest to make NTL exception safe. It is an interesting experience, as I'm learning how to make use of "modern" C++ idioms to manage resources...so my code is no longer so archaic in that respect. As I get closer to finishing this, I'm thinking more about gmp's lack of proper error handling, which is just like NTL's currently: print error message and call abort. Have you Sage people developed any workarounds? One idea I saw floating around on the Web: - override gmp's allocation routines, keeping track of all extant gmp allocations - if out of mem, throw an exception - in any code calling gmp routines, use RAII to clean up any extant gmp allocations (this should be fairly lightweight) I think that with gcc, one can compile C code so that one can safely throw C++ exceptions through it. -fexceptions, or something like that This should work, but it makes some assumptions about gmp that I'm not sure about: - gmp's mpn routines release all memory (NTL only uses mpn routines) between calls - there is no other global state in gmp that would be messed up by exceptions Also, I know that there may be some other places in gmp where an error might be raised, but I highly doubt that NTL would trigger any of these... though I'm not 100% sure. Ideally, gmp would provide a general error callback routine that could throw an exception, as above. I will also reach out to the gmp people on this, but I figured so Sage folks must have thought about these issues already. I hope to have an exception-safe version of NTL (modulo gmp exception safety) ready within a few weeks. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] Re: Future NTL versions and exception handling
Yes, that is an issue. Writing exception-safe code is hard, as I'm finding out... Of course, I'll have to provide a way to turn off/on exceptions, both at compile time and at run time. On Thursday, November 13, 2014 12:04:53 PM UTC-5, Robert Bradshaw wrote: > > Sage's wrapping of NTL should be just fine as long as it's declared in > the Cython declarations, but there's a question of all the libraries > that use NTL indirectly which may have more difficulty adapting to > exceptions being thrown though their call stacks. > > On Tue, Nov 11, 2014 at 3:48 PM, Francesco Biscani > wrote: > > OOM exception handling is gonna be hard to implement, as GMP does not > > provide any mechanism to recover from memory errors. You can replace the > GMP > > memory management functions but the usual problem with that approach is > that > > you might be potentially interacting with other packages which might > also > > want to override the default functions. Another problem is that IIRC > > throwing C++ exceptions from C is undefined (or maybe > > implementation-defined?) behaviour. > > > > In any case, exceptions are the way to go when you program in C++. A > > well-coded C++ program should state precisely what level of exception > safety > > the routines provide (no-throw, strong, basic), and how and what a > routine > > can throw. Ideally you would want strong exception safety always - this > is > > quite doable but sometimes for the sake of performance basic exception > > safety is a good compromise. Of course anything involving move semantics > > should be marked noexcept. Another typical suggestion is always to use > RAII > > patterns when coding routines that can throw - that way you are > guaranteed > > that any resource is properly cleaned up before exiting the function > through > > an exception. > > > > C++11 also has good support for handling exceptions in threads, > including > > transporting exceptions between threads. In particular, using an > std::future > > for managing the return value of (or the exception thrown within) a > thread > > is pretty handy. > > > > Cheers, > > > > Francesco. > > > > On 12 November 2014 00:05, Jean-Pierre Flori > wrote: > >> > >> > >> > >> On Tuesday, November 11, 2014 11:55:49 PM UTC+1, Volker Braun wrote: > >>> > >>> What kind of error states are we talking about? divide by zero and out > of > >>> memory? > >>> > >> Exactly, that is exactly the kind of stuff Victor mentioned. > >> > >>> > >>> IMHO a C++ library should just throw C++ exceptions, thats what they > are > >>> here for. If only for better readability -> less bugs. If you declare > >>> methods with "except +" to Cython then they will automatically be > converted > >>> into Python exceptions, so its also very convenient for us. Pynac uses > that > >>> all the time. > >>> > >>> Pretty much the only potential downside are rumors that exceptions > might > >>> possibly hinder the optimizer. Though I've never seen that in a > reasonable > >>> benchmark. While that is certainly a possibility, it would just be an > >>> optimizer bug. All reasonable C++ compilers uses a zero-cost model so > its at > >>> least as fast as handling / returning some error flag. What _is_ > expensive > >>> is when an exception occurs, but in C++ you are not supposed to use > >>> exceptions for program flow like in Python. > >>> > >>> > >>> > >>> On Tuesday, November 11, 2014 10:15:44 PM UTC, Jean-Pierre Flori > wrote: > >>>> > >>>> Dear all, > >>>> > >>>> As you must have noticed, Victor Shoup just released a new thread > safe > >>>> version of NTL. > >>>> > >>>> He also took the opportunity to ask me (and surely a bunch of other > >>>> people) what would be expected from exception handling in NTL > >>>> Currently NTL just prints something and then aborts. > >>>> Note that we patch that in Sage to call one of our own functions and > >>>> avoid aborting. > >>>> I'm no C++ expert and don't usually play with exceptions, so I don't > >>>> have anything that sart to say. > >>>> But your comments/ideas/suggestion
[sage-devel] NTL v7.0.1
Hi all, I've joined this group, since I think the Sage developer group is probably one of the biggest users of NTL, and so it might be useful to be in more direct contact. Anyway, I just release v7.0.1 of NTL, which fixes a bug in the polynomial multiplication code in v7.0. You will only see the bug for polynomials over ZZ_p of degree greater than 4000-5000, but then it is catastrophic. It turns out my test suite was not covering everything. The only change is to the file FFT.c. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
