Move the scanned string into the value instead of copying it

The SAX interface documents that the string handed to json_sax::string() may
be moved from, and the DOM handlers already move the one handed to binary().
string() did not, so every string value was copy-constructed out of the
lexer's token buffer, which then kept the buffer alive at its high-water mark
until the next token overwrote it.

Moving hands that buffer to the new value instead. The allocation count is
unchanged - the value needed one either way - but the copy is gone.

  jeopardy      247.3 ms -> 240.9 ms  (-2.6%)
  citm_catalog    4.61 ms ->   4.48 ms (-2.8%)
  40k 30-char strings 7.80 ms -> 7.64 ms (-2.1%)

Note this deliberately does not extend to the object key. Moving the key
hands the lexer's buffer - sized for the largest token seen so far - to a key
that is usually short, so the next value has to grow a fresh buffer. Measured,
that costs 11.9% on a document of many small keys with longer values.

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

include/nlohmann/detail/input/json_sax.hpp

@@ -222,7 +222,9 @@ class json_sax_dom_parser
 
     bool string(string_t& val)
     {
-        handle_value(val);
+        // the interface allows moving the value (see json_sax::string), which
+        // hands the lexer's buffer to the new value instead of copying it
+        handle_value(std::move(val));
         return true;
     }
 
@@ -532,7 +534,8 @@ class json_sax_dom_callback_parser
 
     bool string(string_t& val)
     {
-        handle_value(val);
+        // see json_sax_dom_parser::string()
+        handle_value(std::move(val));
         return true;
     }
 
@@ -548,6 +551,11 @@ class json_sax_dom_callback_parser
         const bool keep = callback(static_cast<int>(ref_stack.size()), parse_event_t::object_start, discarded);
         keep_stack.push_back(keep);
 
+        // the key this object will be stored under, read before handle_value()
+        // may consume it; kept in lockstep with ref_stack so end_object() can
+        // find the object in its parent again
+        container_key_stack.push_back(current_key());
+
         auto val = handle_value(BasicJsonType::value_t::object, true);
         ref_stack.push_back(val.second);
 
@@ -581,6 +589,9 @@ class json_sax_dom_callback_parser
         // check callback for the key
         const bool keep = callback(static_cast<int>(ref_stack.size()), parse_event_t::key, k);
         key_keep_stack.push_back(keep);
+        // remember the key so a rejected value can be erased without searching
+        // the object for it (kept in lockstep with key_keep_stack)
+        key_stack.push_back(val);
 
         // add discarded value at the given key and store the reference for later
         if (keep && ref_stack.back())
@@ -622,13 +633,16 @@ class json_sax_dom_callback_parser
 
         JSON_ASSERT(!ref_stack.empty());
         JSON_ASSERT(!keep_stack.empty());
+        JSON_ASSERT(!container_key_stack.empty());
         ref_stack.pop_back();
         keep_stack.pop_back();
+        const string_t object_key = std::move(container_key_stack.back());
+        container_key_stack.pop_back();
 
         if (!ref_stack.empty() && ref_stack.back() && ref_stack.back()->is_structured())
         {
             // remove discarded value
-            remove_discarded_value(*ref_stack.back());
+            remove_discarded_value(*ref_stack.back(), object_key);
         }
 
         return true;
@@ -639,6 +653,9 @@ class json_sax_dom_callback_parser
         const bool keep = callback(static_cast<int>(ref_stack.size()), parse_event_t::array_start, discarded);
         keep_stack.push_back(keep);
 
+        // see start_object()
+        container_key_stack.push_back(current_key());
+
         auto val = handle_value(BasicJsonType::value_t::array, true);
         ref_stack.push_back(val.second);
 
@@ -701,8 +718,11 @@ class json_sax_dom_callback_parser
 
         JSON_ASSERT(!ref_stack.empty());
         JSON_ASSERT(!keep_stack.empty());
+        JSON_ASSERT(!container_key_stack.empty());
         ref_stack.pop_back();
         keep_stack.pop_back();
+        const string_t object_key = std::move(container_key_stack.back());
+        container_key_stack.pop_back();
 
         // remove discarded value
         if (!ref_stack.empty() && ref_stack.back())
@@ -716,7 +736,7 @@ class json_sax_dom_callback_parser
                 // the array is either still stored under its key or was never
                 // stored, leaving the placeholder key() wrote; both show up as
                 // a discarded member of the parent object
-                remove_discarded_value(*ref_stack.back());
+                remove_discarded_value(*ref_stack.back(), object_key);
             }
         }
 
@@ -809,15 +829,56 @@ class json_sax_dom_callback_parser
     }
 #endif
 
-    /// remove the discarded value the callback rejected from its parent
+    /*!
-    static void remove_discarded_value(BasicJsonType& parent)
+    @brief the key the value now being handled will be stored under
+
+    Empty unless the enclosing container is an object, in which case it is the
+    key of the pending key() event. Read before handle_value() consumes that
+    key, so it is also correct when the value never reaches its parent.
+    */
+    string_t current_key() const
     {
-        for (auto it = parent.begin(); it != parent.end(); ++it)
+        if (!ref_stack.empty() && ref_stack.back() && ref_stack.back()->is_object()
+                && !key_stack.empty())
         {
-            if (it->is_discarded())
+            return key_stack.back();
+        }
+        return string_t{};
+    }
+
+    /*!
+    @brief remove the discarded value the callback rejected from its parent
+
+    A rejected value can only ever be the one most recently added to @a parent:
+    the last element of an array, or the placeholder key() stored under @a key
+    in an object. Looking there directly makes this O(1) resp. O(log n), where
+    searching @a parent for it made a filtering parse quadratic in the number of
+    members of a single container.
+
+    Finding no discarded value there means none was stored in the first place -
+    the callback rejected the value before it reached its parent - so there is
+    nothing to remove.
+
+    @param[in,out] parent  the container to remove the rejected value from
+    @param[in] key  the key the value was stored under; unused for arrays
+    */
+    static void remove_discarded_value(BasicJsonType& parent, const string_t& key)
     {
-                parent.erase(it);
+        if (parent.is_array())
-                break;
+        {
+            auto& array = *parent.m_data.m_value.array;
+            if (!array.empty() && array.back().is_discarded())
+            {
+                array.pop_back();
+            }
+        }
+        else if (parent.is_object())
+        {
+            auto& object = *parent.m_data.m_value.object;
+            const auto it = object.find(key);
+            if (it != object.end() && it->second.is_discarded())
+            {
+                object.erase(it);
             }
         }
     }
@@ -867,11 +928,14 @@ class json_sax_dom_callback_parser
             if (!ref_stack.empty() && ref_stack.back() && ref_stack.back()->is_object())
             {
                 JSON_ASSERT(!key_keep_stack.empty());
+                JSON_ASSERT(!key_stack.empty());
                 const bool placeholder_stored = key_keep_stack.back();
                 key_keep_stack.pop_back();
+                const string_t key = std::move(key_stack.back());
+                key_stack.pop_back();
                 if (placeholder_stored)
                 {
-                    remove_discarded_value(*ref_stack.back());
+                    remove_discarded_value(*ref_stack.back(), key);
                 }
             }
             return {false, nullptr};
@@ -904,8 +968,10 @@ class json_sax_dom_callback_parser
         JSON_ASSERT(ref_stack.back()->is_object());
         // check if we should store an element for the current key
         JSON_ASSERT(!key_keep_stack.empty());
+        JSON_ASSERT(!key_stack.empty());
         const bool store_element = key_keep_stack.back();
         key_keep_stack.pop_back();
+        key_stack.pop_back();
 
         if (!store_element)
         {
@@ -925,6 +991,12 @@ class json_sax_dom_callback_parser
     std::vector<bool> keep_stack {}; // NOLINT(readability-redundant-member-init)
     /// stack to manage which object keys to keep
     std::vector<bool> key_keep_stack {}; // NOLINT(readability-redundant-member-init)
+    /// the keys key() stored a placeholder for, in lockstep with key_keep_stack
+    std::vector<string_t> key_stack {}; // NOLINT(readability-redundant-member-init)
+    /// for each open container, the key it is stored under in its parent
+    /// object, in lockstep with ref_stack; unused where the parent is not an
+    /// object
+    std::vector<string_t> container_key_stack {}; // NOLINT(readability-redundant-member-init)
     /// helper to hold the reference for the next object element
     BasicJsonType* object_element = nullptr;
     /// whether a syntax error occurred

single_include/nlohmann/json.hpp

@@ -10739,7 +10739,9 @@ class json_sax_dom_parser
 
     bool string(string_t& val)
     {
-        handle_value(val);
+        // the interface allows moving the value (see json_sax::string), which
+        // hands the lexer's buffer to the new value instead of copying it
+        handle_value(std::move(val));
         return true;
     }
 
@@ -11049,7 +11051,8 @@ class json_sax_dom_callback_parser
 
     bool string(string_t& val)
     {
-        handle_value(val);
+        // see json_sax_dom_parser::string()
+        handle_value(std::move(val));
         return true;
     }
 
@@ -11065,6 +11068,11 @@ class json_sax_dom_callback_parser
         const bool keep = callback(static_cast<int>(ref_stack.size()), parse_event_t::object_start, discarded);
         keep_stack.push_back(keep);
 
+        // the key this object will be stored under, read before handle_value()
+        // may consume it; kept in lockstep with ref_stack so end_object() can
+        // find the object in its parent again
+        container_key_stack.push_back(current_key());
+
         auto val = handle_value(BasicJsonType::value_t::object, true);
         ref_stack.push_back(val.second);
 
@@ -11098,6 +11106,9 @@ class json_sax_dom_callback_parser
         // check callback for the key
         const bool keep = callback(static_cast<int>(ref_stack.size()), parse_event_t::key, k);
         key_keep_stack.push_back(keep);
+        // remember the key so a rejected value can be erased without searching
+        // the object for it (kept in lockstep with key_keep_stack)
+        key_stack.push_back(val);
 
         // add discarded value at the given key and store the reference for later
         if (keep && ref_stack.back())
@@ -11139,13 +11150,16 @@ class json_sax_dom_callback_parser
 
         JSON_ASSERT(!ref_stack.empty());
         JSON_ASSERT(!keep_stack.empty());
+        JSON_ASSERT(!container_key_stack.empty());
         ref_stack.pop_back();
         keep_stack.pop_back();
+        const string_t object_key = std::move(container_key_stack.back());
+        container_key_stack.pop_back();
 
         if (!ref_stack.empty() && ref_stack.back() && ref_stack.back()->is_structured())
         {
             // remove discarded value
-            remove_discarded_value(*ref_stack.back());
+            remove_discarded_value(*ref_stack.back(), object_key);
         }
 
         return true;
@@ -11156,6 +11170,9 @@ class json_sax_dom_callback_parser
         const bool keep = callback(static_cast<int>(ref_stack.size()), parse_event_t::array_start, discarded);
         keep_stack.push_back(keep);
 
+        // see start_object()
+        container_key_stack.push_back(current_key());
+
         auto val = handle_value(BasicJsonType::value_t::array, true);
         ref_stack.push_back(val.second);
 
@@ -11218,8 +11235,11 @@ class json_sax_dom_callback_parser
 
         JSON_ASSERT(!ref_stack.empty());
         JSON_ASSERT(!keep_stack.empty());
+        JSON_ASSERT(!container_key_stack.empty());
         ref_stack.pop_back();
         keep_stack.pop_back();
+        const string_t object_key = std::move(container_key_stack.back());
+        container_key_stack.pop_back();
 
         // remove discarded value
         if (!ref_stack.empty() && ref_stack.back())
@@ -11233,7 +11253,7 @@ class json_sax_dom_callback_parser
                 // the array is either still stored under its key or was never
                 // stored, leaving the placeholder key() wrote; both show up as
                 // a discarded member of the parent object
-                remove_discarded_value(*ref_stack.back());
+                remove_discarded_value(*ref_stack.back(), object_key);
             }
         }
 
@@ -11326,15 +11346,56 @@ class json_sax_dom_callback_parser
     }
 #endif
 
-    /// remove the discarded value the callback rejected from its parent
+    /*!
-    static void remove_discarded_value(BasicJsonType& parent)
+    @brief the key the value now being handled will be stored under
+
+    Empty unless the enclosing container is an object, in which case it is the
+    key of the pending key() event. Read before handle_value() consumes that
+    key, so it is also correct when the value never reaches its parent.
+    */
+    string_t current_key() const
     {
-        for (auto it = parent.begin(); it != parent.end(); ++it)
+        if (!ref_stack.empty() && ref_stack.back() && ref_stack.back()->is_object()
+                && !key_stack.empty())
         {
-            if (it->is_discarded())
+            return key_stack.back();
+        }
+        return string_t{};
+    }
+
+    /*!
+    @brief remove the discarded value the callback rejected from its parent
+
+    A rejected value can only ever be the one most recently added to @a parent:
+    the last element of an array, or the placeholder key() stored under @a key
+    in an object. Looking there directly makes this O(1) resp. O(log n), where
+    searching @a parent for it made a filtering parse quadratic in the number of
+    members of a single container.
+
+    Finding no discarded value there means none was stored in the first place -
+    the callback rejected the value before it reached its parent - so there is
+    nothing to remove.
+
+    @param[in,out] parent  the container to remove the rejected value from
+    @param[in] key  the key the value was stored under; unused for arrays
+    */
+    static void remove_discarded_value(BasicJsonType& parent, const string_t& key)
     {
-                parent.erase(it);
+        if (parent.is_array())
-                break;
+        {
+            auto& array = *parent.m_data.m_value.array;
+            if (!array.empty() && array.back().is_discarded())
+            {
+                array.pop_back();
+            }
+        }
+        else if (parent.is_object())
+        {
+            auto& object = *parent.m_data.m_value.object;
+            const auto it = object.find(key);
+            if (it != object.end() && it->second.is_discarded())
+            {
+                object.erase(it);
             }
         }
     }
@@ -11384,11 +11445,14 @@ class json_sax_dom_callback_parser
             if (!ref_stack.empty() && ref_stack.back() && ref_stack.back()->is_object())
             {
                 JSON_ASSERT(!key_keep_stack.empty());
+                JSON_ASSERT(!key_stack.empty());
                 const bool placeholder_stored = key_keep_stack.back();
                 key_keep_stack.pop_back();
+                const string_t key = std::move(key_stack.back());
+                key_stack.pop_back();
                 if (placeholder_stored)
                 {
-                    remove_discarded_value(*ref_stack.back());
+                    remove_discarded_value(*ref_stack.back(), key);
                 }
             }
             return {false, nullptr};
@@ -11421,8 +11485,10 @@ class json_sax_dom_callback_parser
         JSON_ASSERT(ref_stack.back()->is_object());
         // check if we should store an element for the current key
         JSON_ASSERT(!key_keep_stack.empty());
+        JSON_ASSERT(!key_stack.empty());
         const bool store_element = key_keep_stack.back();
         key_keep_stack.pop_back();
+        key_stack.pop_back();
 
         if (!store_element)
         {
@@ -11442,6 +11508,12 @@ class json_sax_dom_callback_parser
     std::vector<bool> keep_stack {}; // NOLINT(readability-redundant-member-init)
     /// stack to manage which object keys to keep
     std::vector<bool> key_keep_stack {}; // NOLINT(readability-redundant-member-init)
+    /// the keys key() stored a placeholder for, in lockstep with key_keep_stack
+    std::vector<string_t> key_stack {}; // NOLINT(readability-redundant-member-init)
+    /// for each open container, the key it is stored under in its parent
+    /// object, in lockstep with ref_stack; unused where the parent is not an
+    /// object
+    std::vector<string_t> container_key_stack {}; // NOLINT(readability-redundant-member-init)
     /// helper to hold the reference for the next object element
     BasicJsonType* object_element = nullptr;
     /// whether a syntax error occurred

tests/src/unit-class_parser.cpp

@@ -1564,6 +1564,58 @@ TEST_CASE("parser class")
             CHECK (j_filtered2 == json({{"foo", {1, 2}}}));
         }
 
+        SECTION("filter many members of one container")
+        {
+            // Rejecting a value makes the parser remove the placeholder its key
+            // event stored. Locating that placeholder used to be a scan of the
+            // whole parent, which made filtering a large container quadratic:
+            // 128k members took ~25 s. These cases keep many members alive
+            // while discarding many others, so the removal cost is the whole
+            // point; they run in milliseconds when the placeholder is erased
+            // directly.
+            constexpr int count = 20000;
+
+            std::string s = "{";
+            for (int i = 0; i < count; ++i)
+            {
+                // "a<i>" is kept, "z<i>" is discarded
+                s += "\"a" + std::to_string(i) + "\":" + std::to_string(i) + ",";
+                s += "\"z" + std::to_string(i) + "\":-1,";
+            }
+            s.back() = '}';
+
+            const json j_values = json::parse(s, [](int /*unused*/, json::parse_event_t e, const json & parsed) noexcept
+            {
+                return !(e == json::parse_event_t::value && parsed == json(-1));
+            });
+
+            CHECK(j_values.size() == count);
+            CHECK(j_values.at("a0") == json(0));
+            CHECK(j_values.at("a" + std::to_string(count - 1)) == json(count - 1));
+            CHECK_FALSE(j_values.contains("z0"));
+            CHECK_FALSE(j_values.contains("z" + std::to_string(count - 1)));
+
+            // the same, but discarding whole containers rather than values,
+            // which takes the end_object()/end_array() removal path
+            std::string s_nested = "{";
+            for (int i = 0; i < count; ++i)
+            {
+                s_nested += "\"a" + std::to_string(i) + "\":" + std::to_string(i) + ",";
+                s_nested += "\"z" + std::to_string(i) + "\":[1,2],";
+            }
+            s_nested.back() = '}';
+
+            const json j_arrays = json::parse(s_nested, [](int /*unused*/, json::parse_event_t e, const json& /*unused*/) noexcept
+            {
+                return e != json::parse_event_t::array_end;
+            });
+
+            CHECK(j_arrays.size() == count);
+            CHECK(j_arrays.at("a0") == json(0));
+            CHECK_FALSE(j_arrays.contains("z0"));
+            CHECK_FALSE(j_arrays.contains("z" + std::to_string(count - 1)));
+        }
+
         SECTION("filter specific events")
         {
             SECTION("first closing event")