Bugs in miloyip/nativejson-benchmark: roundtrips

[nlohmann]

I checked the library with the latest https://github.com/miloyip/nativejson-benchmark benchmark suite. There are several errors in the round trip tests:

• Roundtrip,Nlohmann (C++11),roundtrip20,false
• Roundtrip,Nlohmann (C++11),roundtrip21,false
• Roundtrip,Nlohmann (C++11),roundtrip24,false
• Roundtrip,Nlohmann (C++11),roundtrip25,false
• Roundtrip,Nlohmann (C++11),roundtrip26,false
• Roundtrip,Nlohmann (C++11),roundtrip27,false

These are the values:

• [0.0]
• [-0.0]
• [5e-324]
• [2.225073858507201e-308]
• [2.2250738585072014e-308]
• [1.7976931348623157e308]

I will have a deeper look at this later. I just wanted to paste the results here before I forget.

[nlohmann]

I wrote a little tool for the roundtrips:

#include <json.hpp>

using nlohmann::json;

int main()
{
    json j;
    std::cin >> j;
    std::cout << j << std::endl;
}

Here are the results:

• [0.0] -> [0]
• [-0.0] -> [0]
• [5e-324] -> [4.94065645841247e-324]
• [2.225073858507201e-308] -> [2.2250738585072e-308]
• [2.2250738585072014e-308] -> [2.2250738585072e-308]
• [1.7976931348623157e308] -> [1.79769313486232e+308]

Indeed, the output differs from the input.

[nlohmann]

The first two items ([0.0] and [-0.0]) are parsed and stored as integer 0, because no precision is lost. As JSON does not define an internal representation of numbers and the value (zero) is the same, I think it's rather nitpicky to treat the output as an error.

[nlohmann]

FYI: The roundtrips are already part of the unit tests (test case ""compliance tests from nativejson-benchmark", section "roundtrip"), where test case 13, 18-21, and 24-27 are skipped.

[twelsby]

Most of these are silly tests in my opinion and seem pretty contrived.

The exception is -0. There is an argument for saying that -0 should remain a float. This is because while 0 = -0, 1/0 != 1/-0 (LHS is positive infinity and RHS is negative infinity). The 0 case is not so much of a problem because if the user expects a float then it will be cast to 0.0, however -0 would be stored as 0 and cast to 0.0. In rare cases this could cause unexpected behaviour.

Here is what causes them to break:
roundtrip13.json (-1234567890123456789) - this exceeds what can be stored in a double without loss of precision so will not be rendered accurately under the old parse method but will be under the 2.0.0 parse method as it will end up being stored as a int64_t with the default basic_json.

roundtrip18.json (1234567890123456789) - as above except that it will be stored as a uint64_t in version 2.0.0.

roundtrip19.json (9223372036854775807) - as above.

roundtrip20.json (0.0) - cast to integer so ends up dumping as 0 not 0.0. This could be fixed by dropping the cast to integer. In 2.0.0 an attempt is made to parse as integers first so dropping the cast would only affect floating point numbers that are expressed in the form of floating point numbers but are actually integers e.g 1.00, 123e4 etc. It could be argued that if someone has gone the effort of writing a number in the form 1.00 then it is probably intended to be a float so this might be the right way to go anyway. Personally I would like to see us go down that track.

roundtrip21.json (-0.0) - similar to above. A special case would be needed to fix it.

roundtrip24.json (5e-324) - this number is right at the limit of the minimum subnormal range (for double's) and cannot be represented more accurately using a double. Even a GCC long double cannot accurately represent this number although it gets much closer - so there isn't really a good use for this in the real world.

roundtrip25.json (2.225073858507201e-308) - this number is below the minimum normal range so is represented using the subnormal range with loss of precision (it is the loss of precision that causes the error in this case). A GCC long double might work but honestly this test is silly.

roundtrip26.json (2.2250738585072014e-308) - this number is exactly the minimum normal range so can be represented exactly in a double. If the fix suggested in #186 is used then it will parse ok however it won't dump correctly because it needs 17 digits and dump() sets the precision based on std::numeric_limits::digits10, which is 15. The problem is that double can represent 15-17 significant figures depending on the number but std::numeric_limits::digits10 takes a conservative approach. This is a fair test but probably not easily solvable.

roundtrip27.json (1.7976931348623157e308) - as above.

[nlohmann]

Update:

• [0.0] -> [0]
• [-0.0] -> [-0.0]
• [5e-324] -> [4.94065645841247e-324]
• [2.225073858507201e-308] -> [2.2250738585072e-308]
• [2.2250738585072014e-308] -> [2.2250738585072e-308]
• [1.7976931348623157e308] -> [179769313486231570814527423731704356798070567525844996598917476803157260780028538760589558632766878171540458953514382464234321326889464182768467546703537516986049910576551282076245490090389328944075868508455133942304583236903222948165808559332123348274797826204144723168738177180919299881250404026184124858368.0]

[nlohmann]

I reran the benchmark:

Fixed:

• Roundtrip,Nlohmann (C++11),roundtrip21,true [-0.0]

New errors:

• Roundtrip,Nlohmann (C++11),roundtrip13,false [-1234567890123456789]
• Roundtrip,Nlohmann (C++11),roundtrip18,false [1234567890123456789]
• Roundtrip,Nlohmann (C++11),roundtrip19,false [9223372036854775807]

Unchanged:

• Roundtrip,Nlohmann (C++11),roundtrip20,false [0.0]
• Roundtrip,Nlohmann (C++11),roundtrip24,false [5e-324]
• Roundtrip,Nlohmann (C++11),roundtrip25,false [2.225073858507201e-308]
• Roundtrip,Nlohmann (C++11),roundtrip26,false [2.2250738585072014e-308]
• Roundtrip,Nlohmann (C++11),roundtrip27,false [1.7976931348623157e308]

[nlohmann]

• example 13, input -1234567890123456789 output -1234567890123456768
• example 18, input 1234567890123456789 output 1234567890123456768
• example 19, input 9223372036854775807 output 9223372036854775808.0

[twelsby]

Actually I don't think these are new - or at least they shouldn't be. I couldn't get the benchmark to successfully run so I uncommented the above tests in unit.cpp and encountered them, which is why I mentioned them above. They will be automatically fixed by the version 2.0.0 get_number() method as they are a consequence of the 1.0.1 method of parsing as double, which is incapable of holding them without loss of precision. The unit.cpp in #193 has these tests re-enabled and they pass

The reason the bottom one now has a trailing .0 is that the top two are able to fit in a int64_t so they get dumped as integers, although they still lose precision by passing through a double, while the bottom one can only be stored as a double so it gets dumped as a floating point.

To summarise where all of these sit at the moment: in 1.0.1 roundtrip21 is fixed (and the relevant unit test uncommented) but everything else is broken, while in 2.0.0 rountrip13, rountrip18, roundtrip19, and roundtrip20 are all fixed (and the relevant unit tests uncommented).

roundtrip24, roundtrip25 and roundtrip27 are (in my opinion) fundamentally unable to be passed by any library that relies on double's as the floating point data type, because this datatype lacks the necessary accuracy with such small values. I would be interested to see how rapidJSON does it but I suspect they keep the original string representation (would explain why their dumping is so fast).

roundtrip26 could be made to pass but the difficulty is that it requires 17 digit precision and you can't guarantee roundtrips for all numbers if you output at 17 digits. It would be necessary to somehow identify which numbers can support roundtrips with 17 digits and this would be very difficult to do efficiently I think. The worst case scenario is that you would have to do trial round trips at three different levels of precision (15, 16 and 17) and that would only work for double's. There may be a way to do this more directly but I don't even know where to begin - and if such a method did exist it would probably be in the standard library.

[nlohmann]

Now all but roundtrip 24-27 work. I'll rerun the benchmarks just to make sure it also works in the setting of https://github.com/miloyip/nativejson-benchmark.

[nlohmann]

Executing the benchmark, 4 errors remain. It is strange, however, that several other libraries seem to be able to pass the tests.

[twelsby]

Well I have achieved 100% 'conformance'. I will explain further but I am just running some more checks. This benchmark doesn't seem that fair however as 'conformance' is not measured against any official standard but is really based on how close the output is to 'RapidJSON_FullPrec', so it is inherently biased, especially around floating point where some variation out to be permitted. As an example, outputting a floating point number in this form will fail: 10e+10, as will this: 10E10 and this: 10E+10. To pass you must output 10e10, which, unless I am mistaken, is impossible with the standard library (either streams or printf) - or at least I can't find a way to do it without an ugly hack. A bit silly if you ask me.

[nlohmann]

@twelsby Well, it seems as if the benchmark started from the testbench for RapidJSON. I don't think achieving 100% "just because" should not be the goal here - I'd rather want to understand why quite some library seem to "agree" on the output.

[twelsby]

I have only looked at rapidJSON so far but the short answer is essentially that it uses its own custom functions to do both parsing and stringifying of doubles that do not rely on the standard library.

The stringifying function used by rapidJSON simply does not emit a '+' for a positive exponent (unlike the standard library). As including the '+' sign is optional and therefore legal there will always be roundtrip tests that a particular implementation will fail (almost - I'll get to that). For example, rapidJSON will fail round trip tests of 123e+45, 123E45 and 123E+45. There aren't any tests like this in the suite so rapidJSON is made to look better than it should. You can test this simply by adding files with these numbers and editing main.cpp to increase the index limit for the roundtrip tests by the number of files you add.

This is what causes the failure for roundtrip27.

The other failing roundtrips pass with rapidJSON because it uses a complex algorithm to make the decision as to how many significant figures to round the output to. The simplest example of this is 5e-324, which, as I said before, can't be accurately represented as a double. The closest you can get is the denormal number 4.940656458412e-324. rapidJSON's algorithm decides that the best representation is to round to 1 significant figure, so it 'correctly' outputs 5e-324.

This approach is fundamentally flawed however and produces its own error that, perhaps conveniently, isn't tested for. The error occurs because 4.940656458412e-324 is itself a valid input but rapidJSON's algorithm can't differentiate the cases because both 4.940656458412e-324 and 5e-324 parse to the same double value of 4.940656458412e-324. Information is being lost during the parse and once lost it can't be restored.

You can test this by putting any of these values into a file and adding it to the round trip tests: 4.940656458412e-324 and 2.2250738585072e-308. rapidJSON will fail them both. There would be a huge number of similar cases. Basically any number that cannot be exactly represented as a binary floating point number and that does not have exactly 15 digits of decimal precision might cause rapidJSON to fail.

The solution is obviously to not lose the information to begin with. Both problems can be fixed by determining the number of significant figures, the capitalization of 'e' and the presence of a '+' sign in the exponent during the parse, storing that information and then using it during the dump. This is only relevant to round trips. If you create a new double object and dump it then the normal 15 max significant figures can be used.

I have developed an implementation of this that actually runs faster than the previous proposed 2.0.0 implementation. It will pass all of the benchmark roundtrips and the additional ones I mentioned. There are some cases involving extra leading or trailing zeros in either the mantissa or exponent that won't pass however.

It is slightly slower than 1.0.1 in the parsing benchmark but only because the test is heavily weighted towards 'canada.json' (due to the time taken to process this file) and this file is pretty much all floating point numbers. It is faster than 1.0.1 with files that have a greater proportion of integers and strings (most real world examples). Stringifying is significantly faster for doubles so the 'canada.json' test is stringified 50% faster with this method. This seems to be because I am using snprintf() rather than writing to the stream directly - so it could just be specific to VS2015, which may have a bad operator<< implementation for doubles.

Memory usage is exactly the same provided single byte struct/class alignment isn't enabled (if it is then a small amount of extra memory is used). It does add some code (only about fifty lines).

My testing was under VS2015 as I couldn't get the tests to build under Linux.

[nlohmann]

Hi @twelsby, thanks (again) for the detailed analysis. I think it does not make sense to "fix" the code toward these tests any more. Instead, we should start a discussion about the benchmark, and maybe adding all kind of valid JSON examples which show that it is hard to find "the" correct JSON serialization. I shall play around with some examples and open a PR at miloyip/nativejson-benchmark.

I am excited about a performance improvements. However, I think we should track this in a different issue. If I can help with test on Linux or OSX, please let me know.

[twelsby]

@nlohmann, when I first began investigating this issue it appeared that the only way to pass those tests that depend on particular (arbitrary) floating point representations was to output numbers in the expected form (e.g. 12e3 rather than 12E3, 12e+3 or 12E+3 and 5e-318 rather than 4.99...e-318). Basically this would be targetting the test. Initially I wrote a hack to do just this but it was never something I would have advocated incorporating.

As I progressed I came up with a better way that simply echos the floating point representation given in the original string (by recording it during the parse). This does not target any particular test and would work for all. This is something I am advocating we incorporate because it adds functionality that is useful in certain circumstances and has effectively zero cost. Take the following code:

#include "json.hpp"

using nlohmann::json;

int main()
{
    std::cout << "Enter a floating point number: ";
    std::string input;
    std::getline(std::cin,input);
    json j = json::parse(input);

    std::cout << "Was your number " << j << "?" << std::endl;

    return 0;
}

Under 2.0.0 and 1.1.0 if you enter a floating point number that cannot be represented exactly as a binary floating point number and which has less than 15 significant figures you will get a different output. The classic case is 5e-324, enter this and you get the output:

Enter a floating point number: 5e-324
Was your number 4.94065645841247e-324?

With my proposed changes you get:

Enter a floating point number: 5e-324
Was your number 5e-324?

Now the underlying floating point number is the same in either case, so if the program is doing floating point calculations then it doesn't make any difference, but if the program is interacting with a user, then it is much better to present the rounded version.

My changes also match use of '+' and capitalization of 'e'. In my view these are nowhere as important as matching precision but since they can be implemented at effectively zero cost it probably makes sense to do so.

The other advantage is that you get to claim class leading conformance that (if you add the additional round trip tests I mentioned) is better than any other library in the test.

I am putting together a pull request so you can see.

[nlohmann]

I opened an issue at miloyip/nativejson-benchmark#33 and hope for a nice discussion. I close this ticket here as we have #201 to discuss.

[nlohmann]

@twelsby: FYI, at miloyip/nativejson-benchmark#33 floating-point numbers and in particular subnormal doubles are discussed.