Prolog still stands apart in languages landscape, and SWI-Prolog has grown big, features rich, since Jan is boosting it in practical SW engineering field.
Since I’d like to use
library(clpfd) for some simple tasks, and it depends on unlimited integers arithmetic, I need efficient unlimited integer arithmetic.
After the announce that the licence transition, from GPL to BSD, would require abandoning the awesome GMP, I started to evaluate if alternatives in my reach were available.
A small benchmark, of little practical interest, but requiring unlimited precision integer arithmetic, is the evaluation of
choose(N, K), best known as binomial coefficient, with large N.
In case of
choose(50000, 50), the result is this big number
I will show it abbreviated in output of the following tests, like
The benchmark originated from Jason, as a study about Python’ native foreign interfaces.
To run with Python 3.4, a small change is required – just added parenthesis to print
I do prefer to use QtCreator when developing C++, so there are .pro files you can use to see dependencies and build details.
Building can be simple as opening the .pro file, configuring the project for release, and build.
After done, right click on the .pro file in Projects, and select
'Open Terminal Here'.
Then paste the bash command line – for instance
$ time ../build-choose-gmp-Desktop_Qt_5_7_0_GCC_64bit-Release/choose-gmp
Here is a table summarizing my tests:
$ time swipl -O -g 'choose,halt' choose.pl 28495...24000 real 0m6.272s user 0m6.189s sys 0m0.064s
|python 2.7||native||6 sec||
$ time python choose.py 28495...24000 real 0m6.010s user 0m5.886s sys 0m0.112s
|python 3.4||native||6.6 sec||
$ time python3 choose-3.py 28495...24000 real 0m6.691s user 0m6.625s sys 0m0.056s
|node (js V8)||OpenSSL BN||15.5 sec||
$ npm install bignum $ time node choose.js <BigNum 28495...24000> real 0m15.501s user 0m12.608s sys 0m2.333s
$ time ../build-choose-gmp-Desktop_Qt_5_7_0_GCC_64bit-Release/choose-gmp 28495...24000 real 0m2.231s user 0m2.095s sys 0m0.003s
|C++||OpenSSL BN||2.5 sec||
$ time ../build-choose-openssl-Desktop_Qt_5_7_0_GCC_64bit-Release/choose-openssl 28495...24000 real 0m2.534s user 0m2.504s sys 0m0.028s
|C++||KNST – native||26.9 sec||
$ time ../build-choose-knst-Desktop_Qt_5_7_0_GCC_64bit-Release/choose-knst 28495...24000 real 0m26.933s user 0m26.711s sys 0m0.200s
SWI-Prolog code requires absolutely a tail recursive loop, otherwise the performance is very slow.
I started with a naive translation, and the execution time was about 95 sec – due to inability to run GC and a lot of big numbers allocation, I guess.
A first attempt to optimize (i.e.
$ time swipl -O -g 'choose,halt' choose.pl) caused a stack overflow.
So far, I’ve been unable to install GMP support in Node.
npm install bigint fails compiling the code,
I think it refers to this repo, indeed rather old.
Also bignum installation is weird, it just works for a session.
When I restart the system, I must reinstall. Anyway, it’s used in
Knst refers to this github project.
OpenSSL BN is practically on par with GMP, but the interface is notably lower level, and requires optimized calls.
You can see the not optimized calls following
main_old, the performance was worse – about 4.5 secs.
In GMP, the code is really simple, thanks to a good C++ interface, but I cannot say if it could be further optimized, maybe applying the same trick used in OpenSSL BN.