Closed BenWiederhake closed 2 months ago
Yeah that can be done.
PartialEqual has a "scale difference" issue, too:
let scaled_int_val = &self.int_val * ten_to_the((rhs.scale - self.scale) as u64);
Where that subtraction could cause an out-of-memory error allocating 10^(terabyte-sized-number)
(and by terabyte I mean exabyte.....)
Oh no, that was the old version. It was fixed in September. I probably meant to fix impl Ord
too but slipped by me.
Implementation is ready, and I included your example test. I'd like to write a few more tests to improve the coverage.
https://github.com/akubera/bigdecimal-rs/compare/trunk...f/ImprovedOrd
It now tries to cast the big ints to u64, then u128, then creates Vec
I'm calling it for the night, but leaving myself a message:
example : cmp(1e-9223372036854775807, 1e+9223372036854775807)
panics as the difference of exponents is out of i64 domain.
I'm not sure what to do in that case. I would guess that it's safe to assume they're not equal, as that would mean exabytes of numbers to reach equality, and go with less Less/Greater base on which scale is larger.
That was fixed with a new checked_diff(i64,i64) -> (Ordering, Option<u64>)
function. If the difference between the two numbers is greater than a u64, we return None in the tuple. Since we're comparing scales (i.e. number of digits) then we're safe to assume if that number doesn't fit in a u64, we can know the ordering/equality of the numbers without needing to inspect them digit-by-digit.
Testing at the boundaries here lead to finding a similar panic in implementation of eq
. That too has been fixed and I think should be faster with a non-allocating algorithm if the scale is <20 digits (max number of decimal-digits which fits in a u64).
Now the hard part is making contrived test cases which avoid the optimizations.
I'm happy with result. It's now merged into trunk in commit https://github.com/akubera/bigdecimal-rs/commit/b34622dc5a71fa17f673d6545c89ec1a7fe5ba26.
Let me know if that works for you.
Fantastic! It works great :D
Merged in 0.4.4
I understand that comparing numbers that are very similar might take a bit of time, as it might need to read all stored digits in the worst case. But certainly there is no expensive computation involved, right?
However, calling
cmp
always has a large overhead in CPU and memory. Example:Note that creating
teenytiny
andone
is very quick: The internalBigInt
and wrappingBigDecimal
require barely any memory at all. However, the comparisons are excruciatingly slow, because:This subtraction effectively runs an infinite loop, even though
cmp
could be determined (for this input) very easily. Implementing some kind of early-return path would be really nice.Related: https://github.com/uutils/coreutils/issues/3318