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 <sh...@cs.nyu.edu > <javascript:>> 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 <javascript:>. > > To post to this group, send email to sage-...@googlegroups.com > <javascript:>. > > 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.
