Improve performance of BigInteger

[axelheer]

Looking at other implementations like...

• IntXLib by @devoyster (faster for really huge numbers)
• NeinMath by @axelheer (faster for numbers with a few thousand bits)
• GNU MP (not .NET based, but super fast, if not the fastest at all)

...there should be room for one or another performance tweak.

Using managed code is by it's nature not as fast as working bare to the metal, but if the algorithms can be improved significantly, that would be great. Or other optimizations (pointer arithmetic, optimised assembly code) are viable as well for this big number stuff, maybe down at CoreCLR level (don't know if unsafe is allowed here).

What do you think?

[terrajobst]

Do you have a concrete scenario for which the performance is substantially worse?

[axelheer]

Any scenario involving big numbers with thousand bits or more.

The current multiplication implementation relies on "grammer-school" methods (as called by literature), which is good for "small" big numbers, but becomes very inefficient for "not so small" big numbers since it operates at Θ(n^2). Usually a switch to Karatsuba's algorithm (Θ(n^1.585)) at some threshold helps, after that a switch to Toom-3 (Θ(n^1.465)), then a switch to another faster algorithm with more overhead albeit less complexity... and I'm only talking about multiplication.

The IntXLib seems to use some kind of FFT based algorithm operating at Θ(n log n log log n). Maybe it's the Schönhage–Strassen algorithm, which is used for numbers with at least 33,000 decimal digits by the GNU MP library. The GNU MP library seems to be the fastest implementation available, it's also used by commercial software like Mathematica or Maple. Thus, it may be possible to just integrate that in a open source .NET framework. :)

On the other hand, my implementation contains many minor tweaks to get this calculations done faster, since I was interested in only a few thousand bits. It also contains the first step to optimize multiplication, and an optimized algorithm for squaring. You can find a simple performance comparison there. But note, like IntXLib it's just a small fun implementation -- if you want to see something serious, you'd have to look at GNU MP... (if you prefer "pure managed code" I could contribute mine, of course)

[rafidka]

@axelheer, out of curiosity, how can GNU MP library be used within C#? I know in C# we can use DllImport to link to libraries built for Windows, but the aim here should be cross platform, right? Unless BigInteger is moved to coreclr so that we can use C/C++, I can't think of any way to use GNU MP for it.

[axelheer]

@rafidka yeah, I think some kind of movement to / involvement of CoreCLR would be required. Since the GNU MP library is already cross platform, I'm fanciful enough to imaging that... Actually, I don't have any idea how to do that, I'd just like a faster BigInteger, which we can get with C# too (but not that fast, and not that mature).

[rafidka]

I see. Yeah, now it makes more sense to me, it definitely need some support from CoreCLR.
@joshfree, I see you added 'upforgrabs' label for this issue, but it looks like there is no agreement on plan on how to do this, so what is the status?

[Maxwe11]

from issue # 1298

In the desktop .NET Framework, although we have a purely managed implementation of the deflate algorithm, customers have reported that the popular cross-platform open-source zlib library is faster and performs high quality compression. In response we include zlib, which we wrap and delegate to. We build it from source using the unmodified 1.2.3 version of the sources in the FX partition, and name the resulting output “clrcompression.dll.”

So GMP could be used 😄

[joshfree]

@rafidka @axelheer if you're interested in working on BigInteger and improving some aspect of it's performance (for example GCD), then you can suggest an improvement and get feedback on your design.

[axelheer]

@joshfree @mellinoe then let me ask one concrete question: is "integrating" the GNU MP library (as already pointed out) an option?

[KrzysztofCwalina]

I understand that there might be additional performance benefits from using C++/assembly, but I think it would be worth trying to simply use the algorithms @axelheer mentions but leave the implementation in C#. Axel, would you be interested in doing such experiment to see what the perf gains and gaps would be?

[axelheer]

@KrzysztofCwalina if you prefer a (safe?) C# based implementation, I can contribute code of mine (if not all of it). It's based on "raw" computations on uint[] objects, which leaves much room for optimizations and is still very readable (more readable for me, in fact -- but that's opinion based). Thus, it would mean dropping much of the current BigIntegerBuilder construction (if not all of it), which is internal stuff anyway.

In addition to it I already made a simple (too simple?) performance comparison there. And since there are already bunch of Unit Tests for the current implementation, we should be quite sure that the "new" code doesn't brake anything. If this sounds reasonable to you, I would indeed "grap" that issue (and hope it's not much more work than I'm guessing... :p).

[KrzysztofCwalina]

@axelheer, yeah, C# based implementation. If it has some unsafe code, that would be fine too (if needed for perf or other reasons).

[axelheer]

@KrzysztofCwalina I made a few tests today for an unsafe implementation for squaring / multiplying (to get rid of some index calculations). It's faster, but not that much. Thus, I would stick to the more convenient safe version for now (but I can provide an unsafe version too, if you prefer).

How should we / I start? Should I just try to "migrate" my Code to BigInteger? Or should we discuss other aspects?

[KrzysztofCwalina]

It would be great if you could simply migrate the code and submit a PR (assuming no API changes are required). If API changes are required (which I don't think you need), then it might be better to do an API review first.

Initially a smaller PR would be best (e.g. just multiplication) to see how it goes. If you could provide perf deltas for memory (allocations) and speed (either elapsed time or sampling profile) for some representative values (big/small), it would help us evaluate the change.

[axelheer]

After "contributing" these optimizations there are still some tasks open:

• Add performance tests as unit tests (as suggested by @stephentoub in Improve performance of BigInteger.Pow/ModPow corefx#2182)
• Port GCD (which is already very sophisticated) to BigIntegerCalculator
• Cleanup (maybe drop) remaining BigIntegerBuilder code

By the way, can someone mark this issue as "grabbed"? Thanks!

[stephentoub]

Thanks for continuing to work on this, @axelheer. I marked it as grabbed.

[axelheer]

I'm finally done here. There is other stuff for very huge numbers (as mentioned within the discussion above), but I'm quite happy now. Please close this issue or remove the "grabbed" tag, depending on your further plans.

And thank you very much for making this even possible! I really like these new ways our industry is going. Those performance improvements were much more work than I've expected, but I learned many things too, wich I didn't expect either. In a word, it was a great experience (at least for me).

[joshfree]

Thank you for all of your contributions to BigInteger and .NET Core Axel!

[stephentoub]

Yes, @axelheer, thank you very much for all of your contributions!