-
Notifications
You must be signed in to change notification settings - Fork 68
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Numeric matching ignores its own precision limitations. #163
Comments
Oh that's a neat find. I think we should not match as well unless the user has mentioned us how to handle higher precision digits. I will ask few folks to confirm to make sure we haven't missed anything obvious. Hoping, I can send a PR tomorrow or next week (away in between for the long weekend). |
My approach was just to count the digit characters (stopping when I saw an 'e' or 'E' and if there were more than 9, refuse to generate. I probably need to do some fuzzing to see if there are any numerical patterns that will cause incorrect results. Switching to ordinary string match is going to produce the correct result almost always but there is a corner case where 1234567890.0 won't match 1234567890 because you lose the number semantic when you get outside the ComparableNumber precision. Hmm, I remember when we rolled in Ruler 2 and you guys did a ton of testing and the only changes were when people were starting to have rule {"x": [ 35 ] } match {"x": 35.0}, when it had failed before. |
I'm reading https://en.wikipedia.org/wiki/Double-precision_floating-point_format (so many years since I learned this stuff) and apparently double floats offer 15 to 17 decimal digits of precision because there are 53 bits of mantissa. So what's limiting the precision isn't the use of doubles but the restriction in ComparableNumber to 14 hex digits. So in principle I guess that ComparableNumber could be changed to be a lot more precise. 53 bits is 14 bytes i.e. 28 hex digits. Of course this could increase memory usage while adding little real-world value. If you read the comments in ComparableNumber.java there's the idea of using tricks like 32/64 radix to compress. Not sure what the right thing to do is… I note that the numbers in CityLots have 17 digits of precision. Hmm… |
Just started looking at the code. I'm naively thinking we should throw errors similar to when a number is beyond our precision range while its still a double here https://github.com/aws/event-ruler/blob/main/src/main/software/amazon/event/ruler/ComparableNumber.java#L49 currently testing a bunch of edge-cases to see if would work. |
FWIW, here's the current Go code (not yet pushed) from Quamina: func comparableFromBytes(s []byte) (comparableNumber, error) {
// first of all, refuse to try to convert if there are too many digits
digits := 0
for _, utf8Byte := range s {
if utf8Byte >= ASCII0 && utf8Byte <= ASCII9 {
digits++
}
if utf8Byte == 'e' || utf8Byte == 'E' {
break
}
}
if digits > MaxComparableDigits {
return nil, errors.New("number too long")
}
numeric, err := strconv.ParseFloat(string(s), 64)
if err != nil {
return nil, errors.New("not a float")
}
return comparableFromFloat(numeric)
} Note that it still needs work to not count leading zeroes… |
on
I wonder this as well but didn't look at because of the benefits are low. |
Yeah, there's a lot to like about the treat-as-string-if-too-precise because ComparableNumber is really designed to help match things like 35.0 vs 35 vs 3.5e1, and that kind of variation isn't seen so much in really precise numbers like the kind in CityLots. But how about I haven't looked at the code but I guess that kind of pattern should be rejected, unless we're willing to increase the precision of ComparableNumber? |
I'm finding a bunch of numbers across ruler with precision above 6 decimals. Checking if there's anything in old commit history if these were intentional or not :
and
The second one seems unintentional for sure. |
Yeah, pretty sure I wrote that second one and totally wasn't thinking about number-of-digits issues. The first one does look like someone was trying to explore a precision issue? |
I spent quite a bit of time investigating this. I believe the code does what it says: Works correctly when the range is between +/-5e9, with <=6 points right of the decimal. This seems to work quite well in practical terms. So I guess for Quamina I will apply those criteria. Since we have a textual version of the number, counting the digits right of the decimal point is easy. |
Yup. It looks like its been there since the beginning. The tests passed until now because Ruler ignored precision. Once I added a change to fail rule-matching even when numbers with more than 6 decimals were passed, the test started to fail. I'm thinking the change needs to be more refined. Ignore precision for comparison (less than, greater than) for backward compatibility but then for equality checks, we should fail if numbers has > 6 levels of decimals. |
That ComparableNumber code was written in ~2017-18 so it took me a while to remember the thinking, which should have been written in a comment. But I think I have it now. What the current scheme does is represent a block in the center of the X-axis, -5e9…+5e9. Those numbers have 10 decimal digits, plus we allow 6 fractional digits, so that is in good harmony with the ~16-decimal-digit precision of 64-bit floats. Thus we have a block of ~2**53 possible values that can be represented preserving order in our 14-byte/28-hex-digit representation. You can see the problem with the numbers in CityLots: They not only have too many digits of precision (17) but, as my example above shows, if there are more than 6 fractional digits, they don't fit into the ComparableNumber constraints. Let's call these "out-of-bounds" numbers. For out-of-bounds numbers, I think the only sensible thing to do is to treat them as strings. This will work well, because for those kinds of “unusual” numbers, e.g. crypto signatures or AWS account numbers or CityLots geometry, they are typically given precisely. That leaves the backward-compatibility issue. In Quamina, for the out-of-bounds numbers, I think I will refuse to attempt < and > comparisons because the chances of being correct are not very good. Unless we can think of a way to represent those out-of-bounds numbers in a state machine… I would ask: In the real world, are there instances of people doing < or > on out-of-bounds numbers? Because they are probably getting wrong answers. So either (a) they are getting wrong answers and don't notice or (b) they are reporting problems (are they?) or (c) this just isn't happening. |
Here's another unit test and its output. This shows that this statement in README.md is wrong: "Numeric matching is limited to value between -5.0e9 and +5.0e9 inclusive, with 15 digits of precision, that is to say 6 digits to the right of the decimal point." +/-5.0e9 is correct, 15 digits is correct, but since 5.0e9 has 10 digits, there can only be 5 digits to the right of the decimal point. This is consistent with the data in @Test
public void WHEN_SixFractionalDigits_THEN_OrderingIsLost() {
double[] lows = {-5_000_000_000.0, -4_999_999_999.999999, -4_999_999_999.999998};
double[] highs = {4_999_999_999.999998, 4_999_999_999.999999, 5_000_000_000.0};
for (double low : lows) {
String c = ComparableNumber.generate(low);
System.out.printf("%f => %s\n", low, c);
}
for (double high : highs) {
String c = ComparableNumber.generate(high);
System.out.printf("%f => %s\n", high, c);
}
} Output:
|
Will update the doc when I send my PR.
I'm giving myself another day to give this a go. If I can't make sufficient progress, I'll roll out a version of ruler where we throw errors to grab real-world data in shadow mode. Until then the next release will be marked as experimental. |
btw @timbray have you considered using generating a longer string from the |
Yes. Even within the current 14-digit limit, notice that the biggest ComparableNumber we generate is 2386F26FC10000 - so we could increase the range by a factor of up to ~6, say to +/-20B, and still retain 5 digits right of the decimal. I don't think we could add another past-the-decimal digit without reducing the range, down to something like +/-2.5B. But I have a nice little test-bench set up now, and if you want more precise data about any proposed changes, I can get it quickly. My honest opinion is that the current setup is hitting a good balance. But you'd know better than me. I know you can't disclose internal stuff but at the time I left Amazon, Ruler was being used by several services and the number-1 gripe was memory usage, I can't remember anyone having pain with the numeric range. But if you say you see a demand for more numeric range or precision, I'll be prepared to believe it's based on experience. But at the moment I'd vote to leave it at +/-5B with 5 fractional digits, improve the documentation, and treat out-of-bounds numbers as strings. |
As I think about this, I'm capturing what I understand in a long comment at the top of Q's
|
after changes in
now outputs
Testing across more edge-cases: large numbers, very small numbers, and so on. |
Will be interested to see the changes to |
minor changes for now but I'm surprised there aren't floating point accuracy discrepancies for the 6th decimal when we multiple or divide. static String generate(final double d) {
if (d < -Constants.FIVE_BILLION || d > Constants.FIVE_BILLION) {
throw new IllegalArgumentException("Value must be between " + -Constants.FIVE_BILLION +
" and " + Constants.FIVE_BILLION + ", inclusive");
}
if (d != Math.round(d * TEN_E_SIX) / TEN_E_SIX) {
throw new IllegalArgumentException("Only values up to 6 decimals are supported.");
}
return toHexStringSkippingFirstByte(Math.round(TEN_E_SIX * Constants.FIVE_BILLION) + Math.round(TEN_E_SIX * d));
} |
Yup. Fails at -4_999_999_999.999994 and -4_999_999_999.999993 . Let me try parsing the string before the number gets turned into a double (though I’m not sure how straight forward it’ll be for octals and hex literals). |
I was expecting something like that, as you were. Ummm… I would be a bit dubious about investing much more time into this, the current design feels like a good compromise to me. The idea that does interest me was the use of something other than hex digits in ComparableNumber (Quamina too). There are several “baseX” encodings for various values of X that are way more space-efficient. |
Oh I'm using this as an excuse to understand this code and then explore moving to base64. Not being familiar with this part of the code as much I didn't feel I had learned enough to go there. Another thing I learned along the way, most of the time we serialize to a double from a string. By moving the string parsing within With Big Decimals (w bug fix)
Current Main Branch (with the bug)
|
Wow, good performance numbers too! |
I was skeptical of the performance as quirk of runnign on my laptop but seems to run well in the sandboxed environment as well
|
I've made one controversial choice within #166 to fallback to the old way for hexadecimal numbers primarily because it used to work that way before and is tied to the way we convert these numbers to double. It's an extreme edge-case, so I think we'd be okay but once the library has merged the change, it'll be easier to confirm under shadow mode. |
…mentation (#166) #163 ### Description of changes: As was reported in issue 163, ruler today ignores precision and causes false matches for numbers or rules with high precision numbers. This change moves away from using `double` for doing arithmetic adjustments within `ComparableNumber`. Along the way the API to generate comparable numbers is changed from using `Strings` instead of `Double`. This allows for more accurate rule matching for numbers with 6+ digits without compromising on performance. A bunch of our tests needed to be changed / fixed as a result of this change. These have been fixed. We're added additional test cases to help catch precision issues in future.
Thanks for creating this one @timbray. Was the perfect excuse to learn enough so that I can now play with higher radix numbers in a follow-up change. Closing this one for now. |
In fact, the precision of ComparableNumber is about 9 decimal digits. Ignoring this produces results that I think are wrong. In Quamina, I changed the equivalent of
ComparableNumber.generate()
to refuse to generate if there are too many digits. This has the effect that for super long numbers like in CityLots, they all get matched as strings, which produces correct results.Here's the test:
It prints out
The text was updated successfully, but these errors were encountered: