Discussion:
[rust-dev] Arbitrary-precision arithmetic
Cody Mack
2014-09-01 12:51:56 UTC
Permalink
Hi,

Regarding issue #8937 (https://github.com/rust-lang/rust/issues/8937),
add a BigDecimal type, there is discussion about wrapping GMP, and
even possibly replacing Rust's current BigInt with this wrapper. One
comment mentions that Rust's current BigInt is ~100x slower than GMP
in some cases. However, GMP is licensed under LGPL.

1. Are there benchmarks displayed somewhere for comparison of BigInt
vs. GMP? It would be helpful to know cases from where the factor 100x
came.

2. Haskell's GHC
(https://ghc.haskell.org/trac/ghc/wiki/ReplacingGMPNotes) takes the
approach of having two implementations available for use: a
pure-Haskell implementation and a wrapper around GMP. The former does
not have the performance of the latter yet has GHC's BSD-style
license. Would there be any objections to having a pure-Rust
implementation and a GMP-wrapper implementation which users could
choose? Starting out, the pure-Rust implementation would not have the
years of optimization which GMP has, but effort could be made to
improve the pure-Rust performance.

Thanks.
Daniel Micay
2014-09-02 03:12:33 UTC
Permalink
Post by Cody Mack
Hi,
Regarding issue #8937 (https://github.com/rust-lang/rust/issues/8937),
add a BigDecimal type, there is discussion about wrapping GMP, and
even possibly replacing Rust's current BigInt with this wrapper. One
comment mentions that Rust's current BigInt is ~100x slower than GMP
in some cases. However, GMP is licensed under LGPL.
1. Are there benchmarks displayed somewhere for comparison of BigInt
vs. GMP? It would be helpful to know cases from where the factor 100x
came.
Rust's BigInt has progressively more inferior *time complexity* as the
numbers get bigger. It's far worse than 100x for very large numbers.

It's significantly slower for relatively small numbers because it lacks
years of work writing optimized assembly. This gets more important as
domain specific instructions like MULX are added to CPUs, along with
more diverse SIMD instructions with wider registers. Auto-vectorization
doesn't work for complex cases like this.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140901/3620eaee/attachment.sig>
Loading...