Brilliant!! 2010/1/10 Case Vanhorsen <cas...@gmail.com>: > On Sun, Jan 10, 2010 at 2:02 PM, Bill Hart <goodwillh...@googlemail.com> > wrote: >> Thanks Case, >> >> those are very useful timings. I see more of what I expected to see >> for unbalanced multiplication, especially here: >> >> 5NxN mpz multiplication: MPIR 1.3.0 GMP 5.0.0 >> 1000 digits: 0.00002064 sec 0.00001863 sec >> 5000 digits: 0.00023417 sec 0.00021708 sec >> 10000 digits: 0.00064239 sec 0.00058681 sec >> 50000 digits: 0.00608666 sec 0.00436574 sec >> >> You also clearly see the asymptotically fast division code in GMP here: >> >> 17N/N mpz quotient: MPIR 1.3.0 GMP 5.0.0 >> 500000 digits: 1.24625611 sec 0.44447249 sec >> 1000000 digits: 2.99730897 sec 1.01921391 sec >> 10000000 digits: 55.43707895 sec 15.77324915 sec >> 100000000 digits: 915.73236585 sec 200.43964195 sec >> >> The squaring is not a surprise. This is due to the mpn_sqr_basecase >> function not being optimised in assembly for the Core 2. It's not bad, >> but for the last couple of releases we have suffered on that one. >> >> I think our strategy to continue working on the multiplication code, >> from karatsuba right through FFT, then completely redo division >> (pretty much from scratch, apart from the little we've already >> touched) is the right one. Of course we also still need to optimise >> that one file in the gcd/xgcd code and cube root. >> >> I see our next_prime is now way faster, but did the two programs agree >> on what the 10,000,000,000th prime actually was? I suppose that they >> should. > They actually agree to the 100,000,000,000th prime and to various > references on the Internet. >> >> Anyhow, I am now about to try and get an rc5 up for testing. There's >> nothing I can change at present to help out Gianrico, but perhaps we >> can encourage Jason Moxham to look at the assembly code for p6 when he >> comes back after his break, perhaps towards the end of March. >> >> I would like to see if Gianrico has found an FFT bug though. I'd like >> to fix that. I think SkyNet/cicero might be similar enough to trigger >> the assertion he encountered, if we have his tuning values. There are >> still plenty of people using such machines. >> >> Bill. >> >> 2010/1/10 Case Vanhorsen <cas...@gmail.com>: >>> On Sun, Jan 10, 2010 at 1:18 PM, Bill Hart <goodwillh...@googlemail.com> >>> wrote: >>>> You are of course welcome to choose whichever package best meets your >>>> needs. And indeed on your particular system, it seems GMP may well do >>>> that for you at present. >>>> >>>> One thing you should bear in mind however. Here are some times as they >>>> have changed over the past year and a half: >>>> >>>> K8 >>>> >>>> Multiplication: GMP 4.3.0 MPIR 1.2.0 MPIR 1.1.2 MPIR 1.0.0 MPIR >>>> 0.9.0 GMP 4.2.1 >>>> ========== ======== ========= ========= ======== >>>> ======== ========= >>>> 128 x 128 : 52766506 53794646 51802252 35856598 >>>> 37299412 25896136 >>>> 512 x 512 : 10879150 12488043 11802334 10928085 >>>> 8122452 6383542 >>>> 8192 x 8192 : 114927 117404 111772 111641 >>>> 86301 60819 >>>> 131072 x 131072 : 1757 2062 1873 1650 >>>> 1165 885 >>>> 2097152 x 2097152 : 52.5 63.4 44.1 44.1 >>>> 36.8 30.1 >>>> >>>> So as you can see, the times have changed *MUCH* more for *both* >>>> projects than the current difference between them. In fact >>>> multiplication speed (the most important speed by far) has nearly >>>> doubled in the past year, right across the board. I think with GMP 5 >>>> and MPIR 1.3 it really has doubled. >>>> >>>> So it is the improvement *over time* which is the important thing. >>>> You'll also note that the projects have leapfrogged each other, MPIR >>>> 0.9.0 beating GMP 4.2.1, GMP 4.3.0 beating MPIR 1.1.2, MPIR 1.2.0 >>>> beating GMP 4.3.0 and so on. So it does depend at what time you do the >>>> comparison whether one or the other is better. >>>> >>>> Also, if you look at the times Case provided, what you said about only >>>> multiplication above 100000 bits being faster is not really true. >>>> There are other places where MPIR beats GMP, even on that system. Also >>>> Case's benchmark only tests certain functionality. The full benchmark >>>> that we were running earlier shows plenty of other improvements of >>>> MPIR over GMP and is intended to give a much better overall guide. >>>> Case is showing us benchmarks that he is personally very interested >>>> in, and so that will be important for us to look at improving. >>> >>> I selected some of the tests specifically because they were improved >>> in GMP (especially diviision) or MPIR (next_prime). It is not a >>> general purpose benchmark. It was intended to highlight differences. >>> >>> BTW, the platform is a 64-bit Core2 running Linux. I'm guessing the >>> results would be radically different on 64-bit Windows. >>> >>> casevh >>>> >>>> Some of the program benchmarks that we have in our full benchmark >>>> suite tell a completely different story, putting MPIR well ahead for >>>> those sorts of things. They show that in an overall program, we do >>>> quite well. >>>> >>>> As I said, it is a mixed bag. Neither is showing clear superiority at >>>> this point. However, I will accept that on your 32 bit system, the >>>> assembly code is better optimised in GMP. That is definitely something >>>> we should look at improving further. >>>> >>>> Of course that is not completely trivial to do though. You are welcome >>>> to give it a go. I believe you will very quickly find that just about >>>> everything you try will make it slower. The assembly optimisation has >>>> got to such an art these days it cannot be done by hand. We have >>>> special optimisation tools for doing it, and it takes large amounts of >>>> CPU time, and human hours, to do the optimisation work. Progressively, >>>> over time, all the code will get optimised, but it is a long process! >>>> >>>> Bill. >>>> >>>> 2010/1/10 Gianrico Fini <gianrico.f...@gmail.com>: >>>>> It seems that also on your platform (32 bits you too?) MPIR is faster >>>>> only for one thing: multiplication (or squaring) above 100000 digits, >>>>> up to 30%. >>>>> And slower almost everywhere... somewhere +100% or more... >>>>> >>>>> This strengthen my decision... >>>>> >>>>> Gian. >>>>> >>>>> On 10 Gen, 18:47, Case Vanhorsen <cas...@gmail.com> wrote: >>>>>> I'll toss in my benchmark results. :-) >>>>>> >>>>>> GMPY performance benchmark >>>>>> >>>>>> Decimal string to mpz: MPIR 1.3.0 GMP 5.0.0 >>>>>> 10 digits: 0.00000021 sec 0.00000022 sec >>>>>> 100 digits: 0.00000063 sec 0.00000066 sec >>>>>> 500 digits: 0.00000318 sec 0.00000302 sec >>>>>> 1000 digits: 0.00000716 sec 0.00000693 sec >>>>>> 5000 digits: 0.00008661 sec 0.00006298 sec >>>>>> 10000 digits: 0.00026616 sec 0.00016775 sec >>>>>> 50000 digits: 0.00265514 sec 0.00168555 sec >>>>>> 100000 digits: 0.00651324 sec 0.00444604 sec >>>>>> 500000 digits: 0.04866513 sec 0.03830050 sec >>>>>> 1000000 digits: 0.11429363 sec 0.09162606 sec >>>>>> 10000000 digits: 2.31600404 sec 1.59257817 sec >>>>>> >>>>>> Mpz to decimal string: MPIR 1.3.0 GMP 5.0.0 >>>>>> 10 digits: 0.00000034 sec 0.00000035 sec >>>>>> 100 digits: 0.00000105 sec 0.00000101 sec >>>>>> 500 digits: 0.00000717 sec 0.00000589 sec >>>>>> 1000 digits: 0.00001586 sec 0.00001262 sec >>>>>> 5000 digits: 0.00014800 sec 0.00010783 sec >>>>>> 10000 digits: 0.00041150 sec 0.00029588 sec >>>>>> 50000 digits: 0.00420932 sec 0.00338085 sec >>>>>> 100000 digits: 0.01185473 sec 0.00920948 sec >>>>>> 500000 digits: 0.12125288 sec 0.08355007 sec >>>>>> 1000000 digits: 0.31727976 sec 0.20738387 sec >>>>>> 10000000 digits: 7.70821309 sec 3.94376493 sec >>>>>> >>>>>> Mpz addition: MPIR 1.3.0 GMP 5.0.0 >>>>>> 10 digits: 0.00000010 sec 0.00000009 sec >>>>>> 100 digits: 0.00000010 sec 0.00000010 sec >>>>>> 500 digits: 0.00000012 sec 0.00000011 sec >>>>>> 1000 digits: 0.00000014 sec 0.00000013 sec >>>>>> 5000 digits: 0.00000051 sec 0.00000050 sec >>>>>> 10000 digits: 0.00000073 sec 0.00000073 sec >>>>>> 50000 digits: 0.00000430 sec 0.00000429 sec >>>>>> 100000 digits: 0.00000822 sec 0.00000818 sec >>>>>> 500000 digits: 0.00003971 sec 0.00003959 sec >>>>>> 1000000 digits: 0.00007838 sec 0.00007884 sec >>>>>> 10000000 digits: 0.00357354 sec 0.00354370 sec >>>>>> 100000000 digits: 0.05413541 sec 0.05324940 sec >>>>>> >>>>>> 1NxN mpz multiplication: MPIR 1.3.0 GMP 5.0.0 >>>>>> 10 digits: 0.00000009 sec 0.00000009 sec >>>>>> 100 digits: 0.00000017 sec 0.00000018 sec >>>>>> 500 digits: 0.00000124 sec 0.00000126 sec >>>>>> 1000 digits: 0.00000414 sec 0.00000378 sec >>>>>> 5000 digits: 0.00004730 sec 0.00004805 sec >>>>>> 10000 digits: 0.00012850 sec 0.00012088 sec >>>>>> 50000 digits: 0.00123085 sec 0.00109137 sec >>>>>> 100000 digits: 0.00290135 sec 0.00280582 sec >>>>>> 500000 digits: 0.01663006 sec 0.01763764 sec >>>>>> 1000000 digits: 0.03379822 sec 0.03994881 sec >>>>>> 10000000 digits: 0.68572044 sec 0.61115754 sec >>>>>> 100000000 digits: 6.44622898 sec 7.93841791 sec >>>>>> >>>>>> 5NxN mpz multiplication: MPIR 1.3.0 GMP 5.0.0 >>>>>> 10 digits: 0.00000011 sec 0.00000010 sec >>>>>> 100 digits: 0.00000038 sec 0.00000040 sec >>>>>> 500 digits: 0.00000604 sec 0.00000652 sec >>>>>> 1000 digits: 0.00002064 sec 0.00001863 sec >>>>>> 5000 digits: 0.00023417 sec 0.00021708 sec >>>>>> 10000 digits: 0.00064239 sec 0.00058681 sec >>>>>> 50000 digits: 0.00608666 sec 0.00436574 sec >>>>>> 100000 digits: 0.00847080 sec 0.00917852 sec >>>>>> 500000 digits: 0.05356821 sec 0.06811212 sec >>>>>> 1000000 digits: 0.12863311 sec 0.14648414 sec >>>>>> 10000000 digits: 2.27829909 sec 2.17810798 sec >>>>>> 100000000 digits: 21.30186605 sec 27.38823199 sec >>>>>> >>>>>> 17NxN mpz multiplication: MPIR 1.3.0 GMP 5.0.0 >>>>>> 10 digits: 0.00000010 sec 0.00000011 sec >>>>>> 100 digits: 0.00000113 sec 0.00000108 sec >>>>>> 500 digits: 0.00002057 sec 0.00002183 sec >>>>>> 1000 digits: 0.00007094 sec 0.00006423 sec >>>>>> 5000 digits: 0.00081254 sec 0.00071725 sec >>>>>> 10000 digits: 0.00217992 sec 0.00197989 sec >>>>>> 50000 digits: 0.02072028 sec 0.01620061 sec >>>>>> 100000 digits: 0.02676870 sec 0.03553003 sec >>>>>> 500000 digits: 0.20828125 sec 0.23191699 sec >>>>>> 1000000 digits: 0.42618978 sec 0.52746260 sec >>>>>> 10000000 digits: 5.84609008 sec 7.77125812 sec >>>>>> 100000000 digits: 74.05822110 sec 100.53587508 sec >>>>>> >>>>>> 2N/N mpz quotient: MPIR 1.3.0 GMP 5.0.0 >>>>>> 10 digits: 0.00000018 sec 0.00000018 sec >>>>>> 100 digits: 0.00000041 sec 0.00000037 sec >>>>>> 500 digits: 0.00000234 sec 0.00000203 sec >>>>>> 1000 digits: 0.00000729 sec 0.00000638 sec >>>>>> 5000 digits: 0.00009662 sec 0.00009747 sec >>>>>> 10000 digits: 0.00029030 sec 0.00029359 sec >>>>>> 50000 digits: 0.00329851 sec 0.00279975 sec >>>>>> 100000 digits: 0.00912671 sec 0.00663861 sec >>>>>> 500000 digits: 0.07756643 sec 0.04376046 sec >>>>>> 1000000 digits: 0.18805614 sec 0.10166769 sec >>>>>> 10000000 digits: 3.46835899 sec 1.65955496 sec >>>>>> 100000000 digits: 57.28032804 sec 21.36209702 sec >>>>>> >>>>>> 5N/N mpz quotient: MPIR 1.3.0 GMP 5.0.0 >>>>>> 10 digits: 0.00000021 sec 0.00000020 sec >>>>>> 100 digits: 0.00000095 sec 0.00000085 sec >>>>>> 500 digits: 0.00000846 sec 0.00000747 sec >>>>>> 1000 digits: 0.00002843 sec 0.00002508 sec >>>>>> 5000 digits: 0.00038293 sec 0.00038840 sec >>>>>> 10000 digits: 0.00115942 sec 0.00117106 sec >>>>>> 50000 digits: 0.01321486 sec 0.00858406 sec >>>>>> 100000 digits: 0.03642362 sec 0.02081330 sec >>>>>> 500000 digits: 0.31158978 sec 0.13223937 sec >>>>>> 1000000 digits: 0.75152898 sec 0.30322999 sec >>>>>> 10000000 digits: 13.88208699 sec 4.75602698 sec >>>>>> 100000000 digits: 228.71033311 sec 60.81353498 sec >>>>>> >>>>>> 17N/N mpz quotient: MPIR 1.3.0 GMP 5.0.0 >>>>>> 10 digits: 0.00000028 sec 0.00000026 sec >>>>>> 100 digits: 0.00000343 sec 0.00000287 sec >>>>>> 500 digits: 0.00003360 sec 0.00002929 sec >>>>>> 1000 digits: 0.00011155 sec 0.00010037 sec >>>>>> 5000 digits: 0.00153300 sec 0.00132398 sec >>>>>> 10000 digits: 0.00462759 sec 0.00346040 sec >>>>>> 50000 digits: 0.05275750 sec 0.02910585 sec >>>>>> 100000 digits: 0.14589587 sec 0.07089074 sec >>>>>> 500000 digits: 1.24625611 sec 0.44447249 sec >>>>>> 1000000 digits: 2.99730897 sec 1.01921391 sec >>>>>> 10000000 digits: 55.43707895 sec 15.77324915 sec >>>>>> 100000000 digits: 915.73236585 sec 200.43964195 sec >>>>>> >>>>>> 2N/N mpz quot & rem: MPIR 1.3.0 GMP 5.0.0 >>>>>> 10 digits: 0.00000026 sec 0.00000025 sec >>>>>> 100 digits: 0.00000049 sec 0.00000045 sec >>>>>> 500 digits: 0.00000242 sec 0.00000207 sec >>>>>> 1000 digits: 0.00000738 sec 0.00000648 sec >>>>>> 5000 digits: 0.00009728 sec 0.00009805 sec >>>>>> 10000 digits: 0.00029146 sec 0.00029408 sec >>>>>> 50000 digits: 0.00330097 sec 0.00279113 sec >>>>>> 100000 digits: 0.00913051 sec 0.00663646 sec >>>>>> 500000 digits: 0.07772918 sec 0.04375675 sec >>>>>> 1000000 digits: 0.18767852 sec 0.10160725 sec >>>>>> 10000000 digits: 3.47579503 sec 1.65892482 sec >>>>>> 100000000 digits: 57.20885682 sec 21.33134699 sec >>>>>> >>>>>> Mpz squaring: MPIR 1.3.0 GMP 5.0.0 >>>>>> 10 digits: 0.00000015 sec 0.00000013 sec >>>>>> 100 digits: 0.00000025 sec 0.00000019 sec >>>>>> 500 digits: 0.00000102 sec 0.00000090 sec >>>>>> 1000 digits: 0.00000288 sec 0.00000267 sec >>>>>> 5000 digits: 0.00003559 sec 0.00003249 sec >>>>>> 10000 digits: 0.00009700 sec 0.00008516 sec >>>>>> 50000 digits: 0.00088845 sec 0.00078422 sec >>>>>> 100000 digits: 0.00201402 sec 0.00190495 sec >>>>>> 500000 digits: 0.01089044 sec 0.01193870 sec >>>>>> 1000000 digits: 0.02389035 sec 0.02675930 sec >>>>>> 10000000 digits: 0.49165547 sec 0.42553878 sec >>>>>> 100000000 digits: 4.66965413 sec 5.35446501 sec >>>>>> >>>>>> Mpz square root & rem: MPIR 1.3.0 GMP 5.0.0 >>>>>> 10 digits: 0.00000030 sec 0.00000026 sec >>>>>> 100 digits: 0.00000058 sec 0.00000051 sec >>>>>> 500 digits: 0.00000167 sec 0.00000139 sec >>>>>> 1000 digits: 0.00000316 sec 0.00000244 sec >>>>>> 5000 digits: 0.00002410 sec 0.00002248 sec >>>>>> 10000 digits: 0.00007203 sec 0.00006785 sec >>>>>> 50000 digits: 0.00083096 sec 0.00080454 sec >>>>>> ... >>>>>> >>>>>> leggi tutto >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google Groups >>>>> "mpir-devel" group. >>>>> To post to this group, send email to mpir-de...@googlegroups.com. >>>>> To unsubscribe from this group, send email to >>>>> mpir-devel+unsubscr...@googlegroups.com. >>>>> For more options, visit this group at >>>>> http://groups.google.com/group/mpir-devel?hl=en. >>>>> >>>>> >>>>> >>>>> >>>> >>>> -- >>>> You received this message because you are subscribed to the Google Groups >>>> "mpir-devel" group. >>>> To post to this group, send email to mpir-de...@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> mpir-devel+unsubscr...@googlegroups.com. >>>> For more options, visit this group at >>>> http://groups.google.com/group/mpir-devel?hl=en. >>>> >>>> >>>> >>>> >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "mpir-devel" group. >>> To post to this group, send email to mpir-de...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> mpir-devel+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/mpir-devel?hl=en. >>> >>> >>> >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "mpir-devel" group. >> To post to this group, send email to mpir-de...@googlegroups.com. >> To unsubscribe from this group, send email to >> mpir-devel+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/mpir-devel?hl=en. >> >> >> >> > > -- > You received this message because you are subscribed to the Google Groups > "mpir-devel" group. > To post to this group, send email to mpir-de...@googlegroups.com. > To unsubscribe from this group, send email to > mpir-devel+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/mpir-devel?hl=en. > > > >
-- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to mpir-de...@googlegroups.com. To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.
