Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.
PrevUpHomeNext

Integer Real World Tests

The first set of tests 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:

Integer Type

Relative Performance (Actual time in parenthesis)

polygon::detail::extended_int

1(0.138831s)

int256_t

1.19247(0.165551s)

int512_t

1.23301(0.17118s)

int1024_t

1.21463(0.168628s)

checked_int256_t

1.31711(0.182855s)

checked_int512_t

1.57413(0.218538s)

checked_int1024_t

1.36992(0.190187s)

cpp_int

1.63244(0.226632s)

mpz_int

5.42511(0.753172s)

tom_int

29.0793(4.03709s)

Note how for this use case, any dynamic allocation is a performance killer.

The next tests 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:

Integer Type

Relative Performance (Actual time in parenthesis)

cpp_int

5.25827(0.379597s)

cpp_int (no Expression templates)

5.15675(0.372268s)

cpp_int (128-bit cache)

5.10882(0.368808s)

cpp_int (256-bit cache)

5.50623(0.397497s)

cpp_int (512-bit cache)

4.82257(0.348144s)

cpp_int (1024-bit cache)

5.00053(0.360991s)

int1024_t

4.37589(0.315897s)

checked_int1024_t

4.52396(0.326587s)

mpz_int

1(0.0721905s)

mpz_int (no Expression templates)

1.0248(0.0739806s)

tom_int

2.60673(0.188181s)

tom_int (no Expression templates)

2.64997(0.191303s)

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

Test code was compiled with Microsoft Visual Studio 2010 with all optimisations turned on (/Ox), and used MPIR-2.3.0 and MPFR-3.0.0. The tests were run on 32-bit Windows Vista machine.


PrevUpHomeNext