Robbepop / apint

Arbitrary precision integers library.
Other
26 stars 4 forks source link

The `checked_`... operations use wrapping arithmetic #17

Closed AaronKutch closed 6 years ago

AaronKutch commented 6 years ago

I was under the impression that checked_, wrapping_, saturating_, etc meant the same as the counterparts in the primitives, and that you had just implemented checked_ ones that returned Result instead of Option like the primitives. Today I was was looking at the implementations for performance issues and realized that it just meant that the sizes were checked and the operation was wrapping.

I won't need true checked or saturating ops for a while but I strongly suggest that you replace the checked_ with wrapping_, and then we can be more consistent with the primitives and the library I am making. In case of functions where the sizes are not checked, I would use some other prefix like nosizecheck_.

Robbepop commented 6 years ago

You are totally right about this confusion. This is a great idea and I will certrainly implement this in the near future!

AaronKutch commented 6 years ago

I think I can refactor arithmetic.rs with macros and stuff while I'm fixing the mul and div functions.

I was checking most of the functions in your crate for performance, and everything looks decent except for this. Just to make sure, is this code optimal?

impl Clone for ApInt {
    fn clone(&self) -> Self {
        match self.storage() {
            Storage::Inl => ApInt::new_inl(self.len, unsafe { self.data.inl }),
            Storage::Ext => {
                use std::mem;
                let req_digits = self.len_digits();
                let mut buffer = self.as_digit_slice().to_vec().into_boxed_slice();
                assert_eq!(buffer.len(), req_digits);
                let ptr_buffer = buffer.as_mut_ptr();
                mem::forget(buffer);
                unsafe { ApInt::new_ext(self.len, ptr_buffer) }
            }
        }
    }
}

Why would there need to be assertions in a cloning function? There are also assertions in the new_ext and new_inl. I don't know enough about raw pointers and unions to say much, but why is there a buffer being made and then discarded?

AaronKutch commented 6 years ago

One more thing: how are the function return types working? I see in the into_ functions -> Result<ApInt> and in the _assign functions -> Result<()>. I thought that Result had to have two arguments like Result<T,E>.

Robbepop commented 6 years ago

Thank you for analyzing the crate for performance issues - that's really important! :)

The Apint::clone implementation clones the given &self instance and thus needs to clone all of the digits in case of a large ApInt instances above 64-bit widths. This copying is done with self.as_digit_slice().to_vec() while into_boxed_slice actually cuts the given allocated buffer to the exact size. This might involve another copy and thus could be inefficient. In the current state I mostly hope that this (maybe)-ineffiency is optimized away by the compiler but we should further investigate here. The assertion is not required and maybe should be a debug_assert instead but also shouldn't pose a performance problem. mem::forget allows to finally transfer ownership of the buffer into the resulting instance returned by the ApInt::new_ext call.

To your other question about Result<T, E>: The apint crate defines its own Result type that is hard coded to apint's Error and thus only requires one generic parameter. So Result<T> actually just means Result<T, apint::Error>.

AaronKutch commented 6 years ago

What do you think about using assign as a prefix instead of a suffix, so that it is symmetric to into as a prefix. I think it also makes more sense to say lhs.assign_wrapping_mul(&rhs) than lhs.wrapping_mul_assign(&rhs) since is is assigning to lhs

Robbepop commented 6 years ago

The assign suffix is originated from the Rust standard library: https://doc.rust-lang.org/std/ops/trait.AddAssign.html

AaronKutch commented 6 years ago

I changed my mind and decided that we should do the name change next. What I currently think they should be: All checked_ should be removed (and wrapping_ added if applicable), excepting the comparison ops like checked_lt. Also, there should be some documentation for the PartialOrd implementation noting that the operations return false when apint sizes are not the same, and documentation on the checked comparison ops saying that the checked means it checks size. I decided that assign should be kept as a suffix. I can't think of any other changes that should be made.

AaronKutch commented 6 years ago

Should you do the name change?

Robbepop commented 6 years ago

You can do it and I will simly merge if you want. :)

AaronKutch commented 6 years ago

And also negate -> wrapping_neg