# Performance

Here are some benchmarks comparing the Malachite to two other libraries:

`num`

, the de facto standard bignum library for Rust.`rug`

, a library that calls GMP, a widely used, highly-optimized bignum library written in C.

The `num`

version that is compared against is 0.4.0, and the `rug`

version is 1.16.0.

The general trend is that Malachite is faster than `num`

due to better algorithms, and slower than
`rug`

. My guess is that the better performance of `rug`

is due partly to GMP’s use of inline
assembly (Malachite has none, being written entirely in safe Rust), and possibly due to operations
on Rust’s slices being a little slower than C’s raw pointers.

The following is just a small sample of the benchmarks that are available in Malachite. For each
benchmark, I’ve included the command that you can use to run it yourself. You can specify the
output file using `-o benchfile.gp`

, and then use gnuplot to convert
the `.gp`

to your format of choice. I like SVG:

`gnuplot -e "set terminal svg; l \"benchfile.gp\"" > benchfile.svg`

## Rational addition

`cargo run --features bin_build --release -- -l 100000 -m random -b benchmark_rational_add_library_comparison -c "mean_bits_n 256"`

The most significant operations involved in adding two rational numbers (fractions) are GCD computation and division.

For GCD computation, `num`

uses the
binary GCD algorithm, a quadratic algorithm.
Malachite follows GMP in using
Lehmer’s GCD algorithm, which takes
advantage of fast multiplication algorithms to achieve \(O(n (\log n)^2 \log \log n)\) time.

For division, `num`

uses Knuth’s
Algorithm D, which is
also quadratic. Malachite, again following GMP, uses several division algorithms depending on the
input size. For the largest inputs, it uses a kind of
Barrett reduction, which takes
\(O(n \log n \log \log n)\) time.

## Converting a Natural to a string

`cargo run --features bin_build --release -- -l 100000 -m random -b benchmark_natural_to_string_library_comparison -c "mean_bits_n 1024"`

When converting a natural number to a string, `num`

seems to use an \(O(n^{3/2})\) algorithm.
Malachite uses a divide-and-conquer algorithm that takes \(O(n (\log n)^2 \log \log n)\) time.

## Natural multiplication

`cargo run --features bin_build --release -- -l 20000 -m random -b benchmark_natural_mul_library_comparison -c "mean_bits_n 16384"`

For multiplying two natural numbers, `num`

uses a basecase quadratic algorithm for small inputs,
then Toom-22 (Karatsuba)
multiplication for larger inputs, and finally Toom-33 for the largest ones. This means that
multiplication takes \(O(n^{\log_3 5}) \approx O(n^{1.465})\) time.

Malachite also uses a basecase quadratic algorithm, then 13 variants of Toom-Cook multiplication, and finally Schönhage-Strassen (FFT) multiplication for the largest inputs, achieving \(O(n \log n \log \log n)\) time.

Given all of this machinery, it’s a little disappointing that Malachite isn’t much faster at
multiplying than `num`

is, in practice. I have a few improvements in mind that should boost
Malachite’s multiplication performance further.

For numbers of up to 1000 bits, all three libraries are about equally fast:

`cargo run --features bin_build --release -- -l 100000 -m random -b benchmark_natural_mul_library_comparison -c "mean_bits_n 64"`

## Natural addition

`cargo run --features bin_build --release -- -l 100000 -m random -b benchmark_natural_add_library_comparison -c "mean_bits_n 1024"`

Addition of natural numbers is fast for all three libraries, being a straightforward and
linear-time affair. Interestingly, `rug`

is the slowest of the bunch. I find it hard to
believe that GMP is slower than `num`

or Malachite, so maybe there’s some overhead
associated with FFI.

Copyright © 2024 Mikhail Hogrefe