to_bson() is O(size × nesting depth), not linear as documented

[nlohmann]

Description

BSON documents are length-prefixed, so write_bson_object (include/nlohmann/detail/output/binary_writer.hpp:1285) calls calc_bson_object_size to compute the prefix — which recursively walks the entire subtree. It then recurses into each child, and each child walks its subtree again. write_bson_array (binary_writer.hpp:1141 / calc_bson_array_size at :1118) does the same.

The result is that every nesting level re-measures everything below it, giving O(size × depth) instead of O(size).

docs/mkdocs/docs/api/basic_json/to_bson.md currently states:

Complexity

Linear in the size of the JSON value j.

which is not correct as written.

Reproduction steps

Serialize objects with a roughly constant payload but increasing nesting depth and time to_bson.

Minimal code example

#include <nlohmann/json.hpp>
#include <chrono>
#include <iostream>
using json = nlohmann::json;

int main()
{
    for (int depth : {200, 400, 800, 1600})
    {
        json j = json::object();
        json* p = &j;
        for (int i = 0; i < depth; ++i)
        {
            (*p)["k"] = json::object();
            p = &(*p)["k"];
        }
        for (int i = 0; i < 200; ++i)
        {
            (*p)[std::to_string(i)] = i;
        }

        const auto t0 = std::chrono::steady_clock::now();
        const auto v = json::to_bson(j);
        const auto t1 = std::chrono::steady_clock::now();

        std::cout << "depth " << depth << "  bytes " << v.size() << "  time "
                  << std::chrono::duration<double, std::milli>(t1 - t0).count() << " ms\n";
    }
}

Expected vs. actual results

Expected: runtime roughly proportional to output size.

Actual: runtime grows quadratically in depth — 27× the time for 4.4× the output:

depth 200   bytes 3295   time 1.35 ms
depth 400   bytes 4895   time 3.50 ms
depth 800   bytes 8095   time 10.08 ms
depth 1600  bytes 14495  time 36.04 ms

36 ms to produce 14 KB of BSON is a poor cost for the format, and it makes to_bson() a cheap amplification target when serializing attacker-shaped documents.

Suggested fix

Either:

1. memoize sizes in a single bottom-up pass, or
2. use the usual patch-the-prefix approach (reserve 4 bytes, write children, seek back and fill in the length) where the output sink supports it.

If neither is desirable, the complexity statement in the to_bson docs should at least be corrected.

Notes

Not addressed by #5286, which is a constant-factor speedup (devirtualized output sink + byte-swap number encoding) and is explicitly output- and algorithm-preserving. write_bson_array also builds each index string twice (std::to_string in both the calc and write passes), which would fold into the same fix.

Compiler and operating system

g++ 13.3.0 (Ubuntu 24.04), -std=c++11 -O2, Linux x86-64

Library version

develop @ 06ac77f