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.
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.
