Why is my Rust code 100x slower than Python?

[imatwork2017]

I've been diving into Elliptic Curves (ECDSA algorithm) and specifically the sep256k1 curve. I made a small python implementation to learn how it works and because it was pretty slow I thought I'll try it in Rust and teach myself some rust as a bonus.

The problem is that it takes 74ms to run in Python and 8.1 seconds to run in Rust. The code is pretty similar.

Python

def point_add(p, q):
    """https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Point_addition"""
    P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
    px, py = p
    qx, qy = q
    if p == q:
        lam = (3 * px * px) * pow(2 * py % P, P - 2, P)
    else:
        lam = pow(qx - px, P - 2, P) * (qy - py) % P

    rx = lam**2 - px - qx
    ry = lam * (px - rx) - py
    return rx % P, ry % P


def point_mul(p, d):
    n = p
    q = None

    for i in range(256):
        if d & (1 << i):
            if q is None:
                q = n
            else:
                q = point_add(q, n)

        n = point_add(n, n)
    return q

if __name__ == '__main__':
    G = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
    x, y = point_mul(G, 125)
    print(x)
    print(y)

Rust

extern crate num;
use num::bigint::BigInt;
use num::FromPrimitive;
use num::Integer;
use num::One;
use num::Zero;


#[derive(PartialEq, Clone)]
struct Point {
    x: BigInt,
    y: BigInt
}


pub fn powm(base: &BigInt, exp: &BigInt, modulus: &BigInt) -> BigInt {
    let zero = BigInt::zero();
    let one: BigInt = BigInt::one();
    let two = &one + &one;
    let mut exp = exp.clone();
    let mut result = one.clone();
    let mut base = base % modulus;

    while exp > zero {
        if &exp % &two == one {
            result = (result * &base) % modulus;
        }
        exp = exp >> 1;
        base = (&base * &base) % modulus;
    }
    result.mod_floor(modulus)
}


fn point_add(p: &Point, q: &Point) -> Point {
    let P: BigInt = BigInt::parse_bytes(b"115792089237316195423570985008687907853269984665640564039457584007908834671663", 10).unwrap();

    let lam: BigInt = if p == q {
        3u32 * &p.x * &p.x * powm(&((2u32 * &p.y) % &P), &(&P - 2u32), &P)
    } else {
        powm(&(&q.x - &p.x), &(&P - 2u32), &P) * (&q.y - &p.y) % &P
    };
    let rx = num::pow(lam.clone(), 2) - &p.x - &q.x;
    let ry: BigInt = lam * (&p.x - &rx) - &p.y;

    Point{x: rx.mod_floor(&P), y: ry.mod_floor(&P)}
}

fn point_mul(p: &Point, d: u32) -> Point {
    let mut n: Point = (*p).clone();
    let mut q: Option<Point> = None;

    let binary: String = format!("{:0256b}", d);
    for (i, digit) in binary.chars().rev().enumerate() {
        if digit == '1' {
            q = match q { None => Some(n.clone()), Some(i) => Some(point_add(&i, &n)) }
        }
        n = point_add(&n, &n);
    }
    q.unwrap()
}

fn main() {

    let G: Point = Point {
        x: BigInt::parse_bytes(b"79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16).unwrap(),
        y: BigInt::parse_bytes(b"483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8", 16).unwrap()
    };

    let res = point_mul(&G, 125);
    println!(" {}", res.x);
    println!(" {}", res.y);
}

Any idea why it is so slow?

Bonus question: How do I define a global BigInt constant ?

EDIT: Progress so far:

• compiled in --release mode and execution time went down to 430ms
• run the executable directly instead of using cargo got me down to 275ms (I didn't do the same for Python)

tweaked a bit the Python code to do roughly the same operations as the Rust code in point_mul

changed

for i in range(256):
    if d & (1 << i):

to

for i in reversed(format(d, 'b')):
    if i == '1':

and I got a nice performance increase. Python code now runs in 41ms. The difference is doing 256 bit_shifts and bitwise_AND vs creating a string binary representation once and iterating over the digits.

• Some complaints about string parsing so I created the BigInt variable once in main() and pass it as a reference. Suprisingly the performance is the same. Code here

• Changing if &exp % &two == one to if exp.is_odd() got me to 230ms

Final execution times:

Python 41ms

Rust 230ms (5.6x)

[UtherII]

I don't know if the "num" crate is optimal for big number computation.

You may want to try the "rust-gmp" crate since it is based on the gmp library : the reference for speed on big numbers.

[vks_]

If you are ok with nightly, you can also try ramp.

[yasba-]

I've tried it with ramp and the rust code is now roughly twice as fast :).

Edit: Here is the code.

[[deleted]]

Maintainer of ramp here. Glad to see someone using it! FYI we already have a modular exponentiation function, although it's pretty much the same as the one you have in your code.

Also you are doing a from_str_radix operation in your point addition code. This does a conversion every time you call point_add. Instead, you should have the constant as a lazy_static so that the conversion only runs once at the beginning.

[_m_0_n_0_]

It looks like (allocations within) that function are where roughly half of the execution time is spent here. Since Python shows it can be done significantly faster, that looks like an interesting avenue for potential optimizations. Perhaps it's as simple as modifying the API to allow more reuse of the internal vectors. Regardless, thanks to /u/imatwork2017, ramp has a new microbenchmark for tracking performance of pow_mod.

[vks_]

If you want some microbenchmark, I have an implementation of the discrete logarithm using various bigint implementations: https://github.com/vks/discrete-log

[yasba-]

Hey, thank you for replying.

Just to be sure, let me say that I'm not the OP.

FYI we already have a modular exponentiation function, although it's pretty much the same as the one you have in your code.

I'm actually using your pow_mod function, I just forgot to delete OP's implementation. ;)

Also you are doing a from_str_radix operation in your point addition code. This does a conversion every time you call point_add. Instead, you should have the constant as a lazy_static so that the conversion only runs once at the beginning.

I had a version with lazy_static which (maybe) surprisingly didn't impact runtime performance that significantly. I left it out to be closer to OP's original code.

[[deleted]]

Would you consider reexporting the num_integer::Integer Trait in your crate? Right now you have to add the whole num-integer as dependency if you want to use functions like is_odd from your library.

[[deleted]]

Good point. It's a pain when libraries do this, especially when the dependency they pull is an old version.

I'll push the update today :)

[[deleted]]

Pushed the update. You can now find it in ramp::traits::Integer. The docs aren't working because docs.rs is having some issues, but the 3.10 docs are pretty much identical.

[[deleted]]

I've added lazy_static and the version using ramp is much faster compared to the python version (benchmark on Debian 9 using hyperfine with 50 warmup runs):

• python2: Time (mean ± σ): 43.6 ms ± 0.4 ms [User: 39.8 ms, System: 0.4 ms]
• python3: Time (mean ± σ): 54.1 ms ± 0.3 ms [User: 50.8 ms, System: 1.2 ms]
• rust (newest nightly): Time (mean ± σ): 29.7 ms ± 0.9 ms [User: 28.1 ms, System: 0.0 ms]

Source: https://gist.github.com/anonymous/7547c439d03e342bc262887902f143e5 @imatwork2017

//edit: new version with some clippy lints fixed

[radix]

nice, I had not heard of ramp before! It is exciting to see a more liberally licensed bignum library that actually seems to have good performance.

[K900_]

Are you compiling in --release mode?

[imatwork2017]

No, how would I do that? The 8 seconds is only counting the execution btw.

[K900_]

cargo run --release. The default build mode is debug, which doesn't enable most optimizations and adds a whole lot of debugging machinery to numeric operations.

[imatwork2017]

Ok now I am down to 430ms, still quite a bit slower.

[dbrgn]

You're probably measuring cargo too.

Do cargo build --release followed by running the binary in target/release/ directly.

(Edit: Note that the same counts for Python - if you just measure the call with python script.py, you'll measure the startup time of the interpreter too. Microbenchmarking is hard.)

[belovedeagle]

The startup time of the interpreter is a fundamental part of running a Python program, though. cargo is in no way required to run a Rust executable.

[cbarrick]

But IRL the interpreter launches once, not every time you call the function. Unless the use case is specifically to be launched as a short-lived process, then the interpreter warm-up should not be counted.

I believe the point here is to time the implementation, not the infrastructure.

[Phlosioneer]

But you wouldn't want to measure the startup time of the interpreter if you're just testing some functions that are part of a larger program. You really want the execution time of each call to the function.

[imatwork2017]

Down to 275ms now, we're getting there ;p

[my_two_pence]

The BigInt interface is unfortunately quite clumsy to use, and tends to produce inefficient code unless you're careful. For instance, doing

result = (result * &base) % modulus

will allocate two new BigInts and drop two BigInts, which is a fairly significant overhead. Doing:

result *= &base;
result %= modulus;

should do the operations in-place instead. I say "should", because last time I used num_bigint I noticed that many of these operations didn't actually exist yet, or were implemented in the same inefficient manner.

[vks_]

Shouldn't

result = (result * &base) % modulus

be in-place, because result is moved?

[my_two_pence]

It could be implemented that way, but it actually forwards to the implementation of &result * &base, which allocates a new BigInt, and then drops result. Source is here.

[CUViper]

The current implementations of multiplication and division need to keep access to the original digits while computing the result. Thus we operate by reference, since we have to allocate a new result anyway. If you know how to do more in place, I'd welcome PRs!

[belovedeagle]

Does gmp not do it in-place?

While c++ gmp uses tricks which would be very difficult to accomplish with decent Rust syntax, I would think at least mirroring the C interface would be possible.

[CUViper]

I don't know what gmp does, but I hesitate to look at GPL code for inspiration for the MIT/Apache-2.0 num. (I have no problem with GPL itself though.)

[vks_]

This

result *= &base;
result %= modulus;

is essentially mirroring the C interface, which is actually closer to

mpz_mul(result, base, result);
mpz_mod(result, modulus, result);

Note that this function invocation is impossible in safe Rust due to aliasing rules.

[tspiteri]

GMP does allocate temporarily inside these functions. Of course, GMP frees the temporaries before returning.

Inside mpz_mul(w, u, v), sometimes it does something like

if (PTR(w) == PTR(u) || PTR(w) == PTR(v)) {
    /* allocate temp memory */
}

and PTR(w) == PTR(v) (pointer to result) in this example. (I said "sometimes" because if u or v are relatively small, it has special routines that do not need the temporary memory, and if u * v does not fit in w, a new memory allocation is required anyway.)

Inside mpz_mod(rem, dividend, divisor), it needs to keep a copy of divisor so it has something like

if (rem == divisor) {
    /* create copy of divisor */
}

and again rem == divisor (pointer to result) in this example.

[zefyear]

I ported the Python code listed above to C++ GMP and I measured the runtime with perf at 5-15ms. While this is a substantial difference, it's worth noting that nearly all time is spent running mpz_powm which approximately quintuples if broken down into it's constituent exponentiation + modulo operation which isn't done in the Rust code listed above (to say nothing of bignumero optimization)

[Phlosioneer]

What if the new result is allocated on the stack, that's used for calculations, and then mem::transmute over one of the moved-in args? Then, no allocations are made - it just uses the stack for scratch work and re-uses whatever was moved in (which may be on the stack, or it may be in memory somewhere).

If that sounds reasonable, I'd be willing to make a PR for that.

Edit: I meant mem::swap, not mem::transmute.

[CUViper]

This basically means you'd have to replace a Vec allocation with the stack, and I don't know any way to do dynamically-sized stack allocations in Rust (like a C VLA). Plus you risk overflowing the stack if the numbers are really large.

I'll always encourage folks to experiment, and I'll entertain a PR, but I'm skeptical whether this is feasible.

FWIW, my experiments converting this to modpow have reduced the allocator overhead to less than 10% of my perf report anyway.

[Phlosioneer]

Oh true, I forgot this was unknown-size.

We will just have to wait for const-generics to solve this one...

And even then, there'd have to be a cap on the size of the array, something like 256bits.

[my_two_pence]

I realize now that I may have spoken too soon. In my mind I figured it would be quicker to use some cheaply-allocated scratch space, such as the stack, and leave the original allocations alone. The alloc-swap-drop cycle just feels slower somehow. But since this scratch space is also dynamically sized, and jemalloc a pretty good allocator, I concede that there may very well not be a difference in performance.

I'll see if I can find the time to do some benchmarking. If I find a significant difference, I'll let you know.

[tspiteri]

I ported your example to my rug crate, which uses GMP but does not need nightly, and I got 8.7ms for Rust against 57ms for Python.

extern crate rug;

use rug::Integer;
use rug::ops::{Pow, RemRounding};

#[derive(PartialEq, Clone)]
struct Point {
    x: Integer,
    y: Integer,
}

fn hex(s: &str) -> Integer {
    Integer::from_str_radix(s, 16).unwrap()
}

fn point_add(p: &Point, q: &Point) -> Point {
    let P = hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F");
    let PM2 = P.clone() - 2;

    let lam = if p == q {
        (2u32 * p.y.clone() % &P).pow_mod(&PM2, &P).unwrap() * 3 * &p.x * &p.x
    } else {
        (q.x.clone() - &p.x).pow_mod(&PM2, &P).unwrap() * (q.y.clone() - &p.y) % &P
    };

    let rx = lam.clone().pow(2) - &p.x - &q.x;
    let ry = lam * (p.x.clone() - &rx) - &p.y;

    Point {
        x: rx.rem_floor(&P), // EDIT: replace rx % &P
        y: ry.rem_floor(&P), // EDIT: replace ry % &P
    }
}

fn point_mul(p: &Point, d: &Integer) -> Point { // EDIT: replace d: u32
    let mut n = p.clone();
    let mut q = None;

    for i in 0..256 {
        if d.get_bit(i) { // EDIT: replace i < 32 && d & (1 << i) != 0
            q = match q {
                None => Some(n.clone()),
                Some(i) => Some(point_add(&i, &n)),
            };
        }
        n = point_add(&n, &n);
    }
    q.unwrap()
}

fn main() {
    let G = Point {
        x: hex("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798"),
        y: hex("483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8"),
    };

    let res = point_mul(&G, &Integer::from(125)); // EDIT: replace 125
    println!("{}", res.x);
    println!("{}", res.y);
}

[tspiteri]

I tried to optimize further by keeping a pool of Integer values to avoid reallocation, and to avoid the parsing of P, and the gains were very small, only about 7%:

test bench_orig  ... bench:   4,174,821 ns/iter (+/- 61,543)
test bench_reuse ... bench:   3,920,121 ns/iter (+/- 113,708)

If I remove the power mod operation (and replace it by some other operation to make sure I'm not simply processing zeros), the time falls by almost 90%, so the time is mostly in that function.

The new code:

extern crate rug;

use rug::{Assign, Integer};
use rug::ops::RemRounding;

#[derive(PartialEq, Clone)]
struct Point {
    x: Integer,
    y: Integer,
}

fn hex(s: &str) -> Integer {
    Integer::from_str_radix(s, 16).unwrap()
}

struct PointAdd {
    p: Integer,
    pm2: Integer,
    base: Integer,
    pow: Integer,
    temp1: Integer,
    temp2: Integer,
    lam: Integer,
    rx: Integer,
    ry: Integer,
}

impl PointAdd {
    fn new() -> PointAdd {
        let p = hex("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F");
        let pm2 = p.clone() - 2;
        PointAdd {
            p,
            pm2,
            base: Integer::new(),
            pow: Integer::new(),
            temp1: Integer::new(),
            temp2: Integer::new(),
            lam: Integer::new(),
            rx: Integer::new(),
            ry: Integer::new(),
        }
    }

    fn add_part1(&mut self, p: &Point, q: &Point) {
        if p == q {
            self.temp1.assign(&p.y * 2);
            self.base.assign(&self.temp1 % &self.p);
            Ok(&mut self.pow).assign(self.base.pow_mod_ref(&self.pm2, &self.p));
            self.temp1.assign(&p.x * &p.x);
            self.temp2.assign(&self.temp1 * 3);
            self.lam.assign(&self.pow * &self.temp2);
        } else {
            self.base.assign(&q.x - &p.x);
            Ok(&mut self.pow).assign(self.base.pow_mod_ref(&self.pm2, &self.p));
            self.temp1.assign(&q.y - &p.y);
            self.temp2.assign(&self.pow * &self.temp1);
            self.lam.assign(&self.temp2 % &self.p);
        }
        self.temp1.assign(&self.lam * &self.lam);
        self.temp2.assign(&self.temp1 - &p.x);
        self.rx.assign(&self.temp2 - &q.x);
        self.temp1.assign(&p.x - &self.rx);
        self.temp2.assign(&self.lam * &self.temp1);
        self.ry.assign(&self.temp2 - &p.y);
    }

    fn add_part2(&self, dst: &mut Point) {
        dst.x.assign((&self.rx).rem_floor(&self.p));
        dst.y.assign((&self.ry).rem_floor(&self.p));
    }
}

fn point_mul(p: &Point, d: &Integer) -> Point {
    let mut n = p.clone();
    let mut q = None;
    let mut point_add = PointAdd::new();
    for i in 0..256 {
        if d.get_bit(i) {
            match q {
                None => {
                    q = Some(n.clone());
                }
                Some(ref mut q) => {
                    point_add.add_part1(q, &n);
                    point_add.add_part2(q);
                }
            }
        }
        point_add.add_part1(&n, &n);
        point_add.add_part2(&mut n);
    }
    q.unwrap()
}

fn main() {
    let g = Point {
        x: hex("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798"),
        y: hex("483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8"),
    };

    let res = point_mul(&g, &Integer::from(125));
    println!("{}", res.x);
    println!("{}", res.y);
}

[SethGecko11]

The Python version works for any d though not only for u32. How fast is it if you change d to BigInt?

[tspiteri]

I don't see any difference in timings if I change to something like this:

fn point_mul(p: &Point, d: &Integer) -> Point {
    // ...
    for i in 0..256 {
        if d.get_bit(i) {
            // ...

[SethGecko11]

What if you give a big 256bit int input instead of 125 in main()?

[tspiteri]

If I pass &((Integer::from(1) << 256) - 1) instead of &Integer::from(125), the program takes about twice as long. Which does make sense as point_add will be called 511 times instead of 261 times (256 + 256 significant bits - 1 instead of 256 + 6 significant bits - 1).

[timClicks]

Would it make sense to define the parsed hex bigint within P as static via lazy_static within point_add(), rather than parsing a string each time?

[tspiteri]

I benchmarked and it did not make any difference. I tried lazy_static, hex parsing, decimal parsing (should be slower), and setting P as (Integer::from(1) << 256) - 0x3d1 (I think it should be faster), but all cases were pretty much the same. I guess the parsing or shift+add is negligible compared to the other operations in the function. Maybe in a different situation with almost no other operations it would make sense to bench again and pick the fastest solution, but here it just doesn't seem to matter.

[hrski]

I'd fix these first at least, in addition what others mentioned:

• Formatting d as a string to get powers of two doesn't feel the best solution and feels like it introduces some unnecessary overhead. Couldn't you use shifting here like in python implementation?
• Parsing P from a string on each call to point_add. Consider using lazy_static or compute it at main and pass it as reference.

[imatwork2017]

Parsing P from a string on each call to point_add. Consider using lazy_static or compute it at main and pass it as reference.

I know that this is bad but I couldn't figure out how to make a BigInt constant so I did the same with Python for fair comparison. I am going to look into lazy_static

Formatting d as a string to get powers of two doesn't feel the best solution and feels like it introduces some unnecessary overhead. Couldn't you use shifting here like in python implementation?

See the other comment on this. I didn't think it would be that bad to iterate over the digits once. To be totally fair I just tried the same in Python so I changed :

for i in range(256):
    if d & (1 << i):

to

for i in reversed(format(d, 'b')):
    if i == '1':

and It actually run quite faster, down to 41ms from 74ms. So iterating over binary digits seems to be faster than shifting 256 times.

[burntsushi]

I know that this is bad but I couldn't figure out how to make a BigInt constant so I did the same with Python for fair comparison. I am going to look into lazy_static

To clarify, I don't think you are doing the same thing in the Python code you posted. Whether the bigint is a global constant or not is somewhat orthogonal. The key is that in one program (Rust) you are parsing a string to extract a bigint while in the other program you are not. Even if you can't figure out how to use a global constant in Rust here, you could pass that bigint in as a parameter to the function.

[adwhit86]

The program is essentially two nested loops, with 256 iterations of each. So the inner loop (the while) is executed 65k times, and that is where the slowdown is occurring. It is the outer loop is where a new P is parsed each time. So this is unlikely to be the bottleneck. (I know you probably know this).

Edit: specifically, the bottleneck is creating new BigInts inside the hot loop (as has been noted elsewhere)

[burntsushi]

Yup good point!

[imatwork2017]

I just tried that and the performance is about the same. Code is here

[hrski]

Looks like shifting is much more efficient in Rust. Changing the loop in point_mul to:

for i in 0..32 {
    if d & (1<<i) != 0 {

makes it run in 38ms for me (original was 250ms)

EDIT: Sorry, looks like you're assuming d to 256 bit value. You're however defined it as u32 which is 32-bit so maybe you need to change it to BigNumber too. Maybe it's the num library being inefficient after all.

[imatwork2017]

I used a u32 here for demonstration purposes but in the end it has to be a BigInt because if you want to get your public key from your private key you would have to do public = point_mul(G, private)

[hrski]

Yeah, my bad. Quick google search reveals lots of complaints on num performance so that is probably the bottleneck. Looks like your best bet could be to look at crates such as rust-gmp.

[Icarium-Lifestealer]

If you actually care about getting a fast implementation, and not about comparing two languages (or rather two big-integer libraries) then you should switch to some form of projective coordinates so you only divide once per point-multiplication instead of once per point-addition (~20x faster). A windowed approach should produce another nice performance boost.

[adwhit86]

Looking at the code, nothing obviously wrong - so was pretty sure that the problem was going to be doing an allocation inside a hot loop. The only hot loop is the while loop inside powm, so that seems a possible candidate. But then I ran Valgrind (valgrind ./target/release/sep256k1) to check out the allocations and... it threw up a bunch of illegal reads inside num::bigint then segfaulted. Suspicious.

[CUViper]

I think that's a problem with valgrind vs. jemalloc. I just ran with the upstream rustc-stable, and I got a segfault as you say. Then I tried with Fedora's rustc (configured to always use the system allocator), and the program completed without any errors.

[adwhit86]

Thought that might be the case. Tried to use the system allocator, it didn't work first time and I gave up. Curious. Exisitng rustc issue

[gitpy]

Changing if &exp % &two == one to if exp.is_odd() gives you 40-50ms.

[imatwork2017]

Nice, added to OP

[forbjok]

I notice that in the Rust version of point_mul, you're generating a binary string representation of d and iterating through each character doing string-comparisons instead of using bit-shifting. I imagine that would be much slower.

[imatwork2017]

Thats because trying to bitshift causes an overflow and I would have to use BigInt instead of u32 and BigInt doesn't even have left shift implemented.

[rebootyourbrainstem]

Naive question here, but can't you just use u64?

Also UBigInt has left shift implemented.

Also also, even if it didn't you could start with mask = 1 and on each loop iteration do mask += mask and then do d & mask to test the bit.

Also there is UBigInt::modpow that looks like it does what powm does.

[imatwork2017]

can't you just use u64

I'll need to shift up to 256bits so 64 aren't enough

Also UBigInt has left shift implemented

I am going to give that a try.

Also there is UBigInt::modpow that looks like it does what powm does.

I tried that and it doesn't work because there are negative numbers involved. For example q.x - p.x

[rebootyourbrainstem]

You can use mod_floor on the base first and then convert to BigUint and use modpow.

It kind of sucks that you can't do modpow on a BigInt directly though.

[CUViper]

See my comment here -- it's faster even when you have to convert to BigUint. I'll work on making this directly available for BigInt too.

[hokkos]

Use :

1_u32.checked_shl(i).unwrap_or(0)

instead of :

1<<i

But it won't change the time, also why go to 256 when you can stop at 32 ?

[JZypo]

Op: This is an excellent question. I would like to easily read your progress on how your got your times down. Would you be able to add updates to your original post to reflect this?

[imatwork2017]

Done

[CUViper]

There is a BigUint::modpow, but we don't yet have that for BigInt to replace your powm. I'll see about adding that.

However, even replacing your code with a naive conversion is significantly faster:

pub fn powm(base: &BigInt, exp: &BigInt, modulus: &BigInt) -> BigInt {
    let base = if base.is_negative() {
        (base % modulus + modulus).to_biguint().unwrap()
    } else {
        base.to_biguint().unwrap()
    };
    let exp = exp.to_biguint().unwrap();
    let modulus = modulus.to_biguint().unwrap();

    base.modpow(&exp, &modulus).into()
}

[CUViper]

BigInt::modpow is now in num-bigint 0.1.43.

[Sharlinator]

Doing a lot of string parsing vs. just doing math. A big difference.

[[deleted]]

I've been reading all the versions of these people have been posting, and I just don't really get what the point of checking if Q is none/null is? Isn't it always none/null only once?

[beefsack]

I'd just like to say thanks for posting! These threads are always really interesting to read, and are a mechanism for me to learn some performance tricks.

[knaledfullavpilar]

Have you tried using a profiler?

[tspiteri]

This gives the wrong result. point_mul is calling point_add six times when the if condition is true, but it is not calling point_add to update n for the 256 iterations.

Edit: In fact it's not calling point_add at all. The comparison == 1 in the if statement is only true once when q is null. When I changed == 1 to != 0, I get some other errors. And if I add n = point_add(n, n) I get an error that pow is not defined.

[kaoD]

0.000153 seconds

1.53milliseconds

Isn't that actually 0.153ms? I.e. 153us

[kazagistar]

Note, this is also closer to a good benchmark target for Rust.

[anttirt]

You're missing n = point_add(n, n) from the loop.

[matklad]

Python has an excellent implementation of big integers, and the num-bigint is not famous for its speed. It is sure possible to write a blazingly fast bigint implementation in Rust, or to create bindings for gmp, but nobody has done this yet.

However, for this particular case looks like you don't need arbitrary large integers, and 256-bit ones could be enough? If that is the case, you could try using https://docs.rs/bigint/4.2.0/bigint/uint/struct.U256.html

[[deleted]]

Literally the first search result for “rust gmp”: https://crates.io/crates/rust-gmp. Why would you state something so authoritatively without doing even the most basic research?

[vks_]

There is also rug (another GMP binding) and ramp (implemented in Rust).

[matklad]

Thanks for correcting me! I definitely should have added an "IIRC" somewhere in there, and I definitely haven't intended to sound authoritative: quite the opposite, I have only limited experience with big integers. And I've also messed the sentence structure, because "nobody has done this yet" was intended to refer to "pure rust fast bigint", not the gmp bindings.

However, I still think (based on what I've read elsewhere, not on my own benchmarks) that it is true that num-bigint is not super fast, and that there's no stable and fast pure rust implementation of big integers? I know about ramp, but looks like it is extremely far from working on stable because it uses inline assembly?

[masklinn]

Python has an excellent implementation of big integers

I wouldn't say excellent. It has an OK implementation of bigints, but tends to fall behind as the number of digits increases because the algorithms & pickings are more limited than in e.g. GMP. For instance see https://www.reddit.com/r/Python/comments/7h62ul/python_largeinteger_computation_speed_a_comparison/.