|
|
Boost : |
From: Joel Young (jdy_at_[hidden])
Date: 2004-05-12 11:28:19
Congratulations Richard!
From: "Richard Peters" <r.a.peters_at_[hidden]>
> The divison algorithm is completely new, and this time it is
> fast (it now uses Knuth's algorithm). The code is also reorganised, which
> made it quite easy to build in support for GNU MP and CLN. When either of
> those two libraries is available, set BOOST_BIG_INTEGER_USE_GMP or
> BOOST_BIG_INTEGER_USE_CLN, and those libraries will be used to implement the
> basic arithmetic functions.
The new version is several thousand times faster then your previous
version. There is still some room for improvement.
The following timing results are for 10000 executions of following loop:
////////////////////////////////
#ifdef _RB
#ifdef _CLN
#define BOOST_BIG_INTEGER_USE_CLN
#elif _GMP
#define BOOST_BIG_INTEGER_USE_GMP
#endif
#include "boost/big_integer.hpp"
#include "boost/rational.hpp"
typedef boost::rational<boost::big_integer> data_t;
#elif _RL
#include "boost/rational.hpp"
typedef boost::rational<long long unsigned int> data_t;
#elif _CR
#include <cln/rational.h>
#include <cln/rational_io.h>
typedef cln::cl_RA data_t;
#endif
int main(int argc, char* argv[]) {
for (int i=0;i<COUNTER;++i) {
data_t tt = data_t(10000000);
data_t ne1 = data_t( 2762) * tt +
data_t(9706925);
data_t de1 = data_t( 1441) * tt * tt +
data_t(1518807) * tt +
data_t(5855872);
data_t e1 = ne1/de1; // 27629706925/144115188075855872
}
return 0;
}
/////////////////////////////
set OPTFLAG="-O2"
////////////////////////////
Rational of Big Integer using GMP:
g++ $OPTFLAG -o c -I ~/boost/boost/include/boost-1_31/ c.cpp -DCOUNTER=$COUNT -l gmp -D_RB -D_GMP
time ./c
0.570u 0.010s 0:00.62 93.5% 0+0k 0+0io 215pf+0w
Rational of Big Integer using CLN
g++ $OPTFLAG -o c -I ~/boost/boost/include/boost-1_31/ c.cpp -DCOUNTER=$COUNT -l cln -D_RB -D_CLN
time ./c
0.280u 0.020s 0:00.40 75.0% 0+0k 0+0io 427pf+0w
Rational of Big Integer
g++ $OPTFLAG -o c -I ~/boost/boost/include/boost-1_31/ c.cpp -DCOUNTER=$COUNT -D_RB
time ./c
1.610u 0.010s 0:01.88 86.1% 0+0k 0+0io 205pf+0w
CLN Rational cln::cl_RA
g++ $OPTFLAG -o c -I ~/boost/boost/include/boost-1_31/ c.cpp -DCOUNTER=$COUNT -l cln -D_CR
time ./c
0.030u 0.010s 0:00.08 50.0% 0+0k 0+0io 423pf+0w
Rational of unsigned long long
g++ $OPTFLAG -o c -I ~/boost/boost/include/boost-1_31/ c.cpp -DCOUNTER=$COUNT -D_RL
time ./c
0.030u 0.000s 0:00.09 33.3% 0+0k 0+0io 188pf+0w
////////////////////////////
Note that Rational of Big Int of CLN has an order of magnitude cost vs. CLN Rational directly.
For 1000 iterations runs, here are the top time consuming function
calls. It seems like there is a lot of construction and destruction going on.
First for Big Integer, then Big Integer with CLN, then Rational long long.
Rational of Big Integer:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls us/call us/call name
66.67 0.02 0.02 72000 0.28 0.33 boost::integer_impl::detail::div_and_mod(std::vector<unsigned int, std::allocator
33.33 0.03 0.01 153000 0.07 0.07 std::vector<unsigned int, std::allocator<unsigned int> >::erase(__gnu_cxx::__norm
0.00 0.03 0.00 405000 0.00 0.00 std::vector<unsigned int, std::allocator<unsigned int> >::~vector()
0.00 0.03 0.00 266000 0.00 0.00 std::vector<unsigned int, std::allocator<unsigned int> >::operator=(std::vector<u
0.00 0.03 0.00 117000 0.00 0.00 std::vector<unsigned int, std::allocator<unsigned int> >::_M_fill_insert(__gnu_cx
0.00 0.03 0.00 109000 0.00 0.00 unsigned int* std::vector<unsigned int, std::allocator<unsigned int> >::_M_alloca
0.00 0.03 0.00 108000 0.00 0.00 std::vector<unsigned int, std::allocator<unsigned int> >::_M_insert_aux(__gnu_cxx
0.00 0.03 0.00 102000 0.00 0.00 std::allocator<unsigned int>::~allocator()
0.00 0.03 0.00 72000 0.00 0.00 std::__simple_alloc<unsigned int, std::__default_alloc_template<true, 0> >::alloc
0.00 0.03 0.00 59000 0.00 0.00 __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::alloca
0.00 0.03 0.00 58000 0.00 0.00 boost::integer_impl::equal(std::pair<std::vector<unsigned int, std::allocator<uns
0.00 0.03 0.00 48000 0.00 0.07 void boost::integer_impl::assign_from_integer<int>(int, std::pair<std::vector<uns
0.00 0.03 0.00 48000 0.00 0.13 void boost::big_integer_base::assign_from_integer<int>(int)
0.00 0.03 0.00 40000 0.00 0.33 boost::expression::expression<boost::expression::big_integer_tag>::operator%=(boo
0.00 0.03 0.00 40000 0.00 0.00 unsigned int* std::fill_n<unsigned int*, unsigned int, unsigned int>(unsigned int
0.00 0.03 0.00 35000 0.00 0.00 boost::big_integer_base::operator=(boost::big_integer_base const&)
0.00 0.03 0.00 33000 0.00 0.00 bool boost::expression::expression<boost::expression::big_integer_tag>::operator<
0.00 0.03 0.00 29000 0.00 0.00 boost::expression::do_div<boost::expression::expression<boost::expression::big_in
Rational of Big Integer using CLN:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls us/call us/call name
33.33 0.01 0.01 48000 0.21 0.21 void boost::integer_impl::assign_from_integer<int>(int, cln::cl_I&)
33.33 0.02 0.01 40000 0.25 0.25 boost::expression::expression<boost::expression::big_integer_tag>::operator%=(bo
33.33 0.03 0.01 16000 0.62 1.46 boost::expression::expression<boost::expression::big_integer_tag> boost::gcd<boo
0.00 0.03 0.00 206000 0.00 0.00 cln::cl_I::operator=(cln::cl_I const&)
0.00 0.03 0.00 106000 0.00 0.00 cln::cl_gcobject::~cl_gcobject()
0.00 0.03 0.00 106000 0.00 0.00 cln::cl_I::~cl_I()
0.00 0.03 0.00 77000 0.00 0.00 boost::expression::expression<boost::expression::big_integer_tag>::~expression()
0.00 0.03 0.00 48000 0.00 0.00 void boost::big_integer_base::assign_from_integer<int>(int)
0.00 0.03 0.00 35000 0.00 0.00 boost::big_integer_base::operator=(boost::big_integer_base const&)
0.00 0.03 0.00 33000 0.00 0.00 bool boost::expression::expression<boost::expression::big_integer_tag>::operator
0.00 0.03 0.00 29000 0.00 0.00 boost::expression::do_div<boost::expression::expression<boost::expression::big_i
0.00 0.03 0.00 26000 0.00 0.00 boost::expression::expression<boost::expression::div<boost::expression::expressi
0.00 0.03 0.00 26000 0.00 0.00 boost::expression::binary_expression<boost::expression::expression<boost::expres
0.00 0.03 0.00 26000 0.00 0.00 boost::expression::div<boost::expression::expression<boost::expression::big_inte
0.00 0.03 0.00 26000 0.00 0.00 boost::expression::do_div<boost::expression::expression<boost::expression::big_i
0.00 0.03 0.00 26000 0.00 0.00 boost::expression::expression<boost::expression::div<boost::expression::expressi
0.00 0.03 0.00 26000 0.00 0.00 boost::expression::do_div<boost::expression::expression<boost::expression::big_i
Long Long:
% cumulative self self total
time seconds seconds calls Ts/call Ts/call name
0.00 0.00 0.00 16000 0.00 0.00 unsigned long long boost::gcd<unsigned long long>(unsigned long long, unsigned long long)
0.00 0.00 0.00 4000 0.00 0.00 boost::rational<unsigned long long>::operator*=(boost::rational<unsigned long long> const&)
0.00 0.00 0.00 3000 0.00 0.00 boost::rational<unsigned long long>::operator+=(boost::rational<unsigned long long> const&)
0.00 0.00 0.00 1000 0.00 0.00 boost::rational<unsigned long long>::operator/=(boost::rational<unsigned long long> const&)
0.00 0.00 0.00 1 0.00 0.00 _GLOBAL__I_main
0.00 0.00 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int)
> From: "Joel Young" <jdy_at_[hidden]>
> >
> > I made a simple program with some big numbers that demonstrate the
> > speed difference:
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk