num-bigint
num-bigint copied to clipboard
rust-num
Support in-place operations
Currently, operations on BigInt such as add_assign is not done in-place, but with the following implementation:
#[inline]
fn add_assign(&mut self, other: &BigInt) {
let n = mem::replace(self, BigInt::zero());
*self = n + other;
}
which would be costly for more complex operations, due to frequent allocation/deallocation.
We already have some in-place operations for BigUint such as add_assign, can we support this for BigInt as well? I'm not familiar with this so idk if it would be very difficult to do so.
BigInt::zero() doesn't require any allocation, so if that's your main concern, I think we should be fine. The goal here was to avoid duplicating the sign logic, which BigUint doesn't have to worry about. Do you have other specific examples of concern?
BigInt::zero()doesn't require any allocation, so if that's your main concern, I think we should be fine. The goal here was to avoid duplicating the sign logic, whichBigUintdoesn't have to worry about. Do you have other specific examples of concern?
No I don't mean BigInt::zero() requires allocation, but in-place operation can reduce allocation and improve performance. The example case is this:
which allocation occupies a significant time. Using += and *= cannot improve the performance.
What is the scale of the numbers being multiplied? If allocation is a significant portion of the calculation, I'm guessing they are relatively small values to begin with.
If one of the operands is only a single BigDigit, I think we could manage to do scalar multiplication in place. With some effort we could probably expand two digits to multiply in place too, but I would expect quickly diminishing returns.
Switching to smallvec could also help if even the result is small enough, depending on how many digits we keep local.
What is the scale of the numbers being multiplied? If allocation is a significant portion of the calculation, I'm guessing they are relatively small values to begin with.
Yes, I think so. The project is RustPython, bigint is used for storing all the numbers, so I think most of the numbers would be pretty small. And smallvec may also help.