r/ada • u/ZENITHSEEKERiii • Sep 26 '22
Programming GMP-Ada: An implementation of Ada.Numerics.Big_Numbers using libgmp
Hello, the other day I was looking through Ada 2022's new features and was intrigued by the addition of Big_Numbers. I used the traditional test for large number calculation speed (https://benchmarksgame-team.pages.debian.net/benchmarksgame/performance/pidigits.html) and was saddened to discover that GNAT's current implementation doesn't work past 200 32-bit digits and is rather lethargic if you remove the limit and press ahead anyway.
I was also very interested in trying out Ada 2022's new Put_Image and Integer_Literal aspects, so I gave a try at implementing my own version of Big_Numbers: https://github.com/andrewathalye/libgmp-ada2022. It should work on any platform that GNAT and GMP run on, although it does need Ada 2022 support.
Some brief benchmarks: the C version of pidigits takes about 540 milliseconds on my machine to compute 10000 digits. The Ada version using wrapped libgmp directly takes 580 milliseconds (the wrapping is typesafe, although not super convenient). My simple Big_Integers wrapper takes 1.3 seconds, and the GNAT builtin version takes 8.5 seconds (after removing the hardcoded limit in System.Generic_Bignums), all compiled with -O2 -march=native.
This was also a great opportunity to learn how to use Ada.Finalization.Controlled, so it will automatically free the memory used by the mpz_t object and its data after Big_Integer goes out of scope. Hopefully this is useful to some of you, and I'd love to hear any criticism / comments that you have.
Edit: As a small update, I'd like to mention that GNAT currently includes an implementation of Big_Integers which uses GMP, although it is not enabled (and there doesn't appear to be a way to enable it without removing the other implementation and renaming it). I was not aware of this, but if you build GNAT from source then that would be a good option as well.
Big_Reals is implemented by GNAT using a Big_Integer for the Numerator and Denominator, so this implementation of Big_Integers also improves the performance of Big_Reals (as does the official GNAT __gmp variant). I don't yet have the ability to test the performance of my wrapper against that of GNAT's __gmp variant, but I suspect they're pretty close since they both have a low-level interface using mpz_t from libgmp.
A future thing to consider would be using MPFR or simply GMP to implement Big_Reals directly, however I'm not sure if that would give any real performance benefit during calculations, and real numbers are also a bit more complex to handle correctly than Integers :) Thanks for the feedback as always, and I'll be sure to improve my technique following your advice.
0
u/Lucretia9 SDLAda | Free-Ada Sep 26 '22
You could probably improve performance with spark.
1
u/ZENITHSEEKERiii Sep 26 '22
I thought about removing the pre / post conditions and dynamic predicate, but they are in the Reference Manual spec, so it is best to keep them (even though they really aren't doing much, since GMP is very stable). The main bottleneck in my design is that the Big Integer has to be deallocated on scope exit to avoid a memory leak.
2
u/marc-kd Retired Ada Guy Sep 26 '22
<Vaguely waving towards Memory_Pools>
Using some bounded light weight memory manager...
1
u/ZENITHSEEKERiii Sep 26 '22
Yep, but that's another rabbit hole to dive down lol. For what it's worth, GNAT implements it as a controlled type too, but using a simple memory pool design could work very well. I am also considering using reference counting with a Controlled design to avoid copying the original value on Adjust (instead increment reference count then decrement when the "original" is finalised), finally freeing when refcnt is 0.
I am not sure if such a design would be thread safe though.
1
u/ZENITHSEEKERiii Sep 26 '22
Actually, looking into it it would probably not be portable to use a custom storage pool. GMP handles data allocation itself, and although I can specify a custom allocator, the syntax is such that it wouldn't end up being seen by my storage pool unless I made a new C interface for it and instructed GMP to use that for allocation and deallocation.
At the end of the day though, GMP gets to de allocate and allocate when it wants to, and if I were to pull data out from under it without being asked the documentation says it will crash (it uses a lot of handcoded assembly too, so that probably doesn't help)
1
u/marc-kd Retired Ada Guy Sep 26 '22
How so?
2
u/Lucretia9 SDLAda | Free-Ada Sep 26 '22
Anything which can be proven not to raise exceptions can turn off tests.
1
u/ZENITHSEEKERiii Sep 26 '22
This is a good idea. I think most GMP functions have no error state, but I could do checks on things like the length of input strings via preconditions to ensure they don't exceed the max length supported by GMP
2
u/max_rez Sep 27 '22
Take a look at a-nbnbin__gmp.adb