BigInteger 300% performance increase

[tecel007]

I developed my own "BigInt" which outperforms BigInteger by a factor of 3 x when calculating Fibonacci(1073741824)

https://github.com/tecel007/BigInt

This performance advantage continues to increase as size grows due to threading.

I think it is way better and more elegant than all that "BigIntegerBuilder" stuff... ALSO, it should be obvious to anyone with low level computer architecture knowledge, that a 64-bit implementation, using a native 2's complement buffer will always outperform a combination of signs, bits and what_ever_the_hell BigIntegerBuilder is. Is there someone at MSFT that can look into this?

I don't have time to integrate and merge 🙁

[huoyaoyuan]

There are already a lot of known opportunities to optimize the performance of BigInteger: #92184 https://github.com/dotnet/runtime/pulls?q=is%3Apr+is%3Aopen+BigInteger

Currently (this year), the .NET team is focusing on more prioritized tasks and doesn't have enough capacity to do major involvement for BigInteger.

[tannergooding]

The reasons for BigInteger being "slower" are well-understood and primarily due to it being a readonly struct, therefore it requiring many allocations and copying across complex expressions. There is also the more minor, but still impactful, case of it using uint[] rather than nuint[]. Finally, there is some inefficiency in the stored representation that "could" be simplified by either using two's complement and/or storing the least number of significant bits alongside some metadata indicating the number of leading/trailing zero/ones (which reduces memory overhead and simplifies much of the leading/trailing logic for most operations). However, these are not the bulk of the costs in typical operations.

Each of these needs to be addressed independently, but the desired result won't actually be achieved without addressing all 3.

BigIntegerBuilder is the solution to the first issue and provides a mutable class plus supporting helpers to allow storing the temporary state of a complex expression, thus minimizing the allocation/copy overhead.

I would be amenable to someone from the community starting with the switch from uint[] to nuint[] as the first major improvement, but this will strictly need to keep churn to a minimum and not be a huge rewrite or going to change how the algorithms fundamentally work.

[tannergooding]

It is worth noting, however, that using BigInteger to do things like compute digits of PI, E, or the fibonacci sequence isn't really a "real world" use case and is not a good microbenchmark to use for comparing performance.

Many of these have spigot algorithms or known simplifications that mean the naive iterative or recursive approach isn't necessary or appropriate, particularly if perf is a consideration.

A lot of these microbenches also try and expand to numbers that are unrealistically large and not likely to be encountered in a real world production application, so aren't necessarily representative of where efforts to improve performance should be focused.

Improving the performance and usability of BigInteger, including for more domains/scenarios is goodness. We just need to ensure that it is targeting the right scenarios and being driven by the most relevant data.

[tecel007]

So you don't think 32-bit code running on 64-bit processors hurts at all?

Assuming 1 cycle each for read, read, add, write, N byte add ->

32-bit cycles = N / 4 * 4
64-bit cycles = N / 8 * 4

Seems like the code is still 32-bit because the author was lazy and / or didn't understand carry.

[tannergooding]

I didn't say or imply that, I explicitly stated that it was impactful:

There is also the more minor, but still impactful, case of it using uint[] rather than nuint[]

There are tradeoffs all around where using ulong[] universally would be bad for 32-bit and using uint[] can be cheaper, even on 64-bit, for some operations. At scale, using nuint[] which is 64-bits on 64-bit platforms and 32-bit on 32-bit platforms tends to be the right balance.

However, this is also not typically the bulk of the cost in any complex expression. The cost of doing 2x32-bit vs 1x64-bit addition tends to be 2 cycle vs 1 cycles, so theoretically a 50% throughput hit if you're using 32-bit on a 64-bit machine. However, you aren't going to bottleneck the CPU on this because you're the addition loop forms a dependency chain. Instead, you're likely to bottleneck or be impacted by the cost of memory where you're paying 4 cycles per L1 read and more around 60-80 cycles for an L3 read. Due to BigInteger being readonly, this means for any operation you have to allocate a new uncached buffer and traverse it. If you have temporaries, this means those buffers are potentially large but still short lived and thrown away, causing "cache pollution", because for something like Add you have to traverse at least 3 full buffers. This also has indirect impact to the rest of your program, something that a microbenchmark won't capture, because it causes more cache misses.

So, the actual negative cost of something like BigInteger today isn't with it using uint[] and technically performing 2x as many loop iterations as needed. The actual negative cost to a real production application, particularly in the context of complex expressions, is one that needs something like BigIntegerBuilder to solve. This is what will have the biggest positive impact towards BigInteger and while changing the backing buffer from uint[] to nuint[] so we can halve the number of loop iterations on 64-bit machines will be nice, it is minor in comparison

[tecel007]

@tannergooding Hi Tanner, thanks for your comments. I can see how nuint would be the perfect outcome for all. The issue I have is that currently, everyone has to put up with 32-bit performance. I did some bench marks and even made a graph for you to look at.

https://github.com/tecel007/BigInt

The results show that for big N....

• Addison/Subtraction 1.4 - 2.0 x faster
• Squaring 1.2 - 3.3 x faster
• Multiplication 1.2 - 2.4 x faster
• Imaginary world examples (Fibonacci) is 3.4 x faster

[kzrnm]

I developed my own "BigInt" which outperforms BigInteger by a factor of 250-300% when calculating Fibonacci(1,073,741,824)

what is Fibonacci(1,073,741,824)? I couldn't find any implementation of the function in your repository—only a mention of it in the README.

[tecel007]

Hi  kzrnm, Sorry, the 1 billionth Fibonacci number. Result = Fibonacci((ulong)1<<30); Takes 417 seconds with BitInt, verses 1500+ with BigInteger. It was just a way to test and baseline performance.  Fibonacci has a mix of add, sub, shift and mul.

[kzrnm]

I'm not asking for the definition of Fibonacci, but rather how it was measured. To be more specific, please provide the actual code you used for the measurement.
Without seeing the code, it's impossible to assess what was measured or how reliable the results are.

[tecel007]

All code, testing and measurement is supplied in... https://github.com/tecel007/BigInt As to, "How reliable the results are...", you can't be surprised that a highly optimised 64-bit, multithreaded implementation pwned 32-bit code and 1 thread?

[tecel007]

Hi @tannergooding, I updated my repo with performance metrics and even a graph

I think the results suggest

• For add/sub, memory bandwidth becomes a factor, 64-bits is still 1.4 - 2.0 x faster (before biginteger fails due to size)
• For mul, bit length is a factor (reaching 2.3 x faster (before biginteger fails due to size)
• For squaring, BigInt is exploiting much more symmetry reaching 3.6 x faster (before biginteger fails due to size)