[Gmp-commit] /var/hg/www: 2 new changesets

[mercurial at gmplib.org]

details:   /var/hg/www/rev/754a815ac8e5
changeset: 82:754a815ac8e5
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Fri May 31 21:56:19 2013 +0200
description:
Update diagrams for improved mu div code.

details:   /var/hg/www/rev/9aff8d034eba
changeset: 83:9aff8d034eba
user:      Torbjorn Granlund <tege at gmplib.org>
date:      Fri May 31 21:57:04 2013 +0200
description:
Remove now obsolete files.

diffstat:

 devel/div-100000.png  |  Bin 
 devel/div-1000000.png |  Bin 
 devel/index.html      |   31 +++++++++++--------------------
 devel/sbr-100000.png  |  Bin 
 devel/sbr-1000000.png |  Bin 
 5 files changed, 11 insertions(+), 20 deletions(-)

diffs (66 lines):

diff -r 7b428f584875 -r 9aff8d034eba devel/div-100000.png
Binary file devel/div-100000.png has changed
diff -r 7b428f584875 -r 9aff8d034eba devel/div-1000000.png
Binary file devel/div-1000000.png has changed
diff -r 7b428f584875 -r 9aff8d034eba devel/index.html
--- a/devel/index.html	Wed May 29 20:48:18 2013 +0200
+++ b/devel/index.html	Fri May 31 21:57:04 2013 +0200
@@ -86,35 +86,26 @@
 <hr>
 
 
-<h3> Division performance anomalies </h3>
+<h3> Division performance anomalies (partly fixed) </h3>
 
 <blockquote>
 <table>
 <tr> <td> <font size="+1"> Division time generating quotient-only for constant
-quotient size = 100,000.  The <i>x</i>-axis is the dividend size: </font>
-<tr> <td> <img src="div-100000.png" alt=""> </td> </tr>
+quotient size = 100,000.  The <i>x</i>-axis is the dividend size.  Red line is
+for the old code, green line is for the new 2013-05-31 code. </font>
+<tr> <td> <img src="sbr-100000.png" alt=""> </td> </tr>
 <tr> <td> <font size="+1"> Division time generating quotient-only for constant
 quotient size = 1,000,000.  The <i>x</i>-axis is the dividend size. </font>
-<tr> <td> <img src="div-1000000.png" alt=""> </td> </tr>
+<tr> <td> <img src="sbr-1000000.png" alt=""> </td> </tr>
 </table>
 </blockquote>
 
-<p> The qn > dn case is where the current code performs badly. For qn =
-100000 we have a slowdown of about 55% (compare nn=200000 with nn=174500). </p>
+<p> The qn > dn case is where the old code performed badly. For qn = 100000
+we had a performance anomaly of about 55% (compare dividend size nn=200000 with
+nn=174500). </p>
 
-<p> There, we now choose to compute an inverse of size in = ⌈dn/2⌉.
-Since qn > dn, we will have 2in < qn, which means that we will need to
-develop quotient limbs in more than 2 blocks; the code computes a most
-significant block of (qn - 2in) quotient limbs, and then two blocks of (in)
-quotient limbs each.  (The final block uses mpn_preinv_mu_divappr_q.) </p>
-
-<p> The inordinate cost we see emanates from the computation of the qn - 2in
-block. </p>
-
-<p> The fix is choosing the inverse size less stupidly, and organising the
-computation in more similarly sized quotient blocks.  It seems this will
-require more than just computing (in) differently, it will require some
-hacking. </p>
+<p> The new code avoids the worst anomalies, but still exhibits a few.  More
+work is needed. </p>
 
 <hr>
 
@@ -399,7 +390,7 @@
 </div>
 
 <div id="footer">
-<font size="-4">Last modified: 2013-05-20 </font>
+<font size="-4">Last modified: 2013-05-31 </font>
 <table cellpadding=0 width="100%" bgcolor="#e8e8e8">
   <tr>
     <td align="center">
diff -r 7b428f584875 -r 9aff8d034eba devel/sbr-100000.png
Binary file devel/sbr-100000.png has changed
diff -r 7b428f584875 -r 9aff8d034eba devel/sbr-1000000.png
Binary file devel/sbr-1000000.png has changed