...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
The first set of tests measure the times taken to calculate the n'th Bernoulli number via mixed rational/integer arithmetic to give an exact rational result.
Table 1.18. Relative times taken to calculate Bm
m |
cpp_rational (time in seconds) |
mpq_rational (time relative to cpp_rational) |
mpq_class (time relative to cpp_rational) |
---|---|---|---|
50 |
1.888453 |
1.7317576874 |
1.893438174 |
54 |
2.250503 |
2.1519411438 |
2.4936252029 |
58 |
2.734527 |
2.2056805437 |
1.9866752093 |
62 |
3.318122 |
2.5182796172 |
2.2662876772 |
66 |
3.887281 |
2.4263077457 |
2.588347485 |
70 |
4.628535 |
1.9756346231 |
2.5367158291 |
74 |
5.3541 |
1.7052929531 |
2.3345854579 |
78 |
6.321172 |
1.6669601776 |
2.0390342171 |
82 |
7.13052 |
1.7689101216 |
1.9837833706 |
86 |
8.390095 |
1.6245518078 |
1.5785492298 |
90 |
10.62176 |
1.6294440846 |
1.5779053566 |
94 |
11.364409 |
1.5786845581 |
1.5614997665 |
98 |
14.030636 |
1.2616490799 |
1.4799734666 |
102 |
15.268211 |
1.6145657798 |
1.6128342738 |
106 |
15.253028 |
1.8985381788 |
1.8206293859 |
110 |
17.637756 |
1.8283953469 |
1.6559522084 |
114 |
18.335007 |
1.8018346543 |
1.8343225612 |
118 |
21.044146 |
2.0462015897 |
1.8106934346 |
122 |
23.71295 |
2.0041556196 |
1.7127701108 |
126 |
25.993901 |
1.9901613075 |
1.6974264848 |
130 |
30.17278 |
1.8897211328 |
1.6405006433 |
134 |
43.992333 |
1.2223514038 |
1.2232961594 |
138 |
40.702777 |
1.3551305848 |
1.492072224 |
142 |
47.01495 |
1.4361410785 |
1.4005683724 |
146 |
51.468592 |
1.4279172043 |
1.4072223891 |
150 |
70.736106 |
1.3628087048 |
1.2309294917 |
154 |
74.638691 |
1.2509392749 |
1.2846060497 |
158 |
76.642396 |
1.3383691449 |
1.2555573941 |
162 |
104.906795 |
1.1722665057 |
1.0121124375 |
166 |
108.175914 |
0.9272805682 |
1.2472813403 |
170 |
125.363885 |
0.8114005082 |
1.1349673712 |
174 |
119.813754 |
0.9747547014 |
1.5677900135 |
178 |
130.672631 |
0.904429444 |
1.6089208382 |
182 |
136.002124 |
0.8359445107 |
1.3173987636 |
186 |
152.169271 |
0.7919228515 |
1.3523570012 |
190 |
149.444035 |
0.8353259734 |
1.4571606823 |
194 |
149.609183 |
0.8898088896 |
1.6132629038 |
198 |
167.594528 |
0.8947434429 |
1.326461858 |
In this use case, most the of the rational numbers are fairly small and so the times taken are dominated by the number of allocations performed. The following table illustrates how well each type performs on suppressing allocations:
Table 1.19. Total Allocation Counts for Bernoulli Number Calculation
m |
cpp_rational |
mpq_rational |
mpq_class |
---|---|---|---|
2 |
0 |
77 |
101 |
4 |
0 |
187 |
252 |
6 |
0 |
345 |
471 |
8 |
0 |
551 |
758 |
10 |
0 |
805 |
1113 |
12 |
0 |
1107 |
1536 |
14 |
0 |
1457 |
2027 |
16 |
0 |
1857 |
2587 |
18 |
0 |
2336 |
3216 |
20 |
0 |
2885 |
3913 |
22 |
6 |
3511 |
4706 |
24 |
22 |
4203 |
5600 |
26 |
83 |
4963 |
6575 |
28 |
377 |
5806 |
7632 |
30 |
780 |
6738 |
8769 |
32 |
1454 |
7771 |
9988 |
34 |
2001 |
9357 |
11289 |
36 |
2789 |
10598 |
12704 |
38 |
3669 |
11948 |
14252 |
40 |
4653 |
13403 |
15891 |
42 |
5923 |
14976 |
17620 |
44 |
7379 |
16622 |
19449 |
46 |
8839 |
18367 |
21367 |
48 |
10296 |
20227 |
23431 |
50 |
12045 |
22857 |
25646 |
52 |
13603 |
25044 |
27962 |
54 |
15276 |
27331 |
30389 |
56 |
17239 |
29749 |
32919 |
58 |
19337 |
32257 |
35552 |
60 |
21409 |
34958 |
38417 |
62 |
23694 |
37800 |
41396 |
64 |
27923 |
39556 |
44498 |
66 |
30240 |
44706 |
47711 |
68 |
32566 |
47934 |
51042 |
70 |
35019 |
51417 |
54637 |
72 |
37460 |
55047 |
58363 |
74 |
40282 |
58777 |
62211 |
76 |
42914 |
62691 |
66183 |
78 |
45752 |
66694 |
70296 |
80 |
48681 |
70905 |
74620 |
82 |
51986 |
77633 |
79160 |
84 |
54855 |
82364 |
83842 |
86 |
59032 |
87239 |
88659 |
88 |
63595 |
92256 |
93618 |
90 |
68352 |
97486 |
98820 |
92 |
72446 |
102974 |
104256 |
94 |
76468 |
108620 |
109844 |
96 |
80361 |
111109 |
115594 |
98 |
84783 |
121460 |
121486 |
100 |
89044 |
127730 |
127633 |
102 |
93561 |
134241 |
134050 |
104 |
98452 |
140919 |
140616 |
106 |
103530 |
147763 |
147364 |
108 |
108326 |
154804 |
154276 |
110 |
113891 |
162184 |
161562 |
112 |
119213 |
169736 |
169038 |
114 |
124770 |
182417 |
176693 |
116 |
130624 |
190589 |
184519 |
118 |
137941 |
198975 |
192525 |
120 |
144829 |
207759 |
200952 |
122 |
152045 |
216736 |
209561 |
124 |
158610 |
225905 |
218371 |
126 |
165383 |
235283 |
227360 |
128 |
173971 |
230678 |
236670 |
130 |
181696 |
248593 |
246308 |
132 |
189310 |
258615 |
256148 |
134 |
197708 |
268800 |
266192 |
136 |
205800 |
279215 |
276436 |
138 |
212940 |
290112 |
287167 |
140 |
217502 |
301235 |
298101 |
142 |
223486 |
312564 |
309243 |
144 |
229579 |
324133 |
320605 |
146 |
237213 |
344671 |
332333 |
148 |
248799 |
357200 |
344420 |
150 |
261345 |
369947 |
356745 |
152 |
272741 |
382909 |
369279 |
154 |
283982 |
396162 |
382048 |
156 |
293626 |
409993 |
395353 |
158 |
304036 |
424022 |
408907 |
160 |
313869 |
427747 |
422690 |
162 |
323626 |
454723 |
436715 |
164 |
333294 |
469863 |
451304 |
166 |
343072 |
485238 |
466149 |
168 |
352236 |
500922 |
481221 |
170 |
362793 |
516840 |
496561 |
172 |
372645 |
533169 |
512315 |
174 |
382908 |
549962 |
528510 |
176 |
392507 |
567018 |
544947 |
178 |
404163 |
597694 |
561666 |
180 |
417539 |
615615 |
578647 |
182 |
432009 |
634079 |
596234 |
184 |
444684 |
652902 |
614114 |
186 |
457104 |
672042 |
632248 |
188 |
469331 |
691451 |
650654 |
190 |
481583 |
711512 |
669753 |
192 |
477225 |
698188 |
689111 |
194 |
488955 |
736905 |
708760 |
196 |
499797 |
757502 |
728675 |
198 |
511163 |
778591 |
749102 |
The second example measures the time taken to calculate the determinant of a 3x3 matrix of rational numbers. These numbers are randomly generated with n bits in both numerator and denominator. In this case the rate limiting step is the cost of calculating the GCD's during the computation:
Table 1.20. Relative Time Taken to Calculate 100 Determinants of Random 3x3 Matrixes
Bits |
cpp_rational (ms) |
mpq_rational (relative to cpp_rational) |
mpq_class (relative to cpp_rational) |
---|---|---|---|
512 |
45 |
0.3111111111 |
0.3177777778 |
1024 |
103 |
0.3038834951 |
0.3038834951 |
2048 |
251 |
0.3087649402 |
0.3011952191 |
4096 |
667 |
0.2983508246 |
0.2893553223 |
8192 |
2033 |
0.261682243 |
0.2956222332 |
16384 |
6423 |
0.2358710883 |
0.3059318076 |
32768 |
24223 |
0.1875903067 |
0.1955992239 |
Table 1.21. Platform Details
Version |
|
---|---|
Compiler |
GNU C++ version 10.3.0 |
GMP |
6.2.0 |
MPFR |
262146 |
Boost |
107800 |
Run date |
Sep 30 2021 |