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/home/debugging.md

@@ -10,13 +10,6 @@ at its root, a [Natvis](https://learn.microsoft.com/en-us/visualstudio/debugger/
 file that gives `json`/`ordered_json` values a friendly, key/value debugger view instead of showing raw internal
 fields, when debugging with the MSVC debug engine (`cppvsdbg`) in Visual Studio or VS Code.
 
-The file also has visualizers for `json_document` and `json_view` (and their `ordered_json`/editable variants). They
-show the value of the document or view, and its elements as an expandable list. Because a document is only a flat index
-into the source text, the strings of the direct elements are shown, but the elements of nested arrays and objects are
-shown as index nodes (their kind, size, and numbers; strings only by length). Arrays and objects that have been edited
-in a `json_editable_document` are not expanded. The visualizers read the internal layout of the MSVC STL (`std::array`,
-`std::unique_ptr`).
-
 The checked-in visualizers cover namespace variants with zero, one, or two ABI tags. Configurations with three or more
 ABI tags are not covered and may show raw internal fields instead. To generate a Natvis file for such a configuration:
 
@@ -36,7 +29,7 @@ ABI tags are not covered and may show raw internal fields instead. To generate a
 
 4. Use the generated file instead of `nlohmann_json.natvis`.
 
-`--abi-tags` can be repeated for several configurations, and `--all` generates every combination (about 60 MB for 11
+`--abi-tags` can be repeated for several configurations, and `--all` generates every combination (about 60 MB for 12
 ABI tags, doubling with each further tag). See
 [`tools/generate_natvis`](https://github.com/nlohmann/json/tree/develop/tools/generate_natvis) for all options.
 

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

tools/generate_natvis/README.md

@@ -6,11 +6,6 @@ The checked-in `nlohmann_json.natvis` covers the default namespace (no ABI tags)
 of ABI tags, with both versioned and unversioned namespace variants. Configurations that enable three or more ABI tags
 are not covered by this reduced file; use `--abi-tags` or `--all` (see below) to generate a file for them.
 
-The visualizers of `basic_json_document` and `basic_json_view` live in the same inline namespaces as `basic_json`, so the
-ABI tags apply to them in the same way, and the `view_mode` template argument is covered by a wildcard: it does not
-multiply the namespaces. Each namespace gets three more types (`basic_json_view<*,*>`, `basic_json_document<*,*>`, and
-`detail::view::node`), which roughly doubles the size of the file.
-
 The ABI tag list and the library version are parsed from
 `include/nlohmann/detail/abi_macros.hpp`, so this script must be re-run (via
 `make natvis`) whenever an `NLOHMANN_JSON_ABI_TAG_*` macro is added to that
@@ -40,7 +35,7 @@ version other than the one in `abi_macros.hpp`.
 |-------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
 | `--list-tags`     | Print every ABI tag (in namespace order) with the macro that enables it and the `NLOHMANN_JSON_ABI_TAG_*` identifier, then exit.                                                                                                                    |
 | `--abi-tags TAGS` | Add the namespaces of one configuration, given as a comma-separated list of ABI tags (`_diag,_dp,_ns`; the leading underscore is optional, and the order does not matter). Can be repeated for several configurations. Unknown tags are an error. |
-| `--all`           | Generate the namespaces for every combination of ABI tags. The file size doubles with each tag (about 60 MB for 11 tags). Cannot be combined with `--abi-tags`.                                                                                    |
+| `--all`           | Generate the namespaces for every combination of ABI tags. The file size doubles with each tag (about 60 MB for 12 tags). Cannot be combined with `--abi-tags`.                                                                                    |
 | `--output FILE`   | Write the Natvis file to `FILE` instead of `nlohmann_json.natvis` in the repository root.                                                                                                                                                           |
 
 Each configuration gets both the versioned (`json_abi_diag_dp_ns_v3_12_0`) and the unversioned (`json_abi_diag_dp_ns`,

tools/generate_natvis/generate_natvis.py

@@ -95,7 +95,7 @@ if __name__ == '__main__':
                                 'optional) of one configuration to add to the default namespaces; can be repeated')
     selection.add_argument('--all', action='store_true',
                            help='Generate the namespaces for every combination of ABI tags; the file size doubles '
-                                'with each ABI tag (about 60 MB for 11 tags)')
+                                'with each ABI tag (about 60 MB for 12 tags)')
     parser.add_argument('--list-tags', action='store_true',
                         help='List the ABI tags with the macros that enable them, and exit')
     parser.add_argument('--output', metavar='FILE',

tools/generate_natvis/nlohmann_json.natvis.j2

@@ -5,39 +5,6 @@
 <!-- * * * * * * * * AUTO-GENERATED FILE  * * * * * * * * -->
 
 <AutoVisualizer xmlns="http://schemas.microsoft.com/vstudio/debugger/natvis/2010">
-{# The children of the container node `node` (a pointer expression) of the document `doc` (a document_data pointer
-   expression). A node is only an index into the source text: strings are read from `doc`, so the strings of the
-   direct children are readable here, but the children of a nested container are shown as nodes (see the node
-   visualizer below). Containers with edits (flag 8, "moved") are not expanded. The node kinds are the numbers of
-   node_kind: 1 object, 2 array, 3 string; the float token is shown only by the node visualizer. #}
-{% macro children(node, doc=none) %}
-            <CustomListItems MaxItemsPerView="1000">
-              <Variable Name="nd" InitialValue="{{ node }}" />
-              <Variable Name="obj" InitialValue="nd != 0 &amp;&amp; (int)nd-&gt;kind == 1" />
-              <Variable Name="n" InitialValue="(nd != 0 &amp;&amp; ((int)nd-&gt;kind == 1 || (int)nd-&gt;kind == 2) &amp;&amp; (nd-&gt;flags &amp; 8) == 0) ? (int)nd-&gt;len : 0" />
-              <Variable Name="p" InitialValue="nd + 1" />
-              <Variable Name="i" InitialValue="0" />
-              <Size>obj ? 2 * n : n</Size>
-              <Loop Condition="i &lt; n">
-{% if doc %}
-                <Item Name="key" Condition="obj">{{ doc }}-&gt;base._Elems[p-&gt;flags &amp; 3] + p-&gt;off,[p-&gt;len]s8</Item>
-{% else %}
-                <Item Name="key" Condition="obj">*p</Item>
-{% endif %}
-                <Exec Condition="obj">p = p + 1</Exec>
-{% if doc %}
-                <Item Name="value" Condition="obj &amp;&amp; (int)p-&gt;kind == 3">{{ doc }}-&gt;base._Elems[p-&gt;flags &amp; 3] + p-&gt;off,[p-&gt;len]s8</Item>
-{% endif %}
-                <Item Name="value" Condition="obj{% if doc %} &amp;&amp; (int)p-&gt;kind != 3{% endif %}">*p</Item>
-{% if doc %}
-                <Item Condition="!obj &amp;&amp; (int)p-&gt;kind == 3">{{ doc }}-&gt;base._Elems[p-&gt;flags &amp; 3] + p-&gt;off,[p-&gt;len]s8</Item>
-{% endif %}
-                <Item Condition="!obj{% if doc %} &amp;&amp; (int)p-&gt;kind != 3{% endif %}">*p</Item>
-                <Exec>p = p + (((int)p-&gt;kind == 1 || (int)p-&gt;kind == 2) ? p-&gt;next : 1)</Exec>
-                <Exec>i = i + 1</Exec>
-              </Loop>
-            </CustomListItems>
-{%- endmacro %}
 {% for ns in namespaces %}
     <!-- Namespace {{ ns }} -->
     <Type Name="{{ ns }}::basic_json&lt;*&gt;">
@@ -95,44 +62,5 @@
     </Type>
 
 {% endfor %}
-
-    <!-- json_view / json_document (include/nlohmann/json_view.hpp). They live in the same inline namespaces as
-         basic_json, so the ABI tags need no extra entries; the view_mode is a template argument that the wildcard
-         covers. A view is a pointer to the document's data and a pointer to a node of its flat index; the
-         strings of the source are found through document_data::base (std::array of the MSVC STL: _Elems). -->
-    <Type Name="{{ ns }}::detail::view::node">
-        <DisplayString Condition="(int)kind == 0">null</DisplayString>
-        <DisplayString Condition="(int)kind == 1">object, size={len}</DisplayString>
-        <DisplayString Condition="(int)kind == 2">array, size={len}</DisplayString>
-        <DisplayString Condition="(int)kind == 3">string, length={len}</DisplayString>
-        <DisplayString Condition="(int)kind == 4">boolean: {(flags &amp; 4) != 0}</DisplayString>
-        <DisplayString Condition="(int)kind == 5">int64: {(__int64)((unsigned __int64)len | ((unsigned __int64)next &lt;&lt; 32))}</DisplayString>
-        <DisplayString Condition="(int)kind == 6">uint64: {(unsigned __int64)len | ((unsigned __int64)next &lt;&lt; 32)}</DisplayString>
-        <DisplayString Condition="(int)kind == 7">float, length={len}</DisplayString>
-        <DisplayString>link</DisplayString>
-        <Expand>
-{{ children('this') }}
-        </Expand>
-    </Type>
-
-    <Type Name="{{ ns }}::basic_json_view&lt;*,*&gt;">
-        <DisplayString Condition="m_node == 0">discarded</DisplayString>
-        <DisplayString Condition="(int)m_node-&gt;kind == 3">{m_doc-&gt;base._Elems[m_node-&gt;flags &amp; 3] + m_node-&gt;off,[m_node-&gt;len]s8}</DisplayString>
-        <DisplayString Condition="(int)m_node-&gt;kind == 7">{m_doc-&gt;base._Elems[m_node-&gt;flags &amp; 3] + m_node-&gt;off,[m_node-&gt;len]s8b}</DisplayString>
-        <DisplayString>{*m_node}</DisplayString>
-        <Expand>
-{{ children('m_node', 'm_doc') }}
-        </Expand>
-    </Type>
-
-    <Type Name="{{ ns }}::basic_json_document&lt;*,*&gt;">
-        <DisplayString Condition="m_data._Mypair._Myval2 == 0 || m_data._Mypair._Myval2-&gt;discarded">discarded</DisplayString>
-        <DisplayString>{*m_data._Mypair._Myval2-&gt;nodes}</DisplayString>
-        <Expand>
-            <Item Name="[source]" Condition="m_data._Mypair._Myval2 != 0">m_data._Mypair._Myval2-&gt;src,[m_data._Mypair._Myval2-&gt;size]s8b</Item>
-            <Item Name="[nodes]" Condition="m_data._Mypair._Myval2 != 0">m_data._Mypair._Myval2-&gt;node_count</Item>
-{{ children('m_data._Mypair._Myval2->nodes', 'm_data._Mypair._Myval2') }}
-        </Expand>
-    </Type>
 {% endfor %}
 </AutoVisualizer>