Speed up writing CBOR and MessagePack, above all integer arrays

Squashed onto develop cd6b428ef (CI fixes from #5860). Original commits:

- Append to the output vector through a position-tracking sink
- Write CBOR integers without branching on their sign or size
- Write MessagePack integers without branching on their sign or size
- Use std::array for the integer size class table
- Fix clang-tidy and GCC warnings in the integer array test
- Regenerate the amalgamation

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

include/nlohmann/detail/json_pointer.hpp

@@ -9,13 +9,10 @@
 #pragma once
 
 #include <algorithm> // all_of
-#include <array> // array
 #include <cctype> // isdigit
 #include <cerrno> // errno, ERANGE
 #include <cstddef> // size_t
-#include <cstdint> // uint64_t
 #include <cstdlib> // strtoull
-#include <cstring> // memcmp, memcpy
 #ifndef JSON_NO_IO
     #include <iosfwd> // ostream
 #endif  // JSON_NO_IO
@@ -495,111 +492,50 @@ class json_pointer
 
   private:
     /*!
-    @brief the pointer prefixes of a flattened object that denote arrays
+    @brief the pointer prefixes of a flattened object, and which of them denote arrays
 
-    @ref unflatten creates arrays exactly below the prefixes that have a
+    @ref unflatten collects the pointer prefixes that have a reference token 0
-    reference token 0 among their children, and objects everywhere else.
+    among their children; @ref get_and_create creates arrays exactly below
-    Deciding this up front keeps the result independent of the order in which
+    those prefixes and objects everywhere else. Deciding this up front keeps
-    the flattened object is iterated, which is unspecified for some object
+    the result independent of the order in which the flattened object is
-    types.
+    iterated, which is unspecified for some object types.
 
-    A prefix is identified by the text of the key it is the beginning of:
+    The prefixes form a tree and are numbered (number 0 is the empty prefix),
-    escaping is unambiguous, so equal prefixes of valid keys are equal texts.
+    so each of them is stored only once (as a node) rather than as a copy of
-    The set refers to the keys, which must outlive it.
+    all of its reference tokens. The tree does not own the reference tokens:
+    it refers to the tokens of the parsed keys, which must outlive it.
     */
-    class array_prefix_set
+    struct prefix_tree
     {
-      public:
+        // open-addressing hash table from (parent, last reference token) to
-        void insert(const char* data, std::size_t size)
+        // the number of the node; empty slots have token == nullptr
-        {
-            // flattened objects are usually sorted, so most keys that have a
-            // 0 yield the prefix of the previous one
-            if (last_data != nullptr && last_size == size && std::memcmp(last_data, data, size) == 0)
-            {
-                return;
-            }
-            last_data = data;
-            last_size = size;
-
-            if (slots.empty())
-            {
-                slots.resize(16);
-            }
-            const std::size_t hash = hash_of(data, size);
-            const std::size_t mask = slots.size() - 1;
-            std::size_t i = hash & mask;
-            while (slots[i].data != nullptr)
-            {
-                if (slots[i].hash == hash && slots[i].size == size && std::memcmp(slots[i].data, data, size) == 0)
-                {
-                    return;
-                }
-                i = (i + 1) & mask;
-            }
-            slots[i] = slot(hash, data, size);
-
-            // keep the load factor below 1/2
-            if (++used * 2 > slots.size())
-            {
-                grow();
-            }
-        }
-
-        bool empty() const noexcept
-        {
-            return used == 0;
-        }
-
-        bool contains(const char* data, std::size_t size) const noexcept
-        {
-            if (used == 0)
-            {
-                return false;
-            }
-            const std::size_t hash = hash_of(data, size);
-            const std::size_t mask = slots.size() - 1;
-            for (std::size_t i = hash & mask; slots[i].data != nullptr; i = (i + 1) & mask)
-            {
-                if (slots[i].hash == hash && slots[i].size == size && std::memcmp(slots[i].data, data, size) == 0)
-                {
-                    return true;
-                }
-            }
-            return false;
-        }
-
-      private:
         struct slot
         {
-            slot() noexcept = default;
+            std::size_t hash;
+            std::size_t parent;
+            const string_t* token;
+            std::size_t id;
 
-            slot(std::size_t h, const char* d, std::size_t s) noexcept
+            slot() noexcept
-                : hash(h), data(d), size(s)
+                : hash(0), parent(0), token(nullptr), id(0)
             {}
 
-            std::size_t hash = 0;
+            slot(std::size_t h, std::size_t p, const string_t* t, std::size_t i) noexcept
-            const char* data = nullptr; // nullptr: the slot is empty
+                : hash(h), parent(p), token(t), id(i)
-            std::size_t size = 0;
+            {}
         };
 
-        static std::size_t hash_of(const char* data, std::size_t size) noexcept
+        std::vector<slot> slots;
+        std::size_t used = 0;
+
+        static std::size_t hash_of(std::size_t parent, const string_t& token) noexcept
         {
-            std::uint64_t h = 0x9E3779B97F4A7C15ULL ^ size;
+            std::size_t h = parent * static_cast<std::size_t>(0x9E3779B97F4A7C15ULL & (std::numeric_limits<std::size_t>::max)());
-            std::size_t i = 0;
+            for (std::size_t i = 0; i < token.size(); ++i)
-            for (; i + 8 <= size; i += 8)
             {
-                std::uint64_t w = 0;
+                h = (h ^ static_cast<unsigned char>(token[i])) * static_cast<std::size_t>(0x100000001B3ULL & (std::numeric_limits<std::size_t>::max)());
-                std::memcpy(&w, data + i, 8);
-                h = (h ^ w) * 0x100000001B3ULL;
-                h ^= h >> 32u;
             }
-            std::uint64_t w = 0;
+            return h ^ (h >> 29u);
-            if (i < size)
-            {
-                std::memcpy(&w, data + i, size - i);
-            }
-            h = (h ^ w) * 0x9E3779B97F4A7C15ULL;
-            return static_cast<std::size_t>(h ^ (h >> 29u));
         }
 
         void grow()
@@ -609,10 +545,10 @@ class json_pointer
             const std::size_t mask = slots.size() - 1;
             for (const auto& s : old)
             {
-                if (s.data != nullptr)
+                if (s.token != nullptr)
                 {
                     std::size_t i = s.hash & mask;
-                    while (slots[i].data != nullptr)
+                    while (slots[i].token != nullptr)
                     {
                         i = (i + 1) & mask;
                     }
@@ -621,160 +557,117 @@ class json_pointer
             }
         }
 
-        std::vector<slot> slots{};
+        // parent[id] is the number of the prefix without its last token
-        std::size_t used = 0;
+        std::vector<std::size_t> parent;
-        const char* last_data = nullptr;
+        // is_array[id] is true iff some flattened key has the reference token
-        std::size_t last_size = 0;
+        // 0 directly below the prefix with number id
+        std::vector<bool> is_array;
+
+        // start with the empty prefix only
+        prefix_tree()
+            : slots(16)
+            , parent(1, 0)
+            , is_array(1, false)
+        {}
+
+        // return the number of the prefix with number id extended by
+        // reference_token, adding it if it is new
+        std::size_t add_child(std::size_t id, const string_t& reference_token)
+        {
+            const std::size_t hash = hash_of(id, reference_token);
+            const std::size_t mask = slots.size() - 1;
+            std::size_t i = hash & mask;
+            while (slots[i].token != nullptr)
+            {
+                if (slots[i].hash == hash && slots[i].parent == id && *slots[i].token == reference_token)
+                {
+                    return slots[i].id;
+                }
+                i = (i + 1) & mask;
+            }
+
+            // new prefix
+            const std::size_t child = parent.size();
+            slots[i] = slot(hash, id, &reference_token, child);
+            if (reference_token == "0")
+            {
+                is_array[id] = true;
+            }
+            parent.push_back(id);
+            is_array.push_back(false);
+
+            // keep the load factor below 1/2
+            if (++used * 2 > slots.size())
+            {
+                grow();
+            }
+            return child;
+        }
     };
 
-    /// @brief the length of the longest common prefix of the first @a limit bytes of @a a and @a b
-    static std::size_t common_prefix_length(const char* a, const char* b, const std::size_t limit) noexcept
-    {
-        std::size_t i = 0;
-        for (; i + 8 <= limit; i += 8)
-        {
-            std::uint64_t x = 0;
-            std::uint64_t y = 0;
-            std::memcpy(&x, a + i, 8);
-            std::memcpy(&y, b + i, 8);
-            if (x != y)
-            {
-                break;
-            }
-        }
-        while (i < limit && a[i] == b[i])
-        {
-            ++i;
-        }
-        return i;
-    }
-
     /*!
-    @brief check that @a key is a valid JSON pointer, and add the prefixes of
+    @brief create and return a reference to the pointed to value
-           it that denote arrays to @a arrays
 
-    @throw parse_error.107  if the key is not empty or begins with '/'
+    @param[in] j  the value to create the pointed to value in
-    @throw parse_error.108  if character '~' is not followed by '0' or '1'
+    @param[in] tokens  the reference tokens of the pointer
+    @param[in] prefixes  prefixes[i] is the number in @a tree of the prefix
+                         consisting of the first i reference tokens
 
-    The same checks as @ref split, which throws the same exceptions, but
+    Complexity: Linear in the number of reference tokens.
-    without building the reference tokens.
-    */
-    static void scan_key(const string_t& key, const string_t* previous, array_prefix_set& arrays)
-    {
-        const std::size_t size = key.size();
-        if (size == 0)
-        {
-            return;
-        }
 
-        const char* const data = key.data();
+    @throw parse_error.106 if an array index begins with '0'
-        if (JSON_HEDLEY_UNLIKELY(data[0] != '/'))
+    @throw parse_error.109 if array index is not a number
-        {
+    @throw type_error.313 if value cannot be unflattened
-            JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_missing_slash, 1, detail::concat("JSON pointer must be empty or begin with '/' - was: '", key, "'"), nullptr));
-        }
-
-        // The beginning of the key that it has in common with the previous
-        // one, which was checked already, is skipped: the scan starts with
-        // the token after the last slash in it.
-        std::size_t begin = 1;
-        if (previous != nullptr)
-        {
-            std::size_t same = common_prefix_length(data, previous->data(), (std::min)(size, previous->size()));
-            while (same > 1 && data[same - 1] != '/')
-            {
-                --same;
-            }
-            if (same > 1)
-            {
-                begin = same;
-            }
-        }
-
-        for (std::size_t i = begin; i <= size; ++i)
-        {
-            if (i == size || data[i] == '/')
-            {
-                // a token 0 makes the pointer before it an array
-                if (i - begin == 1 && data[begin] == '0')
-                {
-                    arrays.insert(data, begin - 1);
-                }
-                begin = i + 1;
-            }
-            else if (data[i] == '~')
-            {
-                // ~ must be followed by 0 or 1
-                if (JSON_HEDLEY_UNLIKELY(i + 1 == size || (data[i + 1] != '0' && data[i + 1] != '1')))
-                {
-                    JSON_THROW(detail::parse_error::create(detail::exception_id::pointer_invalid_escape, 0, "escape character '~' must be followed with '0' or '1'", nullptr));
-                }
-            }
-        }
-    }
-
-    /*!
-    @brief resolve a plain JSON pointer without building its reference tokens
-
-    @param[in] ptr     the value the pointer starts at
-    @param[in] path    a JSON pointer string
-    @param[in] length  the number of leading bytes of @a path to resolve; 0 or
-                       the position of a slash
-    @param[in,out] token  a string to hold the reference tokens, to reuse its storage
-
-    @return the pointed to value, or `nullptr` if the pointer does not denote
-            an existing value, or does so in a way that is not plain: a
-            reference token with an escape, an array index that is malformed or
-            out of range, or a "-". No exception is thrown for these; callers
-            use @ref json_pointer instead, which handles them.
     */
     template<typename BasicJsonType>
-    static BasicJsonType* resolve_plain(BasicJsonType* ptr, const string_t& path, const std::size_t length, string_t& token)
+    static BasicJsonType& get_and_create(BasicJsonType& j, const std::vector<string_t>& tokens,
+                                         const std::vector<std::size_t>& prefixes, const prefix_tree& tree)
     {
-        for (std::size_t pos = 0; pos < length;)
+        auto* result = &j;
+
+        // in case no reference tokens exist, return a reference to the JSON value
+        // j which will be overwritten by a primitive value
+        for (std::size_t i = 0; i < tokens.size(); ++i)
         {
-            if (JSON_HEDLEY_UNLIKELY(path[pos] != '/'))
+            const auto& reference_token = tokens[i];
+            switch (result->type())
             {
-                return nullptr;
+                case detail::value_t::null:
-            }
+                {
+                    if (tree.is_array[prefixes[i]])
+                    {
+                        // some reference token below this position is 0, so the
+                        // value is an array
+                        result = &result->operator[](array_index<BasicJsonType>(reference_token));
+                    }
+                    else
+                    {
+                        // start a new object otherwise
+                        result = &result->operator[](reference_token);
+                    }
+                    break;
+                }
 
-            // the reference token between the slash at pos and the next one
-            std::size_t end = path.find_first_of('/', pos + 1);
-            if (end == string_t::npos || end > length)
-            {
-                end = length;
-            }
-            token.clear();
-            token.append(path.data() + pos + 1, end - pos - 1);
-            if (JSON_HEDLEY_UNLIKELY(token.find_first_of('~') != string_t::npos))
-            {
-                return nullptr;
-            }
-
-            switch (ptr->type())
-            {
                 case detail::value_t::object:
                 {
-                    const auto it = ptr->m_data.m_value.object->find(token);
+                    // create an entry in the object
-                    if (JSON_HEDLEY_UNLIKELY(it == ptr->m_data.m_value.object->end()))
+                    result = &object_member(*result, reference_token);
-                    {
-                        return nullptr;
-                    }
-                    ptr = &it->second;
                     break;
                 }
 
                 case detail::value_t::array:
                 {
-                    typename BasicJsonType::size_type idx{};
+                    // create an entry in the array
-                    if (JSON_HEDLEY_UNLIKELY(parse_array_index<BasicJsonType>(token, idx) != array_index_status::ok || idx >= ptr->m_data.m_value.array->size()))
+                    result = &result->operator[](array_index<BasicJsonType>(reference_token));
-                    {
-                        return nullptr;
-                    }
-                    ptr = &(*ptr->m_data.m_value.array)[idx];
                     break;
                 }
 
-                case detail::value_t::null:
+                /*
+                The following code is only reached if there exists a reference
+                token _and_ the current value is primitive. In this case, we have
+                an error situation, because primitive values may only occur as
+                a single value; that is, with an empty list of reference tokens.
+                */
                 case detail::value_t::string:
                 case detail::value_t::boolean:
                 case detail::value_t::number_integer:
@@ -783,12 +676,11 @@ class json_pointer
                 case detail::value_t::binary:
                 case detail::value_t::discarded:
                 default:
-                    return nullptr;
+                    JSON_THROW(detail::type_error::create(detail::exception_id::unflatten_invalid_value, "invalid value to unflatten", &j));
             }
-            pos = end;
         }
 
-        return ptr;
+        return *result;
     }
 
     /*!
@@ -1243,45 +1135,20 @@ class json_pointer
     // Add the entry (key, v) to the object `obj`. Flattened paths are pairwise
     // distinct, so objects that can append a key known to be absent
     // (ordered_map) skip the lookup, which is linear and would make flatten
-    // quadratic. Objects with a positional insert (std::map) insert next to
+    // quadratic; all other object types use operator[].
-    // the entry added last: paths come out in nearly sorted order, so the
-    // position is usually right and no search from the root is needed.
-    // All other object types use operator[].
     template<typename ObjectType, typename ValueType>
-    static auto add_flattened(ObjectType& obj, typename ObjectType::iterator& /*hint*/, const string_t& key, ValueType&& v, detail::priority_tag<2> /*unused*/)
+    static auto add_flattened(ObjectType& obj, const string_t& key, ValueType&& v, detail::priority_tag<1> /*unused*/)
     -> decltype(obj.emplace_new_key(key, std::forward<ValueType>(v)), void())
     {
         obj.emplace_new_key(key, std::forward<ValueType>(v));
     }
 
     template<typename ObjectType, typename ValueType>
-    static auto add_flattened(ObjectType& obj, typename ObjectType::iterator& hint, const string_t& key, ValueType&& v, detail::priority_tag<1> /*unused*/)
+    static void add_flattened(ObjectType& obj, const string_t& key, ValueType&& v, detail::priority_tag<0> /*unused*/)
-    -> decltype(hint = obj.emplace_hint(hint, key, std::forward<ValueType>(v)), void())
-    {
-        hint = obj.emplace_hint(hint, key, std::forward<ValueType>(v));
-        ++hint;
-    }
-
-    template<typename ObjectType, typename ValueType>
-    static void add_flattened(ObjectType& obj, typename ObjectType::iterator& /*hint*/, const string_t& key, ValueType&& v, detail::priority_tag<0> /*unused*/)
     {
         obj[key] = std::forward<ValueType>(v);
     }
 
-    /// append the decimal representation of @a i to @a out
-    static void append_index(string_t& out, std::size_t i)
-    {
-        std::array<char, 24> buf{};
-        std::size_t pos = buf.size();
-        do
-        {
-            buf[--pos] = static_cast<char>('0' + i % 10);
-            i /= 10;
-        }
-        while (i != 0);
-        out.append(buf.data() + pos, buf.size() - pos);
-    }
-
     /*!
     @param[in] reference_string  the reference string to the current value
     @param[in] value             the value to consider
@@ -1327,8 +1194,7 @@ class json_pointer
         // flatten `v`, whose path is `path`: primitives and empty containers
         // are added to the result right away; other containers get a frame
         auto& object = *result.m_data.m_value.object;
-        typename BasicJsonType::object_t::iterator hint = object.end();
+        const auto enter = [&stack, &path, &object](const BasicJsonType & v)
-        const auto enter = [&stack, &path, &object, &hint](const BasicJsonType & v)
         {
             switch (v.type())
             {
@@ -1337,7 +1203,7 @@ class json_pointer
                     if (v.m_data.m_value.array->empty())
                     {
                         // flatten empty array as null
-                        add_flattened(object, hint, path, nullptr, detail::priority_tag<2> {});
+                        add_flattened(object, path, nullptr, detail::priority_tag<1> {});
                     }
                     else
                     {
@@ -1351,7 +1217,7 @@ class json_pointer
                     if (v.m_data.m_value.object->empty())
                     {
                         // flatten empty object as null
-                        add_flattened(object, hint, path, nullptr, detail::priority_tag<2> {});
+                        add_flattened(object, path, nullptr, detail::priority_tag<1> {});
                     }
                     else
                     {
@@ -1371,7 +1237,7 @@ class json_pointer
                 default:
                 {
                     // add a primitive value with its reference string
-                    add_flattened(object, hint, path, v, detail::priority_tag<2> {});
+                    add_flattened(object, path, v, detail::priority_tag<1> {});
                     return;
                 }
             }
@@ -1399,8 +1265,7 @@ class json_pointer
 
                 // iterate array and use index as a reference string
                 ++stack.back().index;
-                path.push_back('/');
+                detail::concat_into(path, '/', detail::to_string<string_t>(i));
-                append_index(path, i);
                 enter(array[i]);
             }
             else
@@ -1414,8 +1279,7 @@ class json_pointer
 
                 // iterate object and use keys as reference string
                 ++stack.back().member;
-                path.push_back('/');
+                detail::concat_into(path, '/', detail::escape(it->first));
-                detail::escape_into(path, it->first);
                 enter(it->second);
             }
         }
@@ -1446,30 +1310,53 @@ class json_pointer
 
         BasicJsonType result;
 
-        // check every key, and collect the prefixes that have a reference
+        // parse every key once; the reference tokens are kept for the second
-        // token 0 among their children; the values below them are arrays,
+        // pass (the vectors are never resized, so the tree may refer to them)
-        // all others are objects (see array_prefix_set)
+        std::vector<std::vector<string_t>> keys;
-        array_prefix_set arrays;
+        keys.reserve(value.m_data.m_value.object->size());
-        const string_t* previous_key = nullptr;
         for (const auto& element : *value.m_data.m_value.object)
         {
-            scan_key(element.first, previous_key, arrays);
+            json_pointer ptr(element.first);
-            previous_key = &element.first;
+            keys.push_back(std::move(ptr.reference_tokens));
         }
 
-        // values[i] is the value after the first i reference tokens of the
+        // collect the pointer prefixes that have a reference token 0 among
-        // previous key, ends[i] the length of that prefix of the key. Keys are
+        // their children; the values below them are arrays, all others are
-        // often sorted, so most of the path to the value of a key is the
+        // objects (see prefix_tree)
-        // same as for the previous key and need not be looked up again. Only
+        prefix_tree tree;
-        // the values below the common prefix are dropped, and only they can
+        // the number of the prefix with i + 1 tokens of the previous key; keys
-        // move when a value is added: the ones above are not inside the
+        // are often sorted, so most of the prefix is the same as for the
-        // container that grows.
+        // previous key and need not be looked up again
-        std::vector<BasicJsonType*> values(1, &result);
+        std::vector<std::size_t> path;
-        std::vector<std::size_t> ends(1, 0);
+        const std::vector<string_t>* previous = nullptr;
-        const string_t* previous = nullptr;
+        // the number of the complete prefix (i.e., the key) of each key
-        string_t token;
+        std::vector<std::size_t> leaves;
+        leaves.reserve(keys.size());
+        for (const auto& tokens : keys)
+        {
+            std::size_t common = 0;
+            if (previous != nullptr)
+            {
+                const std::size_t limit = (std::min)(tokens.size(), previous->size());
+                while (common < limit && tokens[common] == (*previous)[common])
+                {
+                    ++common;
+                }
+            }
+            path.resize(common);
+            std::size_t id = common == 0 ? 0 : path[common - 1];
+            for (std::size_t i = common; i < tokens.size(); ++i)
+            {
+                id = tree.add_child(id, tokens[i]);
+                path.push_back(id);
+            }
+            leaves.push_back(id);
+            previous = &tokens;
+        }
 
         // iterate the JSON object values
+        std::vector<std::size_t> prefixes;
+        std::size_t key_index = 0;
         for (const auto& element : *value.m_data.m_value.object)
         {
             if (JSON_HEDLEY_UNLIKELY(!element.second.is_primitive()))
@@ -1477,100 +1364,21 @@ class json_pointer
                 JSON_THROW(detail::type_error::create(detail::exception_id::unflatten_value_not_primitive, "values in object must be primitive", &element.second));
             }
 
-            const string_t& key = element.first;
+            const auto& tokens = keys[key_index];
-            const char* const data = key.data();
+            // number the prefixes of this key from its last one to the first
-
+            prefixes.resize(tokens.size());
-            // the number of reference tokens the key has in common with the
+            for (std::size_t i = tokens.size(), id = leaves[key_index]; i > 0; --i)
-            // previous one
-            std::size_t depth = 0;
-            if (previous != nullptr)
             {
-                const std::size_t same = common_prefix_length(data, previous->data(), (std::min)(key.size(), previous->size()));
+                id = tree.parent[id];
-                depth = ends.size() - 1;
+                prefixes[i - 1] = id;
-                while (depth > 0 && (ends[depth] > same || (ends[depth] == same && same < key.size() && data[same] != '/')))
-                {
-                    --depth;
-                }
             }
-            values.resize(depth + 1);
+            ++key_index;
-            ends.resize(depth + 1);
-            previous = &key;
 
             // Assign the value to the reference pointed to by JSON pointer. Note
             // that if the JSON pointer is "" (i.e., points to the whole value),
-            // the value is the result itself. An assignment will then create a
+            // function get_and_create returns a reference to the result itself.
-            // primitive value.
+            // An assignment will then create a primitive value.
-            BasicJsonType* current = values.back();
+            get_and_create(result, tokens, prefixes, tree) = element.second;
-            for (std::size_t pos = ends.back(); pos < key.size();)
-            {
-                // the reference token between the slash at pos and the next
-                std::size_t end = key.find_first_of('/', pos + 1);
-                if (end == string_t::npos)
-                {
-                    end = key.size();
-                }
-                token.clear();
-                token.append(data + pos + 1, end - pos - 1);
-                if (token.find_first_of('~') != string_t::npos)
-                {
-                    detail::unescape(token);
-                }
-
-                switch (current->type())
-                {
-                    case detail::value_t::null:
-                    {
-                        if (arrays.contains(data, pos))
-                        {
-                            // some reference token below this position is 0, so the
-                            // value is an array
-                            current = &current->operator[](array_index<BasicJsonType>(token));
-                        }
-                        else
-                        {
-                            // start a new object otherwise
-                            current = &current->operator[](token);
-                        }
-                        break;
-                    }
-
-                    case detail::value_t::object:
-                    {
-                        // create an entry in the object
-                        current = &object_member(*current, token);
-                        break;
-                    }
-
-                    case detail::value_t::array:
-                    {
-                        // create an entry in the array
-                        current = &current->operator[](array_index<BasicJsonType>(token));
-                        break;
-                    }
-
-                    /*
-                    The following code is only reached if there exists a reference
-                    token _and_ the current value is primitive. In this case, we have
-                    an error situation, because primitive values may only occur as
-                    a single value; that is, with an empty list of reference tokens.
-                    */
-                    case detail::value_t::string:
-                    case detail::value_t::boolean:
-                    case detail::value_t::number_integer:
-                    case detail::value_t::number_unsigned:
-                    case detail::value_t::number_float:
-                    case detail::value_t::binary:
-                    case detail::value_t::discarded:
-                    default:
-                        JSON_THROW(detail::type_error::create(detail::exception_id::unflatten_invalid_value, "invalid value to unflatten", &result));
-                }
-
-                values.push_back(current);
-                ends.push_back(end);
-                pos = end;
-            }
-
-            *current = element.second;
         }
 
         return result;

include/nlohmann/detail/output/binary_writer.hpp

@@ -23,6 +23,7 @@
     #include <cstdlib> // _byteswap_ushort, _byteswap_ulong, _byteswap_uint64
 #endif
 
+#include <nlohmann/detail/bit_ops.hpp>
 #include <nlohmann/detail/input/binary_reader.hpp>
 #include <nlohmann/detail/input/string_scan.hpp>
 #include <nlohmann/detail/macro_scope.hpp>
@@ -204,24 +205,12 @@ class binary_writer
             }
 
             case value_t::number_integer:
-            {
-                if (j.m_data.m_value.number_integer >= 0)
-                {
-                    // CBOR does not differentiate between positive signed
-                    // integers and unsigned integers
-                    write_cbor_head(0x00, static_cast<std::uint64_t>(j.m_data.m_value.number_integer));
-                }
-                else
-                {
-                    // a negative integer n is encoded as -1 - n
-                    write_cbor_head(0x20, static_cast<std::uint64_t>(-1 - j.m_data.m_value.number_integer));
-                }
-                break;
-            }
-
             case value_t::number_unsigned:
             {
-                write_cbor_head(0x00, conditional_static_cast<std::uint64_t>(j.m_data.m_value.number_unsigned));
+                // one case for both, so that an array mixing negative
+                // (number_integer) and non-negative (number_unsigned) values
+                // does not mispredict the switch
+                write_cbor_integer(j);
                 break;
             }
 
@@ -256,13 +245,7 @@ class binary_writer
 
             case value_t::array:
             {
-                // step 1: write control byte and the array size
+                write_cbor_array(j, depth);
-                write_cbor_head(0x80, j.m_data.m_value.array->size());
-
-                for (const auto& el : *j.m_data.m_value.array)
-                {
-                    write_cbor(el, depth + 1);
-                }
                 break;
             }
 
@@ -420,54 +403,12 @@ class binary_writer
             }
 
             case value_t::number_integer:
-            {
-                if (j.m_data.m_value.number_integer >= 0)
-                {
-                    // MessagePack does not differentiate between positive
-                    // signed integers and unsigned integers.
-                    write_msgpack_unsigned(static_cast<std::uint64_t>(j.m_data.m_value.number_integer));
-                }
-                else
-                {
-                    if (j.m_data.m_value.number_integer >= -32)
-                    {
-                        // negative fixnum
-                        write_number(static_cast<std::int8_t>(j.m_data.m_value.number_integer));
-                    }
-                    else if (j.m_data.m_value.number_integer >= (std::numeric_limits<std::int8_t>::min)() &&
-                             j.m_data.m_value.number_integer <= (std::numeric_limits<std::int8_t>::max)())
-                    {
-                        // int 8
-                        oa.write_character(to_char_type(0xD0));
-                        write_number(static_cast<std::int8_t>(j.m_data.m_value.number_integer));
-                    }
-                    else if (j.m_data.m_value.number_integer >= (std::numeric_limits<std::int16_t>::min)() &&
-                             j.m_data.m_value.number_integer <= (std::numeric_limits<std::int16_t>::max)())
-                    {
-                        // int 16
-                        oa.write_character(to_char_type(0xD1));
-                        write_number(static_cast<std::int16_t>(j.m_data.m_value.number_integer));
-                    }
-                    else if (j.m_data.m_value.number_integer >= (std::numeric_limits<std::int32_t>::min)() &&
-                             j.m_data.m_value.number_integer <= (std::numeric_limits<std::int32_t>::max)())
-                    {
-                        // int 32
-                        oa.write_character(to_char_type(0xD2));
-                        write_number(static_cast<std::int32_t>(j.m_data.m_value.number_integer));
-                    }
-                    else
-                    {
-                        // int 64
-                        oa.write_character(to_char_type(0xD3));
-                        write_number(static_cast<std::int64_t>(j.m_data.m_value.number_integer));
-                    }
-                }
-                break;
-            }
-
             case value_t::number_unsigned:
             {
-                write_msgpack_unsigned(static_cast<std::uint64_t>(j.m_data.m_value.number_unsigned));
+                // one case for both, so that an array mixing negative
+                // (number_integer) and non-negative (number_unsigned) values
+                // does not mispredict the switch
+                write_msgpack_integer(j, std::integral_constant<bool, msgpack_integers_fit_64_bits()>());
                 break;
             }
 
@@ -485,13 +426,7 @@ class binary_writer
 
             case value_t::array:
             {
-                // step 1: write control byte and the array size
+                write_msgpack_array(j, depth);
-                write_msgpack_array_prefix(j.m_data.m_value.array->size(), j);
-
-                for (const auto& el : *j.m_data.m_value.array)
-                {
-                    write_msgpack(el, depth + 1);
-                }
                 break;
             }
 
@@ -1951,6 +1886,316 @@ class binary_writer
         }
     }
 
+    /*!
+    @brief size class of an unsigned integer from its bit length
+
+    1, 2, 3, or 4 if @a x fits 1, 2, 4, or 8 bytes. Looked up from the number
+    of leading zero bits instead of found by branches: the sizes of a stream
+    of numbers are hard to predict, and a mispredicted branch costs more than
+    writing the number. (A table, as comparisons are vectorized by clang into
+    slower code.)
+    */
+    static unsigned integer_size_class(const std::uint64_t x) noexcept
+    {
+        static constexpr std::array<std::uint8_t, 64> size_class_by_leading_zeros =
+        {
+            {
+                4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
+                3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+                2, 2, 2, 2, 2, 2, 2, 2,
+                1, 1, 1, 1, 1, 1, 1, 1
+            }
+        };
+        // x | 1 keeps count_leading_zeros() away from 0
+        return size_class_by_leading_zeros[static_cast<std::size_t>(count_leading_zeros(x | 1u))];
+    }
+
+    /*!
+    @brief encode @a first_byte and the low-order bytes of @a value that
+           @a size_class calls for (none, or 1, 2, 4, or 8) in network order
+           to @a out
+    @return the number of characters of the encoding; up to
+            @ref integer_encoding_space characters at @a out are overwritten
+
+    The bytes are written as one byte and one 8-byte word whose bytes after
+    the value are scratch that the caller drops, so that writing them does not
+    depend on the size class. For class 0 the word is all scratch; it is
+    shifted by 60 bits rather than 64, which would be undefined.
+    */
+    std::size_t encode_first_byte_and_tail(CharType* out, const std::uint8_t first_byte, const unsigned size_class, const std::uint64_t value) const noexcept
+    {
+        out[0] = to_char_type(first_byte);
+        const unsigned unused_bits = 64u - ((8u << size_class) >> 1u);
+        const std::uint64_t tail = is_little_endian ? byte_swap(value) >> unused_bits : value << unused_bits;
+        std::memcpy(out + 1, &tail, sizeof(tail));
+        return ((std::size_t{1} << size_class) >> 1u) + 1;
+    }
+
+    /// characters encode_first_byte_and_tail() may overwrite: the first byte
+    /// and one 8-byte word
+    static constexpr std::size_t integer_encoding_space = 9;
+
+    /*!
+    @brief the 64 bits of a number_integer or number_unsigned value, and a mask
+           that is all ones if it is negative, else zero
+
+    Selected through masks rather than branches, as the type and the sign of
+    the values in an array of mixed signs alternate unpredictably (non-negative
+    integers are number_unsigned after parsing). Up to 64 bits, the sign is bit
+    63 of the result (a narrower integer is sign-extended); computing it with
+    masks keeps GCC from branching on the type. A wider integer has to be
+    compared.
+    */
+    static std::uint64_t integer_bits(const BasicJsonType& j, std::uint64_t& sign_mask) noexcept
+    {
+        const bool is_signed = j.m_data.m_type == value_t::number_integer;
+        const std::uint64_t raw = is_signed
+                                  ? static_cast<std::uint64_t>(j.m_data.m_value.number_integer)
+                                  : static_cast<std::uint64_t>(j.m_data.m_value.number_unsigned);
+        sign_mask = sizeof(typename BasicJsonType::number_integer_t) <= sizeof(std::uint64_t)
+                    ? (std::uint64_t{0} - static_cast<std::uint64_t>(is_signed)) & (std::uint64_t{0} - (raw >> 63u))
+                    : std::uint64_t{0} - static_cast<std::uint64_t>(is_signed && j.m_data.m_value.number_integer < 0);
+        return raw;
+    }
+
+    /*!
+    @brief encode the head of a CBOR integer to @a out without branching on its
+           size
+    @return the number of characters of the head
+
+    Same output as @ref write_cbor_head. The lengths of strings and containers
+    are mostly predictable, so their heads keep the branches; the sizes of a
+    run of integers are not, so an integer's head is assembled without them.
+    */
+    std::size_t encode_cbor_integer_head(CharType* out, const std::uint8_t major_type, const std::uint64_t argument) const noexcept
+    {
+        // an argument of at most 23 is in size class 1 (one byte) and is moved
+        // to class 0, the first byte, by subtracting 1
+        const auto is_immediate = static_cast<unsigned>(argument <= 0x17u);
+        const unsigned size_class = integer_size_class(argument) - is_immediate;
+
+        // the first byte: the argument itself if it is immediate, else
+        // 0x17 + size_class, selected through a mask
+        const std::uint64_t immediate_mask = std::uint64_t{0} - is_immediate;
+        const auto first_byte = static_cast<std::uint8_t>(major_type + ((argument & immediate_mask) | ((0x17u + size_class) & ~immediate_mask)));
+        return encode_first_byte_and_tail(out, first_byte, size_class, argument);
+    }
+
+    /*!
+    @brief write an array value (head and elements) as CBOR
+
+    Integer elements, the most common scalar, are written without a call to
+    @ref write_cbor. The loop is kept out of line: inlined into write_cbor, its
+    registers would be saved and restored on every call of write_cbor, which
+    is one call per value nested in an object.
+    */
+    JSON_HEDLEY_NEVER_INLINE
+    void write_cbor_array(const BasicJsonType& j, const std::size_t depth)
+    {
+        write_cbor_head(0x80, j.m_data.m_value.array->size());
+        write_array_elements(j, [this](CharType * out, const BasicJsonType & el)
+        {
+            return encode_cbor_integer(out, el);
+        }, [this, depth](const BasicJsonType & el)
+        {
+            write_cbor(el, depth + 1);
+        });
+    }
+
+    /*!
+    @brief write the elements of the array @a j, runs of integers with
+           @a encode_integer and all other values with @a write_value
+
+    Runs of integers are encoded straight into space reserved from the sink
+    for a whole run: the write pointer stays a local, where it would otherwise
+    be reloaded from the sink for every value, as a store of a character may
+    alias it.
+    */
+    template<typename EncodeInteger, typename WriteValue>
+    void write_array_elements(const BasicJsonType& j, EncodeInteger encode_integer, WriteValue write_value)
+    {
+        constexpr std::size_t max_run = max_reserve_size / integer_encoding_space;
+        auto it = j.m_data.m_value.array->begin();
+        const auto end = j.m_data.m_value.array->end();
+        while (it != end)
+        {
+            if (it->is_number_integer())
+            {
+                CharType* const start = oa.reserve(max_run * integer_encoding_space);
+                CharType* out = start;
+                for (std::size_t n = 0; n < max_run && it != end && it->is_number_integer(); ++n, ++it)
+                {
+                    out += encode_integer(out, *it);
+                }
+                oa.commit(static_cast<std::size_t>(out - start));
+            }
+            else
+            {
+                write_value(*it);
+                ++it;
+            }
+        }
+    }
+
+    /*!
+    @brief write a number_integer or number_unsigned value as a CBOR integer
+
+    A negative integer n has major type 1 and the argument -1 - n, which is ~n.
+    Kept out of line, like the other per-value paths, so that write_cbor stays
+    small (runs of integers in an array are encoded inline instead).
+    */
+    JSON_HEDLEY_NEVER_INLINE
+    void write_cbor_integer(const BasicJsonType& j)
+    {
+        oa.commit(encode_cbor_integer(oa.reserve(integer_encoding_space), j));
+    }
+
+    /// encode a number_integer or number_unsigned value to @a out (see
+    /// @ref write_cbor_integer) and return the number of characters
+    std::size_t encode_cbor_integer(CharType* out, const BasicJsonType& j) const noexcept
+    {
+        std::uint64_t sign_mask = 0;
+        const std::uint64_t raw = integer_bits(j, sign_mask);
+        // ~raw is -1 - n in the 64 bits that are written
+        return encode_cbor_integer_head(out, static_cast<std::uint8_t>(sign_mask & 0x20u), raw ^ sign_mask);
+    }
+
+    /*!
+    @brief whether the MessagePack integers of BasicJsonType are written by
+           @ref encode_msgpack_integer
+
+    It picks the format from the low 64 bits; a wider number type keeps the
+    range checks of @ref write_msgpack on the whole value.
+    */
+    static constexpr bool msgpack_integers_fit_64_bits() noexcept
+    {
+        return sizeof(typename BasicJsonType::number_integer_t) <= sizeof(std::uint64_t)
+               && sizeof(typename BasicJsonType::number_unsigned_t) <= sizeof(std::uint64_t);
+    }
+
+    /*!
+    @brief write a number_integer or number_unsigned value as a MessagePack
+           integer without branching on its sign or size
+
+    Same output as @ref write_msgpack: a non-negative integer as positive fixint
+    (< 128) or uint 8/16/32/64, a negative one as negative fixint (>= -32) or
+    int 8/16/32/64. Kept out of line (see @ref write_cbor_integer).
+    */
+    JSON_HEDLEY_NEVER_INLINE
+    void write_msgpack_integer(const BasicJsonType& j, std::true_type /*fits_64_bits*/)
+    {
+        oa.commit(encode_msgpack_integer(oa.reserve(integer_encoding_space), j));
+    }
+
+    /// encode a number_integer or number_unsigned value to @a out (see
+    /// @ref write_msgpack_integer) and return the number of characters
+    std::size_t encode_msgpack_integer(CharType* out, const BasicJsonType& j) const noexcept
+    {
+        std::uint64_t sign_mask = 0;
+        const std::uint64_t raw = integer_bits(j, sign_mask);
+
+        // A negative n fits int 8/16/32 exactly if 2 * (-1 - n) + 1 fits
+        // uint 8/16/32, so x gives the size class of either sign.
+        const std::uint64_t is_negative = sign_mask & 1u;
+        const std::uint64_t x = ((raw ^ sign_mask) << is_negative) | is_negative;
+
+        // A fixint is at most 127, or at least -32 (x at most 63). It is in
+        // size class 1 and is moved to class 0, the first byte, by subtracting 1.
+        const auto is_fixint = static_cast<unsigned>(x <= (127u ^ (sign_mask & 64u)));
+        const unsigned size_class = integer_size_class(x) - is_fixint;
+
+        // the first byte: the low byte of the integer for a fixint, else the
+        // marker 0xCC..0xCF (uint) or 0xD0..0xD3 (int), selected through a mask
+        const std::uint64_t fixint_mask = std::uint64_t{0} - is_fixint;
+        const std::uint64_t marker = 0xCBu + size_class + (sign_mask & 4u);
+        const auto first_byte = static_cast<std::uint8_t>((raw & fixint_mask) | (marker & ~fixint_mask));
+        return encode_first_byte_and_tail(out, first_byte, size_class, raw);
+    }
+
+    /// write a number_integer or number_unsigned value of a number type wider
+    /// than 64 bits as a MessagePack integer, with range checks on the whole value
+    void write_msgpack_integer(const BasicJsonType& j, std::false_type /*fits_64_bits*/)
+    {
+        if (j.m_data.m_type == value_t::number_unsigned)
+        {
+            write_msgpack_unsigned(static_cast<std::uint64_t>(j.m_data.m_value.number_unsigned));
+            return;
+        }
+
+        if (j.m_data.m_value.number_integer >= 0)
+        {
+            // MessagePack does not differentiate between positive
+            // signed integers and unsigned integers.
+            write_msgpack_unsigned(static_cast<std::uint64_t>(j.m_data.m_value.number_integer));
+        }
+        else
+        {
+            if (j.m_data.m_value.number_integer >= -32)
+            {
+                // negative fixnum
+                write_number(static_cast<std::int8_t>(j.m_data.m_value.number_integer));
+            }
+            else if (j.m_data.m_value.number_integer >= (std::numeric_limits<std::int8_t>::min)() &&
+                     j.m_data.m_value.number_integer <= (std::numeric_limits<std::int8_t>::max)())
+            {
+                // int 8
+                oa.write_character(to_char_type(0xD0));
+                write_number(static_cast<std::int8_t>(j.m_data.m_value.number_integer));
+            }
+            else if (j.m_data.m_value.number_integer >= (std::numeric_limits<std::int16_t>::min)() &&
+                     j.m_data.m_value.number_integer <= (std::numeric_limits<std::int16_t>::max)())
+            {
+                // int 16
+                oa.write_character(to_char_type(0xD1));
+                write_number(static_cast<std::int16_t>(j.m_data.m_value.number_integer));
+            }
+            else if (j.m_data.m_value.number_integer >= (std::numeric_limits<std::int32_t>::min)() &&
+                     j.m_data.m_value.number_integer <= (std::numeric_limits<std::int32_t>::max)())
+            {
+                // int 32
+                oa.write_character(to_char_type(0xD2));
+                write_number(static_cast<std::int32_t>(j.m_data.m_value.number_integer));
+            }
+            else
+            {
+                // int 64
+                oa.write_character(to_char_type(0xD3));
+                write_number(static_cast<std::int64_t>(j.m_data.m_value.number_integer));
+            }
+        }
+    }
+
+    /*!
+    @brief write an array value (head and elements) as MessagePack
+
+    See @ref write_cbor_array.
+    */
+    JSON_HEDLEY_NEVER_INLINE
+    void write_msgpack_array(const BasicJsonType& j, const std::size_t depth)
+    {
+        write_msgpack_array_prefix(j.m_data.m_value.array->size(), j);
+        write_msgpack_array_elements(j, depth, std::integral_constant<bool, msgpack_integers_fit_64_bits()>());
+    }
+
+    void write_msgpack_array_elements(const BasicJsonType& j, const std::size_t depth, std::true_type /*fits_64_bits*/)
+    {
+        write_array_elements(j, [this](CharType * out, const BasicJsonType & el)
+        {
+            return encode_msgpack_integer(out, el);
+        }, [this, depth](const BasicJsonType & el)
+        {
+            write_msgpack(el, depth + 1);
+        });
+    }
+
+    void write_msgpack_array_elements(const BasicJsonType& j, const std::size_t depth, std::false_type /*fits_64_bits*/)
+    {
+        for (const auto& el : *j.m_data.m_value.array)
+        {
+            write_msgpack(el, depth + 1);
+        }
+    }
+
     /*!
     @brief write an object key as a CBOR text string
 

include/nlohmann/detail/output/output_adapters.hpp

@@ -8,7 +8,10 @@
 
 #pragma once
 
+#include <algorithm> // max
+#include <array> // array
 #include <cstddef> // size_t
+#include <cstring> // memcpy
 #include <memory> // shared_ptr, make_shared
 #include <string> // basic_string
 #include <type_traits> // conditional, integral_constant, is_same
@@ -48,32 +51,170 @@ template<typename CharType> struct output_adapter_protocol
 template<typename CharType>
 using output_adapter_t = std::shared_ptr<output_adapter_protocol<CharType>>;
 
+/// the largest number of characters a writer may reserve() from a sink at once;
+/// output_vector_sink also appends writes of at least this size with insert()
+constexpr std::size_t max_reserve_size = 256;
+
 /// @brief non-virtual output sink writing into a std::vector
 ///
 /// This sink is not part of the virtual output_adapter_protocol hierarchy: it is
 /// passed to binary_writer by value as a template parameter, so
 /// write_character()/write_characters() are ordinary (inlinable) calls with no
 /// vtable lookup and no shared_ptr. It is used for the common
-/// `to_cbor`/`to_msgpack`/... into a std::vector. output_vector_adapter below
+/// `to_cbor`/`to_msgpack`/... into a std::vector.
-/// wraps this same sink to provide the virtual interface.
+///
+/// Most writes are a few bytes - a type marker, or a number of 1, 2, 4, or 8
+/// bytes - and appending those with push_back() or insert() cost more than
+/// encoding them: insert() is an out-of-line call into a routine that can insert
+/// anywhere, and resize() is one as well with libstdc++. The sink therefore keeps
+/// its own write position: it grows the vector geometrically ahead of the
+/// position and copies each write to it, so a write is a capacity check and a
+/// short copy. The destructor shrinks the vector to the bytes actually written,
+/// also when a write throws; shrinking a vector never allocates. The sink owns
+/// that trim, so it can be moved but not copied, and the vector must not be used
+/// while the sink is alive.
 template<typename CharType, typename AllocatorType = std::allocator<CharType>>
 class output_vector_sink
 {
   public:
     explicit output_vector_sink(std::vector<CharType, AllocatorType>& vec) noexcept
+        : v(&vec), position(vec.size())
+    {}
+
+    output_vector_sink(const output_vector_sink&) = delete;
+    output_vector_sink& operator=(const output_vector_sink&) = delete;
+    output_vector_sink& operator=(output_vector_sink&&) = delete;
+
+    output_vector_sink(output_vector_sink&& other) noexcept
+        : v(other.v), position(other.position)
+    {
+        other.v = nullptr;
+    }
+
+    ~output_vector_sink()
+    {
+        if (v != nullptr)
+        {
+            v->resize(position);
+        }
+    }
+
+    // always inlined: GCC otherwise keeps these out of line in a large
+    // translation unit, and a call per byte or number costs more than the write
+    JSON_HEDLEY_ALWAYS_INLINE
+    void write_character(CharType c)
+    {
+        if (JSON_HEDLEY_UNLIKELY(position == v->size()))
+        {
+            grow(1);
+        }
+        (*v)[position++] = c;
+    }
+
+    // no JSON_HEDLEY_NON_NULL here: binary_writer legitimately passes a null
+    // pointer with length 0 for empty strings/binary values; memcpy must not
+    // see it.
+    JSON_HEDLEY_ALWAYS_INLINE
+    void write_characters(const CharType* s, std::size_t length)
+    {
+        if (JSON_HEDLEY_UNLIKELY(v->size() - position < length))
+        {
+            if (length >= max_reserve_size)
+            {
+                append(s, length);
+                return;
+            }
+            grow(length);
+        }
+        if (length != 0)
+        {
+            std::memcpy(v->data() + position, s, length * sizeof(CharType));
+            position += length;
+        }
+    }
+
+    /// @brief space for writing up to @a length characters directly
+    ///
+    /// Returns a pointer to at least @a length (at most @ref max_reserve_size)
+    /// writable characters at the write position; @ref commit then keeps the
+    /// first ones of them. A writer can store whole words there and keep only
+    /// the bytes it needs, and keep its write pointer in a register across many
+    /// values instead of updating the sink after each.
+    JSON_HEDLEY_ALWAYS_INLINE
+    CharType* reserve(const std::size_t length)
+    {
+        JSON_ASSERT(length <= max_reserve_size);
+        if (JSON_HEDLEY_UNLIKELY(v->size() - position < length))
+        {
+            grow(length);
+        }
+        return v->data() + position;
+    }
+
+    /// keep the first @a length characters written to the space from reserve()
+    JSON_HEDLEY_ALWAYS_INLINE
+    void commit(const std::size_t length) noexcept
+    {
+        position += length;
+    }
+
+  private:
+    /// make room for at least @a length more characters after the position;
+    /// kept out of line so that the write functions stay small enough for
+    /// GCC to inline them into the writer
+    JSON_HEDLEY_NEVER_INLINE
+    void grow(const std::size_t length)
+    {
+        // use the capacity the vector already has, else at least double it;
+        // never less than 64 characters, so that a small value does not
+        // reallocate for every few bytes
+        const std::size_t needed = position + length;
+        v->resize((std::max)(std::size_t{64}, needed <= v->capacity()
+                             ? v->capacity()
+                             : (std::max)(needed, v->capacity() * 2)));
+    }
+
+    /// append @a length (at least max_reserve_size) characters that do not fit
+    /// the space ahead of the position: insert() copies them once into the
+    /// grown vector, where grow() would first zero the new space and then copy
+    /// over it - noticeable for a large string or binary value
+    JSON_HEDLEY_NEVER_INLINE
+    void append(const CharType* s, const std::size_t length)
+    {
+        v->resize(position);
+        if (v->capacity() - position < length)
+        {
+            // grow geometrically, with room for the writes that follow, so
+            // that the next grow() need not reallocate right away
+            v->reserve((std::max)(v->capacity() * 2, position + length + max_reserve_size));
+        }
+        v->insert(v->end(), s, s + length);
+        position = v->size();
+    }
+
+    std::vector<CharType, AllocatorType>* v;
+    /// number of characters of *v written so far
+    std::size_t position;
+};
+
+/// output adapter for byte vectors
+template<typename CharType, typename AllocatorType = std::allocator<CharType>>
+class output_vector_adapter : public output_adapter_protocol<CharType>
+{
+  public:
+    explicit output_vector_adapter(std::vector<CharType, AllocatorType>& vec) noexcept
         : v(vec)
     {}
 
-    void write_character(CharType c)
+    void write_character(CharType c) override
     {
         v.push_back(c);
     }
 
     // no JSON_HEDLEY_NON_NULL here: binary_writer legitimately passes a null
-    // pointer with length 0 for empty strings/binary values. Appending an empty
+    // pointer with length 0 for empty strings/binary values; appending an empty
-    // range is a no-op; the type-erased path tolerates this via the (unattributed)
+    // range is a no-op
-    // virtual base, and the concrete sink must do the same.
+    void write_characters(const CharType* s, std::size_t length) override
-    void write_characters(const CharType* s, std::size_t length)
     {
         v.insert(v.end(), s, s + length);
     }
@@ -82,33 +223,6 @@ class output_vector_sink
     std::vector<CharType, AllocatorType>& v;
 };
 
-/// output adapter for byte vectors
-///
-/// The appending itself lives in output_vector_sink; this class only adds the
-/// virtual output_adapter_protocol interface on top of it, so both the
-/// type-erased and the templated path share one implementation.
-template<typename CharType, typename AllocatorType = std::allocator<CharType>>
-class output_vector_adapter : public output_adapter_protocol<CharType>
-{
-  public:
-    explicit output_vector_adapter(std::vector<CharType, AllocatorType>& vec) noexcept
-        : sink(vec)
-    {}
-
-    void write_character(CharType c) override
-    {
-        sink.write_character(c);
-    }
-
-    void write_characters(const CharType* s, std::size_t length) override
-    {
-        sink.write_characters(s, length);
-    }
-
-  private:
-    output_vector_sink<CharType, AllocatorType> sink;
-};
-
 #ifndef JSON_NO_IO
 /// output adapter for output streams
 template<typename CharType>
@@ -188,8 +302,24 @@ class output_adapter_sink
         oa->write_characters(s, length);
     }
 
+    /// space for writing up to @a length characters (see
+    /// output_vector_sink::reserve)
+    CharType* reserve(const std::size_t length) noexcept
+    {
+        JSON_ASSERT(length <= max_reserve_size);
+        static_cast<void>(length);
+        return reserved.data();
+    }
+
+    /// write the first @a length characters written to the space from reserve()
+    void commit(const std::size_t length)
+    {
+        oa->write_characters(reserved.data(), length);
+    }
+
   private:
     output_adapter_t<CharType> oa;
+    std::array<CharType, max_reserve_size> reserved{};
 };
 
 /// @brief whether std::basic_string<CharType> has a non-deprecated std::char_traits

include/nlohmann/json.hpp

@@ -7066,125 +7066,6 @@ public:
             detail::throw_patch_not_an_array(json_patch);
         }
 
-        // the usual patch operations "add", "remove", "replace" and "test" on
-        // a pointer without escapes that denotes existing array elements and
-        // object members (as "add" does for the parent of the new value), as
-        // a diff creates them: apply the operation and return true; return
-        // false, with nothing changed, for all others
-        string_t token;
-        const string_t value_key = "value";
-        const auto try_plain = [&result, &token, &value_key](patch_operations operation, const string_t& path, const basic_json & val)
-        {
-            if (path.empty() || path.find_first_of('~') != string_t::npos)
-            {
-                return false;
-            }
-
-            // a missing "value" is reported below
-            const auto value_it = val.m_data.m_value.object->find(value_key);
-            const basic_json& value = value_it != val.m_data.m_value.object->end() ? value_it->second : val;
-            if (operation != patch_operations::remove && value_it == val.m_data.m_value.object->end())
-            {
-                return false;
-            }
-
-            switch (operation)
-            {
-                case patch_operations::replace:
-                {
-                    basic_json* const target = json_pointer::resolve_plain(&result, path, path.size(), token);
-                    if (target == nullptr)
-                    {
-                        return false;
-                    }
-                    *target = value;
-                    return true;
-                }
-
-                case patch_operations::test:
-                {
-                    const basic_json* const target = json_pointer::resolve_plain(&result, path, path.size(), token);
-                    // a failing test is reported below
-                    return target != nullptr && *target == value;
-                }
-
-                case patch_operations::add:
-                case patch_operations::remove:
-                {
-                    // the parent of the pointer and its last reference token
-                    std::size_t slash = path.size();
-                    while (slash > 0 && path[slash - 1] != '/')
-                    {
-                        --slash;
-                    }
-                    if (slash == 0)
-                    {
-                        return false;
-                    }
-                    --slash;
-
-                    basic_json* const parent = json_pointer::resolve_plain(&result, path, slash, token);
-                    if (parent == nullptr)
-                    {
-                        return false;
-                    }
-                    token.clear();
-                    token.append(path.data() + slash + 1, path.size() - slash - 1);
-
-                    if (operation == patch_operations::add)
-                    {
-                        if (parent->is_object())
-                        {
-                            (*parent)[token] = value;
-                            return true;
-                        }
-                        if (parent->is_array())
-                        {
-                            typename basic_json::size_type idx{};
-                            if (token == "-")
-                            {
-                                parent->push_back(value);
-                                return true;
-                            }
-                            if (json_pointer::template parse_array_index<basic_json_t>(token, idx) == json_pointer::array_index_status::ok && idx <= parent->size())
-                            {
-                                parent->insert(parent->begin() + static_cast<difference_type>(idx), value);
-                                return true;
-                            }
-                        }
-                        return false;
-                    }
-
-                    if (parent->is_object())
-                    {
-                        const auto it = parent->find(token);
-                        if (it == parent->end())
-                        {
-                            return false;
-                        }
-                        parent->erase(it);
-                        return true;
-                    }
-                    if (parent->is_array())
-                    {
-                        typename basic_json::size_type idx{};
-                        if (json_pointer::template parse_array_index<basic_json_t>(token, idx) == json_pointer::array_index_status::ok && idx < parent->size())
-                        {
-                            parent->erase(idx);
-                            return true;
-                        }
-                    }
-                    return false;
-                }
-
-                case patch_operations::move:
-                case patch_operations::copy:
-                case patch_operations::invalid:
-                default:
-                    return false;
-            }
-        };
-
         // iterate and apply the operations
         for (const auto& val : json_patch)
         {
@@ -7221,19 +7102,9 @@ public:
             // collect mandatory members
             const string_t& op = *get_value("op", "op", true).m_data.m_value.string;
             const string_t& path = *get_value(op, "path", true).m_data.m_value.string;
-            const patch_operations operation = get_op(op);
-
-            // the usual operations on a plain pointer are applied without
-            // building the pointer's reference tokens; anything else (and
-            // every error) is handled below
-            if (try_plain(operation, path, val))
-            {
-                continue;
-            }
-
             json_pointer ptr(path);
 
-            switch (operation)
+            switch (get_op(op))
             {
                 case patch_operations::add:
                 {
@@ -7341,8 +7212,7 @@ public:
     {
         // the patch
         basic_json result(value_t::array);
-        string_t buffer = path;
+        diff_recursively(result, source, target, path, 0);
-        diff_recursively(result, source, target, buffer, 0);
         return result;
     }
 
@@ -7386,69 +7256,31 @@ public:
     // function it appears in. In diff_recursively, which is on the call stack
     // once per nesting level, that made every level cost kilobytes of stack.
 
-    /// @brief append an operation @a op for @a path to @a result, with @a value if it is not null
-    static void diff_operation(basic_json& result, const char* op, const string_t& path, const basic_json* value)
-    {
-        basic_json entry(value_t::object);
-        entry["op"] = op;
-        entry["path"] = path;
-        if (value != nullptr)
-        {
-            entry["value"] = *value;
-        }
-        result.push_back(std::move(entry));
-    }
-
     /// @brief append a "replace" operation for @a path with @a value to @a result
     static void diff_replace(basic_json& result, const string_t& path, const basic_json& value)
     {
-        diff_operation(result, "replace", path, &value);
+        result.push_back(
+        {
+            {"op", "replace"}, {"path", path}, {"value", value}
+        });
     }
 
     /// @brief append a "remove" operation for @a path to @a result
     static void diff_remove(basic_json& result, const string_t& path)
     {
-        diff_operation(result, "remove", path, nullptr);
+        result.push_back(object(
+        {
+            {"op", "remove"}, {"path", path}
+        }));
     }
 
     /// @brief append an "add" operation for @a path with @a value to @a result
     static void diff_add(basic_json& result, const string_t& path, const basic_json& value)
     {
-        diff_operation(result, "add", path, &value);
+        result.push_back(
-    }
+        {
-
+            {"op", "add"}, {"path", path}, {"value", value}
-    /// @brief append "/" and the decimal representation of @a index to @a path
+        });
-    static void diff_append_index(string_t& path, std::size_t index)
-    {
-        path.push_back('/');
-        json_pointer::append_index(path, index);
-    }
-
-    /// @brief append "/" and the escaped @a key to @a path
-    static void diff_append_key(string_t& path, const string_t& key)
-    {
-        path.push_back('/');
-        detail::escape_into(path, key);
-    }
-
-    /// @brief the path of the member @a key of the value at @a path
-    static string_t diff_key_path(const string_t& path, const string_t& key)
-    {
-        string_t result;
-        result.reserve(path.size() + key.size() + 1);
-        result.append(path.data(), path.size());
-        diff_append_key(result, key);
-        return result;
-    }
-
-    /// @brief the path of the element @a index of the value at @a path
-    static string_t diff_index_path(const string_t& path, const std::size_t index)
-    {
-        string_t result;
-        result.reserve(path.size() + 8);
-        result.append(path.data(), path.size());
-        diff_append_index(result, index);
-        return result;
     }
 
     /// @brief append the "remove" operations for the elements of array
@@ -7461,18 +7293,13 @@ public:
         // in that order avoids the quadratic reinsertion done before
         for (std::size_t j = source.size(); j > index; --j)
         {
-            diff_remove(result, diff_index_path(path, j - 1));
+            diff_remove(result, detail::concat<string_t>(path, '/', detail::to_string<string_t>(j - 1)));
         }
 
         // add other remaining elements
-        if (source.size() < target.size())
+        for (std::size_t i = source.size(); i < target.size(); ++i)
         {
-            string_t tail_path = path;
+            diff_add(result, detail::concat<string_t>(path, "/-"), target[i]);
-            tail_path.append("/-", 2);
-            for (std::size_t i = source.size(); i < target.size(); ++i)
-            {
-                diff_add(result, tail_path, target[i]);
-            }
         }
     }
 
@@ -7481,7 +7308,7 @@ public:
     {
         for (const auto& it : added)
         {
-            diff_add(result, diff_key_path(path, it.key()), it.value());
+            diff_add(result, detail::concat<string_t>(path, '/', detail::escape(it.key())), it.value());
         }
     }
 
@@ -7502,25 +7329,10 @@ public:
                                  std::vector<const_iterator>& added)
     {
         // first pass: one lookup per source key
-        // Objects of the same size usually have the same keys, in the same
-        // order: walk them together as long as that holds, which takes no lookups.
         target_values.reserve(source.size());
         std::size_t common = 0;
-        bool together = source.size() == target.size();
+        for (auto it = source.cbegin(); it != source.cend(); ++it)
-        for (auto it = source.cbegin(), partner = target.cbegin(); it != source.cend(); ++it)
         {
-            if (together)
-            {
-                if (it.key() == partner.key())
-                {
-                    target_values.push_back(&partner.value());
-                    ++common;
-                    ++partner;
-                    continue;
-                }
-                together = false;
-            }
-
             const auto found = target.find(it.key());
             if (found != target.cend())
             {
@@ -7533,12 +7345,6 @@ public:
             }
         }
 
-        // the same keys in the same order
-        if (together)
-        {
-            return true;
-        }
-
         // second pass: find the keys only target has. An object type that
         // keeps its members in insertion order, such as the one backing
         // ordered_json, also needs the common keys to be in the same order
@@ -7604,13 +7410,6 @@ public:
             return true;
         }
 
-        // equal objects, whose members are in a different order, need no
-        // operations
-        if (source == target)
-        {
-            return false;
-        }
-
         // slow path: the common keys are in a different relative
         // order in source and target (only possible for a
         // reorderable object_t like ordered_map). Building a
@@ -7627,7 +7426,7 @@ public:
         // it moves it to the end, fixing its position.
         for (auto it = source.cbegin(); it != source.cend(); ++it)
         {
-            diff_remove(result, diff_key_path(path, it.key()));
+            diff_remove(result, detail::concat<string_t>(path, '/', detail::escape(it.key())));
         }
 
         // add every key that is either common (just removed
@@ -7636,7 +7435,7 @@ public:
         // target exactly
         for (auto it = target.cbegin(); it != target.cend(); ++it)
         {
-            diff_add(result, diff_key_path(path, it.key()), it.value());
+            diff_add(result, detail::concat<string_t>(path, '/', detail::escape(it.key())), it.value());
         }
         return false;
     }
@@ -7645,9 +7444,6 @@ public:
     @brief @ref diff, for values at nesting level @a depth, appending the
            operations to @a result
 
-    @a path is the path of the values; it is a buffer that is extended and
-    shortened again below, and is the same when the function returns.
-
     Diffing two arrays or objects calls this function again, once per nesting
     level, so values nested deeply enough used to exhaust the call stack and
     terminate the process. The descent is bounded here: once @ref
@@ -7655,7 +7451,7 @@ public:
     diff_iteratively diffs what is left without the call stack.
     */
     static void diff_recursively(basic_json& result, const basic_json& source, const basic_json& target,
-                                 string_t& path, const std::size_t depth)
+                                 const string_t& path, const std::size_t depth)
     {
         // if the values are the same, there is nothing to do
         if (source == target)
@@ -7667,9 +7463,9 @@ public:
     }
 
     /// @brief @ref diff_recursively for values known to be unequal; callers
-    ///        compare first so they extend the path only for unequal ones
+    ///        compare first so they build no path for equal ones
     static void diff_unequal(basic_json& result, const basic_json& source, const basic_json& target,
-                             string_t& path, const std::size_t depth)
+                             const string_t& path, const std::size_t depth)
     {
         if (JSON_HEDLEY_UNLIKELY(depth >= detail::recursion_depth_limit()))
         {
@@ -7688,8 +7484,6 @@ public:
         {
             case value_t::array:
             {
-                const std::size_t path_length = path.size();
-
                 // first pass: traverse common elements
                 std::size_t i = 0;
                 while (i < source.size() && i < target.size())
@@ -7697,9 +7491,7 @@ public:
                     // recursive call to compare array values at index i
                     if (!(source[i] == target[i]))
                     {
-                        diff_append_index(path, i);
+                        diff_unequal(result, source[i], target[i], detail::concat<string_t>(path, '/', detail::to_string<string_t>(i)), depth + 1);
-                        diff_unequal(result, source[i], target[i], path, depth + 1);
-                        path.resize(path_length);
                     }
                     ++i;
                 }
@@ -7721,7 +7513,6 @@ public:
                     // lookup is needed. Deleted keys are interleaved here
                     // too, in source's original order, to match the
                     // historical (pre-reordering-aware) output order.
-                    const std::size_t path_length = path.size();
                     std::size_t i = 0;
                     for (auto it = source.cbegin(); it != source.cend(); ++it, ++i)
                     {
@@ -7729,15 +7520,13 @@ public:
                         {
                             if (!(it.value() == *target_values[i]))
                             {
-                                diff_append_key(path, it.key());
+                                diff_unequal(result, it.value(), *target_values[i], detail::concat<string_t>(path, '/', detail::escape(it.key())), depth + 1);
-                                diff_unequal(result, it.value(), *target_values[i], path, depth + 1);
-                                path.resize(path_length);
                             }
                         }
                         else
                         {
                             // found a key that is not in target -> remove it
-                            diff_remove(result, diff_key_path(path, it.key()));
+                            diff_remove(result, detail::concat<string_t>(path, '/', detail::escape(it.key())));
                         }
                     }
 
@@ -7868,7 +7657,7 @@ public:
                 if (i < source_array.size() && i < target_array.size())
                 {
                     ++stack.back().index;
-                    diff_append_index(current_path, i);
+                    detail::concat_into(current_path, '/', detail::to_string<string_t>(i));
                     enter(source_array[i], target_array[i]);
                     if (stack.size() == depth)
                     {
@@ -7891,7 +7680,7 @@ public:
                     if (target_value_ptr != nullptr)
                     {
                         const basic_json& target_value = *target_value_ptr;
-                        diff_append_key(current_path, it.key());
+                        detail::concat_into(current_path, '/', detail::escape(it.key()));
                         enter(it.value(), target_value);
                         if (stack.size() == depth)
                         {
@@ -7901,7 +7690,7 @@ public:
                     else
                     {
                         // found a key that is not in target -> remove it
-                        diff_remove(result, diff_key_path(current_path, it.key()));
+                        diff_remove(result, detail::concat<string_t>(current_path, '/', detail::escape(it.key())));
                     }
                     continue;
                 }

tests/src/unit-binary_writer_sinks.cpp

@@ -11,8 +11,10 @@
 #include <nlohmann/json.hpp>
 using nlohmann::json;
 
+#include <array>
 #include <cstdint>
 #include <limits>
+#include <sstream>
 #include <string>
 #include <vector>
 
@@ -35,6 +37,17 @@ std::vector<json> test_values()
         big_object[std::to_string(i)] = i;
     }
 
+    // large strings and binary values between small ones: a write too large
+    // for the space the vector sink has ahead takes a different path than a
+    // small one, and the small writes after it must still land behind it
+    json large_payloads = json::array();
+    for (int i = 0; i < 50; ++i)
+    {
+        large_payloads.push_back(std::string(300, static_cast<char>('a' + (i % 26))));
+        large_payloads.push_back(i);
+        large_payloads.push_back(json::binary(std::vector<std::uint8_t>(static_cast<std::size_t>(100 * i), static_cast<std::uint8_t>(i))));
+    }
+
     return
     {
         json(nullptr), json(true), json(false),
@@ -46,7 +59,8 @@ std::vector<json> test_values()
         json::array(), json::object(),
         json::array({1, 2, 3}), json({{"a", 1}, {"b", nullptr}}),
         json({{"nested", {{"deep", json::array({1, "two", 3.0, nullptr})}}}}),
-        big_array, big_object
+        big_array, big_object, large_payloads,
+        json::binary(std::vector<std::uint8_t>(5000, 0x42))
     };
 }
 
@@ -170,6 +184,258 @@ TEST_CASE("binary writer output sinks")
     }
 }
 
+namespace
+{
+
+// the CBOR head of an integer, encoded independently of binary_writer
+void reference_cbor_head(std::vector<std::uint8_t>& out, const std::uint8_t major_type, const std::uint64_t argument)
+{
+    if (argument <= 23)
+    {
+        out.push_back(static_cast<std::uint8_t>(major_type + argument));
+        return;
+    }
+
+    int length = 8;
+    std::uint8_t additional = 27;
+    if (argument <= 0xFF)
+    {
+        length = 1;
+        additional = 24;
+    }
+    else if (argument <= 0xFFFF)
+    {
+        length = 2;
+        additional = 25;
+    }
+    else if (argument <= 0xFFFFFFFF)
+    {
+        length = 4;
+        additional = 26;
+    }
+
+    out.push_back(static_cast<std::uint8_t>(major_type + additional));
+    for (int i = length - 1; i >= 0; --i)
+    {
+        out.push_back(static_cast<std::uint8_t>(argument >> (8 * i)));
+    }
+}
+
+// the CBOR encoding of an integer value
+void reference_cbor_integer(std::vector<std::uint8_t>& out, const json& j)
+{
+    if (j.is_number_unsigned())
+    {
+        reference_cbor_head(out, 0x00, j.get<std::uint64_t>());
+        return;
+    }
+
+    const auto n = j.get<std::int64_t>();
+    if (n >= 0)
+    {
+        reference_cbor_head(out, 0x00, static_cast<std::uint64_t>(n));
+    }
+    else
+    {
+        reference_cbor_head(out, 0x20, static_cast<std::uint64_t>(-1 - n));
+    }
+}
+
+// the MessagePack encoding of an integer value, encoded independently of
+// binary_writer
+void reference_msgpack_integer(std::vector<std::uint8_t>& out, const json& j)
+{
+    const auto put = [&out](const std::uint8_t marker, const std::uint64_t bits, const int length)
+    {
+        out.push_back(marker);
+        for (int i = length - 1; i >= 0; --i)
+        {
+            out.push_back(static_cast<std::uint8_t>(bits >> (8 * i)));
+        }
+    };
+
+    if (j.is_number_unsigned() || j.get<std::int64_t>() >= 0)
+    {
+        const auto u = j.get<std::uint64_t>();
+        if (u < 128)
+        {
+            out.push_back(static_cast<std::uint8_t>(u));
+        }
+        else if (u <= 0xFF)
+        {
+            put(0xCC, u, 1);
+        }
+        else if (u <= 0xFFFF)
+        {
+            put(0xCD, u, 2);
+        }
+        else if (u <= 0xFFFFFFFF)
+        {
+            put(0xCE, u, 4);
+        }
+        else
+        {
+            put(0xCF, u, 8);
+        }
+        return;
+    }
+
+    const auto n = j.get<std::int64_t>();
+    const auto bits = static_cast<std::uint64_t>(n);
+    if (n >= -32)
+    {
+        out.push_back(static_cast<std::uint8_t>(bits));
+    }
+    else if (n >= -128)
+    {
+        put(0xD0, bits, 1);
+    }
+    else if (n >= -32768)
+    {
+        put(0xD1, bits, 2);
+    }
+    else if (n >= -2147483648LL)
+    {
+        put(0xD2, bits, 4);
+    }
+    else
+    {
+        put(0xD3, bits, 8);
+    }
+}
+
+// integers at every boundary of the CBOR and MessagePack sizes, signed and
+// unsigned
+std::vector<json> boundary_integers()
+{
+    std::vector<json> result;
+    const std::array<std::uint64_t, 38> boundaries =
+    {
+        {
+            0, 1, 22, 23, 24, 25, 31, 32, 33, 126, 127, 128, 129, 254, 255, 256, 257,
+            32766, 32767, 32768, 32769, 65534, 65535, 65536, 65537,
+            2147483646ULL, 2147483647ULL, 2147483648ULL, 2147483649ULL,
+            4294967294ULL, 4294967295ULL, 4294967296ULL, 4294967297ULL,
+            9223372036854775806ULL, 9223372036854775807ULL, 9223372036854775808ULL,
+            18446744073709551614ULL, 18446744073709551615ULL
+        }
+    };
+    for (const std::uint64_t u : boundaries)
+    {
+        result.emplace_back(u);
+        if (u <= static_cast<std::uint64_t>((std::numeric_limits<std::int64_t>::max)()))
+        {
+            const auto n = static_cast<std::int64_t>(u);
+            result.emplace_back(n);
+            result.emplace_back(-n);
+            result.emplace_back(-n - 1);
+        }
+    }
+    return result;
+}
+
+} // namespace
+
+// Arrays of integers are written in runs straight into space reserved from the
+// sink, with branch-free encodings; check them against independent encoders for
+// runs shorter and longer than one reservation, broken up by other values, and
+// through each sink.
+TEST_CASE("CBOR and MessagePack integer arrays")
+{
+    const std::vector<json> integers = boundary_integers();
+
+    for (const std::size_t length :
+            {
+                std::size_t{1}, std::size_t{27}, std::size_t{28}, std::size_t{29}, std::size_t{57}, std::size_t{1000}
+            })
+    {
+        for (const std::size_t break_every :
+                {
+                    std::size_t{0}, std::size_t{1}, std::size_t{7}, std::size_t{28}
+                })
+        {
+            CAPTURE(length)
+            CAPTURE(break_every)
+
+            json array = json::array();
+            std::vector<std::uint8_t> expected_cbor;
+            std::vector<std::uint8_t> expected_msgpack;
+            for (std::size_t i = 0; i < length; ++i)
+            {
+                if (break_every != 0 && i % (break_every + 1) == break_every)
+                {
+                    array.push_back("x");
+                    expected_cbor.push_back(0x61);
+                    expected_cbor.push_back('x');
+                    expected_msgpack.push_back(0xA1);
+                    expected_msgpack.push_back('x');
+                }
+                else
+                {
+                    const json& value = integers[(i * 7) % integers.size()];
+                    array.push_back(value);
+                    reference_cbor_integer(expected_cbor, value);
+                    reference_msgpack_integer(expected_msgpack, value);
+                }
+            }
+
+            std::vector<std::uint8_t> head;
+            reference_cbor_head(head, 0x80, length);
+            expected_cbor.insert(expected_cbor.begin(), head.begin(), head.end());
+
+            head.clear();
+            if (length <= 15)
+            {
+                head.push_back(static_cast<std::uint8_t>(0x90 + length));
+            }
+            else
+            {
+                head = {0xDC, static_cast<std::uint8_t>(length >> 8), static_cast<std::uint8_t>(length)};
+            }
+            expected_msgpack.insert(expected_msgpack.begin(), head.begin(), head.end());
+
+            CHECK(json::to_cbor(array) == expected_cbor);
+            CHECK(json::to_msgpack(array) == expected_msgpack);
+
+            std::vector<std::uint8_t> through_adapter = {0xAA};
+            json::to_cbor(array, through_adapter);
+            CHECK(std::vector<std::uint8_t>(through_adapter.begin() + 1, through_adapter.end()) == expected_cbor);
+            through_adapter = {0xAA};
+            json::to_msgpack(array, through_adapter);
+            CHECK(std::vector<std::uint8_t>(through_adapter.begin() + 1, through_adapter.end()) == expected_msgpack);
+
+            std::ostringstream stream;
+            json::to_cbor(array, stream);
+            std::string streamed = stream.str();
+            CHECK(std::vector<std::uint8_t>(streamed.begin(), streamed.end()) == expected_cbor);
+            stream.str("");
+            json::to_msgpack(array, stream);
+            streamed = stream.str();
+            CHECK(std::vector<std::uint8_t>(streamed.begin(), streamed.end()) == expected_msgpack);
+
+            CHECK(json::from_cbor(expected_cbor) == array);
+            CHECK(json::from_msgpack(expected_msgpack) == array);
+
+            // the same array as object members
+            const json object = {{"a", array}, {"b", array}};
+            CHECK(json::from_cbor(json::to_cbor(object)) == object);
+            CHECK(json::from_msgpack(json::to_msgpack(object)) == object);
+        }
+    }
+
+    // single values, outside an array
+    for (const auto& value : integers)
+    {
+        CAPTURE(value)
+        std::vector<std::uint8_t> expected;
+        reference_cbor_integer(expected, value);
+        CHECK(json::to_cbor(value) == expected);
+        expected.clear();
+        reference_msgpack_integer(expected, value);
+        CHECK(json::to_msgpack(value) == expected);
+    }
+}
+
 // binary_reserve_hint() is documented as a *lower* bound on the serialized size,
 // so that reserving it up front can never leave the returned vector holding
 // capacity beyond what the value actually needs.