Tencent / rapidjson / 2146

100%

master: 100%

Pull #1485

travis-ci

Make use of an (std::multi)map for object members, if #defined.

When RAPIDJSON_USE_MEMBERS_MAP is defined, an object Value will store
its members in an (re)allocated array of Members like before, but also
in an std::multimap<StringRef,SizeType> where the key and value
reference the corresponding Member by its name and index in the array,
respectively, and in a relocatable manner.

The layout of the members map/array is now:
 {multimap*}<>{capacity}<>{Member[capacity]}<>{multimap::iterator[capacity]}
where <> stands for the RAPIDJSON_ALIGN-ment of each part, if needed.

This layout needs to be reallocated when the current capacity is
exhausted, which requires to take care of the multimap and its iterators
explicitely. The multimap (likely not a POD) is allocated separately and
only its pointer is saved in this layout, so it can easily be restored
in its new position; as for the old/alive iterators, they must move to
their new offset according to the new capacity.

With this in place, it's immediate to get the multimap::iterator from a
MemberIterator and vice versa, thus Find/Remove/EraseMember() working on
a MemberIterator keep the same complexity (O(1) for find/remove, and
still O(n-m) for EraseMember() due to the move/copy).

For operations by name, the lookups complexity switches from O(n)/linear
to the multimap's, usually rbtree's O(log n)/logarithmic, including for
AddMember() which without RAPIDJSON_USE_MEMBERS_MAP is otherwise O(1).

Consequently parsing will be slower, up to ~20% measured in perftests on
my laptop (since it's mainly composed of insertions). But later work on
the Document [usually the goal of parsing...] will be much faster; the
new DocumentFind perftest included in this commit is 8 times faster with
RAPIDJSON_USE_MEMBERS_MAP (still on my laptop). Overall the tests are 4%
slower (mainly composed of parsing), and notably 15% slower for schemas
parsing/validation (which supposedly comes from the larger JSON files
parsing, still).... (continued)

188 of 188 new or added lines in 2 files covered. (100.0%)

5201 of 5205 relevant lines covered (99.92%)

1462078.06 hits per line