so this would be as a better "bsd" default than current integer simple?

1. thats great! (i'm not sure if the openssl one is current best of breed amongh applicable c libs, but having more options isnt a bad thing)

2. one thing thats not discussed in this is what the static vs dynamic linking options here would be. Would this essentially mean that applicable ghc installs would need libssl and friends as dylibs? Or would that subset just be static linked in?

3. so it looks like openssl uses karastuba for large numbers, BUT, it seems the thresholds haven't been measured / tuned since i was in first or second grade 20-22 years ago!
   https://github.com/openssl/openssl/blob/1212818eb07add297fe562eba80ac46a9893781e/crypto/bn/bn_lcl.h#L332-L338

4. could you share some information about how on various representative algorithms libopen ssl fairs vs integer-simple and integer gmp?

theres a LOT of surface area for a good implementation, and among open source implementations, openssl may not be the best, though its omni presence is a boon.

for those watching from home
a) integer simple uses the grad school algorithm for multiplication
b) open ssl uses karatsuba https://en.wikipedia.org/wiki/Karatsuba_algorithm for things with more than 16 words (or limbs) of bits
c) gmp has a HUGE set of families of algorithms which run at various asymptotic / finite thresholds to handle all the trade offs in constant factors vs asymptotics.

• in GMP, for multiplication its grade school, then the toom algorithms (about 5-6 of them?), of which karatsuba is the simplest and slowest asymptotically), then " Schönhage–Strassen algorithm", which is pretty darn fast (theres some even faster asymptotic algorithms, but i've not seen any experimental data that shows them winning out on numbers you can fit into a modern computer).

point being: would be great to see some benchmarking data for mult/ sqrt, etc on rationals, naturals, integers, for showing how these all compare on the differently naive / sophisticated algorithms therein. :)

https://gmplib.org/repo/gmp/file/tip/mpn/x86_64/gmp-mparam.h is the current example thresholds of gmp. i think karatsuba corresponds to toom22

i guess i'm just concerned that the openssl tuning parameters are based on performance data older than some contributors to ghc and llvm :)

@cartazio Seems you have a far better understanding on the maths involved - thanks for the overview.

As far as linking is concerned, the current PoC is linked dynamically against the libcrypto existing on the system. Static linking, however, is mentioned a lot and should be possible.

Some benchmarks of multiplication and divison of small and big (4k bit) integers against the currently builtin (for most users thats integer-gmp) can be run with the PoC. Thr Readme page also shows (older) benchmarks agaonst integer-openssl. I will update them with some graphs soon.

There is also a some prior work on estimating performance of different open source integer libraries in the ghc wiki

Sounds like a good work to me.

But to an external observer it's very mysterious that you propose to call it integer-openssl. That makes it sounds as if this library is something to do with crypto etc. But I assume it's not. I'm guessing it's because the impl uses code from openssl?

Anyway, some less confusing name might be worth considering. Or not. Just raising it because it took me some time to realise that this proposal was not related to crypto

One of the suggested reasons for inclusion is to "allow public key algorithms". Of course you can
use that in the class room but not for serious crypto.

1. Haskell requires a integer library because it provides large arbitrary integer multiplication. But
   it would be dangerous to implement pki (I am assuming RSA) based on that. A better motivation
   could be representing integers in compilers.

2. For crypto purposes it would be sufficient (and better) to implement say 4026 or some fixed size integers carefully done so that there are no side channels etc.

3. More importantly if ghc has to depend on openssl that would be a pity. I do not think it is a good code base to depend on plus it bring out a lot of other useless (for ghc) stuff.

@piyush-kurur The cryptography example was given as the haskell package cryptonite implements public key cryptography primitives in haskell. And IIRC it is using Integer and operations on it. These were particularly slow in a real world scenario using integer-simple.

@cartazio Comparing the performance is definitely important and I tried to get early estimates how much faster than integer-simple and also how much slower than integer-gmp the prototypical implementation of multiplication and division is, I'll add these preliminary results to the PoC and link them in the proposal.
The improvements outlined in https://ghc.haskell.org/trac/ghc/wiki/Design/IntegerGmp2 are already incorporated into integer-gmp and were also considered when creating the current proof of concept of integer-openssl. Sorry just reread your comment, and you seem to refer to the link time selection section.

In general I'd like to say that I took the BIGNUM implementation of openssl as it was a) BSD licensed, b) complete, c) correct and d) likely available on most systems. If we find better alternatives, I am happy to update the proposal, name and implementation to use something else :)

My apologies if this was already clear: I think it would make the most sense to consider this as a more efficient alternative to integer-simple, not a replacement of integer-gmp. GMP seems to be the gold-standard of bignum libraries and I see no reason not to use it unless licensing concerns preclude its use.

I believe this is what the proposal as-written is proposing. Consequently, I don't think the concern that GHC will gain a dependency on OpenSSL is well-founded.

There's also https://github.com/libtom/libtommath (edit: and https://github.com/libtom/tomsfastmath now as well), I wonder how they compare to OpenSSL's bignums.

It seems to be dually licensed now, the first one is the asinine license you mention, and the other one is public domain (like SQLite).

libtommath looks promising as well. After a quick glance over the header, all required ops should be there.. all but one I could not find in openssl/bn so far either: integer <-> double conversion. I am not too good in maths, but in a quick chat with @hvr on monday, he mentioned that one probably does not want to do that by hand.

Other than that, also got updated to what the original intention by @hvr with integer-gmp and link time selection of an integer library was. I'll try to incorporate that into the proposal

Also, the https://github.com/libtom/libtommath/blob/develop/LICENSE is kinda hilarious!

@ch1bo I also suggest libtommath, in particular since it can be vendored easily into an integer-tommath package or into GHC by copying a single c file. Concerning integer<->double conversion, I made libtom/libtommath#123 a while ago, which is not yet part of tommath unfortunately.

@ch1bo thanks for the response. Also @bgamari thanks for clarifying that it is not
to replace gmp. Rereading the proposal the misunderstanding was entirely my fault.
However I am uncomfortable with having an indirect suggestion of using the multi-precision
Integer at the haskell level for cryptography. Even when the underlying library is designed for crypto
I think it is tricky as I am not sure how ghc moves around large integers in its memory during GC.

@minad if you could help shepard that license clarification into being in master that'd be lovely :)

(i'm a little bit too spread thin to do more than be a resource on the sidelines atm :) )

@cartazio I will see what I can do regarding libtommath

We really ought to us backpack for integer-*. I'd hope with 3 implementations it would finally be worth someone's time to do that.

@Ericson2314 yes, this should be a perfect fit for backpack. It was also brought up by @hvr as a suggestion.

I am pretty new to backpack, but I should incorporate it into the proposal..

Tommath changed the license to Unlicense, which is essentially public domain and similar to MIT in jurisdictions which do not recognize the concept of public domain.

Furthermore additional functions were added (float conversion,...), which are also useful for a hypothetical integer-tommath.

https://www.libtom.net/news/LTM_1.1.0RC1/

@Ericson2314 yes, this should be a perfect fit for backpack. It was also brought up by @hvr as a suggestion.

I am pretty new to backpack, but I should incorporate it into the proposal..

Since I tried this recently, here's some problems that will have to be solved:

• there's a bunch of CPP'ed optimizations in base (as well as a couple in text and bytestring I think?) which require intimate knowledge of Integer's particular constructors

• there's a some GHC code that peers into the internals of Integer's particular constructors

  • there's a handy core-prep optimization for turning small integers directly into calls to S# instead of going via mkInteger
  • there's some GHCi code for cleverly printing integers with :sp
  • ????

• integer-simple and integer-gmp don't expose quite the same functions (I'm working on that)

Ideally, we'd have GHC/Integer.hsig as a signature in base (and maybe even GHC/Natural.hsig?) and downstream consumers could instantiate base with integer-*, but it feels like there will be some work to get there.

Would this project make sense in the context of the GSOC? See https://www.reddit.com/r/haskell/comments/ae1i6z/reminder_please_submit_gsoc_ideas/edmpgit

Happy to have the implementation part of this as a GSoC project. If anyone here is interested in mentoring, please let me know.

Little activity recently, marking this as dormant.

Since I tried this recently, here's some problems that will have to be solved:

• there's a bunch of CPP'ed optimizations in base (as well as a couple in text and bytestring I think?) which require intimate knowledge of Integer's particular constructors

• there's a some GHC code that peers into the internals of Integer's particular constructors

  • there's a handy core-prep optimization for turning small integers directly into calls to S# instead of going via mkInteger
  • there's some GHCi code for cleverly printing integers with :sp
  • ????

• integer-simple and integer-gmp don't expose quite the same functions (I'm working on that)

@harpocrates Thanks for that - this is already merged right?

Ideally, we'd have GHC/Integer.hsig as a signature in base (and maybe even GHC/Natural.hsig?) and downstream consumers could instantiate base with integer-*, but it feels like there will be some work to get there.

Although I am a backpack noob, I gave this a try (also a while back) in here https://github.com/ch1bo/backpack-integer

However with the current state of backpack adoption a first iteration without backpack sounds more realistic?

Closing this due to inactivity, but it can be reopened when necessary.

Finally created a MR for GHC here: https://gitlab.haskell.org/ghc/ghc/merge_requests/1677. This adds integer-openssl in the same way as integer-gmp - some cleanup and possibly DRYing with integer-gmp could/should be done - feedback welcome.

I have been working on a new ghc-bignum package replacing both integer-gmp and integer-simple and hopefully available in GHC 8.12. Among other things, it makes the implementation of newer Integer/Natural backends way easier as each backend only has to provide a few functions: https://gitlab.haskell.org/ghc/ghc/merge_requests/2231

@ch1bo if you could try to add libcrypto as a backend for ghc-bignum, that would be great. You don't have to change anything in bytestring, text and so on anymore. I'd be glad to help as needed.

@hsyl20 Your work on ghc-bignum looks very promising, nice! It should be quite trivial to adapt https://github.com/ch1bo/integer-openssl to a backend of your ghc-bignum package. Is the package also available "outside" of GHC? i.e. with a test-suite or benchmarks

Is the package also available "outside" of GHC?

Sadly not anymore. It was initially in https://github.com/haskus/packages/tree/master/haskus-integer with some tests but a lot of things have changed since then (bug fixes, etc.).

with a test-suite or benchmarks

I have some benchmarks which use criterion-measurements from here (to avoid any dependency on non boot packages).

I still have to integrate the QuickCheck tests into GHC's testsuite. Last time I tried, installing QuickCheck for the tests seemed to be a pain.