| 1 | <html> |
|---|
| 2 | <head> |
|---|
| 3 | <title> |
|---|
| 4 | A Tour of NTL: Tips for Getting the Best Performance out of NTL |
|---|
| 5 | </title> |
|---|
| 6 | </head> |
|---|
| 7 | |
|---|
| 8 | <body bgcolor="#fff9e6"> |
|---|
| 9 | <center> |
|---|
| 10 | <a href="tour-win.html"><img src="arrow1.gif" alt="[Previous]" align=bottom></a> |
|---|
| 11 | <a href="tour.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a> |
|---|
| 12 | <a href="tour-impl.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a> |
|---|
| 13 | </center> |
|---|
| 14 | |
|---|
| 15 | <h1> |
|---|
| 16 | <p align=center> |
|---|
| 17 | A Tour of NTL: Tips for Getting the Best Performance out of NTL |
|---|
| 18 | </p> |
|---|
| 19 | </h1> |
|---|
| 20 | |
|---|
| 21 | <p> <hr> <p> |
|---|
| 22 | |
|---|
| 23 | <ol> |
|---|
| 24 | |
|---|
| 25 | <li> |
|---|
| 26 | Build NTL using GMP as the primary long integer package. |
|---|
| 27 | This is extremely important, as the GMP implementation |
|---|
| 28 | of long integer arithmetic is <i>much</i> faster |
|---|
| 29 | than the default implementation. |
|---|
| 30 | Go <a href="tour-gmp.html">here</a> for details. |
|---|
| 31 | |
|---|
| 32 | <p> |
|---|
| 33 | <li> |
|---|
| 34 | On many machines that optionally offer 64-bit integer arithmetic |
|---|
| 35 | (recent Mac OSX machines, for instance), |
|---|
| 36 | you should |
|---|
| 37 | compile using <tt>gcc</tt> with the option <tt>-m64</tt> |
|---|
| 38 | to get the full benefit. |
|---|
| 39 | To do this, |
|---|
| 40 | pass <tt>"CFLAGS=-O2 -m64"</tt> |
|---|
| 41 | to the <tt>configure</tt> script (note the use of quotes). |
|---|
| 42 | If you are using NTL with GMP on such a machine, |
|---|
| 43 | you <i>must</i> do this to get compatible code. |
|---|
| 44 | |
|---|
| 45 | <p> |
|---|
| 46 | <li> |
|---|
| 47 | On Sparcs, |
|---|
| 48 | pass the argument <tt>"CFLAGS=-O2 -mcpu=v8"</tt> |
|---|
| 49 | to the <tt>configure</tt> script. |
|---|
| 50 | On more recent, 64-bit sparcs, pass <tt>"CFLAGS=-O2 -mcpu=v9 -m64"</tt> |
|---|
| 51 | to get the full instruction set and 64-bit code. |
|---|
| 52 | |
|---|
| 53 | <p> |
|---|
| 54 | <li> |
|---|
| 55 | Make sure you run the configuration wizard when you install NTL. |
|---|
| 56 | This is the default behaviour in the makefile |
|---|
| 57 | in the Unix distribution, so don't change this; |
|---|
| 58 | in the Windows distribution, there is unfortunately no |
|---|
| 59 | easy way to run the wizard. |
|---|
| 60 | |
|---|
| 61 | <p> |
|---|
| 62 | <li> |
|---|
| 63 | In time-critical code, avoid creating unnecessary temporary |
|---|
| 64 | objects. |
|---|
| 65 | For example, instead of |
|---|
| 66 | <pre> |
|---|
| 67 | ZZ InnerProduct(const ZZ *a, const ZZ *b, long n) |
|---|
| 68 | { |
|---|
| 69 | long i; |
|---|
| 70 | ZZ res; |
|---|
| 71 | for (i = 0; i < n; i++) |
|---|
| 72 | res += a[i] * b[i]; |
|---|
| 73 | return res; |
|---|
| 74 | } |
|---|
| 75 | </pre> |
|---|
| 76 | write this as |
|---|
| 77 | <pre> |
|---|
| 78 | ZZ InnerProduct(const ZZ *a, const ZZ *b, long n) |
|---|
| 79 | { |
|---|
| 80 | long i; |
|---|
| 81 | ZZ res, t; |
|---|
| 82 | for (i = 0; i < n; i++) { |
|---|
| 83 | mul(t, a[i], b[i]); |
|---|
| 84 | add(res, res, t); |
|---|
| 85 | } |
|---|
| 86 | return res; |
|---|
| 87 | } |
|---|
| 88 | </pre> |
|---|
| 89 | The first version of <tt>InnerProduct</tt> |
|---|
| 90 | creates and destroys a temporary object, holding the value |
|---|
| 91 | <tt>a[i]*b[i]</tt>, in every loop iteration. |
|---|
| 92 | The second does not. |
|---|
| 93 | |
|---|
| 94 | |
|---|
| 95 | |
|---|
| 96 | |
|---|
| 97 | <p> |
|---|
| 98 | <li> |
|---|
| 99 | If you use the class <tt>ZZ_p</tt>, try to avoid switching the modulus |
|---|
| 100 | too often, as this can be a rather expensive operation. |
|---|
| 101 | If you <i>must</i> switch the modulus often, |
|---|
| 102 | use the class <tt>ZZ_pContext</tt> to save the information |
|---|
| 103 | associated with the modulus (see <a href="ZZ.txt">ZZ.txt</a>). |
|---|
| 104 | |
|---|
| 105 | |
|---|
| 106 | |
|---|
| 107 | </ol> |
|---|
| 108 | |
|---|
| 109 | <p> |
|---|
| 110 | |
|---|
| 111 | <center> |
|---|
| 112 | <a href="tour-win.html"><img src="arrow1.gif" alt="[Previous]" align=bottom></a> |
|---|
| 113 | <a href="tour.html"><img src="arrow2.gif" alt="[Up]" align=bottom></a> |
|---|
| 114 | <a href="tour-impl.html"> <img src="arrow3.gif" alt="[Next]" align=bottom></a> |
|---|
| 115 | </center> |
|---|
| 116 | |
|---|
| 117 | |
|---|
| 118 | </body> |
|---|
| 119 | </html> |
|---|
