Slow performance when serializing/deserializing big binary data or big arrays of scalar types

[vlad-nn]

Use case: Json object stores big numeric array (>1M array of floats). Need to serialize Json to some binary format (say, msgpack), send over network, and deserialize at the other end.

Configuration: MSVC 2019, Win10, Release build.

Observations:

• terrible performance when big numeric array is represented as std::vector: even simple assignment to Json object takes hundreds of ms (because of per-element loop with pushback)
• much better performance when big numeric array is assigned as json::binary type (here bulk copy of the whole array is used in your implementation, which helps)
• still bad performance (>100ms) when such Json object with big binary field is serialized to msgpack (or any other format; your implementation of msgpack is just fastest out of all of them, so I sticj with it) - again, because of per-element loop with vector pushback.
• and the most terrible performance (>300ms) when msgpack is deserialized to Json - here because of per-byte SAX parser and again vector pushback.

I did two simple modifications:

In binary_reader::get_binary() method I resized result before for() loop, changed push_back() to [] assignment, and replaced unexpect_eof() call to comparison to eof():

    template<typename NumberType>
    bool get_binary(const input_format_t format,
                    const NumberType len,
                    binary_t& result)
    {
        bool success = true;
        const size_t sz = result.size();
        result.resize(sz + len);

        for (NumberType i = 0; i < len; i++)
        {
            get();
            if (JSON_HEDLEY_UNLIKELY(**current == std::char_traits<char_type>::eof())**)
            {
                success = false;
                break;
            }
            result[sz + i] = static_cast<std::uint8_t>(current);
        }
        if( !success )
            return unexpect_eof(format, "binary");
        return success;
    }

This mod gives ~50 times performance increase (notably, moving unexpect_eof() out of loop alone gives 2x times performance increase).

Another mod is in output_vector_adapter::write_characters() method: instead of std::copy(s, s + length, std::back_inserter(v)), I did this:

    void write_characters(const CharType* s, std::size_t length) override
    {
        if( length == 1 )
            v.push_back(*s);
        else
        {
            const size_t sz = v.size();
            v.resize(sz + length);
            std::copy(s, s + length, v.data() + sz);
        }
    }

This also gives ~30 times performance increase.

I believe that systematic optimizations of all places where arrays/vectors of scalar types are handled, will give tremendous performance increase, when per-element assignment/copy operations will be replaced with bulk memory copy operations.

[gregmarr]

Another mod is in output_vector_adapter::write_characters() method: instead of std::copy(s, s + length, std::back_inserter(v)), I did this:

Note that in optimizing this function for calls with large length, you are pessimizing it for a large number of writes with small length. With the current function, v will will be resized by a growth factor when the needed size exceeds the capacity. With this change, v has the potential to be reallocated, and thus copied, on every call to write_characters() as vector doesn't generally do the same kind of expansion for resize() that it does for push_back(). (Edit: yes, it does, it's reserve() that doesn't, thanks to @vlad-nn for pointing that out.) If I write 4 bytes 100 times with the current function, assuming a capacity factor of 2x, it will resize and copy 7 times. (4, 8, 16, 32, 64, 128, 256, 512). With this change, it can reallocate and copy 99 times.

In binary_reader::get_binary() method I resized result before for() loop, changed push_back() to [] assignment, and replaced unexpect_eof() call to comparison to eof():

Same as above. If you don't know for sure that result is empty coming in, then this is pessimizing the behavior in the general case. However, this one looks like it's always empty coming in, so there is a definite opportunity for improvement there.

This mod gives ~50 times performance increase (notably, moving unexpect_eof() out of loop alone gives 2x times performance increase).

If moving that out of the loop gives that much performance increase, then you probably have an issue with functions not being inlined.

Maybe these changes could be made safer by only using the resize behavior when the buffer being added is large.

[iMineLink]

I guess the resize function does call the reallocator, which by default doubles the underlying vector capacity. So even if resize is called at every insertion (worst case), the reallocation and thus data copy should happen with the same frequency as without the changes.

[gregmarr]

No, reserve() does not double the underlying capacity by default. By default reserve() (Edit: said resize() originally, meant reserve()) grows the capacity to exactly the provided value if it's larger than the current capacity. It's only push_back() that does exponential growth by default. (Edit: It turns out that resize() does too, at least in libc++ and libstdc++, thanks @vlad-nn.)

https://en.cppreference.com/w/cpp/container/vector/reserve

Notes
Correctly using reserve() can prevent unnecessary reallocations, but inappropriate uses of reserve() (for instance, calling it before every push_back() call) may actually increase the number of reallocations (by causing the capacity to grow linearly rather than exponentially) and result in increased computational complexity and decreased performance. For example, a function that receives an arbitrary vector by reference and appends elements to it should usually not call reserve() on the vector, since it does not know of the vector's usage characteristics.

[vlad-nn]

It is really does not matter in terms of this discussion, but for the sake of correctness: yes, reserve() allocates the exact provided amount, while resize() performs geometric growth. See here for experimental results: https://coliru.stacked-crooked.com/view?id=05077d56ead8ba88

Or you can look code of CRT directly.

Since resize() (not reserve()) was used in original code, @iMineLink is right.

[gregmarr]

Good to know, thanks. I'd only seen that behavior before in push_back().

[gregmarr]

Just be aware that if you do resize(n) where n > capacity() * 2, you get a new capacity of n, and your very next insert will also reallocate. In that case, you may want to do a reserve(capacity() * 4) or something like that first before the resize(). I expect however that this pattern is not likely.