CBOR/MessagePack readers: leave one-element arrays to the general path

enter_cbor_array and enter_msgpack_array called the out-of-line scalar
run for every non-empty array. When the array's element is an object or
an array, as on every level of [[...]] or the single ring of a GeoJSON
polygon, the call reads nothing; it made 1,000 arrays nested in each
other cost 4 % more instructions (GCC 13) and up to 8 % more time (Apple
clang) than without the run. #5975 had fixed that with an inline
pre-check, which was later dropped after measuring canada only.

The run is now entered only for arrays of two or more elements: the same
comparison as before, so no other row changes. Arrays of one scalar,
which the run read faster, now take the general path; they are rare in
documents (one in citm_catalog, none in twitter or canada). The new
benchmark FromBinaryShape/singles measures them, next to
FromBinaryShape/nested.

Instructions per repetition, new/old, GCC 13 callgrind: nested arrays
0.973 (CBOR) and 0.971 (MessagePack), arrays of one scalar 1.037 and
1.021, every other row within 0.15 %.

Signed-off-by: Niels Lohmann <mail@nlohmann.me>

include/nlohmann/detail/input/binary_reader.hpp

@@ -1856,14 +1856,18 @@ class binary_reader
 
     Only the start of an array is tried, which covers arrays of numbers
     (e.g. coordinates) but costs arrays of other values only one call, not one
-    per element.
+    per element. An array of one element is not tried at all: that element is
+    mostly an object or an array (`[[...]]`, the single ring of a GeoJSON
+    polygon), for which the call would find no scalar, while a single scalar,
+    which the run would read faster, is rare. The benchmarks
+    `FromBinaryShape/nested` and `FromBinaryShape/singles` show both sides.
 
     @param[in] len  the number of elements
     @return whether the SAX parser accepted the array and the values read
     */
     bool enter_cbor_array(const std::size_t len)
     {
-        return enter_array(len) && (len == 0 || parse_cbor_scalar_run(std::integral_constant<bool, bulk_scan> {}));
+        return enter_array(len) && (len <= 1 || parse_cbor_scalar_run(std::integral_constant<bool, bulk_scan> {}));
     }
 
     /// input that is not contiguous: every value is read by parse_cbor_value
@@ -2764,12 +2768,16 @@ class binary_reader
     /*!
     @brief open a MessagePack array and read the scalars it begins with (see
            @ref parse_msgpack_scalar_run)
+
+    An array of one element is not tried, for the reason given at
+    @ref enter_cbor_array.
+
     @param[in] len  the number of elements
     @return whether the SAX parser accepted the array and the values read
     */
     bool enter_msgpack_array(const std::size_t len)
     {
-        return enter_array(len) && (len == 0 || parse_msgpack_scalar_run(std::integral_constant<bool, bulk_scan> {}));
+        return enter_array(len) && (len <= 1 || parse_msgpack_scalar_run(std::integral_constant<bool, bulk_scan> {}));
     }
 
     /// input that is not contiguous: every value is read by parse_msgpack_value

include/nlohmann/detail/output/serializer.hpp

@@ -8,7 +8,7 @@
 
 #pragma once
 
-#include <algorithm> // copy, none_of, min, search
+#include <algorithm> // remove, fill, find, none_of, min
 #include <array> // array
 #include <clocale> // localeconv, lconv
 #include <cmath> // isfinite
@@ -2095,35 +2095,31 @@ class serializer
         // check if the buffer was large enough
         JSON_ASSERT(static_cast<std::size_t>(len) < number_buffer.size());
 
-        // look up the locale's decimal point now, matching what
-        // snprintf_float() just used (see get_decimal_point() in
-        // number_parse.hpp); it is a string, which can be longer than one
-        // byte (U+066B in ps_AF, #5993).
-        // A thousands separator needs no handling: %g never groups digits.
+        // look up the locale's thousands separator and decimal point now,
+        // matching what snprintf_float() just used (see lexer::get_decimal_point())
         const auto* loc = std::localeconv();
         JSON_ASSERT(loc != nullptr);
-        const char* const decimal_point = (loc->decimal_point == nullptr) ? "" : loc->decimal_point;
-        const std::size_t decimal_point_len = std::char_traits<char>::length(decimal_point);
+        const char thousands_sep = (loc->thousands_sep == nullptr) ? '\0' : *loc->thousands_sep;
+        const char decimal_point = (loc->decimal_point == nullptr) ? '\0' : *loc->decimal_point;
+
+        // erase thousands separators
+        if (thousands_sep != '\0')
+        {
+            // NOLINTNEXTLINE(readability-qualified-auto,llvm-qualified-auto): std::remove returns an iterator, see https://github.com/nlohmann/json/issues/3081
+            const auto end = std::remove(number_buffer.begin(), number_buffer.begin() + len, thousands_sep);
+            std::fill(end, number_buffer.end(), '\0');
+            JSON_ASSERT((end - number_buffer.begin()) <= len);
+            len = (end - number_buffer.begin());
+        }
 
         // convert decimal point to '.'
-        if (decimal_point_len != 0 && !(decimal_point_len == 1 && decimal_point[0] == '.'))
+        if (decimal_point != '\0' && decimal_point != '.')
         {
-            const auto first = number_buffer.begin();
-            const auto last = first + len;
-            // NOLINTNEXTLINE(readability-qualified-auto,llvm-qualified-auto): std::search returns an iterator, see https://github.com/nlohmann/json/issues/3081
-            const auto dec_pos = std::search(first, last, decimal_point, decimal_point + decimal_point_len);
-            if (dec_pos != last)
+            // NOLINTNEXTLINE(readability-qualified-auto,llvm-qualified-auto): std::find returns an iterator, see https://github.com/nlohmann/json/issues/3081
+            const auto dec_pos = std::find(number_buffer.begin(), number_buffer.end(), decimal_point);
+            if (dec_pos != number_buffer.end())
             {
                 *dec_pos = '.';
-                if (decimal_point_len > 1)
-                {
-                    // move the fraction and exponent behind the '.' (std::copy
-                    // allows the overlap, as the destination is before the source)
-                    // NOLINTNEXTLINE(readability-qualified-auto,llvm-qualified-auto): std::copy returns an iterator, see https://github.com/nlohmann/json/issues/3081
-                    const auto end = std::copy(dec_pos + static_cast<std::ptrdiff_t>(decimal_point_len), last, dec_pos + 1);
-                    *end = '\0';
-                    len = end - first;
-                }
             }
         }
 

single_include/nlohmann/json.hpp

@@ -19863,14 +19863,18 @@ class binary_reader
 
     Only the start of an array is tried, which covers arrays of numbers
     (e.g. coordinates) but costs arrays of other values only one call, not one
-    per element.
+    per element. An array of one element is not tried at all: that element is
+    mostly an object or an array (`[[...]]`, the single ring of a GeoJSON
+    polygon), for which the call would find no scalar, while a single scalar,
+    which the run would read faster, is rare. The benchmarks
+    `FromBinaryShape/nested` and `FromBinaryShape/singles` show both sides.
 
     @param[in] len  the number of elements
     @return whether the SAX parser accepted the array and the values read
     */
     bool enter_cbor_array(const std::size_t len)
     {
-        return enter_array(len) && (len == 0 || parse_cbor_scalar_run(std::integral_constant<bool, bulk_scan> {}));
+        return enter_array(len) && (len <= 1 || parse_cbor_scalar_run(std::integral_constant<bool, bulk_scan> {}));
     }
 
     /// input that is not contiguous: every value is read by parse_cbor_value
@@ -20771,12 +20775,16 @@ class binary_reader
     /*!
     @brief open a MessagePack array and read the scalars it begins with (see
            @ref parse_msgpack_scalar_run)
+
+    An array of one element is not tried, for the reason given at
+    @ref enter_cbor_array.
+
     @param[in] len  the number of elements
     @return whether the SAX parser accepted the array and the values read
     */
     bool enter_msgpack_array(const std::size_t len)
     {
-        return enter_array(len) && (len == 0 || parse_msgpack_scalar_run(std::integral_constant<bool, bulk_scan> {}));
+        return enter_array(len) && (len <= 1 || parse_msgpack_scalar_run(std::integral_constant<bool, bulk_scan> {}));
     }
 
     /// input that is not contiguous: every value is read by parse_msgpack_value
@@ -33473,7 +33481,7 @@ NLOHMANN_JSON_NAMESPACE_END
 
 
 
-#include <algorithm> // copy, none_of, min, search
+#include <algorithm> // remove, fill, find, none_of, min
 #include <array> // array
 #include <clocale> // localeconv, lconv
 #include <cmath> // isfinite
@@ -37342,35 +37350,31 @@ class serializer
         // check if the buffer was large enough
         JSON_ASSERT(static_cast<std::size_t>(len) < number_buffer.size());
 
-        // look up the locale's decimal point now, matching what
-        // snprintf_float() just used (see get_decimal_point() in
-        // number_parse.hpp); it is a string, which can be longer than one
-        // byte (U+066B in ps_AF, #5993).
-        // A thousands separator needs no handling: %g never groups digits.
+        // look up the locale's thousands separator and decimal point now,
+        // matching what snprintf_float() just used (see lexer::get_decimal_point())
         const auto* loc = std::localeconv();
         JSON_ASSERT(loc != nullptr);
-        const char* const decimal_point = (loc->decimal_point == nullptr) ? "" : loc->decimal_point;
-        const std::size_t decimal_point_len = std::char_traits<char>::length(decimal_point);
+        const char thousands_sep = (loc->thousands_sep == nullptr) ? '\0' : *loc->thousands_sep;
+        const char decimal_point = (loc->decimal_point == nullptr) ? '\0' : *loc->decimal_point;
+
+        // erase thousands separators
+        if (thousands_sep != '\0')
+        {
+            // NOLINTNEXTLINE(readability-qualified-auto,llvm-qualified-auto): std::remove returns an iterator, see https://github.com/nlohmann/json/issues/3081
+            const auto end = std::remove(number_buffer.begin(), number_buffer.begin() + len, thousands_sep);
+            std::fill(end, number_buffer.end(), '\0');
+            JSON_ASSERT((end - number_buffer.begin()) <= len);
+            len = (end - number_buffer.begin());
+        }
 
         // convert decimal point to '.'
-        if (decimal_point_len != 0 && !(decimal_point_len == 1 && decimal_point[0] == '.'))
+        if (decimal_point != '\0' && decimal_point != '.')
         {
-            const auto first = number_buffer.begin();
-            const auto last = first + len;
-            // NOLINTNEXTLINE(readability-qualified-auto,llvm-qualified-auto): std::search returns an iterator, see https://github.com/nlohmann/json/issues/3081
-            const auto dec_pos = std::search(first, last, decimal_point, decimal_point + decimal_point_len);
-            if (dec_pos != last)
+            // NOLINTNEXTLINE(readability-qualified-auto,llvm-qualified-auto): std::find returns an iterator, see https://github.com/nlohmann/json/issues/3081
+            const auto dec_pos = std::find(number_buffer.begin(), number_buffer.end(), decimal_point);
+            if (dec_pos != number_buffer.end())
             {
                 *dec_pos = '.';
-                if (decimal_point_len > 1)
-                {
-                    // move the fraction and exponent behind the '.' (std::copy
-                    // allows the overlap, as the destination is before the source)
-                    // NOLINTNEXTLINE(readability-qualified-auto,llvm-qualified-auto): std::copy returns an iterator, see https://github.com/nlohmann/json/issues/3081
-                    const auto end = std::copy(dec_pos + static_cast<std::ptrdiff_t>(decimal_point_len), last, dec_pos + 1);
-                    *end = '\0';
-                    len = end - first;
-                }
             }
         }
 

tests/benchmarks/src/benchmarks.cpp

@@ -629,6 +629,22 @@ static json make_containers()
     return j;
 }
 
+/// many arrays of one number each: one-element arrays are left to the general
+/// path (CBOR and MessagePack), which reads a lone number slower than the loop
+/// for arrays of scalars would
+static json make_singles()
+{
+    json data = json::array();
+    for (std::size_t i = 0; i < 100000; ++i)
+    {
+        data.push_back(json::array({i}));
+    }
+
+    json j = json::object();
+    j["data"] = std::move(data);
+    return j;
+}
+
 /// one flat array of numbers: the scalar decoding path, which must not move
 static json make_scalars()
 {
@@ -676,6 +692,8 @@ BENCHMARK_CAPTURE(FromBinaryShape, containers / ubjson_optimized, make_container
 BENCHMARK_CAPTURE(FromBinaryShape, containers / bjdata, make_containers, binary_format::bjdata);
 BENCHMARK_CAPTURE(FromBinaryShape, containers / bson, make_containers, binary_format::bson);
 BENCHMARK_CAPTURE(FromBinaryShape, containers / bon8, make_containers, binary_format::bon8);
+BENCHMARK_CAPTURE(FromBinaryShape, singles / cbor, make_singles, binary_format::cbor);
+BENCHMARK_CAPTURE(FromBinaryShape, singles / msgpack, make_singles, binary_format::msgpack);
 // BSON names every array element, so a large array measures key generation
 // rather than scalar decoding and is left out here
 BENCHMARK_CAPTURE(FromBinaryShape, scalars / cbor, make_scalars, binary_format::cbor);

tests/src/unit-cbor.cpp

@@ -2520,6 +2520,34 @@ TEST_CASE("CBOR arrays of scalars from contiguous and non-contiguous input")
     }
 }
 
+TEST_CASE("CBOR arrays of one element from contiguous and non-contiguous input")
+{
+    // contiguous input leaves an array of one element to the general path
+    // rather than to the loop that reads arrays of scalars; both inputs must
+    // still give the same events, value, or error for the complete document
+    // and for every truncation of it, with enough bytes after each array that
+    // the loop could have been entered
+    const json j = json::parse(R"({"a": [[[[1.5]]]], "b": [7], "c": [{"x": 2.5}], "d": ["s"], "e": [[1, 2]], "f": [null], "g": 1.25})");
+    const std::vector<std::uint8_t> bytes = json::to_cbor(j);
+
+    CHECK(json::from_cbor(bytes) == j);
+
+    for (std::size_t length = 0; length <= bytes.size(); ++length)
+    {
+        CAPTURE(length)
+        const std::vector<std::uint8_t> contiguous(bytes.begin(), bytes.begin() + static_cast<std::ptrdiff_t>(length));
+        const std::list<std::uint8_t> bytewise(contiguous.begin(), contiguous.end());
+
+        CHECK(json::from_cbor(contiguous, true, false).dump() == json::from_cbor(bytewise.begin(), bytewise.end(), true, false).dump());
+
+        SaxEventLogger from_contiguous;
+        SaxEventLogger from_bytewise;
+        CHECK(json::sax_parse(contiguous, &from_contiguous, json::input_format_t::cbor, true, false)
+              == json::sax_parse(bytewise.begin(), bytewise.end(), &from_bytewise, json::input_format_t::cbor, true, false));
+        CHECK(from_contiguous.events == from_bytewise.events);
+    }
+}
+
 TEST_CASE("CBOR indefinite-length strings do not recurse per chunk")
 {
     // Reading an indefinite-length string or byte array used to call itself

tests/src/unit-locale-cpp.cpp

@@ -397,14 +397,6 @@ TEST_CASE("locale with a multi-byte decimal point")
 
         // a value the locale-independent paths convert is not affected
         CHECK(json::parse("12.5") == 12.5);
-
-        // dump() of a long double that takes the snprintf path replaces the
-        // whole decimal point, not only its first byte (#5993)
-        CHECK(long_double_json(1.5L).dump() == "1.5");
-        CHECK(long_double_json(2.0L).dump() == "2.0");
-        CHECK(long_double_json(-0.25L).dump() == "-0.25");
-        CHECK(long_double_json::parse(long_double_json(1.5e-7L).dump()) == long_double_json(1.5e-7L));
-        CHECK(long_double_json::parse(ld.dump()) == expected_long_double);
     }
     if (!tested)
     {

tests/src/unit-msgpack.cpp

@@ -2311,3 +2311,31 @@ TEST_CASE("MessagePack arrays of scalars from contiguous and non-contiguous inpu
               == json::sax_parse(bytewise.begin(), bytewise.end(), &from_bytewise, json::input_format_t::msgpack));
     }
 }
+
+TEST_CASE("MessagePack arrays of one element from contiguous and non-contiguous input")
+{
+    // contiguous input leaves an array of one element to the general path
+    // rather than to the loop that reads arrays of scalars; both inputs must
+    // still give the same events, value, or error for the complete document
+    // and for every truncation of it, with enough bytes after each array that
+    // the loop could have been entered
+    const json j = json::parse(R"({"a": [[[[1.5]]]], "b": [7], "c": [{"x": 2.5}], "d": ["s"], "e": [[1, 2]], "f": [null], "g": 1.25})");
+    const std::vector<std::uint8_t> bytes = json::to_msgpack(j);
+
+    CHECK(json::from_msgpack(bytes) == j);
+
+    for (std::size_t length = 0; length <= bytes.size(); ++length)
+    {
+        CAPTURE(length)
+        const std::vector<std::uint8_t> contiguous(bytes.begin(), bytes.begin() + static_cast<std::ptrdiff_t>(length));
+        const std::list<std::uint8_t> bytewise(contiguous.begin(), contiguous.end());
+
+        CHECK(json::from_msgpack(contiguous, true, false).dump() == json::from_msgpack(bytewise.begin(), bytewise.end(), true, false).dump());
+
+        SaxEventLogger from_contiguous;
+        SaxEventLogger from_bytewise;
+        CHECK(json::sax_parse(contiguous, &from_contiguous, json::input_format_t::msgpack, true, false)
+              == json::sax_parse(bytewise.begin(), bytewise.end(), &from_bytewise, json::input_format_t::msgpack, true, false));
+        CHECK(from_contiguous.events == from_bytewise.events);
+    }
+}