json_view: skip the digits of a fraction 16 bytes at a time (SSE2)

The digits after the decimal point were skipped by skip_digits(), 16 compare-and-branch
steps in a row: about 3.5 instructions per digit, and an exit branch that is
mispredicted when the lengths of the fractions vary. On x86 with SSE2, the
fraction is now skipped by skip_fraction_digits(): 16 bytes are compared at
once and the end of the run is taken from the bit mask, which is about a third
of the instructions for a fraction of 12 digits. The last bytes of the input
are skipped one at a time as before. Where there is no SSE2 (AArch64, other
targets, JSON_NO_SIMD) skip_fraction_digits() is skip_digits(): nothing changes
there. Integer digits keep skip_digits(), whose exit is predictable.

GCC unrolls the loop over the last bytes in every inlined copy of the new
function, which made the parse loop 4 KiB larger and parse() of documents with
hardly any fractions about 4 % slower. For GCC that loop is therefore out of
line (skip_digits_tail()); Clang is faster with it inline.

json_document::parse(), A/B in one binary, 6 code layouts, x86-64 Haswell,
time after / before (GCC 16.2 / Clang 23):

- numbers.json (10,001 floats): 0.715 / 0.680
- canada.json: 0.778 / 0.790
- mesh.json: 0.908 / 0.883
- marine_ik.json: 0.937 / 0.926
- mesh.pretty.json: 0.923 / 0.960

Files with few or no fractions and files with fractions of a fixed length
(20,000 prices with two decimals, 60,000 coordinates with six): between 0.98 and
1.014 on both compilers, except citm_catalog.json with GCC (1.05: the
instruction count is +0.3 %, and that row varies by +-7 % between builds of
unrelated variants on this machine).

New test: fractions of every length from 0 to 40 digits followed by every kind of
byte that ends a number or lies next to the digits in ASCII, in several
positions, and cut in every place near the end of the text, against json::parse()
(the length of the number is part of what is compared), for all option
combinations and with and without a terminating NUL. Checked on x86-64 with GCC 16.2,
Clang 23 and Apple clang under Rosetta, and with a deliberate off-by-one at the 16th byte.

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

docs/mkdocs/docs/features/json_view.md

@@ -253,34 +253,6 @@ Two conversions never copy at all:
 
 Both results are only valid as long as the view — and, for a string with no escapes, the borrowed source text — is.
 
-### `string_view` members
-
-A struct whose member is a `#!cpp std::string_view` (C++17) can be decoded from a view with the
-`NLOHMANN_DEFINE_TYPE_*` macros, and the member is not copied either: for a string without escape sequences it points
-into the document's source text, and for a string with escape sequences into the document's buffer of decoded strings.
-The member is valid as long as the document is alive and, for a document that
-[borrows its source text](#ownership-and-lifetime) (as [`parse()`](../api/basic_json_document/parse.md) does for
-an lvalue `#!cpp std::string`, a `#!cpp std::string_view`, or a C string), as long as that text is.
-
-```cpp
-struct record
-{
-    std::string_view name;
-    int count;
-    NLOHMANN_DEFINE_TYPE_INTRUSIVE(record, name, count)
-};
-
-const std::string text = R"({"name": "widget", "count": 3})";
-const json_document doc = json_document::parse(text);  // borrows text
-const record r = doc.root().get<record>();             // r.name points into text, valid while text and doc are
-```
-
-!!! warning "Decoding into a `string_view` from a `json` value dangles at once"
-
-    The same struct also compiles with `#!cpp json::parse(text).get<record>()`, but there `name` points into the
-    temporary `json` value, which is destroyed at the end of the statement. Use a named
-    [`json_document`](../api/json_document.md), as above, to decode such a struct.
-
 ## Writing generic code
 
 A view's type names its `BasicJsonType` and its [`view_mode`](../api/view_mode.md):

include/nlohmann/detail/view/builder.hpp

@@ -1082,7 +1082,7 @@ indent_done:
             {
                 ++p;
                 const unsigned char* const f0 = p;
-                p = skip_digits(p, e);
+                p = skip_fraction_digits(p, e);
                 if (NLOHMANN_VIEW_UNLIKELY(p == f0))
                 {
                     return fail(error_code::number_after_dot);

include/nlohmann/detail/view/scan.hpp

@@ -198,6 +198,57 @@ inline const unsigned char* find_block_comment_end(const unsigned char* p, const
     return p;
 }
 
+/// The digits of a fraction, whose number varies from one number to the next: skip_digits() with 16 bytes compared at
+/// once and the end of the run taken from a bit mask (SSE2), instead of a compare and a branch for each digit. That
+/// is about a third of the instructions for a fraction of 12 digits, and no branch that is mispredicted when the
+/// lengths vary. Where there is no SSE2, skip_digits() is used.
+#if NLOHMANN_VIEW_SSE2
+// The last bytes of the input, one at a time. GCC unrolls this loop in every inlined copy of the function below, which
+// makes the parse loop 4 KiB larger and slows down documents that have hardly any fractions; out of line, it does
+// not. Clang does better with the loop inline (a call in the parse loop costs it more than the unrolling).
+#if defined(__GNUC__) && !defined(__clang__)
+inline NLOHMANN_VIEW_NOINLINE const unsigned char* skip_digits_tail(const unsigned char* p, const unsigned char* e) noexcept
+{
+    while (p != e && is_digit(*p))
+    {
+        ++p;
+    }
+    return p;
+}
+#else
+NLOHMANN_VIEW_ALWAYS_INLINE const unsigned char* skip_digits_tail(const unsigned char* p, const unsigned char* e) noexcept
+{
+    while (p != e && is_digit(*p))
+    {
+        ++p;
+    }
+    return p;
+}
+#endif
+
+NLOHMANN_VIEW_ALWAYS_INLINE const unsigned char* skip_fraction_digits(const unsigned char* p, const unsigned char* e) noexcept
+{
+    while (e - p >= 16)
+    {
+        const __m128i in = _mm_loadu_si128(static_cast<const __m128i*>(static_cast<const void*>(p))); // NOLINT(bugprone-casting-through-void)
+        // a digit is above '/' and below ':' (signed compares: a byte with the top bit set is negative, and neither)
+        const __m128i digits = _mm_and_si128(_mm_cmpgt_epi8(in, _mm_set1_epi8('/')), _mm_cmplt_epi8(in, _mm_set1_epi8(':')));
+        const auto not_digit = static_cast<std::uint64_t>(~static_cast<unsigned>(_mm_movemask_epi8(digits)) & 0xFFFFu);
+        if (not_digit != 0)
+        {
+            return p + count_trailing_zeros(not_digit);
+        }
+        p += 16;
+    }
+    return skip_digits_tail(p, e);
+}
+#else
+NLOHMANN_VIEW_ALWAYS_INLINE const unsigned char* skip_fraction_digits(const unsigned char* p, const unsigned char* e) noexcept
+{
+    return skip_digits(p, e);
+}
+#endif
+
 /// powers of ten up to 10^19 as integers
 inline std::uint64_t int_pow10(unsigned k) noexcept
 {

single_include/nlohmann/json_view.hpp

@@ -1218,6 +1218,57 @@ inline const unsigned char* find_block_comment_end(const unsigned char* p, const
     return p;
 }
 
+/// The digits of a fraction, whose number varies from one number to the next: skip_digits() with 16 bytes compared at
+/// once and the end of the run taken from a bit mask (SSE2), instead of a compare and a branch for each digit. That
+/// is about a third of the instructions for a fraction of 12 digits, and no branch that is mispredicted when the
+/// lengths vary. Where there is no SSE2, skip_digits() is used.
+#if NLOHMANN_VIEW_SSE2
+// The last bytes of the input, one at a time. GCC unrolls this loop in every inlined copy of the function below, which
+// makes the parse loop 4 KiB larger and slows down documents that have hardly any fractions; out of line, it does
+// not. Clang does better with the loop inline (a call in the parse loop costs it more than the unrolling).
+#if defined(__GNUC__) && !defined(__clang__)
+inline NLOHMANN_VIEW_NOINLINE const unsigned char* skip_digits_tail(const unsigned char* p, const unsigned char* e) noexcept
+{
+    while (p != e && is_digit(*p))
+    {
+        ++p;
+    }
+    return p;
+}
+#else
+NLOHMANN_VIEW_ALWAYS_INLINE const unsigned char* skip_digits_tail(const unsigned char* p, const unsigned char* e) noexcept
+{
+    while (p != e && is_digit(*p))
+    {
+        ++p;
+    }
+    return p;
+}
+#endif
+
+NLOHMANN_VIEW_ALWAYS_INLINE const unsigned char* skip_fraction_digits(const unsigned char* p, const unsigned char* e) noexcept
+{
+    while (e - p >= 16)
+    {
+        const __m128i in = _mm_loadu_si128(static_cast<const __m128i*>(static_cast<const void*>(p))); // NOLINT(bugprone-casting-through-void)
+        // a digit is above '/' and below ':' (signed compares: a byte with the top bit set is negative, and neither)
+        const __m128i digits = _mm_and_si128(_mm_cmpgt_epi8(in, _mm_set1_epi8('/')), _mm_cmplt_epi8(in, _mm_set1_epi8(':')));
+        const auto not_digit = static_cast<std::uint64_t>(~static_cast<unsigned>(_mm_movemask_epi8(digits)) & 0xFFFFu);
+        if (not_digit != 0)
+        {
+            return p + count_trailing_zeros(not_digit);
+        }
+        p += 16;
+    }
+    return skip_digits_tail(p, e);
+}
+#else
+NLOHMANN_VIEW_ALWAYS_INLINE const unsigned char* skip_fraction_digits(const unsigned char* p, const unsigned char* e) noexcept
+{
+    return skip_digits(p, e);
+}
+#endif
+
 /// powers of ten up to 10^19 as integers
 inline std::uint64_t int_pow10(unsigned k) noexcept
 {
@@ -2324,7 +2375,7 @@ indent_done:
             {
                 ++p;
                 const unsigned char* const f0 = p;
-                p = skip_digits(p, e);
+                p = skip_fraction_digits(p, e);
                 if (NLOHMANN_VIEW_UNLIKELY(p == f0))
                 {
                     return fail(error_code::number_after_dot);

tests/src/unit-json_view_builder.cpp

@@ -523,6 +523,47 @@ TEST_CASE("json_view builder: strings across vector blocks")
     }
 }
 
+TEST_CASE("json_view builder: fraction digits")
+{
+    // The digits of a fraction are skipped 16 bytes at a time where there are
+    // that many left (SSE2), and one at a time after that. Fractions of every
+    // length from 0 to 40 digits, followed by every kind of byte that ends a
+    // number or lies next to the digits in ASCII ('/' and ':'), as values, as
+    // keys' neighbours, and at the very end of the text (a vector without a
+    // terminating NUL). The length of the number is part of the value that
+    // the test compares with json::parse().
+    const std::string followers = ",]}/:.eE+-x \n\t\"09";
+    std::mt19937 rng(2028); // NOLINT(cert-msc32-c,cert-msc51-cpp,bugprone-random-generator-seed): reproducible
+    for (std::size_t digits = 0; digits <= 40; ++digits)
+    {
+        for (int i = 0; i < 3; ++i)
+        {
+            std::string fraction;
+            for (std::size_t k = 0; k < digits; ++k)
+            {
+                fraction += static_cast<char>('0' + (rng() % 10));
+            }
+            const std::string number = std::string(rng() % 2 == 0 ? "-" : "") + std::to_string(rng() % 100000) + "." + fraction;
+            check_same(number);
+            check_same("[" + number + "]");
+            check_same("[" + number + "," + number + "]");
+            check_same("{\"a\":" + number + "}");
+            for (const char follower : followers)
+            {
+                check_same(number + follower);
+                check_same("[" + number + follower + "]");
+                check_same("[" + number + follower + std::string(rng() % 20, '1'));
+            }
+            // everything near the end of the text: the number cut in every place
+            for (std::size_t cut = 1; cut <= 18 && cut <= number.size(); ++cut)
+            {
+                check_same(number.substr(0, number.size() - cut));
+                check_same("[" + number.substr(0, number.size() - cut));
+            }
+        }
+    }
+}
+
 TEST_CASE("json_view builder: escapes between runs of text")
 {
     // The text between escapes is copied 16 bytes at a time where there are

tests/src/unit-json_view_from_json.cpp

@@ -39,7 +39,6 @@ using nlohmann::ordered_json_document;
 
 #ifdef JSON_HAS_CPP_17
     #include <optional>
-    #include <string_view>
 #endif
 
 // NLOHMANN_JSON_SERIALIZE_ENUM uses a static std::pair; same() compares floating-point values on purpose
@@ -470,70 +469,5 @@ TEST_CASE("json_view from_json")
 #endif
 }
 
-#ifdef JSON_HAS_CPP_17
-namespace view_from_json
-{
-// a string_view member is not copied: it points into the source text or, for a
-// string with escape sequences, into the buffer of decoded strings of the document
-struct named_view
-{
-    // initialized for GCC -Weffc++
-    // NOLINTNEXTLINE(readability-redundant-member-init)
-    std::string_view name{};
-    int n = 0;
-    NLOHMANN_DEFINE_TYPE_INTRUSIVE(named_view, name, n)
-};
-}  // namespace view_from_json
-
-TEST_CASE("json_view from_json: string_view members borrow from the document")
-{
-    using view_from_json::named_view;
-
-    // whether all of s is inside the bytes of text
-    const auto within = [](std::string_view s, std::string_view text)
-    {
-        const auto first = reinterpret_cast<std::uintptr_t>(text.data());
-        const auto begin = reinterpret_cast<std::uintptr_t>(s.data());
-        return begin >= first && begin + s.size() <= first + text.size();
-    };
-
-    SECTION("a string without escapes points into the source text")
-    {
-        const std::string text = R"({"name": "hello", "n": 1})";
-        const json_document d = json_document::parse(text);
-        REQUIRE_FALSE(d.owns_source());
-        const auto r = d.root().get<named_view>();
-        CHECK(r.name == "hello");
-        CHECK(r.n == 1);
-        CHECK(within(r.name, text));
-        CHECK(within(r.name, d.source()));
-    }
-
-    SECTION("a string with escapes points into the document, not into the source text")
-    {
-        const std::string text = R"({"name": "a\nb", "n": 2})";
-        json_document d = json_document::parse(text);
-        REQUIRE_FALSE(d.owns_source());
-        const auto r = d.root().get<named_view>();
-        CHECK(r.name == "a\nb");
-        CHECK(r.n == 2);
-        CHECK_FALSE(within(r.name, text));
-        // valid as long as the document is alive, even if the document is moved
-        const json_document moved = std::move(d);
-        CHECK(r.name == "a\nb");
-        CHECK(moved.root().get<named_view>().name == r.name);
-    }
-
-    SECTION("a document that owns its text keeps the members readable while it is alive")
-    {
-        const json_document d = json_document::parse(std::string(R"({"name": "owned", "n": 3})"));
-        REQUIRE(d.owns_source());
-        const auto r = d.root().get<named_view>();
-        CHECK(r.name == "owned");
-        CHECK(within(r.name, d.source()));
-    }
-}
-#endif
-
 DOCTEST_CLANG_SUPPRESS_WARNING_POP
 DOCTEST_GCC_SUPPRESS_WARNING_POP