cyclone
cyclone copied to clipboard
justinethier
Faster bignums
Would it be possible to use this library instead of libtommath? This has the potential to speed up all of our bignum operations. I am just not sure how much would need to be reworked in Cyclone.
To get started, EG on Debian:
apt show libtfm-dev
Alternatively, perhaps we can consolidate the libtommath code we use and find a way to speed it up (more aggressive compilation options, one source file, etc). That would also eliminate a run time dependency.
Here is a list of all the libtommath operations used by Cyclone:
mp_abs mp_add mp_and mp_clear mp_cmp mp_cmp_mag mp_copy mp_div mp_div_2 mp_error_to_string mp_expt_d mp_get_double mp_get_int mp_init mp_init_copy mp_int mp_mul mp_mul_2 mp_neg mp_or mp_radix_size mp_read_radix mp_set_int mp_sqrt mp_sub mp_sub_d mp_toradix mp_toradix_n mp_xor mp_zero
What about GMP? It's probably the most mature system.
It is needed to build the GCC, so it should be available on most systems.
@mnieper Point taken. The main concern with GMP are the license restrictions from the GPL. There are no such restrictions for LibTomMath.
Some (me included) would see this as an argument in favor, not against. :)
Anyway, GNU GMP is also licensed under the LGPL v3. I am not an expert in licenses but that license seems to be compatible with the rest of Cyclone.
@justinethier My recommendation would be to allow cyclone to be compiled with both gmp and tommath backends, this is also what I am doing in another language implementation. The backend can then be chosen depending on the requirements. I would advise against tfm, since it is unmaintained. See what I wrote in https://github.com/libtom/libtommath/issues/429.
Regarding bigint language implementations, there are a few other points to consider:
- Small integer unboxing. You are probably doing that if you implement some kind of scheme numeric tower?
- How does the library interact with the language allocator? For example GMP does not allow failing allocation. This has to be ensured in your custom allocation function. I don't think it is a big problem, but it is still some kind of wart.
- You probably implement parts of the runtime in the language itself. An option I considered was to use only the low-level GMP mpn-functions, since these are optimized in assembly. All the higher level functions have to be reimplemented on the higher level. GHC is basically doing that. If license is a concern, the low-level functions could be replicated in C, but this is a lot of work.
@minad Thanks, that's a good idea, as much as I would prefer not adding another library dependency.
Correct, small integers are used for small values. It would be prohibitively expensive to use bigints everywhere :)
I will have to look at the gmp API but it could be as simple as ifdef'ing around calls to the lower-level C functions and the corresponding bigint data structure. There is already code to handle allocations for ltm so it would probably just be a matter of doing the same for gmp.
@justinethier I made an attempt to implement a tiny embeddable bignum library which can optionally use the fast non-allocating mpn_* primitives of GMP. The library is just a thin wrapper around the GMP primitives. The wrapper takes care of allocations and the allocation function can be overwritten such that this plays together nicely with GC. This means no copying back and forth between GC and C heap is needed. In order to compile without GMP, I added naiive baseline implementations for the mpn_* primitives.
So if you want to avoid GMP and have fast performance this won't help you. But it could be interesting if you want to offer both a fast GMP and a slower statically linked option, by using the non-GMP primitives.
Maybe this is interesting for you. See here https://github.com/minad/z. There are no docs yet. I extracted this from my runtime.
@minad, very nice of you to look into it! Coincidentally in the past weekend I was trying to benchmark Cyclone using LFM and GMP. But gave up after noticing that LFM is not maintained anymore (as you've already mentioned) and that GMP is licensed under GPL.
Justin researched a bit for the decision on LTM. But your idea on dynamically linking into GMP as an option, while keeping in our case LTM as a fallback, seems very interesting! With this and a future support for arbitrary number of parameters to functions, what would be Cyclone's limitations? :)
I don't like comparisons per se and I suppose performance isn't among Cyclone's first goals, but just for the record I searched for "numeric" and other math-related tests on ecraven's benchmark and calculated Cyclone's position. Of course for most of the tests Gambit/Gerbil and Chez are the winners. For curiosity's sake, in order to occupy 2nd position on those benchmarks Cyclone would need more 11 first-place scores (on any tests) and, to occupy 1st position, 23. The current state is already tremendously impressive as Cyclone's core is a one-man piece of art in contrast to years of academia and industry investment on the fastest implementations.
| Tests (16 out of 57) | Cyclone's position (out of 29 impl.) |
|---|---|
| fib | 1 |
| fibfp | 1 |
| sum1 | 1 |
| fibc | 4 |
| mbrotz | 4 |
| nucleic | 6 |
| sumfp | 6 |
| diviter | 7 |
| mbrot | 7 |
| divrec | 9 |
| sum | 9 |
| fft | 10 |
| pnpoly | 10 |
| pi | 10 |
| primes | 11 |
| chudnovsky | 11 |
| Average position | 6.7 |
Am Mi., 23. Okt. 2019 um 05:06 Uhr schrieb Justin Ethier < [email protected]>:
@mnieper https://github.com/mnieper Point taken. The main concern with GMP are the license restrictions from the GPL. There are no such restrictions for LibTomMath.
With the few big monopolists in the computer sector and their embracement of open source, the GPL has become even more important than it was. In the long run, GPL'd code will lead to the fewest restrictions.
Marc
@arthurmaciel I am proposing something else now. I think the only provided implementation should be GMP, more specificially the low-level mpn functions, which can be used nicely in a garbage collected language, since they are not interacting with the allocator. However since you might still want to provide a static linking option, I made a thin wrapper on top of the GMP mpn primitives and added baseline implementations of the mpn functions. I don't believe it makes sense to support both LTM and GMP (I am saying that, despite being a committer to LTM). LTM ultimately falls short on performance. Furthermore since LTM also interacts with the allocator, it is a poor fit in contrast to the GMP mpn primitives.
@mnieper I agree with your point regarding monopolists. Therefore I think one should go with GMP and use free software where possible. But it is a hard sell for a programming language to produce binaries, which require dynamic linking to a third party library. This is something I really dislike about the GPL. The GPL messes with and limits technical decisions. I rather believe that the problem, which GPL and GNU aim to solve is a social and political one - unfortunately we cannot solve it by technical means.
Am Sa., 30. Mai 2020 um 15:27 Uhr schrieb Daniel Mendler < [email protected]>:
@mnieper https://github.com/mnieper I agree with your point regarding monopolists. Therefore I think one should go with GMP and use free software where possible. But it is a hard sell for a programming language to produce binaries, which require dynamic linking to a third party library. This is something I really dislike about the GPL. The GPL messes and limits technical decisions. I rather believe that the problem, which GPL and GNU aim to solve is a social and political one - unfortunately we cannot solve it by technical means.
GMP is licensed under the LGPLv3 as well, much like the glibc. So I don't see much of a difference to other language implementations, which also produce binaries that have to be dynamically linked to some (LGPL'd) third party libraries. If you want static linking, it is enough to make the object files available that have to be linked, which shouldn't be a problem even for those who do not want to share code.
The (L)GPL has to mess with technical stuff because it has to guarantee the freedom of the user to improve the program.
Marc
@arthurmaciel I am proposing something else now. I think the only provided implementation should be GMP, more specificially the low-level mpn functions, which can be used nicely in a garbage collected language, since they are not interacting with the allocator. However since you might still want to provide a static linking option, I made a thin wrapper on top of the GMP mpn primitives and added baseline implementations of the mpn functions. I don't believe it makes sense to support both LTM and GMP (I am saying that, despite being a committer to LTM). LTM ultimately falls short on performance. Furthermore since LTM also interacts with the allocator, it is a poor fit in contrast to the GMP mpn primitives.
@mnieper I agree with your point regarding monopolists. Therefore I think one should go with GMP and use free software where possible. But it is a hard sell for a programming language to produce binaries, which require dynamic linking to a third party library. This is something I really dislike about the GPL. The GPL messes with and limits technical decisions. I rather believe that the problem, which GPL and GNU aim to solve is a social and political one - unfortunately we cannot solve it by technical means.
@minad, sorry for misunderstanding your proposal. I am not sure it would be desirable to trust on GMP and the fallback be something slower than LTM. The fact is LTM, AFAIK, does not have benchmarks which would make clear this decision. Let's see what @justinethier thinks about it.
@arthurmaciel Regarding performance, my baseline implementations should be approximately as fast as GMP for small numbers. This will degrade quickly however for larger numbers. Maybe additional to the baseline karatsuba/toom multiplication could be added.
More ideas at this article: https://www.wilfred.me.uk/blog/2014/10/20/the-fastest-bigint-in-the-west/
It is fascinating how well the CPython implementation performs: https://github.com/python/cpython/blob/65d4639677d60ec503bb2ccd2a196e5347065f27/Objects/longobject.c