[ceph.git] / ceph / src / boost / libs / multiprecision / doc / html / boost_multiprecision / perf / int_real_world.html

<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Integer Real World Tests</title>
<link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../../index.html" title="Chapter&#160;1.&#160;Boost.Multiprecision">
<link rel="up" href="../perf.html" title="Performance Comparison">
<link rel="prev" href="realworld.html" title="Floating-Point Real World Tests">
<link rel="next" href="float_performance.html" title="Float Algorithm Performance">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="realworld.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../perf.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="float_performance.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="boost_multiprecision.perf.int_real_world"></a><a class="link" href="int_real_world.html" title="Integer Real World Tests">Integer Real
      World Tests</a>
</h3></div></div></div>
<p>
        The first set of <a href="../../../../performance/voronoi_performance.cpp" target="_top">tests</a>
        measure the times taken to execute the multiprecision part of the Voronoi-diagram
        builder from Boost.Polygon. The tests mainly create a large number of temporaries
        "just in case" multiprecision arithmetic is required, for comparison,
        also included in the tests is Boost.Polygon's own partial-multiprecision
        integer type which was custom written for this specific task:
      </p>
<div class="informaltable"><table class="table">
<colgroup>
<col>
<col>
</colgroup>
<thead><tr>
<th>
                <p>
                  Integer Type
                </p>
              </th>
<th>
                <p>
                  Relative Performance (Actual time in parenthesis)
                </p>
              </th>
</tr></thead>
<tbody>
<tr>
<td>
                <p>
                  polygon::detail::extended_int
                </p>
              </td>
<td>
                <p>
                  1(0.138831s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  int256_t
                </p>
              </td>
<td>
                <p>
                  1.19247(0.165551s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  int512_t
                </p>
              </td>
<td>
                <p>
                  1.23301(0.17118s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  int1024_t
                </p>
              </td>
<td>
                <p>
                  1.21463(0.168628s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  checked_int256_t
                </p>
              </td>
<td>
                <p>
                  1.31711(0.182855s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  checked_int512_t
                </p>
              </td>
<td>
                <p>
                  1.57413(0.218538s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  checked_int1024_t
                </p>
              </td>
<td>
                <p>
                  1.36992(0.190187s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  cpp_int
                </p>
              </td>
<td>
                <p>
                  1.63244(0.226632s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  mpz_int
                </p>
              </td>
<td>
                <p>
                  5.42511(0.753172s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  tom_int
                </p>
              </td>
<td>
                <p>
                  29.0793(4.03709s)
                </p>
              </td>
</tr>
</tbody>
</table></div>
<p>
        Note how for this use case, any dynamic allocation is a performance killer.
      </p>
<p>
        The next <a href="../../../../performance/miller_rabin_performance.cpp" target="_top">tests</a>
        measure the time taken to generate 1000 128-bit random numbers and test for
        primality using the Miller Rabin test. This is primarily a test of modular-exponentiation
        since that is the rate limiting step:
      </p>
<div class="informaltable"><table class="table">
<colgroup>
<col>
<col>
</colgroup>
<thead><tr>
<th>
                <p>
                  Integer Type
                </p>
              </th>
<th>
                <p>
                  Relative Performance (Actual time in parenthesis)
                </p>
              </th>
</tr></thead>
<tbody>
<tr>
<td>
                <p>
                  cpp_int
                </p>
              </td>
<td>
                <p>
                  5.25827(0.379597s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  cpp_int (no Expression templates)
                </p>
              </td>
<td>
                <p>
                  5.15675(0.372268s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  cpp_int (128-bit cache)
                </p>
              </td>
<td>
                <p>
                  5.10882(0.368808s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  cpp_int (256-bit cache)
                </p>
              </td>
<td>
                <p>
                  5.50623(0.397497s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  cpp_int (512-bit cache)
                </p>
              </td>
<td>
                <p>
                  4.82257(0.348144s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  cpp_int (1024-bit cache)
                </p>
              </td>
<td>
                <p>
                  5.00053(0.360991s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  int1024_t
                </p>
              </td>
<td>
                <p>
                  4.37589(0.315897s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  checked_int1024_t
                </p>
              </td>
<td>
                <p>
                  4.52396(0.326587s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  mpz_int
                </p>
              </td>
<td>
                <p>
                  1(0.0721905s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  mpz_int (no Expression templates)
                </p>
              </td>
<td>
                <p>
                  1.0248(0.0739806s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  tom_int
                </p>
              </td>
<td>
                <p>
                  2.60673(0.188181s)
                </p>
              </td>
</tr>
<tr>
<td>
                <p>
                  tom_int (no Expression templates)
                </p>
              </td>
<td>
                <p>
                  2.64997(0.191303s)
                </p>
              </td>
</tr>
</tbody>
</table></div>
<p>
        It's interesting to note that expression templates have little effect here
        - perhaps because the actual expressions involved are relatively trivial
        in this case - so the time taken for multiplication and division tends to
        dominate. Also note how increasing the internal cache size used by <code class="computeroutput"><span class="identifier">cpp_int</span></code> is quite effective in this case
        in cutting out memory allocations altogether - cutting about a third off
        the total runtime. Finally the much quicker times from GMP and tommath are
        down to their much better modular-exponentiation algorithms (GMP's is about
        5x faster). That's an issue which needs to be addressed in a future release
        for <a class="link" href="../tut/ints/cpp_int.html" title="cpp_int">cpp_int</a>.
      </p>
<p>
        Test code was compiled with Microsoft Visual Studio 2010 with all optimisations
        turned on (/Ox), and used MPIR-2.3.0 and <a href="http://www.mpfr.org" target="_top">MPFR</a>-3.0.0.
        The tests were run on 32-bit Windows Vista machine.
      </p>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright &#169; 2002-2013 John Maddock and Christopher Kormanyos<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
      </p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="realworld.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../perf.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="float_performance.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
Commit	Line	Data
7c673cae FG	1	<html>
	2	<head>
	3	<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
	4	<title>Integer Real World Tests</title>
	5	<link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css">
	6	<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
	7	<link rel="home" href="../../index.html" title="Chapter 1. Boost.Multiprecision">
	8	<link rel="up" href="../perf.html" title="Performance Comparison">
	9	<link rel="prev" href="realworld.html" title="Floating-Point Real World Tests">
	10	<link rel="next" href="float_performance.html" title="Float Algorithm Performance">
	11	</head>
	12	<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
	13	<table cellpadding="2" width="100%"><tr>
	14	<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
	15	<td align="center"><a href="../../../../../../index.html">Home</a></td>
	16	<td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
	17	<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
	18	<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
	19	<td align="center"><a href="../../../../../../more/index.htm">More</a></td>
	20	</tr></table>
	21	<hr>
	22	<div class="spirit-nav">
	23	<a accesskey="p" href="realworld.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../perf.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="float_performance.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
	24	</div>
	25	<div class="section">
	26	<div class="titlepage"><div><div><h3 class="title">
	27	<a name="boost_multiprecision.perf.int_real_world"></a><a class="link" href="int_real_world.html" title="Integer Real World Tests">Integer Real
	28	World Tests</a>
	29	</h3></div></div></div>
	30	<p>
	31	The first set of <a href="../../../../performance/voronoi_performance.cpp" target="_top">tests</a>
	32	measure the times taken to execute the multiprecision part of the Voronoi-diagram
	33	builder from Boost.Polygon. The tests mainly create a large number of temporaries
	34	"just in case" multiprecision arithmetic is required, for comparison,
	35	also included in the tests is Boost.Polygon's own partial-multiprecision
	36	integer type which was custom written for this specific task:
	37	</p>
	38	<div class="informaltable"><table class="table">
	39	<colgroup>
	40	<col>
	41	<col>
	42	</colgroup>
	43	<thead><tr>
	44	<th>
	45	<p>
	46	Integer Type
	47	</p>
	48	</th>
	49	<th>
	50	<p>
	51	Relative Performance (Actual time in parenthesis)
	52	</p>
	53	</th>
	54	</tr></thead>
	55	<tbody>
	56	<tr>
	57	<td>
	58	<p>
	59	polygon::detail::extended_int
	60	</p>
	61	</td>
	62	<td>
	63	<p>
	64	1(0.138831s)
65	</p>
66	</td>
67	</tr>
68	<tr>
69	<td>
70	<p>
71	int256_t
72	</p>
73	</td>
74	<td>
75	<p>
76	1.19247(0.165551s)
77	</p>
78	</td>
79	</tr>
80	<tr>
81	<td>
82	<p>
83	int512_t
84	</p>
85	</td>
86	<td>
87	<p>
88	1.23301(0.17118s)
89	</p>
90	</td>
91	</tr>
92	<tr>
93	<td>
94	<p>
95	int1024_t
96	</p>
97	</td>
98	<td>
99	<p>
100	1.21463(0.168628s)
101	</p>
102	</td>
103	</tr>
104	<tr>
105	<td>
106	<p>
107	checked_int256_t
108	</p>
109	</td>
110	<td>
111	<p>
112	1.31711(0.182855s)
113	</p>
114	</td>
115	</tr>
116	<tr>
117	<td>
118	<p>
119	checked_int512_t
120	</p>
121	</td>
122	<td>
123	<p>
124	1.57413(0.218538s)
125	</p>
126	</td>
127	</tr>
128	<tr>
129	<td>
130	<p>
131	checked_int1024_t
132	</p>
133	</td>
134	<td>
135	<p>
136	1.36992(0.190187s)
137	</p>
138	</td>
139	</tr>
140	<tr>
141	<td>
142	<p>
143	cpp_int
144	</p>
145	</td>
146	<td>
147	<p>
148	1.63244(0.226632s)
149	</p>
150	</td>
151	</tr>
152	<tr>
153	<td>
154	<p>
155	mpz_int
156	</p>
157	</td>
158	<td>
159	<p>
160	5.42511(0.753172s)
161	</p>
162	</td>
163	</tr>
164	<tr>
165	<td>
166	<p>
167	tom_int
168	</p>
169	</td>
170	<td>
171	<p>
172	29.0793(4.03709s)
173	</p>
174	</td>
175	</tr>
176	</tbody>
177	</table></div>
178	<p>
179	Note how for this use case, any dynamic allocation is a performance killer.
180	</p>
181	<p>
182	The next <a href="../../../../performance/miller_rabin_performance.cpp" target="_top">tests</a>
183	measure the time taken to generate 1000 128-bit random numbers and test for
184	primality using the Miller Rabin test. This is primarily a test of modular-exponentiation
185	since that is the rate limiting step:
186	</p>
187	<div class="informaltable"><table class="table">
188	<colgroup>
189	<col>
190	<col>
191	</colgroup>
192	<thead><tr>
193	<th>
194	<p>
195	Integer Type
196	</p>
197	</th>
198	<th>
199	<p>
200	Relative Performance (Actual time in parenthesis)
201	</p>
202	</th>
203	</tr></thead>
204	<tbody>
205	<tr>
206	<td>
207	<p>
208	cpp_int
209	</p>
210	</td>
211	<td>
212	<p>
213	5.25827(0.379597s)
214	</p>
215	</td>
216	</tr>
217	<tr>
218	<td>
219	<p>
220	cpp_int (no Expression templates)
221	</p>
222	</td>
223	<td>
224	<p>
225	5.15675(0.372268s)
226	</p>
227	</td>
228	</tr>
229	<tr>
230	<td>
231	<p>
232	cpp_int (128-bit cache)
233	</p>
234	</td>
235	<td>
236	<p>
237	5.10882(0.368808s)
238	</p>
239	</td>
240	</tr>
241	<tr>
242	<td>
243	<p>
244	cpp_int (256-bit cache)
245	</p>
246	</td>
247	<td>
248	<p>
249	5.50623(0.397497s)
250	</p>
251	</td>
252	</tr>
253	<tr>
254	<td>
255	<p>
256	cpp_int (512-bit cache)
257	</p>
258	</td>
259	<td>
260	<p>
261	4.82257(0.348144s)
262	</p>
263	</td>
264	</tr>
265	<tr>
266	<td>
267	<p>
268	cpp_int (1024-bit cache)
269	</p>
270	</td>
271	<td>
272	<p>
273	5.00053(0.360991s)
274	</p>
275	</td>
276	</tr>
277	<tr>
278	<td>
279	<p>
280	int1024_t
281	</p>
282	</td>
283	<td>
284	<p>
285	4.37589(0.315897s)
286	</p>
287	</td>
288	</tr>
289	<tr>
290	<td>
291	<p>
292	checked_int1024_t
293	</p>
294	</td>
295	<td>
296	<p>
297	4.52396(0.326587s)
298	</p>
299	</td>
300	</tr>
301	<tr>
302	<td>
303	<p>
304	mpz_int
305	</p>
306	</td>
307	<td>
308	<p>
309	1(0.0721905s)
310	</p>
311	</td>
312	</tr>
313	<tr>
314	<td>
315	<p>
316	mpz_int (no Expression templates)
317	</p>
318	</td>
319	<td>
320	<p>
321	1.0248(0.0739806s)
322	</p>
323	</td>
324	</tr>
325	<tr>
326	<td>
327	<p>
328	tom_int
329	</p>
330	</td>
331	<td>
332	<p>
333	2.60673(0.188181s)
334	</p>
335	</td>
336	</tr>
337	<tr>
338	<td>
339	<p>
340	tom_int (no Expression templates)
341	</p>
342	</td>
343	<td>
344	<p>
345	2.64997(0.191303s)
346	</p>
347	</td>
348	</tr>
349	</tbody>
350	</table></div>
351	<p>
352	It's interesting to note that expression templates have little effect here
353	- perhaps because the actual expressions involved are relatively trivial
354	in this case - so the time taken for multiplication and division tends to
355	dominate. Also note how increasing the internal cache size used by <code class="computeroutput"><span class="identifier">cpp_int</span></code> is quite effective in this case
356	in cutting out memory allocations altogether - cutting about a third off
357	the total runtime. Finally the much quicker times from GMP and tommath are
358	down to their much better modular-exponentiation algorithms (GMP's is about
359	5x faster). That's an issue which needs to be addressed in a future release
360	for <a class="link" href="../tut/ints/cpp_int.html" title="cpp_int">cpp_int</a>.
361	</p>
362	<p>
363	Test code was compiled with Microsoft Visual Studio 2010 with all optimisations
364	turned on (/Ox), and used MPIR-2.3.0 and <a href="http://www.mpfr.org" target="_top">MPFR</a>-3.0.0.
365	The tests were run on 32-bit Windows Vista machine.
366	</p>
367	</div>
368	<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
369	<td align="left"></td>
370	<td align="right"><div class="copyright-footer">Copyright © 2002-2013 John Maddock and Christopher Kormanyos<p>
371	Distributed under the Boost Software License, Version 1.0. (See accompanying
372	file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
373	</p>
374	</div></td>
375	</tr></table>
376	<hr>
377	<div class="spirit-nav">
378	<a accesskey="p" href="realworld.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../perf.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="float_performance.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
379	</div>
380	</body>
381	</html>