search

Tencent / rapidjson

A fast JSON parser/generator for C++ with both SAX/DOM style API
http://rapidjson.org/
Other
14.19k stars 3.53k forks source link

GenericSchema::schemaMap_ is not a map and leads to O(n) complexity #2286

Open svart-riddare opened 3 months ago

svart-riddare commented 3 months ago

Upon investigation of performance issues, we found out that GenericSchema::schemaMap_ is a linear type container and thus methods GenericSchema::GetSchema() and GenericSchema::GetPointer() have O(n) complexity, yielding a huge performance impact on our application.

aikawayataro commented 3 months ago

This is indeed a map. Map (associative array/dictionary, etc.) has no implementation constraints. A map with a hash table is probably what you want to see. But I suspect that nothing is going to change. Are you really able to confirm that GetPointer is the culprit for the performance issues?

svart-riddare commented 3 months ago

You are right, my wording was not precise enough, by map I meant "efficient" map !

Yes, I used the perf tool to confirm that more than 60% of the time was spent in those functions; I bluntly inserted a std::map for GenericSchema::schemaMap_ and I got a x3 speedup and those functions disappeared from perf report.

aikawayataro commented 3 months ago

If it's 60% of a large complex application, it's certainly a problem. I believe you can implement your own SchemaDocument using the reference implementation but with std::map or std::hash_map. Or you can just patch the code :) .

svart-riddare commented 3 months ago

Yes, that's what I did; there's no release/tag of rapidjson since 2016 anyway. I opened a ticket to let other know.