Question:
I compare the performance. This problem is taken as an example. C ++ solution
#include <iostream>
#include <limits>
#include <cmath>
#include <string>
#include <cstdlib>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/rational.hpp>
using namespace boost;
typedef boost::multiprecision::cpp_int LL;
const char MSG_ERR[] = "Error\n";
const size_t MSG_ERR_LEN = std::strlen(MSG_ERR);
rational<LL> *x;
rational<LL> fun(const rational<LL> & y, const rational<LL> & z) {
rational<LL> ret = 108 - (815 - (1500 / z))/y;
return ret;
}
int main(int argn, char *argv[]) {
if(argn != 2) {
std::cout.write(MSG_ERR, MSG_ERR_LEN);
return 1;
}
int n = std::atoi(argv[1]) + 1;
if(n < 1) {
std::cout.write(MSG_ERR, MSG_ERR_LEN);
return 1;
}
x = new rational<LL>[n];
x[0] = 4;
x[1] = rational<LL>(17,4);
for(int i = 2; i < n; ++i)
x[i] = fun(x[i-1], x[i-2]);
std::cout << x[n-1] << std::endl;
return 0;
}
Haskell:
import Data.Ratio
import System.Environment
f y z = 108 - (815 - 1500 / z) / y
xlist = 4 : (17 % 4) : zipWith f (tail xlist) xlist
main = do
args <- getArgs
case args of
[arg1] -> do
let x = read arg1
putStrLn $ show $ xlist !! x
_ -> error "ERR: Main.Args"
Results: C ++:
$ clang++37 -O3 -I/usr/local/include -o CPP t1.cpp
$ time ./CPP 10000 > /dev/null
39,64 real 39,62 user 0,00 sys
Haskell:
$ ghc -O2 t1.hs -o HS
Linking HS ...
$ time ./HS 10000 > /dev/null
6,73 real 6,73 user 0,00 sys
How can you explain such a significant difference? Boost? Laziness?
Answer:
Such a significant difference can be explained by the fact that boost
not optimized as much as possible, although the result is much better than writing long arithmetic by hand.
Now let's look at what potential we can squeeze out of С++
. For this we will use the GMP
library, take this code:
#include <cstddef>
#include <iostream>
#include <vector>
#include <gmpxx.h>
const char MSG_ERR[] = "Error\n";
const size_t MSG_ERR_LEN = std::strlen(MSG_ERR);
mpq_class fun(const mpq_class & y, const mpq_class & z) {
mpq_class ret = 108 - (815 - (1500 / z))/y;
return ret;
}
int main(int argc, char *argv[])
{
if(argc != 2)
{
std::cout.write(MSG_ERR, MSG_ERR_LEN);
return 1;
}
int n = std::atoi(argv[1]) + 1;
if(n < 1)
{
std::cout.write(MSG_ERR, MSG_ERR_LEN);
return 1;
}
std::vector<mpq_class> v;
v.push_back(mpq_class(4, 1));
v.push_back(mpq_class(17, 4));
for (int i = 2; i < n; ++i)
{
v.push_back(fun(v[i - 1], v[i - 2]));
}
std::cout << v.rbegin()->get_num() << " / " << v.rbegin()->get_den() << std::endl;
return 0;
}
And let's collect all the results in a heap, on my machine I got the following result:
Haskell
> ghc -O2 test.hs -o HS
> time ./HS 10000 > /dev/null
real 0m7.491s
user 0m7.420s
sys 0m0.004s
C++, boost
> g++-5 -O2 -o CPP test.cpp
> time ./CPP 10000 > /dev/null
real 0m22.272s
user 0m22.256s
sys 0m0.012s
> clang++ -O2 -o CPP-CLANG test.cpp
> time ./CPP-CLANG 10000 > /dev/null
real 0m20.638s
user 0m20.628s
sys 0m0.008s
C++, gmp
> g++-5 -O2 -std=c++14 -lgmpxx -lgmp -o CPP-GMP testgmp.cpp
> time ./CPP-GMP 10000 > /dev/null
real 0m1.418s
user 0m1.404s
sys 0m0.016s
We made sure that boost
doesn't give us the best performance.