Add support for BigInt in compiled mode

[perlun]

This (MIT-licensed) library seems useful: https://github.com/faheel/BigInt.

One challenge is that we haven't solved #378; where should bigints be allocated? From the stack? From the heap? Sometimes one and sometimes the other? To begin with, let's just allocate them on the heap and let the kernel/OS handle the cleanup for us. For static number constants, this will be the right choice anyway. For dynamically generated bigints, we obviously need something better but we'll keep this as part of the scope of #378 for now.

[perlun]

This (MIT-licensed) library seems useful: https://github.com/faheel/BigInt.

This is also another option:

• https://github.com/libtom/libtommath (found referenced at https://github.com/fffaraz/awesome-cpp, as one of the backends for Boost.MultiPrecision)
• https://github.com/libtom/tomsfastmath: "a port of LibTomMath with optional support for inline assembler multipliers"

GMP and and MPFR are also mentioned there, but I'll rule them out for now because of the (LGPL) licensing. It's not completely unlikely that I'll change the license for Perlang (to a split license where the compiler is GPL or AGPL and the stdlib is under another license), but I don't want to include LGPL or GPL:ed code at this stage. I want to retain the possibility to make the stdlib available under the MIT license, since I think this might be the most suitable option.

[perlun]

This is now in place, and works, for a certain definition of "works", but... now that I've fixed #420, I realize how dog slow this stuff is. (or rather, seems to be. Very important note: I haven't benchmarked anything, so I don't know that the https://github.com/faheel/BigInt library is causing this.. but it seems likely, given the discussion in faheel/BigInt#69 (comment)).

Running docs/examples/quickstart/pi.per in compiled mode

$ time ./pi 
31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798609437027705392171762931767523846748184676694051320005681271452635608277857713427577896091736371787214684409012249534301465495853710507922796892589235420199561121290219608640344181598136297747713099605187072113499999983729780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083814206171776691473035982534904287554687311595628638823537875937519577818577805321712268066130019278766111959092164201989

real	0m7.413s
user	0m7.413s
sys	0m0.000s

Running docs/examples/quickstart/pi.per in interpreted mode

$ time ~/.perlang/release/bin/perlang pi.per 
31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798609437027705392171762931767523846748184676694051320005681271452635608277857713427577896091736371787214684409012249534301465495853710507922796892589235420199561121290219608640344181598136297747713099605187072113499999983729780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083814206171776691473035982534904287554687311595628638823537875937519577818577805321712268066130019278766111959092164201989

real	0m0.165s
user	0m0.081s
sys	0m0.026s

Conclusions

Of course, more runs would be needed for any serious benchmarking but we see now already that this is way, way slower than you would expect. Ideally, the compiled version should be faster than my silly C# interpreter. 🙂 But the "problem" so to speak is that the Perlang code (and my interpreter) is likely not the bottleneck at all here; rather the BigInteger implementation in C# (which seems to be much faster than the C++ BigInt library we use).

So what I think we should do:

• Use the lesson from the BigInt libary we now have to provide roughly the same C++ API (essentially, bigint.hpp currently in place)
• Instead of using the bigint.cpp implementation, back the new BigInt class with data structures suitable for working with the https://github.com/libtom/libtommath. This will take some effort; learning how this C-based library works, what files in it that relevant for us (hopefully not all of it), and so forth.
• Evaluate the effort and ensure that we go well below 0.165s for the above pi calulations, in compiled mode. I think a reasonable goal should be something like 0.082s, i.e. 50% faster. Let's see if this achievable or not; at the very least, we should at least not be slower than interpreted mode.

Reopening the issue.

[perlun]

There we go. With the changes in #425 in place, we are now down to something reasonable in compiled mode too. Bear in mind that this is just for calculating 1000 decimals now; the 10 000 decimal version is still not as fast as neither the C# nor JavaScript versions mentioned in our own docs, but I think it's "good enough" for now. If/when we need better performance than this, we'll have to investigate it further.

❯ time docs/examples/quickstart/pi 
31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798609437027705392171762931767523846748184676694051320005681271452635608277857713427577896091736371787214684409012249534301465495853710507922796892589235420199561121290219608640344181598136297747713099605187072113499999983729780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083814206171776691473035982534904287554687311595628638823537875937519577818577805321712268066130019278766111959092164201989

real	0m0.035s
user	0m0.027s
sys	0m0.009s

[perlun]

Fixed in #425.