While working on nativejson-benchmark, I found that the runtime performance of folly::toJson() is extremely low for big JSONs (OS X 10.11.6, clang7.0, 6a6ac91):
After profiling, it is found that the time killer is in:
// json.cpp
void escapeString(
StringPiece input,
std::string& out,
const serialization_opts& opts) {
auto hexDigit = [] (int c) -> char {
return c < 10 ? c + '0' : c - 10 + 'a';
};
out.reserve(out.size() + input.size() + 2); // <-- this line
out.push_back('\"');
// ...
This line causes O(n^2) time complexity, because every time it expands just fit for the string to be appended. This may be only the behavior of libc++. And C++ says:
If new_cap is greater than the current capacity(), new storage is allocated, and capacity() is made equal or greater than new_cap.
The std::string::push_back() and std::string::append() expand double (or other multiples) of the current capacity, which makes amortized O(n).
After removing that reserve() call, the result looks much more normal:
I will prepare a pull request on this.
The text was updated successfully, but these errors were encountered:
While working on nativejson-benchmark, I found that the runtime performance of
folly::toJson()
is extremely low for big JSONs (OS X 10.11.6, clang7.0, 6a6ac91):After profiling, it is found that the time killer is in:
This line causes
O(n^2)
time complexity, because every time it expands just fit for the string to be appended. This may be only the behavior of libc++. And C++ says:The
std::string::push_back()
andstd::string::append()
expand double (or other multiples) of the current capacity, which makes amortizedO(n)
.After removing that
reserve()
call, the result looks much more normal:I will prepare a pull request on this.
The text was updated successfully, but these errors were encountered: